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