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