SEGV in CFX_BaseSegmentedArray::Iterate() when CS has malformed dictionary.
[pdfium.git] / core / src / fxcrt / fx_basic_maps.cpp
index cb397ee..8ae44ce 100644 (file)
-// Copyright 2014 PDFium Authors. All rights reserved.\r
-// Use of this source code is governed by a BSD-style license that can be\r
-// found in the LICENSE file.\r
\r
-// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com\r
-\r
-#include "../../include/fxcrt/fx_ext.h"\r
-#include "plex.h"\r
-static void ConstructElement(CFX_ByteString* pNewData)\r
-{\r
-    new (pNewData) CFX_ByteString();\r
-}\r
-static void DestructElement(CFX_ByteString* pOldData)\r
-{\r
-    pOldData->~CFX_ByteString();\r
-}\r
-CFX_MapPtrToPtr::CFX_MapPtrToPtr(int nBlockSize, IFX_Allocator* pAllocator)\r
-    : m_pAllocator(pAllocator)\r
-    , m_pHashTable(NULL)\r
-    , m_nHashTableSize(17)\r
-    , m_nCount(0)\r
-    , m_pFreeList(NULL)\r
-    , m_pBlocks(NULL)\r
-    , m_nBlockSize(nBlockSize)\r
-{\r
-    ASSERT(m_nBlockSize > 0);\r
-}\r
-void CFX_MapPtrToPtr::RemoveAll()\r
-{\r
-    if (m_pHashTable) {\r
-        FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
-        m_pHashTable = NULL;\r
-    }\r
-    m_nCount = 0;\r
-    m_pFreeList = NULL;\r
-    m_pBlocks->FreeDataChain(m_pAllocator);\r
-    m_pBlocks = NULL;\r
-}\r
-CFX_MapPtrToPtr::~CFX_MapPtrToPtr()\r
-{\r
-    RemoveAll();\r
-    ASSERT(m_nCount == 0);\r
-}\r
-FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const\r
-{\r
-    return ((FX_DWORD)(FX_UINTPTR)key) >> 4;\r
-}\r
-void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition, void*& rKey, void*& rValue) const\r
-{\r
-    ASSERT(m_pHashTable != NULL);\r
-    CAssoc* pAssocRet = (CAssoc*)rNextPosition;\r
-    ASSERT(pAssocRet != NULL);\r
-    if (pAssocRet == (CAssoc*) - 1) {\r
-        for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)\r
-            if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {\r
-                break;\r
-            }\r
-        ASSERT(pAssocRet != NULL);\r
-    }\r
-    CAssoc* pAssocNext;\r
-    if ((pAssocNext = pAssocRet->pNext) == NULL) {\r
-        for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1; nBucket < m_nHashTableSize; nBucket ++) {\r
-            if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {\r
-                break;\r
-            }\r
-        }\r
-    }\r
-    rNextPosition = (FX_POSITION) pAssocNext;\r
-    rKey = pAssocRet->key;\r
-    rValue = pAssocRet->value;\r
-}\r
-FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const\r
-{\r
-    FX_DWORD nHash;\r
-    CAssoc* pAssoc = GetAssocAt(key, nHash);\r
-    if (pAssoc == NULL) {\r
-        return FALSE;\r
-    }\r
-    rValue = pAssoc->value;\r
-    return TRUE;\r
-}\r
-void* CFX_MapPtrToPtr::GetValueAt(void* key) const\r
-{\r
-    FX_DWORD nHash;\r
-    CAssoc* pAssoc = GetAssocAt(key, nHash);\r
-    if (pAssoc == NULL) {\r
-        return NULL;\r
-    }\r
-    return pAssoc->value;\r
-}\r
-void*& CFX_MapPtrToPtr::operator[](void* key)\r
-{\r
-    FX_DWORD nHash;\r
-    CAssoc* pAssoc;\r
-    if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {\r
-        if (m_pHashTable == NULL) {\r
-            InitHashTable(m_nHashTableSize);\r
-        }\r
-        pAssoc = NewAssoc();\r
-        pAssoc->key = key;\r
-        pAssoc->pNext = m_pHashTable[nHash];\r
-        m_pHashTable[nHash] = pAssoc;\r
-    }\r
-    return pAssoc->value;\r
-}\r
-CFX_MapPtrToPtr::CAssoc*\r
-CFX_MapPtrToPtr::GetAssocAt(void* key, FX_DWORD& nHash) const\r
-{\r
-    nHash = HashKey(key) % m_nHashTableSize;\r
-    if (m_pHashTable == NULL) {\r
-        return NULL;\r
-    }\r
-    CAssoc* pAssoc;\r
-    for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
-        if (pAssoc->key == key) {\r
-            return pAssoc;\r
-        }\r
-    }\r
-    return NULL;\r
-}\r
-CFX_MapPtrToPtr::CAssoc*\r
-CFX_MapPtrToPtr::NewAssoc()\r
-{\r
-    if (m_pFreeList == NULL) {\r
-        CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapPtrToPtr::CAssoc));\r
-        CFX_MapPtrToPtr::CAssoc* pAssoc = (CFX_MapPtrToPtr::CAssoc*)newBlock->data();\r
-        pAssoc += m_nBlockSize - 1;\r
-        for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {\r
-            pAssoc->pNext = m_pFreeList;\r
-            m_pFreeList = pAssoc;\r
-        }\r
-    }\r
-    ASSERT(m_pFreeList != NULL);\r
-    CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList;\r
-    m_pFreeList = m_pFreeList->pNext;\r
-    m_nCount++;\r
-    ASSERT(m_nCount > 0);\r
-    pAssoc->key = 0;\r
-    pAssoc->value = 0;\r
-    return pAssoc;\r
-}\r
-void CFX_MapPtrToPtr::InitHashTable(\r
-    FX_DWORD nHashSize, FX_BOOL bAllocNow)\r
-{\r
-    ASSERT(m_nCount == 0);\r
-    ASSERT(nHashSize > 0);\r
-    if (m_pHashTable != NULL) {\r
-        FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
-        m_pHashTable = NULL;\r
-    }\r
-    if (bAllocNow) {\r
-        m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);\r
-        if (m_pHashTable) {\r
-            FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);\r
-        }\r
-    }\r
-    m_nHashTableSize = nHashSize;\r
-}\r
-FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key)\r
-{\r
-    if (m_pHashTable == NULL) {\r
-        return FALSE;\r
-    }\r
-    CAssoc** ppAssocPrev;\r
-    ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];\r
-    CAssoc* pAssoc;\r
-    for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
-        if (pAssoc->key == key) {\r
-            *ppAssocPrev = pAssoc->pNext;\r
-            FreeAssoc(pAssoc);\r
-            return TRUE;\r
-        }\r
-        ppAssocPrev = &pAssoc->pNext;\r
-    }\r
-    return FALSE;\r
-}\r
-void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc)\r
-{\r
-    pAssoc->pNext = m_pFreeList;\r
-    m_pFreeList = pAssoc;\r
-    m_nCount--;\r
-    ASSERT(m_nCount >= 0);\r
-    if (m_nCount == 0) {\r
-        RemoveAll();\r
-    }\r
-}\r
-CFX_MapByteStringToPtr::CFX_MapByteStringToPtr(int nBlockSize, IFX_Allocator* pAllocator)\r
-    : m_pAllocator(pAllocator)\r
-    , m_pHashTable(NULL)\r
-    , m_nHashTableSize(17)\r
-    , m_nCount(0)\r
-    , m_pFreeList(NULL)\r
-    , m_pBlocks(NULL)\r
-    , m_nBlockSize(nBlockSize)\r
-{\r
-    ASSERT(m_nBlockSize > 0);\r
-}\r
-void CFX_MapByteStringToPtr::RemoveAll()\r
-{\r
-    if (m_pHashTable != NULL) {\r
-        for (FX_DWORD nHash = 0; nHash < m_nHashTableSize; nHash++) {\r
-            CAssoc* pAssoc;\r
-            for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;\r
-                    pAssoc = pAssoc->pNext) {\r
-                DestructElement(&pAssoc->key);\r
-            }\r
-        }\r
-        FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
-        m_pHashTable = NULL;\r
-    }\r
-    m_nCount = 0;\r
-    m_pFreeList = NULL;\r
-    m_pBlocks->FreeDataChain(m_pAllocator);\r
-    m_pBlocks = NULL;\r
-}\r
-CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr()\r
-{\r
-    RemoveAll();\r
-    ASSERT(m_nCount == 0);\r
-}\r
-void CFX_MapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition,\r
-        CFX_ByteString& rKey, void*& rValue) const\r
-{\r
-    ASSERT(m_pHashTable != NULL);\r
-    CAssoc* pAssocRet = (CAssoc*)rNextPosition;\r
-    ASSERT(pAssocRet != NULL);\r
-    if (pAssocRet == (CAssoc*) - 1) {\r
-        for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)\r
-            if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {\r
-                break;\r
-            }\r
-        ASSERT(pAssocRet != NULL);\r
-    }\r
-    CAssoc* pAssocNext;\r
-    if ((pAssocNext = pAssocRet->pNext) == NULL) {\r
-        for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;\r
-                nBucket < m_nHashTableSize; nBucket++)\r
-            if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {\r
-                break;\r
-            }\r
-    }\r
-    rNextPosition = (FX_POSITION) pAssocNext;\r
-    rKey = pAssocRet->key;\r
-    rValue = pAssocRet->value;\r
-}\r
-FX_LPVOID CFX_MapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const\r
-{\r
-    ASSERT(m_pHashTable != NULL);\r
-    CAssoc* pAssocRet = (CAssoc*)rNextPosition;\r
-    ASSERT(pAssocRet != NULL);\r
-    if (pAssocRet == (CAssoc*) - 1) {\r
-        for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)\r
-            if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {\r
-                break;\r
-            }\r
-        ASSERT(pAssocRet != NULL);\r
-    }\r
-    CAssoc* pAssocNext;\r
-    if ((pAssocNext = pAssocRet->pNext) == NULL) {\r
-        for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;\r
-                nBucket < m_nHashTableSize; nBucket++)\r
-            if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {\r
-                break;\r
-            }\r
-    }\r
-    rNextPosition = (FX_POSITION) pAssocNext;\r
-    return pAssocRet->value;\r
-}\r
-void*& CFX_MapByteStringToPtr::operator[](FX_BSTR key)\r
-{\r
-    FX_DWORD nHash;\r
-    CAssoc* pAssoc;\r
-    if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {\r
-        if (m_pHashTable == NULL) {\r
-            InitHashTable(m_nHashTableSize);\r
-        }\r
-        pAssoc = NewAssoc();\r
-        pAssoc->nHashValue = nHash;\r
-        pAssoc->key = key;\r
-        pAssoc->pNext = m_pHashTable[nHash];\r
-        m_pHashTable[nHash] = pAssoc;\r
-    }\r
-    return pAssoc->value;\r
-}\r
-CFX_MapByteStringToPtr::CAssoc*\r
-CFX_MapByteStringToPtr::NewAssoc()\r
-{\r
-    if (m_pFreeList == NULL) {\r
-        CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapByteStringToPtr::CAssoc));\r
-        CFX_MapByteStringToPtr::CAssoc* pAssoc = (CFX_MapByteStringToPtr::CAssoc*)newBlock->data();\r
-        pAssoc += m_nBlockSize - 1;\r
-        for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {\r
-            pAssoc->pNext = m_pFreeList;\r
-            m_pFreeList = pAssoc;\r
-        }\r
-    }\r
-    ASSERT(m_pFreeList != NULL);\r
-    CFX_MapByteStringToPtr::CAssoc* pAssoc = m_pFreeList;\r
-    m_pFreeList = m_pFreeList->pNext;\r
-    m_nCount++;\r
-    ASSERT(m_nCount > 0);\r
-    ConstructElement(&pAssoc->key);\r
-    pAssoc->value = 0;\r
-    return pAssoc;\r
-}\r
-void CFX_MapByteStringToPtr::FreeAssoc(CFX_MapByteStringToPtr::CAssoc* pAssoc)\r
-{\r
-    DestructElement(&pAssoc->key);\r
-    pAssoc->pNext = m_pFreeList;\r
-    m_pFreeList = pAssoc;\r
-    m_nCount--;\r
-    ASSERT(m_nCount >= 0);\r
-    if (m_nCount == 0) {\r
-        RemoveAll();\r
-    }\r
-}\r
-CFX_MapByteStringToPtr::CAssoc*\r
-CFX_MapByteStringToPtr::GetAssocAt(FX_BSTR key, FX_DWORD& nHash) const\r
-{\r
-    nHash = HashKey(key) % m_nHashTableSize;\r
-    if (m_pHashTable == NULL) {\r
-        return NULL;\r
-    }\r
-    CAssoc* pAssoc;\r
-    for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
-        if (pAssoc->key == key) {\r
-            return pAssoc;\r
-        }\r
-    }\r
-    return NULL;\r
-}\r
-FX_BOOL CFX_MapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const\r
-{\r
-    FX_DWORD nHash;\r
-    CAssoc* pAssoc = GetAssocAt(key, nHash);\r
-    if (pAssoc == NULL) {\r
-        return FALSE;\r
-    }\r
-    rValue = pAssoc->value;\r
-    return TRUE;\r
-}\r
-void CFX_MapByteStringToPtr::InitHashTable(\r
-    FX_DWORD nHashSize, FX_BOOL bAllocNow)\r
-{\r
-    ASSERT(m_nCount == 0);\r
-    ASSERT(nHashSize > 0);\r
-    if (m_pHashTable != NULL) {\r
-        FX_Allocator_Free(m_pAllocator, m_pHashTable);\r
-        m_pHashTable = NULL;\r
-    }\r
-    if (bAllocNow) {\r
-        m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);\r
-        if (m_pHashTable) {\r
-            FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);\r
-        }\r
-    }\r
-    m_nHashTableSize = nHashSize;\r
-}\r
-inline FX_DWORD CFX_MapByteStringToPtr::HashKey(FX_BSTR key) const\r
-{\r
-    FX_DWORD nHash = 0;\r
-    int len = key.GetLength();\r
-    FX_LPCBYTE buf = key;\r
-    for (int i = 0; i < len; i ++) {\r
-        nHash = (nHash << 5) + nHash + buf[i];\r
-    }\r
-    return nHash;\r
-}\r
-FX_BOOL CFX_MapByteStringToPtr::RemoveKey(FX_BSTR key)\r
-{\r
-    if (m_pHashTable == NULL) {\r
-        return FALSE;\r
-    }\r
-    CAssoc** ppAssocPrev;\r
-    ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];\r
-    CAssoc* pAssoc;\r
-    for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {\r
-        if (pAssoc->key == key) {\r
-            *ppAssocPrev = pAssoc->pNext;\r
-            FreeAssoc(pAssoc);\r
-            return TRUE;\r
-        }\r
-        ppAssocPrev = &pAssoc->pNext;\r
-    }\r
-    return FALSE;\r
-}\r
-struct _CompactString {\r
-    FX_BYTE            m_CompactLen;\r
-    FX_BYTE            m_LenHigh;\r
-    FX_BYTE            m_LenLow;\r
-    FX_BYTE            m_Unused;\r
-    FX_LPBYTE  m_pBuffer;\r
-};\r
-static void _CompactStringRelease(IFX_Allocator* pAllocator, _CompactString* pCompact)\r
-{\r
-    if (pCompact->m_CompactLen == 0xff) {\r
-        FX_Allocator_Free(pAllocator, pCompact->m_pBuffer);\r
-    }\r
-}\r
-static FX_BOOL _CompactStringSame(_CompactString* pCompact, FX_LPCBYTE pStr, int len)\r
-{\r
-    if (len < sizeof(_CompactString)) {\r
-        if (pCompact->m_CompactLen != len) {\r
-            return FALSE;\r
-        }\r
-        return FXSYS_memcmp32(&pCompact->m_LenHigh, pStr, len) == 0;\r
-    }\r
-    if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) {\r
-        return FALSE;\r
-    }\r
-    return FXSYS_memcmp32(pCompact->m_pBuffer, pStr, len) == 0;\r
-}\r
-static void _CompactStringStore(IFX_Allocator* pAllocator, _CompactString* pCompact, FX_LPCBYTE pStr, int len)\r
-{\r
-    if (len < (int)sizeof(_CompactString)) {\r
-        pCompact->m_CompactLen = (FX_BYTE)len;\r
-        FXSYS_memcpy32(&pCompact->m_LenHigh, pStr, len);\r
-        return;\r
-    }\r
-    pCompact->m_CompactLen = 0xff;\r
-    pCompact->m_LenHigh = len / 256;\r
-    pCompact->m_LenLow = len % 256;\r
-    pCompact->m_pBuffer = FX_Allocator_Alloc(pAllocator, FX_BYTE, len);\r
-    if (pCompact->m_pBuffer) {\r
-        FXSYS_memcpy32(pCompact->m_pBuffer, pStr, len);\r
-    }\r
-}\r
-static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact)\r
-{\r
-    if (pCompact->m_CompactLen == 0xff) {\r
-        return CFX_ByteStringC(pCompact->m_pBuffer, pCompact->m_LenHigh * 256 + pCompact->m_LenLow);\r
-    }\r
-    if (pCompact->m_CompactLen == 0xfe) {\r
-        return CFX_ByteStringC();\r
-    }\r
-    return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen);\r
-}\r
-#define CMAP_ALLOC_STEP                8\r
-#define CMAP_INDEX_SIZE                8\r
-CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr(IFX_Allocator* pAllocator)\r
-    : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE, pAllocator)\r
-{\r
-}\r
-CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr()\r
-{\r
-    RemoveAll();\r
-}\r
-void CFX_CMapByteStringToPtr::RemoveAll()\r
-{\r
-    IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;\r
-    int size = m_Buffer.GetSize();\r
-    for (int i = 0; i < size; i ++) {\r
-        _CompactStringRelease(pAllocator, (_CompactString*)m_Buffer.GetAt(i));\r
-    }\r
-    m_Buffer.RemoveAll();\r
-}\r
-FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const\r
-{\r
-    int size = m_Buffer.GetSize();\r
-    for (int i = 0; i < size; i ++) {\r
-        _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);\r
-        if (pKey->m_CompactLen != 0xfe) {\r
-            return (FX_POSITION)(FX_UINTPTR)(i + 1);\r
-        }\r
-    }\r
-    return NULL;\r
-}\r
-void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const\r
-{\r
-    if (rNextPosition == NULL) {\r
-        return;\r
-    }\r
-    int index = (int)(FX_UINTPTR)rNextPosition - 1;\r
-    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
-    rKey = _CompactStringGet(pKey);\r
-    rValue = *(void**)(pKey + 1);\r
-    index ++;\r
-    int size = m_Buffer.GetSize();\r
-    while (index < size) {\r
-        pKey = (_CompactString*)m_Buffer.GetAt(index);\r
-        if (pKey->m_CompactLen != 0xfe) {\r
-            rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);\r
-            return;\r
-        }\r
-        index ++;\r
-    }\r
-    rNextPosition = NULL;\r
-}\r
-FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const\r
-{\r
-    if (rNextPosition == NULL) {\r
-        return NULL;\r
-    }\r
-    int index = (int)(FX_UINTPTR)rNextPosition - 1;\r
-    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
-    FX_LPVOID rValue = *(void**)(pKey + 1);\r
-    index ++;\r
-    int size = m_Buffer.GetSize();\r
-    while (index < size) {\r
-        pKey = (_CompactString*)m_Buffer.GetAt(index);\r
-        if (pKey->m_CompactLen != 0xfe) {\r
-            rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);\r
-            return rValue;\r
-        }\r
-        index ++;\r
-    }\r
-    rNextPosition = NULL;\r
-    return rValue;\r
-}\r
-FX_BOOL _CMapLookupCallback(void* param, void* pData)\r
-{\r
-    return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength());\r
-}\r
-FX_BOOL CFX_CMapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const\r
-{\r
-    void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key);\r
-    if (!p) {\r
-        return FALSE;\r
-    }\r
-    rValue = *(void**)((_CompactString*)p + 1);\r
-    return TRUE;\r
-}\r
-void CFX_CMapByteStringToPtr::SetAt(FX_BSTR key, void* value)\r
-{\r
-    ASSERT(value != NULL);\r
-    int index, key_len = key.GetLength();\r
-    int size = m_Buffer.GetSize();\r
-    for (index = 0; index < size; index ++) {\r
-        _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
-        if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {\r
-            continue;\r
-        }\r
-        *(void**)(pKey + 1) = value;\r
-        return;\r
-    }\r
-    IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;\r
-    for (index = 0; index < size; index ++) {\r
-        _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
-        if (pKey->m_CompactLen) {\r
-            continue;\r
-        }\r
-        _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);\r
-        *(void**)(pKey + 1) = value;\r
-        return;\r
-    }\r
-    _CompactString* pKey = (_CompactString*)m_Buffer.Add();\r
-    _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);\r
-    *(void**)(pKey + 1) = value;\r
-}\r
-void CFX_CMapByteStringToPtr::AddValue(FX_BSTR key, void* value)\r
-{\r
-    ASSERT(value != NULL);\r
-    _CompactString* pKey = (_CompactString*)m_Buffer.Add();\r
-    _CompactStringStore(m_Buffer.m_pAllocator, pKey, (FX_LPCBYTE)key, key.GetLength());\r
-    *(void**)(pKey + 1) = value;\r
-}\r
-void CFX_CMapByteStringToPtr::RemoveKey(FX_BSTR key)\r
-{\r
-    int key_len = key.GetLength();\r
-    IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;\r
-    int size = m_Buffer.GetSize();\r
-    for (int index = 0; index < size; index ++) {\r
-        _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);\r
-        if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {\r
-            continue;\r
-        }\r
-        _CompactStringRelease(pAllocator, pKey);\r
-        pKey->m_CompactLen = 0xfe;\r
-        return;\r
-    }\r
-}\r
-int CFX_CMapByteStringToPtr::GetCount() const\r
-{\r
-    int count = 0;\r
-    int size = m_Buffer.GetSize();\r
-    for (int i = 0; i < size; i ++) {\r
-        _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);\r
-        if (pKey->m_CompactLen != 0xfe) {\r
-            count ++;\r
-        }\r
-    }\r
-    return count;\r
-}\r
-extern "C" {\r
-    static int _CompareDWord(const void* p1, const void* p2)\r
-    {\r
-        return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2);\r
-    }\r
-};\r
-struct _DWordPair {\r
-    FX_DWORD key;\r
-    FX_DWORD value;\r
-};\r
-FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const\r
-{\r
-    FX_LPVOID pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize() / sizeof(_DWordPair),\r
-                                      sizeof(_DWordPair), _CompareDWord);\r
-    if (pResult == NULL) {\r
-        return FALSE;\r
-    }\r
-    value = ((FX_DWORD*)pResult)[1];\r
-    return TRUE;\r
-}\r
-FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const\r
-{\r
-    FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);\r
-    if (count == 0) {\r
-        return NULL;\r
-    }\r
-    return (FX_POSITION)1;\r
-}\r
-void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const\r
-{\r
-    if (pos == 0) {\r
-        return;\r
-    }\r
-    FX_DWORD index = ((FX_DWORD)(FX_UINTPTR)pos) - 1;\r
-    FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);\r
-    _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();\r
-    key = buf[index].key;\r
-    value = buf[index].value;\r
-    if (index == count - 1) {\r
-        pos = 0;\r
-    } else {\r
-        pos = (FX_POSITION)((FX_UINTPTR)pos + 1);\r
-    }\r
-}\r
-void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value)\r
-{\r
-    FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);\r
-    _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();\r
-    _DWordPair pair = {key, value};\r
-    if (count == 0 || key > buf[count - 1].key) {\r
-        m_Buffer.AppendBlock(&pair, sizeof(_DWordPair));\r
-        return;\r
-    }\r
-    int low = 0, high = count - 1;\r
-    while (low <= high) {\r
-        int mid = (low + high) / 2;\r
-        if (buf[mid].key < key) {\r
-            low = mid + 1;\r
-        } else if (buf[mid].key > key) {\r
-            high = mid - 1;\r
-        } else {\r
-            buf[mid].value = value;\r
-            return;\r
-        }\r
-    }\r
-    m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair));\r
-}\r
-void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by)\r
-{\r
-    m_Buffer.EstimateSize(size, grow_by);\r
-}\r
+// 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_ext.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()
+{
+    if (m_pHashTable) {
+        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)(FX_UINTPTR)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);
+    if (m_pHashTable != NULL) {
+        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;
+}
+FX_LPVOID 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[](FX_BSTR 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(FX_BSTR 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(FX_BSTR 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);
+    if (m_pHashTable != NULL) {
+        FX_Free(m_pHashTable);
+        m_pHashTable = NULL;
+    }
+    if (bAllocNow) {
+        m_pHashTable = FX_Alloc(CAssoc*, nHashSize);
+    }
+    m_nHashTableSize = nHashSize;
+}
+inline FX_DWORD CFX_MapByteStringToPtr::HashKey(FX_BSTR key) const
+{
+    FX_DWORD nHash = 0;
+    int len = key.GetLength();
+    FX_LPCBYTE buf = key.GetPtr();
+    for (int i = 0; i < len; i ++) {
+        nHash = (nHash << 5) + nHash + buf[i];
+    }
+    return nHash;
+}
+FX_BOOL CFX_MapByteStringToPtr::RemoveKey(FX_BSTR 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 {
+    FX_BYTE            m_CompactLen;
+    FX_BYTE            m_LenHigh;
+    FX_BYTE            m_LenLow;
+    FX_BYTE            m_Unused;
+    FX_LPBYTE  m_pBuffer;
+};
+static void _CompactStringRelease(_CompactString* pCompact)
+{
+    if (pCompact->m_CompactLen == 0xff) {
+        FX_Free(pCompact->m_pBuffer);
+    }
+}
+static FX_BOOL _CompactStringSame(_CompactString* pCompact, FX_LPCBYTE pStr, int len)
+{
+    if (len < sizeof(_CompactString)) {
+        if (pCompact->m_CompactLen != len) {
+            return FALSE;
+        }
+        return FXSYS_memcmp32(&pCompact->m_LenHigh, pStr, len) == 0;
+    }
+    if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) {
+        return FALSE;
+    }
+    return FXSYS_memcmp32(pCompact->m_pBuffer, pStr, len) == 0;
+}
+static void _CompactStringStore(_CompactString* pCompact, FX_LPCBYTE pStr, int len)
+{
+    if (len < (int)sizeof(_CompactString)) {
+        pCompact->m_CompactLen = (FX_BYTE)len;
+        FXSYS_memcpy32(&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(FX_BYTE, len);
+    if (pCompact->m_pBuffer) {
+        FXSYS_memcpy32(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)(FX_UINTPTR)(i + 1);
+        }
+    }
+    return NULL;
+}
+void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const
+{
+    if (rNextPosition == NULL) {
+        return;
+    }
+    int index = (int)(FX_UINTPTR)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)(FX_UINTPTR)(index + 1);
+            return;
+        }
+        index ++;
+    }
+    rNextPosition = NULL;
+}
+FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const
+{
+    if (rNextPosition == NULL) {
+        return NULL;
+    }
+    int index = (int)(FX_UINTPTR)rNextPosition - 1;
+    _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
+    FX_LPVOID 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)(FX_UINTPTR)(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(FX_BSTR 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(FX_BSTR 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(FX_BSTR 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(FX_BSTR 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
+{
+    FX_LPVOID 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)(FX_UINTPTR)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)((FX_UINTPTR)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);
+}