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,IFX_Allocator * pAllocator)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 }
AddTail(void * newElement)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 }
AddHead(void * newElement)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 }
InsertAfter(FX_POSITION position,void * newElement)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 }
RemoveAt(FX_POSITION position)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 }
FreeNode(CFX_PtrList::CNode * pNode)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 }
RemoveAll()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*
NewNode(CFX_PtrList::CNode * pPrev,CFX_PtrList::CNode * pNext)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 }
~CFX_PtrList()112 CFX_PtrList::~CFX_PtrList()
113 {
114 RemoveAll();
115 ASSERT(m_nCount == 0);
116 }
FindIndex(int nIndex) const117 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 }
Find(void * searchValue,FX_POSITION startAfter) const128 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 }
142