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