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