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"
CFX_PtrList(int nBlockSize)9 CFX_PtrList::CFX_PtrList(int nBlockSize)
10 : m_pNodeHead(NULL)
11 , m_pNodeTail(NULL)
12 , m_nCount(0)
13 , m_pNodeFree(NULL)
14 , m_pBlocks(NULL)
15 , m_nBlockSize(nBlockSize)
16 {
17 }
AddTail(void * newElement)18 FX_POSITION CFX_PtrList::AddTail(void* newElement)
19 {
20 CNode* pNewNode = NewNode(m_pNodeTail, NULL);
21 pNewNode->data = newElement;
22 if (m_pNodeTail != NULL) {
23 m_pNodeTail->pNext = pNewNode;
24 } else {
25 m_pNodeHead = pNewNode;
26 }
27 m_pNodeTail = pNewNode;
28 return (FX_POSITION) pNewNode;
29 }
AddHead(void * newElement)30 FX_POSITION CFX_PtrList::AddHead(void* newElement)
31 {
32 CNode* pNewNode = NewNode(NULL, m_pNodeHead);
33 pNewNode->data = newElement;
34 if (m_pNodeHead != NULL) {
35 m_pNodeHead->pPrev = pNewNode;
36 } else {
37 m_pNodeTail = pNewNode;
38 }
39 m_pNodeHead = pNewNode;
40 return (FX_POSITION) pNewNode;
41 }
InsertAfter(FX_POSITION position,void * newElement)42 FX_POSITION CFX_PtrList::InsertAfter(FX_POSITION position, void* newElement)
43 {
44 if (position == NULL) {
45 return AddTail(newElement);
46 }
47 CNode* pOldNode = (CNode*) position;
48 CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
49 pNewNode->data = newElement;
50 if (pOldNode->pNext != NULL) {
51 pOldNode->pNext->pPrev = pNewNode;
52 } else {
53 m_pNodeTail = pNewNode;
54 }
55 pOldNode->pNext = pNewNode;
56 return (FX_POSITION) pNewNode;
57 }
RemoveAt(FX_POSITION position)58 void CFX_PtrList::RemoveAt(FX_POSITION position)
59 {
60 CNode* pOldNode = (CNode*) position;
61 if (pOldNode == m_pNodeHead) {
62 m_pNodeHead = pOldNode->pNext;
63 } else {
64 pOldNode->pPrev->pNext = pOldNode->pNext;
65 }
66 if (pOldNode == m_pNodeTail) {
67 m_pNodeTail = pOldNode->pPrev;
68 } else {
69 pOldNode->pNext->pPrev = pOldNode->pPrev;
70 }
71 FreeNode(pOldNode);
72 }
FreeNode(CFX_PtrList::CNode * pNode)73 void CFX_PtrList::FreeNode(CFX_PtrList::CNode* pNode)
74 {
75 pNode->pNext = m_pNodeFree;
76 m_pNodeFree = pNode;
77 m_nCount--;
78 if (m_nCount == 0) {
79 RemoveAll();
80 }
81 }
RemoveAll()82 void CFX_PtrList::RemoveAll()
83 {
84 m_nCount = 0;
85 m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
86 m_pBlocks->FreeDataChain();
87 m_pBlocks = NULL;
88 }
89 CFX_PtrList::CNode*
NewNode(CFX_PtrList::CNode * pPrev,CFX_PtrList::CNode * pNext)90 CFX_PtrList::NewNode(CFX_PtrList::CNode* pPrev, CFX_PtrList::CNode* pNext)
91 {
92 if (m_pNodeFree == NULL) {
93 CFX_Plex* pNewBlock = CFX_Plex::Create(m_pBlocks, m_nBlockSize, sizeof(CNode));
94 CNode* pNode = (CNode*)pNewBlock->data();
95 pNode += m_nBlockSize - 1;
96 for (int i = m_nBlockSize - 1; i >= 0; i--, pNode--) {
97 pNode->pNext = m_pNodeFree;
98 m_pNodeFree = pNode;
99 }
100 }
101 ASSERT(m_pNodeFree != NULL);
102 CFX_PtrList::CNode* pNode = m_pNodeFree;
103 m_pNodeFree = m_pNodeFree->pNext;
104 pNode->pPrev = pPrev;
105 pNode->pNext = pNext;
106 m_nCount++;
107 ASSERT(m_nCount > 0);
108 pNode->data = 0;
109 return pNode;
110 }
~CFX_PtrList()111 CFX_PtrList::~CFX_PtrList()
112 {
113 RemoveAll();
114 ASSERT(m_nCount == 0);
115 }
FindIndex(int nIndex) const116 FX_POSITION CFX_PtrList::FindIndex(int nIndex) const
117 {
118 if (nIndex >= m_nCount || nIndex < 0) {
119 return NULL;
120 }
121 CNode* pNode = m_pNodeHead;
122 while (nIndex--) {
123 pNode = pNode->pNext;
124 }
125 return (FX_POSITION) pNode;
126 }
Find(void * searchValue,FX_POSITION startAfter) const127 FX_POSITION CFX_PtrList::Find(void* searchValue, FX_POSITION startAfter) const
128 {
129 CNode* pNode = (CNode*) startAfter;
130 if (pNode == NULL) {
131 pNode = m_pNodeHead;
132 } else {
133 pNode = pNode->pNext;
134 }
135 for (; pNode != NULL; pNode = pNode->pNext)
136 if (pNode->data == searchValue) {
137 return (FX_POSITION) pNode;
138 }
139 return NULL;
140 }
141