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 7ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann#include "core/include/fxcrt/fx_basic.h" 8e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov#include "plex.h" 9ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann 10e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovCFX_PtrList::CFX_PtrList(int nBlockSize) 11ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann : m_pNodeHead(NULL), 12ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeTail(NULL), 13ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nCount(0), 14ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeFree(NULL), 15ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pBlocks(NULL), 16ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nBlockSize(nBlockSize) {} 17ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_POSITION CFX_PtrList::AddTail(void* newElement) { 18ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pNewNode = NewNode(m_pNodeTail, NULL); 19ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNewNode->data = newElement; 20ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_pNodeTail) { 21ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeTail->pNext = pNewNode; 22ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 23ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeHead = pNewNode; 24ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 25ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeTail = pNewNode; 26ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (FX_POSITION)pNewNode; 27e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 28ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_POSITION CFX_PtrList::AddHead(void* newElement) { 29ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pNewNode = NewNode(NULL, m_pNodeHead); 30ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNewNode->data = newElement; 31ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_pNodeHead) { 32ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeHead->pPrev = pNewNode; 33ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 34e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_pNodeTail = pNewNode; 35ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 36ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeHead = pNewNode; 37ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (FX_POSITION)pNewNode; 38e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 39ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_POSITION CFX_PtrList::InsertAfter(FX_POSITION position, void* newElement) { 40ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!position) { 41ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return AddTail(newElement); 42ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 43ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pOldNode = (CNode*)position; 44ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext); 45ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNewNode->data = newElement; 46ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (pOldNode->pNext) { 47ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pOldNode->pNext->pPrev = pNewNode; 48ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 49ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeTail = pNewNode; 50ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 51ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pOldNode->pNext = pNewNode; 52ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (FX_POSITION)pNewNode; 53e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 54ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid CFX_PtrList::RemoveAt(FX_POSITION position) { 55ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pOldNode = (CNode*)position; 56ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (pOldNode == m_pNodeHead) { 57ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeHead = pOldNode->pNext; 58ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 59ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pOldNode->pPrev->pNext = pOldNode->pNext; 60ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 61ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (pOldNode == m_pNodeTail) { 62ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeTail = pOldNode->pPrev; 63ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 64ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pOldNode->pNext->pPrev = pOldNode->pPrev; 65ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 66ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FreeNode(pOldNode); 67e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 68ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid CFX_PtrList::FreeNode(CFX_PtrList::CNode* pNode) { 69ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode->pNext = m_pNodeFree; 70ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeFree = pNode; 71ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nCount--; 72ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_nCount == 0) { 73ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann RemoveAll(); 74ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 75e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 76ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid CFX_PtrList::RemoveAll() { 77ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nCount = 0; 78ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL; 79ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pBlocks->FreeDataChain(); 80ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pBlocks = NULL; 81e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 82ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannCFX_PtrList::CNode* CFX_PtrList::NewNode(CFX_PtrList::CNode* pPrev, 83ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CFX_PtrList::CNode* pNext) { 84ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!m_pNodeFree) { 85ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CFX_Plex* pNewBlock = 86ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CFX_Plex::Create(m_pBlocks, m_nBlockSize, sizeof(CNode)); 87ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pNode = (CNode*)pNewBlock->data(); 88ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode += m_nBlockSize - 1; 89ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (int i = m_nBlockSize - 1; i >= 0; i--, pNode--) { 90ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode->pNext = m_pNodeFree; 91ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeFree = pNode; 92e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 93ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 94ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CFX_PtrList::CNode* pNode = m_pNodeFree; 95ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pNodeFree = m_pNodeFree->pNext; 96ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode->pPrev = pPrev; 97ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode->pNext = pNext; 98ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nCount++; 99ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann ASSERT(m_nCount > 0); 100ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode->data = 0; 101ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return pNode; 102e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 103ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannCFX_PtrList::~CFX_PtrList() { 104ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann RemoveAll(); 105ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann ASSERT(m_nCount == 0); 106e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 107ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_POSITION CFX_PtrList::FindIndex(int nIndex) const { 108ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (nIndex >= m_nCount || nIndex < 0) { 109e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return NULL; 110ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 111ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pNode = m_pNodeHead; 112ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann while (nIndex--) { 113ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode = pNode->pNext; 114ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 115ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (FX_POSITION)pNode; 116ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann} 117ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_POSITION CFX_PtrList::Find(void* searchValue, FX_POSITION startAfter) const { 118ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann CNode* pNode = (CNode*)startAfter; 119ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNode = pNode ? pNode->pNext : m_pNodeHead; 120ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (; pNode; pNode = pNode->pNext) { 121ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (pNode->data == searchValue) 122ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (FX_POSITION)pNode; 123ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 124ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 125e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 126