diff options
Diffstat (limited to 'dep/CascLib/src/common/Map.cpp')
| -rw-r--r-- | dep/CascLib/src/common/Map.cpp | 183 |
1 files changed, 145 insertions, 38 deletions
diff --git a/dep/CascLib/src/common/Map.cpp b/dep/CascLib/src/common/Map.cpp index 70697a158ab..30ae8ea0531 100644 --- a/dep/CascLib/src/common/Map.cpp +++ b/dep/CascLib/src/common/Map.cpp @@ -15,51 +15,82 @@ //----------------------------------------------------------------------------- // Local functions -static DWORD CalcHashIndex(PCASC_MAP pMap, void * pvIdentifier) +// Returns the extension, right after "." +static const char * String_GetExtension(const char * szString) { + const char * szExtension = strrchr(szString, '.'); + return (szExtension != NULL) ? szExtension + 1 : NULL; +} + +static DWORD CalcHashIndex_Key(PCASC_MAP pMap, void * pvKey) +{ + LPBYTE pbKey = (LPBYTE)pvKey; DWORD dwHash = 0x7EEE7EEE; - // Is it a string table? - if(pMap->KeyLength == KEY_LENGTH_STRING) - { - char * szString = (char *)pvIdentifier; + // Construct the hash from the first 8 digits + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[0]; + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[1]; + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[2]; + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[3]; + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[4]; + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[5]; + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[6]; + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbKey[7]; - for(size_t i = 0; szString[i] != 0; i++) - dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ szString[i]; - } - else - { - LPBYTE pbHash = (LPBYTE)pvIdentifier; + // Return the hash limited by the table size + return (dwHash % pMap->TableSize); +} + +static DWORD CalcHashIndex_String(PCASC_MAP pMap, const char * szString, const char * szStringEnd) +{ + LPBYTE pbKeyEnd = (LPBYTE)szStringEnd; + LPBYTE pbKey = (LPBYTE)szString; + DWORD dwHash = 0x7EEE7EEE; - // Construct the hash from the first 4 digits - for(size_t i = 0; i < pMap->KeyLength; i++) - dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ pbHash[i]; + // Hash the string itself + while(pbKey < pbKeyEnd) + { + dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ AsciiToUpperTable_BkSlash[pbKey[0]]; + pbKey++; } // Return the hash limited by the table size return (dwHash % pMap->TableSize); } -static bool CompareIdentifier(PCASC_MAP pMap, void * pvTableEntry, void * pvIdentifier) +static bool CompareObject_Key(PCASC_MAP pMap, void * pvObject, void * pvKey) { - // Is it a string table? - if(pMap->KeyLength == KEY_LENGTH_STRING) - { - char * szTableEntry = (char *)pvTableEntry; - char * szIdentifier = (char *)pvIdentifier; + LPBYTE pbObjectKey = (LPBYTE)pvObject + pMap->KeyOffset; - return (strcmp(szTableEntry, szIdentifier) == 0); - } - else + return (memcmp(pbObjectKey, pvKey, pMap->KeyLength) == 0); +} + +static bool CompareObject_String( + PCASC_MAP pMap, + const char * szExistingString, + const char * szString, + const char * szStringEnd) +{ + // Keep compiler happy + CASCLIB_UNUSED(pMap); + + // Compare the whole part, case insensitive + while(szString < szStringEnd) { - return (memcmp(pvTableEntry, pvIdentifier, pMap->KeyLength) == 0); + if(AsciiToUpperTable_BkSlash[*szExistingString] != AsciiToUpperTable_BkSlash[*szString]) + return false; + + szExistingString++; + szString++; } + + return true; } //----------------------------------------------------------------------------- // Public functions -PCASC_MAP Map_Create(DWORD dwMaxItems, DWORD dwKeyLength, DWORD dwMemberOffset) +PCASC_MAP Map_Create(DWORD dwMaxItems, DWORD dwKeyLength, DWORD dwKeyOffset) { PCASC_MAP pMap; size_t cbToAllocate; @@ -76,7 +107,7 @@ PCASC_MAP Map_Create(DWORD dwMaxItems, DWORD dwKeyLength, DWORD dwMemberOffset) memset(pMap, 0, cbToAllocate); pMap->KeyLength = dwKeyLength; pMap->TableSize = dwTableSize; - pMap->MemberOffset = dwMemberOffset; + pMap->KeyOffset = dwKeyOffset; } // Return the allocated map @@ -104,24 +135,28 @@ size_t Map_EnumObjects(PCASC_MAP pMap, void **ppvArray) return pMap->ItemCount; } -void * Map_FindObject(PCASC_MAP pMap, void * pvIdentifier) +void * Map_FindObject(PCASC_MAP pMap, void * pvKey, PDWORD PtrIndex) { - void * pvTableEntry; + void * pvObject; DWORD dwHashIndex; // Verify pointer to the map if(pMap != NULL) { // Construct the main index - dwHashIndex = CalcHashIndex(pMap, pvIdentifier); + dwHashIndex = CalcHashIndex_Key(pMap, pvKey); while(pMap->HashTable[dwHashIndex] != NULL) { // Get the pointer at that position - pvTableEntry = pMap->HashTable[dwHashIndex]; + pvObject = pMap->HashTable[dwHashIndex]; // Compare the hash - if(CompareIdentifier(pMap, pvTableEntry, pvIdentifier)) - return ((LPBYTE)pvTableEntry - pMap->MemberOffset); + if(CompareObject_Key(pMap, pvObject, pvKey)) + { + if(PtrIndex != NULL) + PtrIndex[0] = dwHashIndex; + return pvObject; + } // Move to the next entry dwHashIndex = (dwHashIndex + 1) % pMap->TableSize; @@ -132,9 +167,47 @@ void * Map_FindObject(PCASC_MAP pMap, void * pvIdentifier) return NULL; } -bool Map_InsertObject(PCASC_MAP pMap, void * pvIdentifier) +bool Map_InsertObject(PCASC_MAP pMap, void * pvNewObject, void * pvKey) +{ + void * pvExistingObject; + DWORD dwHashIndex; + + // Verify pointer to the map + if(pMap != NULL) + { + // Limit check + if((pMap->ItemCount + 1) >= pMap->TableSize) + return false; + + // Construct the hash index + dwHashIndex = CalcHashIndex_Key(pMap, pvKey); + while(pMap->HashTable[dwHashIndex] != NULL) + { + // Get the pointer at that position + pvExistingObject = pMap->HashTable[dwHashIndex]; + + // Check if hash being inserted conflicts with an existing hash + if(CompareObject_Key(pMap, pvExistingObject, pvKey)) + return false; + + // Move to the next entry + dwHashIndex = (dwHashIndex + 1) % pMap->TableSize; + } + + // Insert at that position + pMap->HashTable[dwHashIndex] = pvNewObject; + pMap->ItemCount++; + return true; + } + + // Failed + return false; +} + +bool Map_InsertString(PCASC_MAP pMap, const char * szString, bool bCutExtension) { - void * pvTableEntry; + const char * szExistingString; + const char * szStringEnd = NULL; DWORD dwHashIndex; // Verify pointer to the map @@ -144,15 +217,21 @@ bool Map_InsertObject(PCASC_MAP pMap, void * pvIdentifier) if((pMap->ItemCount + 1) >= pMap->TableSize) return false; + // Retrieve the length of the string without extension + if(bCutExtension) + szStringEnd = String_GetExtension(szString); + if(szStringEnd == NULL) + szStringEnd = szString + strlen(szString); + // Construct the hash index - dwHashIndex = CalcHashIndex(pMap, pvIdentifier); + dwHashIndex = CalcHashIndex_String(pMap, szString, szStringEnd); while(pMap->HashTable[dwHashIndex] != NULL) { // Get the pointer at that position - pvTableEntry = pMap->HashTable[dwHashIndex]; + szExistingString = (const char *)pMap->HashTable[dwHashIndex]; // Check if hash being inserted conflicts with an existing hash - if(CompareIdentifier(pMap, pvTableEntry, pvIdentifier)) + if(CompareObject_String(pMap, szExistingString, szString, szStringEnd)) return false; // Move to the next entry @@ -160,7 +239,7 @@ bool Map_InsertObject(PCASC_MAP pMap, void * pvIdentifier) } // Insert at that position - pMap->HashTable[dwHashIndex] = pvIdentifier; + pMap->HashTable[dwHashIndex] = (void *)szString; pMap->ItemCount++; return true; } @@ -169,6 +248,34 @@ bool Map_InsertObject(PCASC_MAP pMap, void * pvIdentifier) return false; } +const char * Map_FindString(PCASC_MAP pMap, const char * szString, const char * szStringEnd) +{ + const char * szExistingString; + DWORD dwHashIndex; + + // Verify pointer to the map + if(pMap != NULL) + { + // Construct the main index + dwHashIndex = CalcHashIndex_String(pMap, szString, szStringEnd); + while(pMap->HashTable[dwHashIndex] != NULL) + { + // Get the pointer at that position + szExistingString = (const char *)pMap->HashTable[dwHashIndex]; + + // Compare the hash + if(CompareObject_String(pMap, szExistingString, szString, szStringEnd)) + return szExistingString; + + // Move to the next entry + dwHashIndex = (dwHashIndex + 1) % pMap->TableSize; + } + } + + // Not found, sorry + return NULL; +} + void Map_Free(PCASC_MAP pMap) { if(pMap != NULL) |