core/src/fxcrt/fx_basic_array.cpp

   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 #include "../../../third_party/base/numerics/safe_math.h"
   9
  10 CFX_BasicArray::CFX_BasicArray(int unit_size)
  11     : m_pData(NULL), m_nSize(0), m_nMaxSize(0) {
  12   if (unit_size < 0 || unit_size > (1 << 28)) {
  13     m_nUnitSize = 4;
  14   } else {
  15     m_nUnitSize = unit_size;
  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       }
 336     } else {
 337       FX_Free(m_pIndex);
 338       m_pIndex = NULL;
 339     }
 340   }
 341   m_DataSize -= count;
 342 }