core/src/fxcrt/fx_basic_maps.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"
#include "plex.h"

static void ConstructElement(CFX_ByteString* pNewData) {
  new (pNewData) CFX_ByteString();
}
static void DestructElement(CFX_ByteString* pOldData) {
  pOldData->~CFX_ByteString();
}
CFX_MapPtrToPtr::CFX_MapPtrToPtr(int nBlockSize)
    : m_pHashTable(NULL),
      m_nHashTableSize(17),
      m_nCount(0),
      m_pFreeList(NULL),
      m_pBlocks(NULL),
      m_nBlockSize(nBlockSize) {
  ASSERT(m_nBlockSize > 0);
}
void CFX_MapPtrToPtr::RemoveAll() {
  FX_Free(m_pHashTable);
  m_pHashTable = NULL;
  m_nCount = 0;
  m_pFreeList = NULL;
  m_pBlocks->FreeDataChain();
  m_pBlocks = NULL;
}
CFX_MapPtrToPtr::~CFX_MapPtrToPtr() {
  RemoveAll();
  ASSERT(m_nCount == 0);
}
FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const {
  return ((FX_DWORD)(uintptr_t)key) >> 4;
}
void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition,
                                   void*& rKey,
                                   void*& rValue) const {
  ASSERT(m_pHashTable != NULL);
  CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  ASSERT(pAssocRet != NULL);
  if (pAssocRet == (CAssoc*)-1) {
    for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
      if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {
        break;
      }
    ASSERT(pAssocRet != NULL);
  }
  CAssoc* pAssocNext;
  if ((pAssocNext = pAssocRet->pNext) == NULL) {
    for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1;
         nBucket < m_nHashTableSize; nBucket++) {
      if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {
        break;
      }
    }
  }
  rNextPosition = (FX_POSITION)pAssocNext;
  rKey = pAssocRet->key;
  rValue = pAssocRet->value;
}
FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const {
  FX_DWORD nHash;
  CAssoc* pAssoc = GetAssocAt(key, nHash);
  if (pAssoc == NULL) {
    return FALSE;
  }
  rValue = pAssoc->value;
  return TRUE;
}
void* CFX_MapPtrToPtr::GetValueAt(void* key) const {
  FX_DWORD nHash;
  CAssoc* pAssoc = GetAssocAt(key, nHash);
  if (pAssoc == NULL) {
    return NULL;
  }
  return pAssoc->value;
}
void*& CFX_MapPtrToPtr::operator[](void* key) {
  FX_DWORD nHash;
  CAssoc* pAssoc;
  if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {
    if (m_pHashTable == NULL) {
      InitHashTable(m_nHashTableSize);
    }
    pAssoc = NewAssoc();
    pAssoc->key = key;
    pAssoc->pNext = m_pHashTable[nHash];
    m_pHashTable[nHash] = pAssoc;
  }
  return pAssoc->value;
}
CFX_MapPtrToPtr::CAssoc* CFX_MapPtrToPtr::GetAssocAt(void* key,
                                                     FX_DWORD& nHash) const {
  nHash = HashKey(key) % m_nHashTableSize;
  if (m_pHashTable == NULL) {
    return NULL;
  }
  CAssoc* pAssoc;
  for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    if (pAssoc->key == key) {
      return pAssoc;
    }
  }
  return NULL;
}
CFX_MapPtrToPtr::CAssoc* CFX_MapPtrToPtr::NewAssoc() {
  if (m_pFreeList == NULL) {
    CFX_Plex* newBlock = CFX_Plex::Create(m_pBlocks, m_nBlockSize,
                                          sizeof(CFX_MapPtrToPtr::CAssoc));
    CFX_MapPtrToPtr::CAssoc* pAssoc =
        (CFX_MapPtrToPtr::CAssoc*)newBlock->data();
    pAssoc += m_nBlockSize - 1;
    for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {
      pAssoc->pNext = m_pFreeList;
      m_pFreeList = pAssoc;
    }
  }
  ASSERT(m_pFreeList != NULL);
  CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList;
  m_pFreeList = m_pFreeList->pNext;
  m_nCount++;
  ASSERT(m_nCount > 0);
  pAssoc->key = 0;
  pAssoc->value = 0;
  return pAssoc;
}
void CFX_MapPtrToPtr::InitHashTable(FX_DWORD nHashSize, FX_BOOL bAllocNow) {
  ASSERT(m_nCount == 0);
  ASSERT(nHashSize > 0);
  FX_Free(m_pHashTable);
  m_pHashTable = NULL;
  if (bAllocNow) {
    m_pHashTable = FX_Alloc(CAssoc*, nHashSize);
  }
  m_nHashTableSize = nHashSize;
}
FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key) {
  if (m_pHashTable == NULL) {
    return FALSE;
  }
  CAssoc** ppAssocPrev;
  ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  CAssoc* pAssoc;
  for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    if (pAssoc->key == key) {
      *ppAssocPrev = pAssoc->pNext;
      FreeAssoc(pAssoc);
      return TRUE;
    }
    ppAssocPrev = &pAssoc->pNext;
  }
  return FALSE;
}
void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc) {
  pAssoc->pNext = m_pFreeList;
  m_pFreeList = pAssoc;
  m_nCount--;
  ASSERT(m_nCount >= 0);
  if (m_nCount == 0) {
    RemoveAll();
  }
}
CFX_MapByteStringToPtr::CFX_MapByteStringToPtr(int nBlockSize)
    : m_pHashTable(NULL),
      m_nHashTableSize(17),
      m_nCount(0),
      m_pFreeList(NULL),
      m_pBlocks(NULL),
      m_nBlockSize(nBlockSize) {
  ASSERT(m_nBlockSize > 0);
}
void CFX_MapByteStringToPtr::RemoveAll() {
  if (m_pHashTable != NULL) {
    for (FX_DWORD nHash = 0; nHash < m_nHashTableSize; nHash++) {
      CAssoc* pAssoc;
      for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
           pAssoc = pAssoc->pNext) {
        DestructElement(&pAssoc->key);
      }
    }
    FX_Free(m_pHashTable);
    m_pHashTable = NULL;
  }
  m_nCount = 0;
  m_pFreeList = NULL;
  m_pBlocks->FreeDataChain();
  m_pBlocks = NULL;
}
CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr() {
  RemoveAll();
  ASSERT(m_nCount == 0);
}
void CFX_MapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition,
                                          CFX_ByteString& rKey,
                                          void*& rValue) const {
  ASSERT(m_pHashTable != NULL);
  CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  ASSERT(pAssocRet != NULL);
  if (pAssocRet == (CAssoc*)-1) {
    for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
      if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {
        break;
      }
    ASSERT(pAssocRet != NULL);
  }
  CAssoc* pAssocNext;
  if ((pAssocNext = pAssocRet->pNext) == NULL) {
    for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;
         nBucket < m_nHashTableSize; nBucket++)
      if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {
        break;
      }
  }
  rNextPosition = (FX_POSITION)pAssocNext;
  rKey = pAssocRet->key;
  rValue = pAssocRet->value;
}
void* CFX_MapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const {
  ASSERT(m_pHashTable != NULL);
  CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  ASSERT(pAssocRet != NULL);
  if (pAssocRet == (CAssoc*)-1) {
    for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
      if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {
        break;
      }
    ASSERT(pAssocRet != NULL);
  }
  CAssoc* pAssocNext;
  if ((pAssocNext = pAssocRet->pNext) == NULL) {
    for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;
         nBucket < m_nHashTableSize; nBucket++)
      if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {
        break;
      }
  }
  rNextPosition = (FX_POSITION)pAssocNext;
  return pAssocRet->value;
}
void*& CFX_MapByteStringToPtr::operator[](const CFX_ByteStringC& key) {
  FX_DWORD nHash;
  CAssoc* pAssoc;
  if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {
    if (m_pHashTable == NULL) {
      InitHashTable(m_nHashTableSize);
    }
    pAssoc = NewAssoc();
    pAssoc->nHashValue = nHash;
    pAssoc->key = key;
    pAssoc->pNext = m_pHashTable[nHash];
    m_pHashTable[nHash] = pAssoc;
  }
  return pAssoc->value;
}
CFX_MapByteStringToPtr::CAssoc* CFX_MapByteStringToPtr::NewAssoc() {
  if (m_pFreeList == NULL) {
    CFX_Plex* newBlock = CFX_Plex::Create(
        m_pBlocks, m_nBlockSize, sizeof(CFX_MapByteStringToPtr::CAssoc));
    CFX_MapByteStringToPtr::CAssoc* pAssoc =
        (CFX_MapByteStringToPtr::CAssoc*)newBlock->data();
    pAssoc += m_nBlockSize - 1;
    for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {
      pAssoc->pNext = m_pFreeList;
      m_pFreeList = pAssoc;
    }
  }
  ASSERT(m_pFreeList != NULL);
  CFX_MapByteStringToPtr::CAssoc* pAssoc = m_pFreeList;
  m_pFreeList = m_pFreeList->pNext;
  m_nCount++;
  ASSERT(m_nCount > 0);
  ConstructElement(&pAssoc->key);
  pAssoc->value = 0;
  return pAssoc;
}
void CFX_MapByteStringToPtr::FreeAssoc(CFX_MapByteStringToPtr::CAssoc* pAssoc) {
  DestructElement(&pAssoc->key);
  pAssoc->pNext = m_pFreeList;
  m_pFreeList = pAssoc;
  m_nCount--;
  ASSERT(m_nCount >= 0);
  if (m_nCount == 0) {
    RemoveAll();
  }
}
CFX_MapByteStringToPtr::CAssoc* CFX_MapByteStringToPtr::GetAssocAt(
    const CFX_ByteStringC& key,
    FX_DWORD& nHash) const {
  nHash = HashKey(key) % m_nHashTableSize;
  if (m_pHashTable == NULL) {
    return NULL;
  }
  CAssoc* pAssoc;
  for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    if (pAssoc->key == key) {
      return pAssoc;
    }
  }
  return NULL;
}
FX_BOOL CFX_MapByteStringToPtr::Lookup(const CFX_ByteStringC& key,
                                       void*& rValue) const {
  FX_DWORD nHash;
  CAssoc* pAssoc = GetAssocAt(key, nHash);
  if (pAssoc == NULL) {
    return FALSE;
  }
  rValue = pAssoc->value;
  return TRUE;
}
void CFX_MapByteStringToPtr::InitHashTable(FX_DWORD nHashSize,
                                           FX_BOOL bAllocNow) {
  ASSERT(m_nCount == 0);
  ASSERT(nHashSize > 0);
  FX_Free(m_pHashTable);
  m_pHashTable = NULL;
  if (bAllocNow) {
    m_pHashTable = FX_Alloc(CAssoc*, nHashSize);
  }
  m_nHashTableSize = nHashSize;
}
inline FX_DWORD CFX_MapByteStringToPtr::HashKey(
    const CFX_ByteStringC& key) const {
  FX_DWORD nHash = 0;
  int len = key.GetLength();
  const uint8_t* buf = key.GetPtr();
  for (int i = 0; i < len; i++) {
    nHash = (nHash << 5) + nHash + buf[i];
  }
  return nHash;
}
FX_BOOL CFX_MapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) {
  if (m_pHashTable == NULL) {
    return FALSE;
  }
  CAssoc** ppAssocPrev;
  ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  CAssoc* pAssoc;
  for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    if (pAssoc->key == key) {
      *ppAssocPrev = pAssoc->pNext;
      FreeAssoc(pAssoc);
      return TRUE;
    }
    ppAssocPrev = &pAssoc->pNext;
  }
  return FALSE;
}
struct _CompactString {
  uint8_t m_CompactLen;
  uint8_t m_LenHigh;
  uint8_t m_LenLow;
  uint8_t m_Unused;
  uint8_t* m_pBuffer;
};
static void _CompactStringRelease(_CompactString* pCompact) {
  if (pCompact->m_CompactLen == 0xff) {
    FX_Free(pCompact->m_pBuffer);
  }
}
static FX_BOOL _CompactStringSame(_CompactString* pCompact,
                                  const uint8_t* pStr,
                                  int len) {
  if (len < sizeof(_CompactString)) {
    if (pCompact->m_CompactLen != len) {
      return FALSE;
    }
    return FXSYS_memcmp(&pCompact->m_LenHigh, pStr, len) == 0;
  }
  if (pCompact->m_CompactLen != 0xff ||
      pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) {
    return FALSE;
  }
  return FXSYS_memcmp(pCompact->m_pBuffer, pStr, len) == 0;
}
static void _CompactStringStore(_CompactString* pCompact,
                                const uint8_t* pStr,
                                int len) {
  if (len < (int)sizeof(_CompactString)) {
    pCompact->m_CompactLen = (uint8_t)len;
    FXSYS_memcpy(&pCompact->m_LenHigh, pStr, len);
    return;
  }
  pCompact->m_CompactLen = 0xff;
  pCompact->m_LenHigh = len / 256;
  pCompact->m_LenLow = len % 256;
  pCompact->m_pBuffer = FX_Alloc(uint8_t, len);
  FXSYS_memcpy(pCompact->m_pBuffer, pStr, len);
}
static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact) {
  if (pCompact->m_CompactLen == 0xff) {
    return CFX_ByteStringC(pCompact->m_pBuffer,
                           pCompact->m_LenHigh * 256 + pCompact->m_LenLow);
  }
  if (pCompact->m_CompactLen == 0xfe) {
    return CFX_ByteStringC();
  }
  return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen);
}
#define CMAP_ALLOC_STEP 8
#define CMAP_INDEX_SIZE 8
CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr()
    : m_Buffer(sizeof(_CompactString) + sizeof(void*),
               CMAP_ALLOC_STEP,
               CMAP_INDEX_SIZE) {}
CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr() {
  RemoveAll();
}
void CFX_CMapByteStringToPtr::RemoveAll() {
  int size = m_Buffer.GetSize();
  for (int i = 0; i < size; i++) {
    _CompactStringRelease((_CompactString*)m_Buffer.GetAt(i));
  }
  m_Buffer.RemoveAll();
}
FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const {
  int size = m_Buffer.GetSize();
  for (int i = 0; i < size; i++) {
    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
    if (pKey->m_CompactLen != 0xfe) {
      return (FX_POSITION)(uintptr_t)(i + 1);
    }
  }
  return NULL;
}
void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition,
                                           CFX_ByteString& rKey,
                                           void*& rValue) const {
  if (rNextPosition == NULL) {
    return;
  }
  int index = (int)(uintptr_t)rNextPosition - 1;
  _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
  rKey = _CompactStringGet(pKey);
  rValue = *(void**)(pKey + 1);
  index++;
  int size = m_Buffer.GetSize();
  while (index < size) {
    pKey = (_CompactString*)m_Buffer.GetAt(index);
    if (pKey->m_CompactLen != 0xfe) {
      rNextPosition = (FX_POSITION)(uintptr_t)(index + 1);
      return;
    }
    index++;
  }
  rNextPosition = NULL;
}
void* CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const {
  if (rNextPosition == NULL) {
    return NULL;
  }
  int index = (int)(uintptr_t)rNextPosition - 1;
  _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
  void* rValue = *(void**)(pKey + 1);
  index++;
  int size = m_Buffer.GetSize();
  while (index < size) {
    pKey = (_CompactString*)m_Buffer.GetAt(index);
    if (pKey->m_CompactLen != 0xfe) {
      rNextPosition = (FX_POSITION)(uintptr_t)(index + 1);
      return rValue;
    }
    index++;
  }
  rNextPosition = NULL;
  return rValue;
}
FX_BOOL _CMapLookupCallback(void* param, void* pData) {
  return !_CompactStringSame((_CompactString*)pData,
                             ((CFX_ByteStringC*)param)->GetPtr(),
                             ((CFX_ByteStringC*)param)->GetLength());
}
FX_BOOL CFX_CMapByteStringToPtr::Lookup(const CFX_ByteStringC& key,
                                        void*& rValue) const {
  void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key);
  if (!p) {
    return FALSE;
  }
  rValue = *(void**)((_CompactString*)p + 1);
  return TRUE;
}
void CFX_CMapByteStringToPtr::SetAt(const CFX_ByteStringC& key, void* value) {
  ASSERT(value != NULL);
  int index, key_len = key.GetLength();
  int size = m_Buffer.GetSize();
  for (index = 0; index < size; index++) {
    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) {
      continue;
    }
    *(void**)(pKey + 1) = value;
    return;
  }
  for (index = 0; index < size; index++) {
    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    if (pKey->m_CompactLen) {
      continue;
    }
    _CompactStringStore(pKey, key.GetPtr(), key_len);
    *(void**)(pKey + 1) = value;
    return;
  }
  _CompactString* pKey = (_CompactString*)m_Buffer.Add();
  _CompactStringStore(pKey, key.GetPtr(), key_len);
  *(void**)(pKey + 1) = value;
}
void CFX_CMapByteStringToPtr::AddValue(const CFX_ByteStringC& key,
                                       void* value) {
  ASSERT(value != NULL);
  _CompactString* pKey = (_CompactString*)m_Buffer.Add();
  _CompactStringStore(pKey, key.GetPtr(), key.GetLength());
  *(void**)(pKey + 1) = value;
}
void CFX_CMapByteStringToPtr::RemoveKey(const CFX_ByteStringC& key) {
  int key_len = key.GetLength();
  int size = m_Buffer.GetSize();
  for (int index = 0; index < size; index++) {
    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    if (!_CompactStringSame(pKey, key.GetPtr(), key_len)) {
      continue;
    }
    _CompactStringRelease(pKey);
    pKey->m_CompactLen = 0xfe;
    return;
  }
}
int CFX_CMapByteStringToPtr::GetCount() const {
  int count = 0;
  int size = m_Buffer.GetSize();
  for (int i = 0; i < size; i++) {
    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
    if (pKey->m_CompactLen != 0xfe) {
      count++;
    }
  }
  return count;
}
extern "C" {
static int _CompareDWord(const void* p1, const void* p2) {
  return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2);
}
};
struct _DWordPair {
  FX_DWORD key;
  FX_DWORD value;
};
FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const {
  void* pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(),
                                m_Buffer.GetSize() / sizeof(_DWordPair),
                                sizeof(_DWordPair), _CompareDWord);
  if (pResult == NULL) {
    return FALSE;
  }
  value = ((FX_DWORD*)pResult)[1];
  return TRUE;
}
FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const {
  FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
  if (count == 0) {
    return NULL;
  }
  return (FX_POSITION)1;
}
void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos,
                                        FX_DWORD& key,
                                        FX_DWORD& value) const {
  if (pos == 0) {
    return;
  }
  FX_DWORD index = ((FX_DWORD)(uintptr_t)pos) - 1;
  FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
  _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();
  key = buf[index].key;
  value = buf[index].value;
  if (index == count - 1) {
    pos = 0;
  } else {
    pos = (FX_POSITION)((uintptr_t)pos + 1);
  }
}
void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value) {
  FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
  _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();
  _DWordPair pair = {key, value};
  if (count == 0 || key > buf[count - 1].key) {
    m_Buffer.AppendBlock(&pair, sizeof(_DWordPair));
    return;
  }
  int low = 0, high = count - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (buf[mid].key < key) {
      low = mid + 1;
    } else if (buf[mid].key > key) {
      high = mid - 1;
    } else {
      buf[mid].value = value;
      return;
    }
  }
  m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair));
}
void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by) {
  m_Buffer.EstimateSize(size, grow_by);
}