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 FX_POSITION CFX_PtrList::AddTail(void* newElement) {
  17   CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  18   pNewNode->data = newElement;
  19   if (m_pNodeTail != NULL) {
  20     m_pNodeTail->pNext = pNewNode;
  21   } else {
  22     m_pNodeHead = pNewNode;
  23   }
  24   m_pNodeTail = pNewNode;
  25   return (FX_POSITION)pNewNode;
  26 }
  27 FX_POSITION CFX_PtrList::AddHead(void* newElement) {
  28   CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  29   pNewNode->data = newElement;
  30   if (m_pNodeHead != NULL) {
  31     m_pNodeHead->pPrev = pNewNode;
  32   } else {
  33     m_pNodeTail = pNewNode;
  34   }
  35   m_pNodeHead = pNewNode;
  36   return (FX_POSITION)pNewNode;
  37 }
  38 FX_POSITION CFX_PtrList::InsertAfter(FX_POSITION position, void* newElement) {
  39   if (position == NULL) {
  40     return AddTail(newElement);
  41   }
  42   CNode* pOldNode = (CNode*)position;
  43   CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  44   pNewNode->data = newElement;
  45   if (pOldNode->pNext != NULL) {
  46     pOldNode->pNext->pPrev = pNewNode;
  47   } else {
  48     m_pNodeTail = pNewNode;
  49   }
  50   pOldNode->pNext = pNewNode;
  51   return (FX_POSITION)pNewNode;
  52 }
  53 void CFX_PtrList::RemoveAt(FX_POSITION position) {
  54   CNode* pOldNode = (CNode*)position;
  55   if (pOldNode == m_pNodeHead) {
  56     m_pNodeHead = pOldNode->pNext;
  57   } else {
  58     pOldNode->pPrev->pNext = pOldNode->pNext;
  59   }
  60   if (pOldNode == m_pNodeTail) {
  61     m_pNodeTail = pOldNode->pPrev;
  62   } else {
  63     pOldNode->pNext->pPrev = pOldNode->pPrev;
  64   }
  65   FreeNode(pOldNode);
  66 }
  67 void CFX_PtrList::FreeNode(CFX_PtrList::CNode* pNode) {
  68   pNode->pNext = m_pNodeFree;
  69   m_pNodeFree = pNode;
  70   m_nCount--;
  71   if (m_nCount == 0) {
  72     RemoveAll();
  73   }
  74 }
  75 void CFX_PtrList::RemoveAll() {
  76   m_nCount = 0;
  77   m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  78   m_pBlocks->FreeDataChain();
  79   m_pBlocks = NULL;
  80 }
  81 CFX_PtrList::CNode* CFX_PtrList::NewNode(CFX_PtrList::CNode* pPrev,
  82                                          CFX_PtrList::CNode* pNext) {
  83   if (m_pNodeFree == NULL) {
  84     CFX_Plex* pNewBlock =
  85         CFX_Plex::Create(m_pBlocks, m_nBlockSize, sizeof(CNode));
  86     CNode* pNode = (CNode*)pNewBlock->data();
  87     pNode += m_nBlockSize - 1;
  88     for (int i = m_nBlockSize - 1; i >= 0; i--, pNode--) {
  89       pNode->pNext = m_pNodeFree;
  90       m_pNodeFree = pNode;
  91     }
  92   }
  93   ASSERT(m_pNodeFree != NULL);
  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 }
 103 CFX_PtrList::~CFX_PtrList() {
 104   RemoveAll();
 105   ASSERT(m_nCount == 0);
 106 }
 107 FX_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 }
 117 FX_POSITION CFX_PtrList::Find(void* searchValue, FX_POSITION startAfter) const {
 118   CNode* pNode = (CNode*)startAfter;
 119   if (pNode == NULL) {
 120     pNode = m_pNodeHead;
 121   } else {
 122     pNode = pNode->pNext;
 123   }
 124   for (; pNode != NULL; pNode = pNode->pNext)
 125     if (pNode->data == searchValue) {
 126       return (FX_POSITION)pNode;
 127     }
 128   return NULL;
 129 }