Kill operator LPCWSTR from CFX_WideString().
[pdfium.git] / core / src / fxcrt / fx_basic_array.cpp
index 36857ce..9bdc607 100644 (file)
-// Copyright 2014 PDFium Authors. All rights reserved.\r
-// Use of this source code is governed by a BSD-style license that can be\r
-// found in the LICENSE file.\r
\r
-// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com\r
-\r
-#include "../../include/fxcrt/fx_basic.h"\r
-CFX_BasicArray::CFX_BasicArray(int unit_size, IFX_Allocator* pAllocator)\r
-    : m_pAllocator(pAllocator)\r
-    , m_pData(NULL)\r
-    , m_nSize(0)\r
-    , m_nMaxSize(0)\r
-    , m_nGrowBy(0)\r
-{\r
-    if (unit_size < 0 || unit_size > (1 << 28)) {\r
-        m_nUnitSize = 4;\r
-    } else {\r
-        m_nUnitSize = unit_size;\r
-    }\r
-}\r
-CFX_BasicArray::~CFX_BasicArray()\r
-{\r
-    FX_Allocator_Free(m_pAllocator, m_pData);\r
-}\r
-FX_BOOL CFX_BasicArray::SetSize(int nNewSize, int nGrowBy)\r
-{\r
-    if (nNewSize < 0 || nNewSize > (1 << 28) / m_nUnitSize) {\r
-        m_pData = NULL;\r
-        m_nSize = m_nMaxSize = 0;\r
-        return FALSE;\r
-    }\r
-    if (nGrowBy >= 0) {\r
-        m_nGrowBy = nGrowBy;\r
-    }\r
-    if (nNewSize == 0) {\r
-        if (m_pData != NULL) {\r
-            FX_Allocator_Free(m_pAllocator, m_pData);\r
-            m_pData = NULL;\r
-        }\r
-        m_nSize = m_nMaxSize = 0;\r
-    } else if (m_pData == NULL) {\r
-        m_pData = FX_Allocator_Alloc(m_pAllocator, FX_BYTE, nNewSize * m_nUnitSize);\r
-        if (!m_pData) {\r
-            m_nSize = m_nMaxSize = 0;\r
-            return FALSE;\r
-        }\r
-        FXSYS_memset32(m_pData, 0, nNewSize * m_nUnitSize);\r
-        m_nSize = m_nMaxSize = nNewSize;\r
-    } else if (nNewSize <= m_nMaxSize) {\r
-        if (nNewSize > m_nSize) {\r
-            FXSYS_memset32(m_pData + m_nSize * m_nUnitSize, 0, (nNewSize - m_nSize) * m_nUnitSize);\r
-        }\r
-        m_nSize = nNewSize;\r
-    } else {\r
-        int nGrowBy = m_nGrowBy;\r
-        if (nGrowBy == 0) {\r
-            nGrowBy = m_nSize / 8;\r
-            nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);\r
-        }\r
-        int nNewMax;\r
-        if (nNewSize < m_nMaxSize + nGrowBy) {\r
-            nNewMax = m_nMaxSize + nGrowBy;\r
-        } else {\r
-            nNewMax = nNewSize;\r
-        }\r
-        FX_LPBYTE pNewData = FX_Allocator_Realloc(m_pAllocator, FX_BYTE, m_pData, nNewMax * m_nUnitSize);\r
-        if (pNewData == NULL) {\r
-            return FALSE;\r
-        }\r
-        FXSYS_memset32(pNewData + m_nSize * m_nUnitSize, 0, (nNewMax - m_nSize) * m_nUnitSize);\r
-        m_pData = pNewData;\r
-        m_nSize = nNewSize;\r
-        m_nMaxSize = nNewMax;\r
-    }\r
-    return TRUE;\r
-}\r
-FX_BOOL CFX_BasicArray::Append(const CFX_BasicArray& src)\r
-{\r
-    int nOldSize = m_nSize;\r
-    if (!SetSize(m_nSize + src.m_nSize, -1)) {\r
-        return FALSE;\r
-    }\r
-    FXSYS_memcpy32(m_pData + nOldSize * m_nUnitSize, src.m_pData, src.m_nSize * m_nUnitSize);\r
-    return TRUE;\r
-}\r
-FX_BOOL CFX_BasicArray::Copy(const CFX_BasicArray& src)\r
-{\r
-    if (!SetSize(src.m_nSize, -1)) {\r
-        return FALSE;\r
-    }\r
-    FXSYS_memcpy32(m_pData, src.m_pData, src.m_nSize * m_nUnitSize);\r
-    return TRUE;\r
-}\r
-FX_LPBYTE CFX_BasicArray::InsertSpaceAt(int nIndex, int nCount)\r
-{\r
-    if (nIndex < 0 || nCount <= 0) {\r
-        return NULL;\r
-    }\r
-    if (nIndex >= m_nSize) {\r
-        if (!SetSize(nIndex + nCount, -1)) {\r
-            return NULL;\r
-        }\r
-    } else {\r
-        int nOldSize = m_nSize;\r
-        if (!SetSize(m_nSize + nCount, -1)) {\r
-            return NULL;\r
-        }\r
-        FXSYS_memmove32(m_pData + (nIndex + nCount)*m_nUnitSize, m_pData + nIndex * m_nUnitSize,\r
-                        (nOldSize - nIndex) * m_nUnitSize);\r
-        FXSYS_memset32(m_pData + nIndex * m_nUnitSize, 0, nCount * m_nUnitSize);\r
-    }\r
-    return m_pData + nIndex * m_nUnitSize;\r
-}\r
-FX_BOOL CFX_BasicArray::RemoveAt(int nIndex, int nCount)\r
-{\r
-    if (nIndex < 0 || nCount <= 0 || m_nSize < nIndex + nCount) {\r
-        return FALSE;\r
-    }\r
-    int nMoveCount = m_nSize - (nIndex + nCount);\r
-    if (nMoveCount) {\r
-        FXSYS_memmove32(m_pData + nIndex * m_nUnitSize, m_pData + (nIndex + nCount) * m_nUnitSize, nMoveCount * m_nUnitSize);\r
-    }\r
-    m_nSize -= nCount;\r
-    return TRUE;\r
-}\r
-FX_BOOL CFX_BasicArray::InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray)\r
-{\r
-    if (pNewArray == NULL) {\r
-        return FALSE;\r
-    }\r
-    if (pNewArray->m_nSize == 0) {\r
-        return TRUE;\r
-    }\r
-    if (!InsertSpaceAt(nStartIndex, pNewArray->m_nSize)) {\r
-        return FALSE;\r
-    }\r
-    FXSYS_memcpy32(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, pNewArray->m_nSize * m_nUnitSize);\r
-    return TRUE;\r
-}\r
-const void* CFX_BasicArray::GetDataPtr(int index) const\r
-{\r
-    if (index < 0 || index >= m_nSize || m_pData == NULL) {\r
-        return NULL;\r
-    }\r
-    return m_pData + index * m_nUnitSize;\r
-}\r
-CFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, int segment_units, int index_size, IFX_Allocator* pAllocator)\r
-    : m_pAllocator(pAllocator)\r
-    , m_UnitSize(unit_size)\r
-    , m_SegmentSize(segment_units)\r
-    , m_IndexSize(index_size)\r
-    , m_IndexDepth(0)\r
-    , m_DataSize(0)\r
-    , m_pIndex(NULL)\r
-{\r
-}\r
-void CFX_BaseSegmentedArray::SetUnitSize(int unit_size, int segment_units, int index_size)\r
-{\r
-    ASSERT(m_DataSize == 0);\r
-    m_UnitSize = unit_size;\r
-    m_SegmentSize = segment_units;\r
-    m_IndexSize = index_size;\r
-}\r
-CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray()\r
-{\r
-    RemoveAll();\r
-}\r
-static void _ClearIndex(IFX_Allocator* pAllcator, int level, int size, void** pIndex)\r
-{\r
-    if (level == 0) {\r
-        FX_Allocator_Free(pAllcator, pIndex);\r
-        return;\r
-    }\r
-    for (int i = 0; i < size; i ++) {\r
-        if (pIndex[i] == NULL) {\r
-            continue;\r
-        }\r
-        _ClearIndex(pAllcator, level - 1, size, (void**)pIndex[i]);\r
-    }\r
-    FX_Allocator_Free(pAllcator, pIndex);\r
-}\r
-void CFX_BaseSegmentedArray::RemoveAll()\r
-{\r
-    if (m_pIndex == NULL) {\r
-        return;\r
-    }\r
-    _ClearIndex(m_pAllocator, m_IndexDepth, m_IndexSize, (void**)m_pIndex);\r
-    m_pIndex = NULL;\r
-    m_IndexDepth = 0;\r
-    m_DataSize = 0;\r
-}\r
-void* CFX_BaseSegmentedArray::Add()\r
-{\r
-    if (m_DataSize % m_SegmentSize) {\r
-        return GetAt(m_DataSize ++);\r
-    }\r
-    void* pSegment = FX_Allocator_Alloc(m_pAllocator, FX_BYTE, m_UnitSize * m_SegmentSize);\r
-    if (!pSegment) {\r
-        return NULL;\r
-    }\r
-    if (m_pIndex == NULL) {\r
-        m_pIndex = pSegment;\r
-        m_DataSize ++;\r
-        return pSegment;\r
-    }\r
-    if (m_IndexDepth == 0) {\r
-        void** pIndex = (void**)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize);\r
-        if (pIndex == NULL) {\r
-            FX_Allocator_Free(m_pAllocator, pSegment);\r
-            return NULL;\r
-        }\r
-        FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize);\r
-        pIndex[0] = m_pIndex;\r
-        pIndex[1] = pSegment;\r
-        m_pIndex = pIndex;\r
-        m_DataSize ++;\r
-        m_IndexDepth ++;\r
-        return pSegment;\r
-    }\r
-    int seg_index = m_DataSize / m_SegmentSize;\r
-    if (seg_index % m_IndexSize) {\r
-        void** pIndex = GetIndex(seg_index);\r
-        pIndex[seg_index % m_IndexSize] = pSegment;\r
-        m_DataSize ++;\r
-        return pSegment;\r
-    }\r
-    int tree_size = 1;\r
-    int i;\r
-    for (i = 0; i < m_IndexDepth; i ++) {\r
-        tree_size *= m_IndexSize;\r
-    }\r
-    if (m_DataSize == tree_size * m_SegmentSize) {\r
-        void** pIndex = (void**)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize);\r
-        if (pIndex == NULL) {\r
-            FX_Allocator_Free(m_pAllocator, pSegment);\r
-            return NULL;\r
-        }\r
-        FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize);\r
-        pIndex[0] = m_pIndex;\r
-        m_pIndex = pIndex;\r
-        m_IndexDepth ++;\r
-    } else {\r
-        tree_size /= m_IndexSize;\r
-    }\r
-    void** pSpot = (void**)m_pIndex;\r
-    for (i = 1; i < m_IndexDepth; i ++) {\r
-        if (pSpot[seg_index / tree_size] == NULL) {\r
-            pSpot[seg_index / tree_size] = (void*)FX_Allocator_Alloc(m_pAllocator, void*, m_IndexSize);\r
-            if (pSpot[seg_index / tree_size] == NULL) {\r
-                break;\r
-            }\r
-            FXSYS_memset32(pSpot[seg_index / tree_size], 0, sizeof(void*) * m_IndexSize);\r
-        }\r
-        pSpot = (void**)pSpot[seg_index / tree_size];\r
-        seg_index = seg_index % tree_size;\r
-        tree_size /= m_IndexSize;\r
-    }\r
-    if (i < m_IndexDepth) {\r
-        FX_Allocator_Free(m_pAllocator, pSegment);\r
-        RemoveAll();\r
-        return NULL;\r
-    }\r
-    pSpot[seg_index % m_IndexSize] = pSegment;\r
-    m_DataSize ++;\r
-    return pSegment;\r
-}\r
-void** CFX_BaseSegmentedArray::GetIndex(int seg_index) const\r
-{\r
-    ASSERT(m_IndexDepth != 0);\r
-    if (m_IndexDepth == 1) {\r
-        return (void**)m_pIndex;\r
-    } else if (m_IndexDepth == 2) {\r
-        return (void**)((void**)m_pIndex)[seg_index / m_IndexSize];\r
-    }\r
-    int tree_size = 1;\r
-    int i;\r
-    for (i = 1; i < m_IndexDepth; i ++) {\r
-        tree_size *= m_IndexSize;\r
-    }\r
-    void** pSpot = (void**)m_pIndex;\r
-    for (i = 1; i < m_IndexDepth; i ++) {\r
-        pSpot = (void**)pSpot[seg_index / tree_size];\r
-        seg_index = seg_index % tree_size;\r
-        tree_size /= m_IndexSize;\r
-    }\r
-    return pSpot;\r
-}\r
-void* CFX_BaseSegmentedArray::IterateSegment(FX_LPCBYTE pSegment, int count, FX_BOOL (*callback)(void* param, void* pData), void* param) const\r
-{\r
-    for (int i = 0; i < count; i ++) {\r
-        if (!callback(param, (void*)(pSegment + i * m_UnitSize))) {\r
-            return (void*)(pSegment + i * m_UnitSize);\r
-        }\r
-    }\r
-    return NULL;\r
-}\r
-void* CFX_BaseSegmentedArray::IterateIndex(int level, int& start, void** pIndex, FX_BOOL (*callback)(void* param, void* pData), void* param) const\r
-{\r
-    if (level == 0) {\r
-        int count = m_DataSize - start;\r
-        if (count > m_SegmentSize) {\r
-            count = m_SegmentSize;\r
-        }\r
-        start += count;\r
-        return IterateSegment((FX_LPCBYTE)pIndex, count, callback, param);\r
-    }\r
-    for (int i = 0; i < m_IndexSize; i ++) {\r
-        if (pIndex[i] == NULL) {\r
-            continue;\r
-        }\r
-        void* p = IterateIndex(level - 1, start, (void**)pIndex[i], callback, param);\r
-        if (p) {\r
-            return p;\r
-        }\r
-    }\r
-    return NULL;\r
-}\r
-void* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, void* pData), void* param) const\r
-{\r
-    if (m_pIndex == NULL) {\r
-        return NULL;\r
-    }\r
-    int start = 0;\r
-    return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param);\r
-}\r
-void* CFX_BaseSegmentedArray::GetAt(int index) const\r
-{\r
-    if (index < 0 || index >= m_DataSize) {\r
-        return NULL;\r
-    }\r
-    if (m_IndexDepth == 0) {\r
-        return (FX_LPBYTE)m_pIndex + m_UnitSize * index;\r
-    }\r
-    int seg_index = index / m_SegmentSize;\r
-    return (FX_LPBYTE)GetIndex(seg_index)[seg_index % m_IndexSize] + (index % m_SegmentSize) * m_UnitSize;\r
-}\r
-void CFX_BaseSegmentedArray::Delete(int index, int count)\r
-{\r
-    if(index < 0 || count < 1 || index + count > m_DataSize) {\r
-        return;\r
-    }\r
-    int i;\r
-    for (i = index; i < m_DataSize - count; i ++) {\r
-        FX_BYTE* pSrc = (FX_BYTE*)GetAt(i + count);\r
-        FX_BYTE* pDest = (FX_BYTE*)GetAt(i);\r
-        for (int j = 0; j < m_UnitSize; j ++) {\r
-            pDest[j] = pSrc[j];\r
-        }\r
-    }\r
-    int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize;\r
-    int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize;\r
-    if (new_segs < old_segs) {\r
-        if(m_IndexDepth) {\r
-            for (i = new_segs; i < old_segs; i ++) {\r
-                void** pIndex = GetIndex(i);\r
-                FX_Allocator_Free(m_pAllocator, pIndex[i % m_IndexSize]);\r
-                pIndex[i % m_IndexSize] = NULL;\r
-            }\r
-        } else {\r
-            FX_Allocator_Free(m_pAllocator, m_pIndex);\r
-            m_pIndex = NULL;\r
-        }\r
-    }\r
-    m_DataSize -= count;\r
-}\r
+// Copyright 2014 PDFium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
+
+#include "../../include/fxcrt/fx_basic.h"
+#include "../../../third_party/base/numerics/safe_math.h"
+
+CFX_BasicArray::CFX_BasicArray(int unit_size)
+    : m_pData(NULL)
+    , m_nSize(0)
+    , m_nMaxSize(0)
+{
+    if (unit_size < 0 || unit_size > (1 << 28)) {
+        m_nUnitSize = 4;
+    } else {
+        m_nUnitSize = unit_size;
+    }
+}
+CFX_BasicArray::~CFX_BasicArray()
+{
+    FX_Free(m_pData);
+}
+FX_BOOL CFX_BasicArray::SetSize(int nNewSize)
+{
+    if (nNewSize <= 0) {
+        FX_Free(m_pData);
+        m_pData = NULL;
+        m_nSize = m_nMaxSize = 0;
+        return 0 == nNewSize;
+    }
+
+    if (m_pData == NULL) {
+        pdfium::base::CheckedNumeric<int> totalSize = nNewSize;
+        totalSize *= m_nUnitSize;
+        if (!totalSize.IsValid()) {
+            m_nSize = m_nMaxSize = 0;
+            return FALSE;
+        }
+        m_pData = FX_Alloc(FX_BYTE, totalSize.ValueOrDie());
+        if (!m_pData) {
+            m_nSize = m_nMaxSize = 0;
+            return FALSE;
+        }
+        m_nSize = m_nMaxSize = nNewSize;
+    } else if (nNewSize <= m_nMaxSize) {
+        if (nNewSize > m_nSize) {
+            FXSYS_memset32(m_pData + m_nSize * m_nUnitSize, 0, (nNewSize - m_nSize) * m_nUnitSize);
+        }
+        m_nSize = nNewSize;
+    } else {
+        int nNewMax = nNewSize < m_nMaxSize ? m_nMaxSize : nNewSize;
+        pdfium::base::CheckedNumeric<int> totalSize = nNewMax;
+        totalSize *= m_nUnitSize;
+        if (!totalSize.IsValid() || nNewMax < m_nSize) {
+            return FALSE;
+        }
+        FX_LPBYTE pNewData = FX_Realloc(FX_BYTE, m_pData, totalSize.ValueOrDie());
+        if (pNewData == NULL) {
+            return FALSE;
+        }
+        FXSYS_memset32(pNewData + m_nSize * m_nUnitSize, 0, (nNewMax - m_nSize) * m_nUnitSize);
+        m_pData = pNewData;
+        m_nSize = nNewSize;
+        m_nMaxSize = nNewMax;
+    }
+    return TRUE;
+}
+FX_BOOL CFX_BasicArray::Append(const CFX_BasicArray& src)
+{
+    int nOldSize = m_nSize;
+    pdfium::base::CheckedNumeric<int> newSize = m_nSize;
+    newSize += src.m_nSize;
+    if (m_nUnitSize != src.m_nUnitSize || !newSize.IsValid() || !SetSize(newSize.ValueOrDie())) {
+        return FALSE;
+    }
+
+    FXSYS_memcpy32(m_pData + nOldSize * m_nUnitSize, src.m_pData, src.m_nSize * m_nUnitSize);
+    return TRUE;
+}
+FX_BOOL CFX_BasicArray::Copy(const CFX_BasicArray& src)
+{
+    if (!SetSize(src.m_nSize)) {
+        return FALSE;
+    }
+    FXSYS_memcpy32(m_pData, src.m_pData, src.m_nSize * m_nUnitSize);
+    return TRUE;
+}
+FX_LPBYTE CFX_BasicArray::InsertSpaceAt(int nIndex, int nCount)
+{
+    if (nIndex < 0 || nCount <= 0) {
+        return NULL;
+    }
+    if (nIndex >= m_nSize) {
+        if (!SetSize(nIndex + nCount)) {
+            return NULL;
+        }
+    } else {
+        int nOldSize = m_nSize;
+        if (!SetSize(m_nSize + nCount)) {
+            return NULL;
+        }
+        FXSYS_memmove32(m_pData + (nIndex + nCount)*m_nUnitSize, m_pData + nIndex * m_nUnitSize,
+                        (nOldSize - nIndex) * m_nUnitSize);
+        FXSYS_memset32(m_pData + nIndex * m_nUnitSize, 0, nCount * m_nUnitSize);
+    }
+    return m_pData + nIndex * m_nUnitSize;
+}
+FX_BOOL CFX_BasicArray::RemoveAt(int nIndex, int nCount)
+{
+    if (nIndex < 0 || nCount <= 0 || m_nSize < nIndex + nCount) {
+        return FALSE;
+    }
+    int nMoveCount = m_nSize - (nIndex + nCount);
+    if (nMoveCount) {
+        FXSYS_memmove32(m_pData + nIndex * m_nUnitSize, m_pData + (nIndex + nCount) * m_nUnitSize, nMoveCount * m_nUnitSize);
+    }
+    m_nSize -= nCount;
+    return TRUE;
+}
+FX_BOOL CFX_BasicArray::InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray)
+{
+    if (pNewArray == NULL) {
+        return FALSE;
+    }
+    if (pNewArray->m_nSize == 0) {
+        return TRUE;
+    }
+    if (!InsertSpaceAt(nStartIndex, pNewArray->m_nSize)) {
+        return FALSE;
+    }
+    FXSYS_memcpy32(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, pNewArray->m_nSize * m_nUnitSize);
+    return TRUE;
+}
+const void* CFX_BasicArray::GetDataPtr(int index) const
+{
+    if (index < 0 || index >= m_nSize || m_pData == NULL) {
+        return NULL;
+    }
+    return m_pData + index * m_nUnitSize;
+}
+CFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, int segment_units, int index_size)
+    : m_UnitSize(unit_size)
+    , m_SegmentSize(segment_units)
+    , m_IndexSize(index_size)
+    , m_IndexDepth(0)
+    , m_DataSize(0)
+    , m_pIndex(NULL)
+{
+}
+void CFX_BaseSegmentedArray::SetUnitSize(int unit_size, int segment_units, int index_size)
+{
+    ASSERT(m_DataSize == 0);
+    m_UnitSize = unit_size;
+    m_SegmentSize = segment_units;
+    m_IndexSize = index_size;
+}
+CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray()
+{
+    RemoveAll();
+}
+static void _ClearIndex(int level, int size, void** pIndex)
+{
+    if (level == 0) {
+        FX_Free(pIndex);
+        return;
+    }
+    for (int i = 0; i < size; i++) {
+        if (pIndex[i] == NULL) {
+            continue;
+        }
+        _ClearIndex(level - 1, size, (void**)pIndex[i]);
+    }
+    FX_Free(pIndex);
+}
+void CFX_BaseSegmentedArray::RemoveAll()
+{
+    if (m_pIndex == NULL) {
+        return;
+    }
+    _ClearIndex(m_IndexDepth, m_IndexSize, (void**)m_pIndex);
+    m_pIndex = NULL;
+    m_IndexDepth = 0;
+    m_DataSize = 0;
+}
+void* CFX_BaseSegmentedArray::Add()
+{
+    if (m_DataSize % m_SegmentSize) {
+        return GetAt(m_DataSize ++);
+    }
+    void* pSegment = FX_Alloc(FX_BYTE, m_UnitSize * m_SegmentSize);
+    if (!pSegment) {
+        return NULL;
+    }
+    if (m_pIndex == NULL) {
+        m_pIndex = pSegment;
+        m_DataSize ++;
+        return pSegment;
+    }
+    if (m_IndexDepth == 0) {
+        void** pIndex = (void**)FX_Alloc(void*, m_IndexSize);
+        if (pIndex == NULL) {
+            FX_Free(pSegment);
+            return NULL;
+        }
+        pIndex[0] = m_pIndex;
+        pIndex[1] = pSegment;
+        m_pIndex = pIndex;
+        m_DataSize ++;
+        m_IndexDepth ++;
+        return pSegment;
+    }
+    int seg_index = m_DataSize / m_SegmentSize;
+    if (seg_index % m_IndexSize) {
+        void** pIndex = GetIndex(seg_index);
+        pIndex[seg_index % m_IndexSize] = pSegment;
+        m_DataSize ++;
+        return pSegment;
+    }
+    int tree_size = 1;
+    int i;
+    for (i = 0; i < m_IndexDepth; i ++) {
+        tree_size *= m_IndexSize;
+    }
+    if (m_DataSize == tree_size * m_SegmentSize) {
+        void** pIndex = (void**)FX_Alloc(void*, m_IndexSize);
+        if (pIndex == NULL) {
+            FX_Free(pSegment);
+            return NULL;
+        }
+        pIndex[0] = m_pIndex;
+        m_pIndex = pIndex;
+        m_IndexDepth ++;
+    } else {
+        tree_size /= m_IndexSize;
+    }
+    void** pSpot = (void**)m_pIndex;
+    for (i = 1; i < m_IndexDepth; i ++) {
+        if (pSpot[seg_index / tree_size] == NULL) {
+            pSpot[seg_index / tree_size] = (void*)FX_Alloc(void*, m_IndexSize);
+            if (pSpot[seg_index / tree_size] == NULL) {
+                break;
+            }
+        }
+        pSpot = (void**)pSpot[seg_index / tree_size];
+        seg_index = seg_index % tree_size;
+        tree_size /= m_IndexSize;
+    }
+    if (i < m_IndexDepth) {
+        FX_Free(pSegment);
+        RemoveAll();
+        return NULL;
+    }
+    pSpot[seg_index % m_IndexSize] = pSegment;
+    m_DataSize ++;
+    return pSegment;
+}
+void** CFX_BaseSegmentedArray::GetIndex(int seg_index) const
+{
+    ASSERT(m_IndexDepth != 0);
+    if (m_IndexDepth == 1) {
+        return (void**)m_pIndex;
+    } else if (m_IndexDepth == 2) {
+        return (void**)((void**)m_pIndex)[seg_index / m_IndexSize];
+    }
+    int tree_size = 1;
+    int i;
+    for (i = 1; i < m_IndexDepth; i ++) {
+        tree_size *= m_IndexSize;
+    }
+    void** pSpot = (void**)m_pIndex;
+    for (i = 1; i < m_IndexDepth; i ++) {
+        pSpot = (void**)pSpot[seg_index / tree_size];
+        seg_index = seg_index % tree_size;
+        tree_size /= m_IndexSize;
+    }
+    return pSpot;
+}
+void* CFX_BaseSegmentedArray::IterateSegment(FX_LPCBYTE pSegment, int count, FX_BOOL (*callback)(void* param, void* pData), void* param) const
+{
+    for (int i = 0; i < count; i ++) {
+        if (!callback(param, (void*)(pSegment + i * m_UnitSize))) {
+            return (void*)(pSegment + i * m_UnitSize);
+        }
+    }
+    return NULL;
+}
+void* CFX_BaseSegmentedArray::IterateIndex(int level, int& start, void** pIndex, FX_BOOL (*callback)(void* param, void* pData), void* param) const
+{
+    if (level == 0) {
+        int count = m_DataSize - start;
+        if (count > m_SegmentSize) {
+            count = m_SegmentSize;
+        }
+        start += count;
+        return IterateSegment((FX_LPCBYTE)pIndex, count, callback, param);
+    }
+    for (int i = 0; i < m_IndexSize; i ++) {
+        if (pIndex[i] == NULL) {
+            continue;
+        }
+        void* p = IterateIndex(level - 1, start, (void**)pIndex[i], callback, param);
+        if (p) {
+            return p;
+        }
+    }
+    return NULL;
+}
+void* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, void* pData), void* param) const
+{
+    if (m_pIndex == NULL) {
+        return NULL;
+    }
+    int start = 0;
+    return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param);
+}
+void* CFX_BaseSegmentedArray::GetAt(int index) const
+{
+    if (index < 0 || index >= m_DataSize) {
+        return NULL;
+    }
+    if (m_IndexDepth == 0) {
+        return (FX_LPBYTE)m_pIndex + m_UnitSize * index;
+    }
+    int seg_index = index / m_SegmentSize;
+    return (FX_LPBYTE)GetIndex(seg_index)[seg_index % m_IndexSize] + (index % m_SegmentSize) * m_UnitSize;
+}
+void CFX_BaseSegmentedArray::Delete(int index, int count)
+{
+    if(index < 0 || count < 1 || index + count > m_DataSize) {
+        return;
+    }
+    int i;
+    for (i = index; i < m_DataSize - count; i ++) {
+        FX_BYTE* pSrc = (FX_BYTE*)GetAt(i + count);
+        FX_BYTE* pDest = (FX_BYTE*)GetAt(i);
+        for (int j = 0; j < m_UnitSize; j ++) {
+            pDest[j] = pSrc[j];
+        }
+    }
+    int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize;
+    int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize;
+    if (new_segs < old_segs) {
+        if(m_IndexDepth) {
+            for (i = new_segs; i < old_segs; i ++) {
+                void** pIndex = GetIndex(i);
+                FX_Free(pIndex[i % m_IndexSize]);
+                pIndex[i % m_IndexSize] = NULL;
+            }
+        } else {
+            FX_Free(m_pIndex);
+            m_pIndex = NULL;
+        }
+    }
+    m_DataSize -= count;
+}