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