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" 8ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann#include "third_party/base/numerics/safe_math.h" 9e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 10e6986e1e8d4a57987f47c215490cb080a65ee29aSvet GanovCFX_BasicArray::CFX_BasicArray(int unit_size) 11ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann : m_pData(NULL), m_nSize(0), m_nMaxSize(0) { 12ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (unit_size < 0 || unit_size > (1 << 28)) { 13ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nUnitSize = 4; 14ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 15ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nUnitSize = unit_size; 16ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 17e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 18ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannCFX_BasicArray::~CFX_BasicArray() { 19ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_Free(m_pData); 20e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 21ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_BOOL CFX_BasicArray::SetSize(int nNewSize) { 22ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (nNewSize <= 0) { 23ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_Free(m_pData); 24ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pData = NULL; 25ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nSize = m_nMaxSize = 0; 26ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return 0 == nNewSize; 27ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 28e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 29ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!m_pData) { 30ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pdfium::base::CheckedNumeric<int> totalSize = nNewSize; 31ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann totalSize *= m_nUnitSize; 32ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!totalSize.IsValid()) { 33ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nSize = m_nMaxSize = 0; 34ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 35ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 36ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pData = FX_Alloc(uint8_t, totalSize.ValueOrDie()); 37ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nSize = m_nMaxSize = nNewSize; 38ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else if (nNewSize <= m_nMaxSize) { 39ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (nNewSize > m_nSize) { 40ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memset(m_pData + m_nSize * m_nUnitSize, 0, 41ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann (nNewSize - m_nSize) * m_nUnitSize); 42ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 43ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nSize = nNewSize; 44ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 45ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int nNewMax = nNewSize < m_nMaxSize ? m_nMaxSize : nNewSize; 46ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pdfium::base::CheckedNumeric<int> totalSize = nNewMax; 47ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann totalSize *= m_nUnitSize; 48ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!totalSize.IsValid() || nNewMax < m_nSize) { 49ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 50ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 51ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann uint8_t* pNewData = FX_Realloc(uint8_t, m_pData, totalSize.ValueOrDie()); 52ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!pNewData) { 53ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 54ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 55ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memset(pNewData + m_nSize * m_nUnitSize, 0, 56ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann (nNewMax - m_nSize) * m_nUnitSize); 57ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pData = pNewData; 58ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nSize = nNewSize; 59ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nMaxSize = nNewMax; 60ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 61ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return TRUE; 62e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 63ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_BOOL CFX_BasicArray::Append(const CFX_BasicArray& src) { 64ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int nOldSize = m_nSize; 65ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pdfium::base::CheckedNumeric<int> newSize = m_nSize; 66ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann newSize += src.m_nSize; 67ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_nUnitSize != src.m_nUnitSize || !newSize.IsValid() || 68ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann !SetSize(newSize.ValueOrDie())) { 69ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 70ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 71e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov 72ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memcpy(m_pData + nOldSize * m_nUnitSize, src.m_pData, 73ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann src.m_nSize * m_nUnitSize); 74ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return TRUE; 75e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 76ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_BOOL CFX_BasicArray::Copy(const CFX_BasicArray& src) { 77ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!SetSize(src.m_nSize)) { 78ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 79ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 80ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memcpy(m_pData, src.m_pData, src.m_nSize * m_nUnitSize); 81ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return TRUE; 82e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 83ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannuint8_t* CFX_BasicArray::InsertSpaceAt(int nIndex, int nCount) { 84ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (nIndex < 0 || nCount <= 0) { 85ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 86ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 87ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (nIndex >= m_nSize) { 88ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!SetSize(nIndex + nCount)) { 89ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 90e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 91ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 92ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int nOldSize = m_nSize; 93ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!SetSize(m_nSize + nCount)) { 94ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 95ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 96ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memmove(m_pData + (nIndex + nCount) * m_nUnitSize, 97ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pData + nIndex * m_nUnitSize, 98ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann (nOldSize - nIndex) * m_nUnitSize); 99ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memset(m_pData + nIndex * m_nUnitSize, 0, nCount * m_nUnitSize); 100ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 101ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return m_pData + nIndex * m_nUnitSize; 102e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 103ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_BOOL CFX_BasicArray::RemoveAt(int nIndex, int nCount) { 104ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (nIndex < 0 || nCount <= 0 || m_nSize < nIndex + nCount) { 105ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 106ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 107ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int nMoveCount = m_nSize - (nIndex + nCount); 108ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (nMoveCount) { 109ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memmove(m_pData + nIndex * m_nUnitSize, 110ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pData + (nIndex + nCount) * m_nUnitSize, 111ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann nMoveCount * m_nUnitSize); 112ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 113ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_nSize -= nCount; 114ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return TRUE; 115e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 116ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannFX_BOOL CFX_BasicArray::InsertAt(int nStartIndex, 117ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann const CFX_BasicArray* pNewArray) { 118ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!pNewArray) { 119ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 120ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 121ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (pNewArray->m_nSize == 0) { 122e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return TRUE; 123ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 124ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!InsertSpaceAt(nStartIndex, pNewArray->m_nSize)) { 125ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return FALSE; 126ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 127ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FXSYS_memcpy(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, 128ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pNewArray->m_nSize * m_nUnitSize); 129ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return TRUE; 130e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 131ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannconst void* CFX_BasicArray::GetDataPtr(int index) const { 132ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (index < 0 || index >= m_nSize || !m_pData) { 133ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 134ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 135ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return m_pData + index * m_nUnitSize; 136e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 137ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannCFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, 138ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int segment_units, 139ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int index_size) 140ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann : m_UnitSize(unit_size), 141ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_SegmentSize(segment_units), 142ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_IndexSize(index_size), 143ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_IndexDepth(0), 144ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_DataSize(0), 145ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pIndex(NULL) {} 146ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid CFX_BaseSegmentedArray::SetUnitSize(int unit_size, 147ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int segment_units, 148ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int index_size) { 149ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann ASSERT(m_DataSize == 0); 150ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_UnitSize = unit_size; 151ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_SegmentSize = segment_units; 152ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_IndexSize = index_size; 153e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 154ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. MoltmannCFX_BaseSegmentedArray::~CFX_BaseSegmentedArray() { 155ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann RemoveAll(); 156e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 157ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannstatic void _ClearIndex(int level, int size, void** pIndex) { 158ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (level == 0) { 159e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov FX_Free(pIndex); 160ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return; 161ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 162ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (int i = 0; i < size; ++i) { 163ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (pIndex[i]) 164ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann _ClearIndex(level - 1, size, (void**)pIndex[i]); 165ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 166ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_Free(pIndex); 167e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 168ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid CFX_BaseSegmentedArray::RemoveAll() { 169ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!m_pIndex) { 170ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return; 171ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 172ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann _ClearIndex(m_IndexDepth, m_IndexSize, (void**)m_pIndex); 173ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pIndex = NULL; 174ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_IndexDepth = 0; 175ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_DataSize = 0; 176e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 177ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid* CFX_BaseSegmentedArray::Add() { 178ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_DataSize % m_SegmentSize) { 179ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return GetAt(m_DataSize++); 180ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 181ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* pSegment = FX_Alloc2D(uint8_t, m_UnitSize, m_SegmentSize); 182ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!m_pIndex) { 183ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pIndex = pSegment; 184ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_DataSize++; 185ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return pSegment; 186ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 187ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_IndexDepth == 0) { 188ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void** pIndex = FX_Alloc(void*, m_IndexSize); 189ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pIndex[0] = m_pIndex; 190ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pIndex[1] = pSegment; 191ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pIndex = pIndex; 192ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_DataSize++; 193ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_IndexDepth++; 194e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov return pSegment; 195ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 196ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int seg_index = m_DataSize / m_SegmentSize; 197ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (seg_index % m_IndexSize) { 198ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void** pIndex = GetIndex(seg_index); 199ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pIndex[seg_index % m_IndexSize] = pSegment; 200ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_DataSize++; 201ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return pSegment; 202ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 203ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int tree_size = 1; 204ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int i; 205ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (i = 0; i < m_IndexDepth; i++) { 206ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann tree_size *= m_IndexSize; 207ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 208ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_DataSize == tree_size * m_SegmentSize) { 209ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void** pIndex = FX_Alloc(void*, m_IndexSize); 210ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pIndex[0] = m_pIndex; 211ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pIndex = pIndex; 212ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_IndexDepth++; 213ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 214ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann tree_size /= m_IndexSize; 215ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 216ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void** pSpot = (void**)m_pIndex; 217ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (i = 1; i < m_IndexDepth; i++) { 218ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!pSpot[seg_index / tree_size]) { 219ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pSpot[seg_index / tree_size] = FX_Alloc(void*, m_IndexSize); 220ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 221ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pSpot = (void**)pSpot[seg_index / tree_size]; 222ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann seg_index = seg_index % tree_size; 223ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann tree_size /= m_IndexSize; 224ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 225ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (i < m_IndexDepth) { 226ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_Free(pSegment); 227ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann RemoveAll(); 228ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 229ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 230ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pSpot[seg_index % m_IndexSize] = pSegment; 231ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_DataSize++; 232ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return pSegment; 233e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 234ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid** CFX_BaseSegmentedArray::GetIndex(int seg_index) const { 235ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann ASSERT(m_IndexDepth != 0); 236ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_IndexDepth == 1) { 237ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (void**)m_pIndex; 238ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 239ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_IndexDepth == 2) { 240ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (void**)((void**)m_pIndex)[seg_index / m_IndexSize]; 241ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 242ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int tree_size = 1; 243ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int i; 244ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (i = 1; i < m_IndexDepth; i++) { 245ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann tree_size *= m_IndexSize; 246ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 247ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void** pSpot = (void**)m_pIndex; 248ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (i = 1; i < m_IndexDepth; i++) { 249ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pSpot = (void**)pSpot[seg_index / tree_size]; 250ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann seg_index = seg_index % tree_size; 251ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann tree_size /= m_IndexSize; 252ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 253ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return pSpot; 254e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 255ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid* CFX_BaseSegmentedArray::IterateSegment(const uint8_t* pSegment, 256ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int count, 257ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_BOOL (*callback)(void* param, 258ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* pData), 259ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* param) const { 260ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (int i = 0; i < count; i++) { 261ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!callback(param, (void*)(pSegment + i * m_UnitSize))) { 262ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (void*)(pSegment + i * m_UnitSize); 263ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 264ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 265ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 266e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 267ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid* CFX_BaseSegmentedArray::IterateIndex(int level, 268ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int& start, 269ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void** pIndex, 270ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_BOOL (*callback)(void* param, 271ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* pData), 272ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* param) const { 273ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (level == 0) { 274ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int count = m_DataSize - start; 275ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (count > m_SegmentSize) { 276ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann count = m_SegmentSize; 277ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 278ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann start += count; 279ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return IterateSegment((const uint8_t*)pIndex, count, callback, param); 280ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 281ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (int i = 0; i < m_IndexSize; i++) { 282ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!pIndex[i]) { 283ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann continue; 284ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 285ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* p = 286ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann IterateIndex(level - 1, start, (void**)pIndex[i], callback, param); 287ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (p) { 288ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return p; 289ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 290ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 291ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 292e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 293ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, 294ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* pData), 295ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void* param) const { 296ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (!m_pIndex) { 297ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 298ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 299ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int start = 0; 300ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param); 301e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 302ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid* CFX_BaseSegmentedArray::GetAt(int index) const { 303ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (index < 0 || index >= m_DataSize) { 304ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return NULL; 305ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 306ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_IndexDepth == 0) { 307ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (uint8_t*)m_pIndex + m_UnitSize * index; 308ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 309ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int seg_index = index / m_SegmentSize; 310ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return (uint8_t*)GetIndex(seg_index)[seg_index % m_IndexSize] + 311ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann (index % m_SegmentSize) * m_UnitSize; 312e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 313ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannvoid CFX_BaseSegmentedArray::Delete(int index, int count) { 314ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (index < 0 || count < 1 || index + count > m_DataSize) { 315ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann return; 316ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 317ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int i; 318ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (i = index; i < m_DataSize - count; i++) { 319ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann uint8_t* pSrc = (uint8_t*)GetAt(i + count); 320ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann uint8_t* pDest = (uint8_t*)GetAt(i); 321ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (int j = 0; j < m_UnitSize; j++) { 322ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pDest[j] = pSrc[j]; 323ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 324ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 325ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize; 326ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize; 327ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (new_segs < old_segs) { 328ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann if (m_IndexDepth) { 329ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann for (i = new_segs; i < old_segs; i++) { 330ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann void** pIndex = GetIndex(i); 331ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_Free(pIndex[i % m_IndexSize]); 332ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann pIndex[i % m_IndexSize] = NULL; 333ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 334ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } else { 335ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann FX_Free(m_pIndex); 336ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_pIndex = NULL; 337e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov } 338ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann } 339ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann m_DataSize -= count; 340e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov} 341