Home | History | Annotate | Download | only in fxcrt 
      1 // Copyright 2014 PDFium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
      6 
      7 #include "../../include/fxcrt/fx_ext.h"
      8 #include "plex.h"
      9 static void ConstructElement(CFX_ByteString* pNewData)
     10 {
     11     new (pNewData) CFX_ByteString();
     12 }
     13 static void DestructElement(CFX_ByteString* pOldData)
     14 {
     15     pOldData->~CFX_ByteString();
     16 }
     17 CFX_MapPtrToPtr::CFX_MapPtrToPtr(int nBlockSize, IFX_Allocator* pAllocator)
     18     : m_pAllocator(pAllocator)
     19     , m_pHashTable(NULL)
     20     , m_nHashTableSize(17)
     21     , m_nCount(0)
     22     , m_pFreeList(NULL)
     23     , m_pBlocks(NULL)
     24     , m_nBlockSize(nBlockSize)
     25 {
     26     ASSERT(m_nBlockSize > 0);
     27 }
     28 void CFX_MapPtrToPtr::RemoveAll()
     29 {
     30     if (m_pHashTable) {
     31         FX_Allocator_Free(m_pAllocator, m_pHashTable);
     32         m_pHashTable = NULL;
     33     }
     34     m_nCount = 0;
     35     m_pFreeList = NULL;
     36     m_pBlocks->FreeDataChain(m_pAllocator);
     37     m_pBlocks = NULL;
     38 }
     39 CFX_MapPtrToPtr::~CFX_MapPtrToPtr()
     40 {
     41     RemoveAll();
     42     ASSERT(m_nCount == 0);
     43 }
     44 FX_DWORD CFX_MapPtrToPtr::HashKey(void* key) const
     45 {
     46     return ((FX_DWORD)(FX_UINTPTR)key) >> 4;
     47 }
     48 void CFX_MapPtrToPtr::GetNextAssoc(FX_POSITION& rNextPosition, void*& rKey, void*& rValue) const
     49 {
     50     ASSERT(m_pHashTable != NULL);
     51     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
     52     ASSERT(pAssocRet != NULL);
     53     if (pAssocRet == (CAssoc*) - 1) {
     54         for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
     55             if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {
     56                 break;
     57             }
     58         ASSERT(pAssocRet != NULL);
     59     }
     60     CAssoc* pAssocNext;
     61     if ((pAssocNext = pAssocRet->pNext) == NULL) {
     62         for (FX_DWORD nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1; nBucket < m_nHashTableSize; nBucket ++) {
     63             if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {
     64                 break;
     65             }
     66         }
     67     }
     68     rNextPosition = (FX_POSITION) pAssocNext;
     69     rKey = pAssocRet->key;
     70     rValue = pAssocRet->value;
     71 }
     72 FX_BOOL CFX_MapPtrToPtr::Lookup(void* key, void*& rValue) const
     73 {
     74     FX_DWORD nHash;
     75     CAssoc* pAssoc = GetAssocAt(key, nHash);
     76     if (pAssoc == NULL) {
     77         return FALSE;
     78     }
     79     rValue = pAssoc->value;
     80     return TRUE;
     81 }
     82 void* CFX_MapPtrToPtr::GetValueAt(void* key) const
     83 {
     84     FX_DWORD nHash;
     85     CAssoc* pAssoc = GetAssocAt(key, nHash);
     86     if (pAssoc == NULL) {
     87         return NULL;
     88     }
     89     return pAssoc->value;
     90 }
     91 void*& CFX_MapPtrToPtr::operator[](void* key)
     92 {
     93     FX_DWORD nHash;
     94     CAssoc* pAssoc;
     95     if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {
     96         if (m_pHashTable == NULL) {
     97             InitHashTable(m_nHashTableSize);
     98         }
     99         pAssoc = NewAssoc();
    100         pAssoc->key = key;
    101         pAssoc->pNext = m_pHashTable[nHash];
    102         m_pHashTable[nHash] = pAssoc;
    103     }
    104     return pAssoc->value;
    105 }
    106 CFX_MapPtrToPtr::CAssoc*
    107 CFX_MapPtrToPtr::GetAssocAt(void* key, FX_DWORD& nHash) const
    108 {
    109     nHash = HashKey(key) % m_nHashTableSize;
    110     if (m_pHashTable == NULL) {
    111         return NULL;
    112     }
    113     CAssoc* pAssoc;
    114     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    115         if (pAssoc->key == key) {
    116             return pAssoc;
    117         }
    118     }
    119     return NULL;
    120 }
    121 CFX_MapPtrToPtr::CAssoc*
    122 CFX_MapPtrToPtr::NewAssoc()
    123 {
    124     if (m_pFreeList == NULL) {
    125         CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapPtrToPtr::CAssoc));
    126         CFX_MapPtrToPtr::CAssoc* pAssoc = (CFX_MapPtrToPtr::CAssoc*)newBlock->data();
    127         pAssoc += m_nBlockSize - 1;
    128         for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {
    129             pAssoc->pNext = m_pFreeList;
    130             m_pFreeList = pAssoc;
    131         }
    132     }
    133     ASSERT(m_pFreeList != NULL);
    134     CFX_MapPtrToPtr::CAssoc* pAssoc = m_pFreeList;
    135     m_pFreeList = m_pFreeList->pNext;
    136     m_nCount++;
    137     ASSERT(m_nCount > 0);
    138     pAssoc->key = 0;
    139     pAssoc->value = 0;
    140     return pAssoc;
    141 }
    142 void CFX_MapPtrToPtr::InitHashTable(
    143     FX_DWORD nHashSize, FX_BOOL bAllocNow)
    144 {
    145     ASSERT(m_nCount == 0);
    146     ASSERT(nHashSize > 0);
    147     if (m_pHashTable != NULL) {
    148         FX_Allocator_Free(m_pAllocator, m_pHashTable);
    149         m_pHashTable = NULL;
    150     }
    151     if (bAllocNow) {
    152         m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);
    153         if (m_pHashTable) {
    154             FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
    155         }
    156     }
    157     m_nHashTableSize = nHashSize;
    158 }
    159 FX_BOOL CFX_MapPtrToPtr::RemoveKey(void* key)
    160 {
    161     if (m_pHashTable == NULL) {
    162         return FALSE;
    163     }
    164     CAssoc** ppAssocPrev;
    165     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
    166     CAssoc* pAssoc;
    167     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    168         if (pAssoc->key == key) {
    169             *ppAssocPrev = pAssoc->pNext;
    170             FreeAssoc(pAssoc);
    171             return TRUE;
    172         }
    173         ppAssocPrev = &pAssoc->pNext;
    174     }
    175     return FALSE;
    176 }
    177 void CFX_MapPtrToPtr::FreeAssoc(CFX_MapPtrToPtr::CAssoc* pAssoc)
    178 {
    179     pAssoc->pNext = m_pFreeList;
    180     m_pFreeList = pAssoc;
    181     m_nCount--;
    182     ASSERT(m_nCount >= 0);
    183     if (m_nCount == 0) {
    184         RemoveAll();
    185     }
    186 }
    187 CFX_MapByteStringToPtr::CFX_MapByteStringToPtr(int nBlockSize, IFX_Allocator* pAllocator)
    188     : m_pAllocator(pAllocator)
    189     , m_pHashTable(NULL)
    190     , m_nHashTableSize(17)
    191     , m_nCount(0)
    192     , m_pFreeList(NULL)
    193     , m_pBlocks(NULL)
    194     , m_nBlockSize(nBlockSize)
    195 {
    196     ASSERT(m_nBlockSize > 0);
    197 }
    198 void CFX_MapByteStringToPtr::RemoveAll()
    199 {
    200     if (m_pHashTable != NULL) {
    201         for (FX_DWORD nHash = 0; nHash < m_nHashTableSize; nHash++) {
    202             CAssoc* pAssoc;
    203             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
    204                     pAssoc = pAssoc->pNext) {
    205                 DestructElement(&pAssoc->key);
    206             }
    207         }
    208         FX_Allocator_Free(m_pAllocator, m_pHashTable);
    209         m_pHashTable = NULL;
    210     }
    211     m_nCount = 0;
    212     m_pFreeList = NULL;
    213     m_pBlocks->FreeDataChain(m_pAllocator);
    214     m_pBlocks = NULL;
    215 }
    216 CFX_MapByteStringToPtr::~CFX_MapByteStringToPtr()
    217 {
    218     RemoveAll();
    219     ASSERT(m_nCount == 0);
    220 }
    221 void CFX_MapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition,
    222         CFX_ByteString& rKey, void*& rValue) const
    223 {
    224     ASSERT(m_pHashTable != NULL);
    225     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
    226     ASSERT(pAssocRet != NULL);
    227     if (pAssocRet == (CAssoc*) - 1) {
    228         for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
    229             if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {
    230                 break;
    231             }
    232         ASSERT(pAssocRet != NULL);
    233     }
    234     CAssoc* pAssocNext;
    235     if ((pAssocNext = pAssocRet->pNext) == NULL) {
    236         for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;
    237                 nBucket < m_nHashTableSize; nBucket++)
    238             if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {
    239                 break;
    240             }
    241     }
    242     rNextPosition = (FX_POSITION) pAssocNext;
    243     rKey = pAssocRet->key;
    244     rValue = pAssocRet->value;
    245 }
    246 FX_LPVOID CFX_MapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const
    247 {
    248     ASSERT(m_pHashTable != NULL);
    249     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
    250     ASSERT(pAssocRet != NULL);
    251     if (pAssocRet == (CAssoc*) - 1) {
    252         for (FX_DWORD nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
    253             if ((pAssocRet = m_pHashTable[nBucket]) != NULL) {
    254                 break;
    255             }
    256         ASSERT(pAssocRet != NULL);
    257     }
    258     CAssoc* pAssocNext;
    259     if ((pAssocNext = pAssocRet->pNext) == NULL) {
    260         for (FX_DWORD nBucket = pAssocRet->nHashValue + 1;
    261                 nBucket < m_nHashTableSize; nBucket++)
    262             if ((pAssocNext = m_pHashTable[nBucket]) != NULL) {
    263                 break;
    264             }
    265     }
    266     rNextPosition = (FX_POSITION) pAssocNext;
    267     return pAssocRet->value;
    268 }
    269 void*& CFX_MapByteStringToPtr::operator[](FX_BSTR key)
    270 {
    271     FX_DWORD nHash;
    272     CAssoc* pAssoc;
    273     if ((pAssoc = GetAssocAt(key, nHash)) == NULL) {
    274         if (m_pHashTable == NULL) {
    275             InitHashTable(m_nHashTableSize);
    276         }
    277         pAssoc = NewAssoc();
    278         pAssoc->nHashValue = nHash;
    279         pAssoc->key = key;
    280         pAssoc->pNext = m_pHashTable[nHash];
    281         m_pHashTable[nHash] = pAssoc;
    282     }
    283     return pAssoc->value;
    284 }
    285 CFX_MapByteStringToPtr::CAssoc*
    286 CFX_MapByteStringToPtr::NewAssoc()
    287 {
    288     if (m_pFreeList == NULL) {
    289         CFX_Plex* newBlock = CFX_Plex::Create(m_pAllocator, m_pBlocks, m_nBlockSize, sizeof(CFX_MapByteStringToPtr::CAssoc));
    290         CFX_MapByteStringToPtr::CAssoc* pAssoc = (CFX_MapByteStringToPtr::CAssoc*)newBlock->data();
    291         pAssoc += m_nBlockSize - 1;
    292         for (int i = m_nBlockSize - 1; i >= 0; i--, pAssoc--) {
    293             pAssoc->pNext = m_pFreeList;
    294             m_pFreeList = pAssoc;
    295         }
    296     }
    297     ASSERT(m_pFreeList != NULL);
    298     CFX_MapByteStringToPtr::CAssoc* pAssoc = m_pFreeList;
    299     m_pFreeList = m_pFreeList->pNext;
    300     m_nCount++;
    301     ASSERT(m_nCount > 0);
    302     ConstructElement(&pAssoc->key);
    303     pAssoc->value = 0;
    304     return pAssoc;
    305 }
    306 void CFX_MapByteStringToPtr::FreeAssoc(CFX_MapByteStringToPtr::CAssoc* pAssoc)
    307 {
    308     DestructElement(&pAssoc->key);
    309     pAssoc->pNext = m_pFreeList;
    310     m_pFreeList = pAssoc;
    311     m_nCount--;
    312     ASSERT(m_nCount >= 0);
    313     if (m_nCount == 0) {
    314         RemoveAll();
    315     }
    316 }
    317 CFX_MapByteStringToPtr::CAssoc*
    318 CFX_MapByteStringToPtr::GetAssocAt(FX_BSTR key, FX_DWORD& nHash) const
    319 {
    320     nHash = HashKey(key) % m_nHashTableSize;
    321     if (m_pHashTable == NULL) {
    322         return NULL;
    323     }
    324     CAssoc* pAssoc;
    325     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    326         if (pAssoc->key == key) {
    327             return pAssoc;
    328         }
    329     }
    330     return NULL;
    331 }
    332 FX_BOOL CFX_MapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const
    333 {
    334     FX_DWORD nHash;
    335     CAssoc* pAssoc = GetAssocAt(key, nHash);
    336     if (pAssoc == NULL) {
    337         return FALSE;
    338     }
    339     rValue = pAssoc->value;
    340     return TRUE;
    341 }
    342 void CFX_MapByteStringToPtr::InitHashTable(
    343     FX_DWORD nHashSize, FX_BOOL bAllocNow)
    344 {
    345     ASSERT(m_nCount == 0);
    346     ASSERT(nHashSize > 0);
    347     if (m_pHashTable != NULL) {
    348         FX_Allocator_Free(m_pAllocator, m_pHashTable);
    349         m_pHashTable = NULL;
    350     }
    351     if (bAllocNow) {
    352         m_pHashTable = FX_Allocator_Alloc(m_pAllocator, CAssoc*, nHashSize);
    353         if (m_pHashTable) {
    354             FXSYS_memset32(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
    355         }
    356     }
    357     m_nHashTableSize = nHashSize;
    358 }
    359 inline FX_DWORD CFX_MapByteStringToPtr::HashKey(FX_BSTR key) const
    360 {
    361     FX_DWORD nHash = 0;
    362     int len = key.GetLength();
    363     FX_LPCBYTE buf = key;
    364     for (int i = 0; i < len; i ++) {
    365         nHash = (nHash << 5) + nHash + buf[i];
    366     }
    367     return nHash;
    368 }
    369 FX_BOOL CFX_MapByteStringToPtr::RemoveKey(FX_BSTR key)
    370 {
    371     if (m_pHashTable == NULL) {
    372         return FALSE;
    373     }
    374     CAssoc** ppAssocPrev;
    375     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
    376     CAssoc* pAssoc;
    377     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) {
    378         if (pAssoc->key == key) {
    379             *ppAssocPrev = pAssoc->pNext;
    380             FreeAssoc(pAssoc);
    381             return TRUE;
    382         }
    383         ppAssocPrev = &pAssoc->pNext;
    384     }
    385     return FALSE;
    386 }
    387 struct _CompactString {
    388     FX_BYTE		m_CompactLen;
    389     FX_BYTE		m_LenHigh;
    390     FX_BYTE		m_LenLow;
    391     FX_BYTE		m_Unused;
    392     FX_LPBYTE	m_pBuffer;
    393 };
    394 static void _CompactStringRelease(IFX_Allocator* pAllocator, _CompactString* pCompact)
    395 {
    396     if (pCompact->m_CompactLen == 0xff) {
    397         FX_Allocator_Free(pAllocator, pCompact->m_pBuffer);
    398     }
    399 }
    400 static FX_BOOL _CompactStringSame(_CompactString* pCompact, FX_LPCBYTE pStr, int len)
    401 {
    402     if (len < sizeof(_CompactString)) {
    403         if (pCompact->m_CompactLen != len) {
    404             return FALSE;
    405         }
    406         return FXSYS_memcmp32(&pCompact->m_LenHigh, pStr, len) == 0;
    407     }
    408     if (pCompact->m_CompactLen != 0xff || pCompact->m_LenHigh * 256 + pCompact->m_LenLow != len) {
    409         return FALSE;
    410     }
    411     return FXSYS_memcmp32(pCompact->m_pBuffer, pStr, len) == 0;
    412 }
    413 static void _CompactStringStore(IFX_Allocator* pAllocator, _CompactString* pCompact, FX_LPCBYTE pStr, int len)
    414 {
    415     if (len < (int)sizeof(_CompactString)) {
    416         pCompact->m_CompactLen = (FX_BYTE)len;
    417         FXSYS_memcpy32(&pCompact->m_LenHigh, pStr, len);
    418         return;
    419     }
    420     pCompact->m_CompactLen = 0xff;
    421     pCompact->m_LenHigh = len / 256;
    422     pCompact->m_LenLow = len % 256;
    423     pCompact->m_pBuffer = FX_Allocator_Alloc(pAllocator, FX_BYTE, len);
    424     if (pCompact->m_pBuffer) {
    425         FXSYS_memcpy32(pCompact->m_pBuffer, pStr, len);
    426     }
    427 }
    428 static CFX_ByteStringC _CompactStringGet(_CompactString* pCompact)
    429 {
    430     if (pCompact->m_CompactLen == 0xff) {
    431         return CFX_ByteStringC(pCompact->m_pBuffer, pCompact->m_LenHigh * 256 + pCompact->m_LenLow);
    432     }
    433     if (pCompact->m_CompactLen == 0xfe) {
    434         return CFX_ByteStringC();
    435     }
    436     return CFX_ByteStringC(&pCompact->m_LenHigh, pCompact->m_CompactLen);
    437 }
    438 #define CMAP_ALLOC_STEP		8
    439 #define CMAP_INDEX_SIZE		8
    440 CFX_CMapByteStringToPtr::CFX_CMapByteStringToPtr(IFX_Allocator* pAllocator)
    441     : m_Buffer(sizeof(_CompactString) + sizeof(void*), CMAP_ALLOC_STEP, CMAP_INDEX_SIZE, pAllocator)
    442 {
    443 }
    444 CFX_CMapByteStringToPtr::~CFX_CMapByteStringToPtr()
    445 {
    446     RemoveAll();
    447 }
    448 void CFX_CMapByteStringToPtr::RemoveAll()
    449 {
    450     IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;
    451     int size = m_Buffer.GetSize();
    452     for (int i = 0; i < size; i ++) {
    453         _CompactStringRelease(pAllocator, (_CompactString*)m_Buffer.GetAt(i));
    454     }
    455     m_Buffer.RemoveAll();
    456 }
    457 FX_POSITION CFX_CMapByteStringToPtr::GetStartPosition() const
    458 {
    459     int size = m_Buffer.GetSize();
    460     for (int i = 0; i < size; i ++) {
    461         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
    462         if (pKey->m_CompactLen != 0xfe) {
    463             return (FX_POSITION)(FX_UINTPTR)(i + 1);
    464         }
    465     }
    466     return NULL;
    467 }
    468 void CFX_CMapByteStringToPtr::GetNextAssoc(FX_POSITION& rNextPosition, CFX_ByteString& rKey, void*& rValue) const
    469 {
    470     if (rNextPosition == NULL) {
    471         return;
    472     }
    473     int index = (int)(FX_UINTPTR)rNextPosition - 1;
    474     _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    475     rKey = _CompactStringGet(pKey);
    476     rValue = *(void**)(pKey + 1);
    477     index ++;
    478     int size = m_Buffer.GetSize();
    479     while (index < size) {
    480         pKey = (_CompactString*)m_Buffer.GetAt(index);
    481         if (pKey->m_CompactLen != 0xfe) {
    482             rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);
    483             return;
    484         }
    485         index ++;
    486     }
    487     rNextPosition = NULL;
    488 }
    489 FX_LPVOID CFX_CMapByteStringToPtr::GetNextValue(FX_POSITION& rNextPosition) const
    490 {
    491     if (rNextPosition == NULL) {
    492         return NULL;
    493     }
    494     int index = (int)(FX_UINTPTR)rNextPosition - 1;
    495     _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    496     FX_LPVOID rValue = *(void**)(pKey + 1);
    497     index ++;
    498     int size = m_Buffer.GetSize();
    499     while (index < size) {
    500         pKey = (_CompactString*)m_Buffer.GetAt(index);
    501         if (pKey->m_CompactLen != 0xfe) {
    502             rNextPosition = (FX_POSITION)(FX_UINTPTR)(index + 1);
    503             return rValue;
    504         }
    505         index ++;
    506     }
    507     rNextPosition = NULL;
    508     return rValue;
    509 }
    510 FX_BOOL _CMapLookupCallback(void* param, void* pData)
    511 {
    512     return !_CompactStringSame((_CompactString*)pData, ((CFX_ByteStringC*)param)->GetPtr(), ((CFX_ByteStringC*)param)->GetLength());
    513 }
    514 FX_BOOL CFX_CMapByteStringToPtr::Lookup(FX_BSTR key, void*& rValue) const
    515 {
    516     void* p = m_Buffer.Iterate(_CMapLookupCallback, (void*)&key);
    517     if (!p) {
    518         return FALSE;
    519     }
    520     rValue = *(void**)((_CompactString*)p + 1);
    521     return TRUE;
    522 }
    523 void CFX_CMapByteStringToPtr::SetAt(FX_BSTR key, void* value)
    524 {
    525     ASSERT(value != NULL);
    526     int index, key_len = key.GetLength();
    527     int size = m_Buffer.GetSize();
    528     for (index = 0; index < size; index ++) {
    529         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    530         if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {
    531             continue;
    532         }
    533         *(void**)(pKey + 1) = value;
    534         return;
    535     }
    536     IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;
    537     for (index = 0; index < size; index ++) {
    538         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    539         if (pKey->m_CompactLen) {
    540             continue;
    541         }
    542         _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);
    543         *(void**)(pKey + 1) = value;
    544         return;
    545     }
    546     _CompactString* pKey = (_CompactString*)m_Buffer.Add();
    547     _CompactStringStore(pAllocator, pKey, (FX_LPCBYTE)key, key_len);
    548     *(void**)(pKey + 1) = value;
    549 }
    550 void CFX_CMapByteStringToPtr::AddValue(FX_BSTR key, void* value)
    551 {
    552     ASSERT(value != NULL);
    553     _CompactString* pKey = (_CompactString*)m_Buffer.Add();
    554     _CompactStringStore(m_Buffer.m_pAllocator, pKey, (FX_LPCBYTE)key, key.GetLength());
    555     *(void**)(pKey + 1) = value;
    556 }
    557 void CFX_CMapByteStringToPtr::RemoveKey(FX_BSTR key)
    558 {
    559     int key_len = key.GetLength();
    560     IFX_Allocator* pAllocator = m_Buffer.m_pAllocator;
    561     int size = m_Buffer.GetSize();
    562     for (int index = 0; index < size; index ++) {
    563         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(index);
    564         if (!_CompactStringSame(pKey, (FX_LPCBYTE)key, key_len)) {
    565             continue;
    566         }
    567         _CompactStringRelease(pAllocator, pKey);
    568         pKey->m_CompactLen = 0xfe;
    569         return;
    570     }
    571 }
    572 int CFX_CMapByteStringToPtr::GetCount() const
    573 {
    574     int count = 0;
    575     int size = m_Buffer.GetSize();
    576     for (int i = 0; i < size; i ++) {
    577         _CompactString* pKey = (_CompactString*)m_Buffer.GetAt(i);
    578         if (pKey->m_CompactLen != 0xfe) {
    579             count ++;
    580         }
    581     }
    582     return count;
    583 }
    584 extern "C" {
    585     static int _CompareDWord(const void* p1, const void* p2)
    586     {
    587         return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2);
    588     }
    589 };
    590 struct _DWordPair {
    591     FX_DWORD key;
    592     FX_DWORD value;
    593 };
    594 FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const
    595 {
    596     FX_LPVOID pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), m_Buffer.GetSize() / sizeof(_DWordPair),
    597                                       sizeof(_DWordPair), _CompareDWord);
    598     if (pResult == NULL) {
    599         return FALSE;
    600     }
    601     value = ((FX_DWORD*)pResult)[1];
    602     return TRUE;
    603 }
    604 FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const
    605 {
    606     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
    607     if (count == 0) {
    608         return NULL;
    609     }
    610     return (FX_POSITION)1;
    611 }
    612 void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const
    613 {
    614     if (pos == 0) {
    615         return;
    616     }
    617     FX_DWORD index = ((FX_DWORD)(FX_UINTPTR)pos) - 1;
    618     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
    619     _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();
    620     key = buf[index].key;
    621     value = buf[index].value;
    622     if (index == count - 1) {
    623         pos = 0;
    624     } else {
    625         pos = (FX_POSITION)((FX_UINTPTR)pos + 1);
    626     }
    627 }
    628 void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value)
    629 {
    630     FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair);
    631     _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer();
    632     _DWordPair pair = {key, value};
    633     if (count == 0 || key > buf[count - 1].key) {
    634         m_Buffer.AppendBlock(&pair, sizeof(_DWordPair));
    635         return;
    636     }
    637     int low = 0, high = count - 1;
    638     while (low <= high) {
    639         int mid = (low + high) / 2;
    640         if (buf[mid].key < key) {
    641             low = mid + 1;
    642         } else if (buf[mid].key > key) {
    643             high = mid - 1;
    644         } else {
    645             buf[mid].value = value;
    646             return;
    647         }
    648     }
    649     m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair));
    650 }
    651 void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by)
    652 {
    653     m_Buffer.EstimateSize(size, grow_by);
    654 }
    655