Home | History | Annotate | Download | only in fxcrt 
      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