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