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, 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}
19FX_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}
31FX_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}
43FX_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}
59void 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}
74void 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}
83void 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}
90CFX_PtrList::CNode*
91CFX_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}
112CFX_PtrList::~CFX_PtrList()
113{
114    RemoveAll();
115    ASSERT(m_nCount == 0);
116}
117FX_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}
128FX_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