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"
9CFX_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}
18FX_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}
30FX_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}
42FX_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}
58void 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}
73void 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}
82void 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}
89CFX_PtrList::CNode*
90CFX_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}
111CFX_PtrList::~CFX_PtrList()
112{
113    RemoveAll();
114    ASSERT(m_nCount == 0);
115}
116FX_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}
127FX_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