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 "core/include/fxcrt/fx_basic.h"
#include "third_party/base/numerics/safe_math.h"

CFX_BasicArray::CFX_BasicArray(int unit_size)
    : m_pData(NULL), m_nSize(0), m_nMaxSize(0) {
  if (unit_size < 0 || unit_size > (1 << 28)) {
    m_nUnitSize = 4;
  } else {
    m_nUnitSize = unit_size;
  }
}
CFX_BasicArray::~CFX_BasicArray() {
  FX_Free(m_pData);
}
FX_BOOL CFX_BasicArray::SetSize(int nNewSize) {
  if (nNewSize <= 0) {
    FX_Free(m_pData);
    m_pData = NULL;
    m_nSize = m_nMaxSize = 0;
    return 0 == nNewSize;
  }

  if (!m_pData) {
    pdfium::base::CheckedNumeric<int> totalSize = nNewSize;
    totalSize *= m_nUnitSize;
    if (!totalSize.IsValid()) {
      m_nSize = m_nMaxSize = 0;
      return FALSE;
    }
    m_pData = FX_Alloc(uint8_t, totalSize.ValueOrDie());
    m_nSize = m_nMaxSize = nNewSize;
  } else if (nNewSize <= m_nMaxSize) {
    if (nNewSize > m_nSize) {
      FXSYS_memset(m_pData + m_nSize * m_nUnitSize, 0,
                   (nNewSize - m_nSize) * m_nUnitSize);
    }
    m_nSize = nNewSize;
  } else {
    int nNewMax = nNewSize < m_nMaxSize ? m_nMaxSize : nNewSize;
    pdfium::base::CheckedNumeric<int> totalSize = nNewMax;
    totalSize *= m_nUnitSize;
    if (!totalSize.IsValid() || nNewMax < m_nSize) {
      return FALSE;
    }
    uint8_t* pNewData = FX_Realloc(uint8_t, m_pData, totalSize.ValueOrDie());
    if (!pNewData) {
      return FALSE;
    }
    FXSYS_memset(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;
  pdfium::base::CheckedNumeric<int> newSize = m_nSize;
  newSize += src.m_nSize;
  if (m_nUnitSize != src.m_nUnitSize || !newSize.IsValid() ||
      !SetSize(newSize.ValueOrDie())) {
    return FALSE;
  }

  FXSYS_memcpy(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)) {
    return FALSE;
  }
  FXSYS_memcpy(m_pData, src.m_pData, src.m_nSize * m_nUnitSize);
  return TRUE;
}
uint8_t* CFX_BasicArray::InsertSpaceAt(int nIndex, int nCount) {
  if (nIndex < 0 || nCount <= 0) {
    return NULL;
  }
  if (nIndex >= m_nSize) {
    if (!SetSize(nIndex + nCount)) {
      return NULL;
    }
  } else {
    int nOldSize = m_nSize;
    if (!SetSize(m_nSize + nCount)) {
      return NULL;
    }
    FXSYS_memmove(m_pData + (nIndex + nCount) * m_nUnitSize,
                  m_pData + nIndex * m_nUnitSize,
                  (nOldSize - nIndex) * m_nUnitSize);
    FXSYS_memset(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_memmove(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) {
    return FALSE;
  }
  if (pNewArray->m_nSize == 0) {
    return TRUE;
  }
  if (!InsertSpaceAt(nStartIndex, pNewArray->m_nSize)) {
    return FALSE;
  }
  FXSYS_memcpy(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) {
    return NULL;
  }
  return m_pData + index * m_nUnitSize;
}
CFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size,
                                               int segment_units,
                                               int index_size)
    : 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(int level, int size, void** pIndex) {
  if (level == 0) {
    FX_Free(pIndex);
    return;
  }
  for (int i = 0; i < size; ++i) {
    if (pIndex[i])
      _ClearIndex(level - 1, size, (void**)pIndex[i]);
  }
  FX_Free(pIndex);
}
void CFX_BaseSegmentedArray::RemoveAll() {
  if (!m_pIndex) {
    return;
  }
  _ClearIndex(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_Alloc2D(uint8_t, m_UnitSize, m_SegmentSize);
  if (!m_pIndex) {
    m_pIndex = pSegment;
    m_DataSize++;
    return pSegment;
  }
  if (m_IndexDepth == 0) {
    void** pIndex = FX_Alloc(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 = FX_Alloc(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]) {
      pSpot[seg_index / tree_size] = FX_Alloc(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_Free(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;
  }
  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(const uint8_t* 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((const uint8_t*)pIndex, count, callback, param);
  }
  for (int i = 0; i < m_IndexSize; i++) {
    if (!pIndex[i]) {
      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) {
    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 (uint8_t*)m_pIndex + m_UnitSize * index;
  }
  int seg_index = index / m_SegmentSize;
  return (uint8_t*)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++) {
    uint8_t* pSrc = (uint8_t*)GetAt(i + count);
    uint8_t* pDest = (uint8_t*)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_Free(pIndex[i % m_IndexSize]);
        pIndex[i % m_IndexSize] = NULL;
      }
    } else {
      FX_Free(m_pIndex);
      m_pIndex = NULL;
    }
  }
  m_DataSize -= count;
}