src/fxcrt/fx_basic_array.cpp

// 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;
}