1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Copyright 2014 PDFium Authors. All rights reserved.
2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Use of this source code is governed by a BSD-style license that can be
3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// found in the LICENSE file.
4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov
5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov
7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/fxcrt/fx_basic.h"
8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "plex.h"
9ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_PtrList::CFX_PtrList(int nBlockSize, IFX_Allocator* pAllocator)
10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    : m_pAllocator(pAllocator)
11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    , m_pNodeHead(NULL)
12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    , m_pNodeTail(NULL)
13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    , m_nCount(0)
14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    , m_pNodeFree(NULL)
15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    , m_pBlocks(NULL)
16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    , m_nBlockSize(nBlockSize)
17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
19ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_POSITION CFX_PtrList::AddTail(void* newElement)
20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
21ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CNode* pNewNode = NewNode(m_pNodeTail, NULL);
22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pNewNode->data = newElement;
23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (m_pNodeTail != NULL) {
24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        m_pNodeTail->pNext = pNewNode;
25ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    } else {
26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        m_pNodeHead = pNewNode;
27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_pNodeTail = pNewNode;
29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    return (FX_POSITION) pNewNode;
30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
31ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_POSITION CFX_PtrList::AddHead(void* newElement)
32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CNode* pNewNode = NewNode(NULL, m_pNodeHead);
34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pNewNode->data = newElement;
35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (m_pNodeHead != NULL) {
36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        m_pNodeHead->pPrev = pNewNode;
37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    } else {
38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        m_pNodeTail = pNewNode;
39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_pNodeHead = pNewNode;
41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    return (FX_POSITION) pNewNode;
42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
43ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_POSITION CFX_PtrList::InsertAfter(FX_POSITION position, void* newElement)
44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (position == NULL) {
46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        return AddTail(newElement);
47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CNode* pOldNode = (CNode*) position;
49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pNewNode->data = newElement;
51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (pOldNode->pNext != NULL) {
52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        pOldNode->pNext->pPrev = pNewNode;
53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    } else {
54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        m_pNodeTail = pNewNode;
55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pOldNode->pNext = pNewNode;
57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    return (FX_POSITION) pNewNode;
58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid CFX_PtrList::RemoveAt(FX_POSITION position)
60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CNode* pOldNode = (CNode*) position;
62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (pOldNode == m_pNodeHead) {
63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        m_pNodeHead = pOldNode->pNext;
64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    } else {
65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        pOldNode->pPrev->pNext = pOldNode->pNext;
66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (pOldNode == m_pNodeTail) {
68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        m_pNodeTail = pOldNode->pPrev;
69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    } else {
70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        pOldNode->pNext->pPrev = pOldNode->pPrev;
71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    FreeNode(pOldNode);
73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid CFX_PtrList::FreeNode(CFX_PtrList::CNode* pNode)
75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pNode->pNext = m_pNodeFree;
77ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_pNodeFree = pNode;
78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_nCount--;
79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (m_nCount == 0) {
80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        RemoveAll();
81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid CFX_PtrList::RemoveAll()
84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_nCount = 0;
86ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_pBlocks->FreeDataChain(m_pAllocator);
88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_pBlocks = NULL;
89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
90ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_PtrList::CNode*
91ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_PtrList::NewNode(CFX_PtrList::CNode* pPrev, CFX_PtrList::CNode* pNext)
92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (m_pNodeFree == NULL) {
94ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        CFX_Plex* pNewBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CNode));
95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        CNode* pNode = (CNode*)pNewBlock->data();
96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        pNode += m_nBlockSize - 1;
97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        for (int i = m_nBlockSize - 1; i >= 0; i--, pNode--) {
98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov            pNode->pNext = m_pNodeFree;
99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov            m_pNodeFree = pNode;
100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        }
101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    ASSERT(m_pNodeFree != NULL);
103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CFX_PtrList::CNode* pNode = m_pNodeFree;
104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_pNodeFree = m_pNodeFree->pNext;
105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pNode->pPrev = pPrev;
106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pNode->pNext = pNext;
107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    m_nCount++;
108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    ASSERT(m_nCount > 0);
109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    pNode->data = 0;
110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    return pNode;
111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
112ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_PtrList::~CFX_PtrList()
113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
114ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    RemoveAll();
115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    ASSERT(m_nCount == 0);
116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
117ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_POSITION CFX_PtrList::FindIndex(int nIndex) const
118ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (nIndex >= m_nCount || nIndex < 0) {
120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        return NULL;
121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CNode* pNode = m_pNodeHead;
123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    while (nIndex--) {
124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        pNode = pNode->pNext;
125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
126ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    return (FX_POSITION) pNode;
127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
128ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_POSITION CFX_PtrList::Find(void* searchValue, FX_POSITION startAfter) const
129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{
130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    CNode* pNode = (CNode*) startAfter;
131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    if (pNode == NULL) {
132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        pNode = m_pNodeHead;
133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    } else {
134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        pNode = pNode->pNext;
135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    }
136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    for (; pNode != NULL; pNode = pNode->pNext)
137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        if (pNode->data == searchValue) {
138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov            return (FX_POSITION) pNode;
139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov        }
140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov    return NULL;
141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}
142