1e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// Copyright 2014 PDFium Authors. All rights reserved. 2e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// Use of this source code is governed by a BSD-style license that can be 3e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// found in the LICENSE file. 4e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 5e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 7e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#include "../../include/fxcrt/fx_basic.h" 8e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#include "plex.h" 9e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovCFX_PtrList::CFX_PtrList(int nBlockSize) 10e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov : m_pNodeHead(NULL) 11e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov , m_pNodeTail(NULL) 12e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov , m_nCount(0) 13e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov , m_pNodeFree(NULL) 14e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov , m_pBlocks(NULL) 15e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov , m_nBlockSize(nBlockSize) 16e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 17e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 18e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovFX_POSITION CFX_PtrList::AddTail(void* newElement) 19e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 20e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pNewNode = NewNode(m_pNodeTail, NULL); 21e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNewNode->data = newElement; 22e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (m_pNodeTail != NULL) { 23e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeTail->pNext = pNewNode; 24e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } else { 25e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeHead = pNewNode; 26e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 27e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeTail = pNewNode; 28e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return (FX_POSITION) pNewNode; 29e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 30e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovFX_POSITION CFX_PtrList::AddHead(void* newElement) 31e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 32e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pNewNode = NewNode(NULL, m_pNodeHead); 33e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNewNode->data = newElement; 34e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (m_pNodeHead != NULL) { 35e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeHead->pPrev = pNewNode; 36e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } else { 37e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeTail = pNewNode; 38e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 39e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeHead = pNewNode; 40e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return (FX_POSITION) pNewNode; 41e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 42e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovFX_POSITION CFX_PtrList::InsertAfter(FX_POSITION position, void* newElement) 43e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 44e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (position == NULL) { 45e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return AddTail(newElement); 46e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 47e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pOldNode = (CNode*) position; 48e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext); 49e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNewNode->data = newElement; 50e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (pOldNode->pNext != NULL) { 51e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pOldNode->pNext->pPrev = pNewNode; 52e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } else { 53e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeTail = pNewNode; 54e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 55e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pOldNode->pNext = pNewNode; 56e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return (FX_POSITION) pNewNode; 57e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 58e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovvoid CFX_PtrList::RemoveAt(FX_POSITION position) 59e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 60e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pOldNode = (CNode*) position; 61e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (pOldNode == m_pNodeHead) { 62e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeHead = pOldNode->pNext; 63e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } else { 64e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pOldNode->pPrev->pNext = pOldNode->pNext; 65e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 66e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (pOldNode == m_pNodeTail) { 67e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeTail = pOldNode->pPrev; 68e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } else { 69e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pOldNode->pNext->pPrev = pOldNode->pPrev; 70e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 71e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov FreeNode(pOldNode); 72e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 73e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovvoid CFX_PtrList::FreeNode(CFX_PtrList::CNode* pNode) 74e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 75e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode->pNext = m_pNodeFree; 76e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeFree = pNode; 77e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_nCount--; 78e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (m_nCount == 0) { 79e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov RemoveAll(); 80e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 81e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 82e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovvoid CFX_PtrList::RemoveAll() 83e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 84e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_nCount = 0; 85e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL; 86e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pBlocks->FreeDataChain(); 87e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pBlocks = NULL; 88e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 89e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovCFX_PtrList::CNode* 90e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovCFX_PtrList::NewNode(CFX_PtrList::CNode* pPrev, CFX_PtrList::CNode* pNext) 91e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 92e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (m_pNodeFree == NULL) { 93e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CFX_Plex* pNewBlock = CFX_Plex::Create(m_pBlocks, m_nBlockSize, sizeof(CNode)); 94e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pNode = (CNode*)pNewBlock->data(); 95e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode += m_nBlockSize - 1; 96e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov for (int i = m_nBlockSize - 1; i >= 0; i--, pNode--) { 97e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode->pNext = m_pNodeFree; 98e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeFree = pNode; 99e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 100e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 101e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov ASSERT(m_pNodeFree != NULL); 102e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CFX_PtrList::CNode* pNode = m_pNodeFree; 103e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeFree = m_pNodeFree->pNext; 104e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode->pPrev = pPrev; 105e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode->pNext = pNext; 106e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_nCount++; 107e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov ASSERT(m_nCount > 0); 108e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode->data = 0; 109e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return pNode; 110e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 111e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovCFX_PtrList::~CFX_PtrList() 112e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 113e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov RemoveAll(); 114e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov ASSERT(m_nCount == 0); 115e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 116e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovFX_POSITION CFX_PtrList::FindIndex(int nIndex) const 117e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 118e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (nIndex >= m_nCount || nIndex < 0) { 119e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return NULL; 120e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 121e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pNode = m_pNodeHead; 122e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov while (nIndex--) { 123e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode = pNode->pNext; 124e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 125e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return (FX_POSITION) pNode; 126e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 127e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovFX_POSITION CFX_PtrList::Find(void* searchValue, FX_POSITION startAfter) const 128e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov{ 129e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov CNode* pNode = (CNode*) startAfter; 130e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (pNode == NULL) { 131e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode = m_pNodeHead; 132e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } else { 133e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov pNode = pNode->pNext; 134e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 135e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov for (; pNode != NULL; pNode = pNode->pNext) 136e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov if (pNode->data == searchValue) { 137e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return (FX_POSITION) pNode; 138e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 139e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return NULL; 140e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 141