1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Copyright 2014 PDFium Authors. All rights reserved. 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Use of this source code is governed by a BSD-style license that can be 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// found in the LICENSE file. 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/fxcrt/fx_basic.h" 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_BasicArray::CFX_BasicArray(int unit_size, IFX_Allocator* pAllocator) 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov : m_pAllocator(pAllocator) 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_pData(NULL) 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_nSize(0) 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_nMaxSize(0) 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_nGrowBy(0) 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (unit_size < 0 || unit_size > (1 << 28)) { 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nUnitSize = 4; 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nUnitSize = unit_size; 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 21ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_BasicArray::~CFX_BasicArray() 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(m_pAllocator, m_pData); 24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 25ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_BOOL CFX_BasicArray::SetSize(int nNewSize, int nGrowBy) 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nNewSize < 0 || nNewSize > (1 << 28) / m_nUnitSize) { 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pData = NULL; 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nSize = m_nMaxSize = 0; 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nGrowBy >= 0) { 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nGrowBy = nGrowBy; 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nNewSize == 0) { 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_pData != NULL) { 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(m_pAllocator, m_pData); 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pData = NULL; 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nSize = m_nMaxSize = 0; 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (m_pData == NULL) { 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pData = FX_Allocator_Alloc(m_pAllocator, FX_BYTE, nNewSize * m_nUnitSize); 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!m_pData) { 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nSize = m_nMaxSize = 0; 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset32(m_pData, 0, nNewSize * m_nUnitSize); 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nSize = m_nMaxSize = nNewSize; 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (nNewSize <= m_nMaxSize) { 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nNewSize > m_nSize) { 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset32(m_pData + m_nSize * m_nUnitSize, 0, (nNewSize - m_nSize) * m_nUnitSize); 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nSize = nNewSize; 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int nGrowBy = m_nGrowBy; 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nGrowBy == 0) { 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov nGrowBy = m_nSize / 8; 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy); 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int nNewMax; 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nNewSize < m_nMaxSize + nGrowBy) { 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov nNewMax = m_nMaxSize + nGrowBy; 63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov nNewMax = nNewSize; 65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_LPBYTE pNewData = FX_Allocator_Realloc(m_pAllocator, FX_BYTE, m_pData, nNewMax * m_nUnitSize); 67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pNewData == NULL) { 68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset32(pNewData + m_nSize * m_nUnitSize, 0, (nNewMax - m_nSize) * m_nUnitSize); 71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pData = pNewData; 72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nSize = nNewSize; 73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nMaxSize = nNewMax; 74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return TRUE; 76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 77ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_BOOL CFX_BasicArray::Append(const CFX_BasicArray& src) 78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int nOldSize = m_nSize; 80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!SetSize(m_nSize + src.m_nSize, -1)) { 81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy32(m_pData + nOldSize * m_nUnitSize, src.m_pData, src.m_nSize * m_nUnitSize); 84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return TRUE; 85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 86ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_BOOL CFX_BasicArray::Copy(const CFX_BasicArray& src) 87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!SetSize(src.m_nSize, -1)) { 89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 90ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 91ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy32(m_pData, src.m_pData, src.m_nSize * m_nUnitSize); 92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return TRUE; 93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 94ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_LPBYTE CFX_BasicArray::InsertSpaceAt(int nIndex, int nCount) 95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nIndex < 0 || nCount <= 0) { 97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nIndex >= m_nSize) { 100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!SetSize(nIndex + nCount, -1)) { 101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int nOldSize = m_nSize; 105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!SetSize(m_nSize + nCount, -1)) { 106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memmove32(m_pData + (nIndex + nCount)*m_nUnitSize, m_pData + nIndex * m_nUnitSize, 109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (nOldSize - nIndex) * m_nUnitSize); 110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset32(m_pData + nIndex * m_nUnitSize, 0, nCount * m_nUnitSize); 111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 112ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_pData + nIndex * m_nUnitSize; 113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 114ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_BOOL CFX_BasicArray::RemoveAt(int nIndex, int nCount) 115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nIndex < 0 || nCount <= 0 || m_nSize < nIndex + nCount) { 117ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 118ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int nMoveCount = m_nSize - (nIndex + nCount); 120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nMoveCount) { 121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memmove32(m_pData + nIndex * m_nUnitSize, m_pData + (nIndex + nCount) * m_nUnitSize, nMoveCount * m_nUnitSize); 122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_nSize -= nCount; 124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return TRUE; 125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 126ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFX_BOOL CFX_BasicArray::InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray) 127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 128ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pNewArray == NULL) { 129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pNewArray->m_nSize == 0) { 132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return TRUE; 133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!InsertSpaceAt(nStartIndex, pNewArray->m_nSize)) { 135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FALSE; 136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy32(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, pNewArray->m_nSize * m_nUnitSize); 138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return TRUE; 139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovconst void* CFX_BasicArray::GetDataPtr(int index) const 141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 142ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (index < 0 || index >= m_nSize || m_pData == NULL) { 143ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 144ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 145ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_pData + index * m_nUnitSize; 146ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 147ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, int segment_units, int index_size, IFX_Allocator* pAllocator) 148ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov : m_pAllocator(pAllocator) 149ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_UnitSize(unit_size) 150ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_SegmentSize(segment_units) 151ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_IndexSize(index_size) 152ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_IndexDepth(0) 153ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_DataSize(0) 154ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov , m_pIndex(NULL) 155ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 156ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 157ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid CFX_BaseSegmentedArray::SetUnitSize(int unit_size, int segment_units, int index_size) 158ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 159ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ASSERT(m_DataSize == 0); 160ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_UnitSize = unit_size; 161ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_SegmentSize = segment_units; 162ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_IndexSize = index_size; 163ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 164ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovCFX_BaseSegmentedArray::~CFX_BaseSegmentedArray() 165ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 166ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov RemoveAll(); 167ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 168ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovstatic void _ClearIndex(IFX_Allocator* pAllcator, int level, int size, void** pIndex) 169ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 170ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (level == 0) { 171ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(pAllcator, pIndex); 172ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 173ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 174ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (int i = 0; i < size; i ++) { 175ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pIndex[i] == NULL) { 176ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov continue; 177ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 178ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov _ClearIndex(pAllcator, level - 1, size, (void**)pIndex[i]); 179ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 180ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(pAllcator, pIndex); 181ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 182ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid CFX_BaseSegmentedArray::RemoveAll() 183ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 184ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_pIndex == NULL) { 185ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 186ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 187ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov _ClearIndex(m_pAllocator, m_IndexDepth, m_IndexSize, (void**)m_pIndex); 188ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pIndex = NULL; 189ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_IndexDepth = 0; 190ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_DataSize = 0; 191ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 192ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid* CFX_BaseSegmentedArray::Add() 193ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 194ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_DataSize % m_SegmentSize) { 195ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return GetAt(m_DataSize ++); 196ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 197ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void* pSegment = FX_Allocator_Alloc(m_pAllocator, FX_BYTE, m_UnitSize * m_SegmentSize); 198ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!pSegment) { 199ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 200ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 201ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_pIndex == NULL) { 202ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pIndex = pSegment; 203ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_DataSize ++; 204ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return pSegment; 205ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 206ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_IndexDepth == 0) { 207ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void** pIndex = (void**)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize); 208ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pIndex == NULL) { 209ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(m_pAllocator, pSegment); 210ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 211ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 212ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize); 213ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pIndex[0] = m_pIndex; 214ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pIndex[1] = pSegment; 215ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pIndex = pIndex; 216ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_DataSize ++; 217ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_IndexDepth ++; 218ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return pSegment; 219ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 220ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int seg_index = m_DataSize / m_SegmentSize; 221ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (seg_index % m_IndexSize) { 222ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void** pIndex = GetIndex(seg_index); 223ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pIndex[seg_index % m_IndexSize] = pSegment; 224ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_DataSize ++; 225ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return pSegment; 226ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 227ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int tree_size = 1; 228ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int i; 229ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 0; i < m_IndexDepth; i ++) { 230ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree_size *= m_IndexSize; 231ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 232ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_DataSize == tree_size * m_SegmentSize) { 233ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void** pIndex = (void**)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize); 234ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pIndex == NULL) { 235ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(m_pAllocator, pSegment); 236ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 237ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 238ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize); 239ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pIndex[0] = m_pIndex; 240ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pIndex = pIndex; 241ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_IndexDepth ++; 242ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 243ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree_size /= m_IndexSize; 244ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 245ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void** pSpot = (void**)m_pIndex; 246ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 1; i < m_IndexDepth; i ++) { 247ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pSpot[seg_index / tree_size] == NULL) { 248ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pSpot[seg_index / tree_size] = (void*)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize); 249ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pSpot[seg_index / tree_size] == NULL) { 250ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 251ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 252ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset32(pSpot[seg_index / tree_size], 0, sizeof(void*) * m_IndexSize); 253ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 254ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pSpot = (void**)pSpot[seg_index / tree_size]; 255ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov seg_index = seg_index % tree_size; 256ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree_size /= m_IndexSize; 257ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 258ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (i < m_IndexDepth) { 259ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(m_pAllocator, pSegment); 260ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov RemoveAll(); 261ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 262ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 263ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pSpot[seg_index % m_IndexSize] = pSegment; 264ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_DataSize ++; 265ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return pSegment; 266ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 267ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid** CFX_BaseSegmentedArray::GetIndex(int seg_index) const 268ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 269ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ASSERT(m_IndexDepth != 0); 270ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_IndexDepth == 1) { 271ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (void**)m_pIndex; 272ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (m_IndexDepth == 2) { 273ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (void**)((void**)m_pIndex)[seg_index / m_IndexSize]; 274ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 275ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int tree_size = 1; 276ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int i; 277ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 1; i < m_IndexDepth; i ++) { 278ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree_size *= m_IndexSize; 279ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 280ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void** pSpot = (void**)m_pIndex; 281ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 1; i < m_IndexDepth; i ++) { 282ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pSpot = (void**)pSpot[seg_index / tree_size]; 283ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov seg_index = seg_index % tree_size; 284ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree_size /= m_IndexSize; 285ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 286ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return pSpot; 287ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 288ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid* CFX_BaseSegmentedArray::IterateSegment(FX_LPCBYTE pSegment, int count, FX_BOOL (*callback)(void* param, void* pData), void* param) const 289ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 290ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (int i = 0; i < count; i ++) { 291ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (!callback(param, (void*)(pSegment + i * m_UnitSize))) { 292ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (void*)(pSegment + i * m_UnitSize); 293ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 294ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 295ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 296ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 297ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid* CFX_BaseSegmentedArray::IterateIndex(int level, int& start, void** pIndex, FX_BOOL (*callback)(void* param, void* pData), void* param) const 298ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 299ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (level == 0) { 300ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int count = m_DataSize - start; 301ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (count > m_SegmentSize) { 302ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov count = m_SegmentSize; 303ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 304ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov start += count; 305ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return IterateSegment((FX_LPCBYTE)pIndex, count, callback, param); 306ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 307ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (int i = 0; i < m_IndexSize; i ++) { 308ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (pIndex[i] == NULL) { 309ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov continue; 310ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 311ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void* p = IterateIndex(level - 1, start, (void**)pIndex[i], callback, param); 312ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (p) { 313ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return p; 314ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 315ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 316ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 317ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 318ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, void* pData), void* param) const 319ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 320ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_pIndex == NULL) { 321ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 322ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 323ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int start = 0; 324ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param); 325ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 326ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid* CFX_BaseSegmentedArray::GetAt(int index) const 327ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 328ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (index < 0 || index >= m_DataSize) { 329ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return NULL; 330ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 331ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m_IndexDepth == 0) { 332ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (FX_LPBYTE)m_pIndex + m_UnitSize * index; 333ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 334ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int seg_index = index / m_SegmentSize; 335ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (FX_LPBYTE)GetIndex(seg_index)[seg_index % m_IndexSize] + (index % m_SegmentSize) * m_UnitSize; 336ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 337ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid CFX_BaseSegmentedArray::Delete(int index, int count) 338ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 339ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(index < 0 || count < 1 || index + count > m_DataSize) { 340ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 341ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 342ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int i; 343ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = index; i < m_DataSize - count; i ++) { 344ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_BYTE* pSrc = (FX_BYTE*)GetAt(i + count); 345ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_BYTE* pDest = (FX_BYTE*)GetAt(i); 346ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (int j = 0; j < m_UnitSize; j ++) { 347ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pDest[j] = pSrc[j]; 348ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 349ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 350ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize; 351ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize; 352ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (new_segs < old_segs) { 353ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(m_IndexDepth) { 354ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = new_segs; i < old_segs; i ++) { 355ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void** pIndex = GetIndex(i); 356ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(m_pAllocator, pIndex[i % m_IndexSize]); 357ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pIndex[i % m_IndexSize] = NULL; 358ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 359ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 360ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Allocator_Free(m_pAllocator, m_pIndex); 361ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_pIndex = NULL; 362ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 363ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 364ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_DataSize -= count; 365ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 366