From 5110c4743751145c4ae1934cd1d83bc6c55bb43f Mon Sep 17 00:00:00 2001 From: John Abd-El-Malek Date: Sat, 17 May 2014 22:33:34 -0700 Subject: Initial commit. --- core/src/fxcrt/fx_basic_array.cpp | 365 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 365 insertions(+) create mode 100644 core/src/fxcrt/fx_basic_array.cpp (limited to 'core/src/fxcrt/fx_basic_array.cpp') diff --git a/core/src/fxcrt/fx_basic_array.cpp b/core/src/fxcrt/fx_basic_array.cpp new file mode 100644 index 0000000000..36857ce336 --- /dev/null +++ b/core/src/fxcrt/fx_basic_array.cpp @@ -0,0 +1,365 @@ +// 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" +CFX_BasicArray::CFX_BasicArray(int unit_size, IFX_Allocator* pAllocator) + : m_pAllocator(pAllocator) + , m_pData(NULL) + , m_nSize(0) + , m_nMaxSize(0) + , m_nGrowBy(0) +{ + if (unit_size < 0 || unit_size > (1 << 28)) { + m_nUnitSize = 4; + } else { + m_nUnitSize = unit_size; + } +} +CFX_BasicArray::~CFX_BasicArray() +{ + FX_Allocator_Free(m_pAllocator, m_pData); +} +FX_BOOL CFX_BasicArray::SetSize(int nNewSize, int nGrowBy) +{ + if (nNewSize < 0 || nNewSize > (1 << 28) / m_nUnitSize) { + m_pData = NULL; + m_nSize = m_nMaxSize = 0; + return FALSE; + } + if (nGrowBy >= 0) { + m_nGrowBy = nGrowBy; + } + if (nNewSize == 0) { + if (m_pData != NULL) { + FX_Allocator_Free(m_pAllocator, m_pData); + m_pData = NULL; + } + m_nSize = m_nMaxSize = 0; + } else if (m_pData == NULL) { + m_pData = FX_Allocator_Alloc(m_pAllocator, FX_BYTE, nNewSize * m_nUnitSize); + if (!m_pData) { + m_nSize = m_nMaxSize = 0; + return FALSE; + } + FXSYS_memset32(m_pData, 0, nNewSize * m_nUnitSize); + 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 nGrowBy = m_nGrowBy; + if (nGrowBy == 0) { + nGrowBy = m_nSize / 8; + nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy); + } + int nNewMax; + if (nNewSize < m_nMaxSize + nGrowBy) { + nNewMax = m_nMaxSize + nGrowBy; + } else { + nNewMax = nNewSize; + } + FX_LPBYTE pNewData = FX_Allocator_Realloc(m_pAllocator, FX_BYTE, m_pData, nNewMax * m_nUnitSize); + 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; + if (!SetSize(m_nSize + src.m_nSize, -1)) { + 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, -1)) { + 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, -1)) { + return NULL; + } + } else { + int nOldSize = m_nSize; + if (!SetSize(m_nSize + nCount, -1)) { + 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, IFX_Allocator* pAllocator) + : m_pAllocator(pAllocator) + , 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(IFX_Allocator* pAllcator, int level, int size, void** pIndex) +{ + if (level == 0) { + FX_Allocator_Free(pAllcator, pIndex); + return; + } + for (int i = 0; i < size; i ++) { + if (pIndex[i] == NULL) { + continue; + } + _ClearIndex(pAllcator, level - 1, size, (void**)pIndex[i]); + } + FX_Allocator_Free(pAllcator, pIndex); +} +void CFX_BaseSegmentedArray::RemoveAll() +{ + if (m_pIndex == NULL) { + return; + } + _ClearIndex(m_pAllocator, 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_Allocator_Alloc(m_pAllocator, 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_Allocator_Alloc(m_pAllocator, void*, m_IndexSize); + if (pIndex == NULL) { + FX_Allocator_Free(m_pAllocator, pSegment); + return NULL; + } + FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize); + 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_Allocator_Alloc(m_pAllocator, void*, m_IndexSize); + if (pIndex == NULL) { + FX_Allocator_Free(m_pAllocator, pSegment); + return NULL; + } + FXSYS_memset32(pIndex, 0, sizeof(void*) * m_IndexSize); + 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_Allocator_Alloc(m_pAllocator, void*, m_IndexSize); + if (pSpot[seg_index / tree_size] == NULL) { + break; + } + FXSYS_memset32(pSpot[seg_index / tree_size], 0, sizeof(void*) * m_IndexSize); + } + pSpot = (void**)pSpot[seg_index / tree_size]; + seg_index = seg_index % tree_size; + tree_size /= m_IndexSize; + } + if (i < m_IndexDepth) { + FX_Allocator_Free(m_pAllocator, 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_Allocator_Free(m_pAllocator, pIndex[i % m_IndexSize]); + pIndex[i % m_IndexSize] = NULL; + } + } else { + FX_Allocator_Free(m_pAllocator, m_pIndex); + m_pIndex = NULL; + } + } + m_DataSize -= count; +} -- cgit v1.2.3