src/third_party/pdfium/core/src/fxcrt/fx_basic_list.cpp

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