1 files changed, 178 insertions, 0 deletions
diff --git a/dep/CascLib/src/common/Map.cpp b/dep/CascLib/src/common/Map.cpp
new file mode 100644
index 00000000000..70697a158ab
--- /dev/null
+++ b/dep/CascLib/src/common/Map.cpp
@@ -0,0 +1,178 @@
+/*****************************************************************************/
+/* Map.cpp                                Copyright (c) Ladislav Zezula 2014 */
+/*---------------------------------------------------------------------------*/
+/* Implementation of map for CascLib                                         */
+/*---------------------------------------------------------------------------*/
+/*   Date    Ver   Who  Comment                                              */
+/* --------  ----  ---  -------                                              */
+/* 10.06.14  1.00  Lad  The first version of Map.cpp                         */
+/*****************************************************************************/
+
+#define __CASCLIB_SELF__
+#include "../CascLib.h"
+#include "../CascCommon.h"
+
+//-----------------------------------------------------------------------------
+// Local functions
+
+static DWORD CalcHashIndex(PCASC_MAP pMap, void * pvIdentifier)
+{
+    DWORD dwHash = 0x7EEE7EEE;
+
+    // Is it a string table?
+    if(pMap->KeyLength == KEY_LENGTH_STRING)
+    {
+        char * szString = (char *)pvIdentifier;
+
+        for(size_t i = 0; szString[i] != 0; i++)
+            dwHash = (dwHash >> 24) ^ (dwHash << 5) ^ dwHash ^ szString[i];
+    }
+    else
+    {
+        LPBYTE pbHash = (LPBYTE)pvIdentifier;
+
+        // 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];
+    }
+
+    // Return the hash limited by the table size
+    return (dwHash % pMap->TableSize);
+}
+
+static bool CompareIdentifier(PCASC_MAP pMap, void * pvTableEntry, void * pvIdentifier)
+{
+    // Is it a string table?
+    if(pMap->KeyLength == KEY_LENGTH_STRING)
+    {
+        char * szTableEntry = (char *)pvTableEntry;
+        char * szIdentifier = (char *)pvIdentifier;
+
+        return (strcmp(szTableEntry, szIdentifier) == 0);
+    }
+    else
+    {
+        return (memcmp(pvTableEntry, pvIdentifier, pMap->KeyLength) == 0);
+    }
+}
+
+//-----------------------------------------------------------------------------
+// Public functions
+
+PCASC_MAP Map_Create(DWORD dwMaxItems, DWORD dwKeyLength, DWORD dwMemberOffset)
+{
+    PCASC_MAP pMap;
+    size_t cbToAllocate;
+    size_t dwTableSize;
+
+    // Calculate the size of the table
+    dwTableSize = (dwMaxItems * 3 / 2) | 0x01;
+
+    // Allocate new map for the objects
+    cbToAllocate = sizeof(CASC_MAP) + (dwTableSize * sizeof(void *));
+    pMap = (PCASC_MAP)CASC_ALLOC(LPBYTE, cbToAllocate);
+    if(pMap != NULL)
+    {
+        memset(pMap, 0, cbToAllocate);
+        pMap->KeyLength = dwKeyLength;
+        pMap->TableSize = dwTableSize;
+        pMap->MemberOffset = dwMemberOffset;
+    }
+
+    // Return the allocated map
+    return pMap;
+}
+
+size_t Map_EnumObjects(PCASC_MAP pMap, void **ppvArray)
+{
+    size_t nIndex = 0;
+
+    // Verify pointer to the map
+    if(pMap != NULL && ppvArray != NULL)
+    {
+        // Enumerate all items in main table
+        for(size_t i = 0; i < pMap->TableSize; i++)
+        {
+            // Is that cell valid?
+            if(pMap->HashTable[i] != NULL)
+            {
+                ppvArray[nIndex++] = pMap->HashTable[i];
+            }
+        }
+    }
+
+    return pMap->ItemCount;
+}
+
+void * Map_FindObject(PCASC_MAP pMap, void * pvIdentifier)
+{
+    void * pvTableEntry;
+    DWORD dwHashIndex;
+
+    // Verify pointer to the map
+    if(pMap != NULL)
+    {
+        // Construct the main index
+        dwHashIndex = CalcHashIndex(pMap, pvIdentifier);
+        while(pMap->HashTable[dwHashIndex] != NULL)
+        {
+            // Get the pointer at that position
+            pvTableEntry = pMap->HashTable[dwHashIndex];
+
+            // Compare the hash
+            if(CompareIdentifier(pMap, pvTableEntry, pvIdentifier))
+                return ((LPBYTE)pvTableEntry - pMap->MemberOffset);
+
+            // Move to the next entry
+            dwHashIndex = (dwHashIndex + 1) % pMap->TableSize;
+        }
+    }
+
+    // Not found, sorry
+    return NULL;
+}
+
+bool Map_InsertObject(PCASC_MAP pMap, void * pvIdentifier)
+{
+    void * pvTableEntry;
+    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(pMap, pvIdentifier);
+        while(pMap->HashTable[dwHashIndex] != NULL)
+        {
+            // Get the pointer at that position
+            pvTableEntry = pMap->HashTable[dwHashIndex];
+
+            // Check if hash being inserted conflicts with an existing hash
+            if(CompareIdentifier(pMap, pvTableEntry, pvIdentifier))
+                return false;
+
+            // Move to the next entry
+            dwHashIndex = (dwHashIndex + 1) % pMap->TableSize;
+        }
+
+        // Insert at that position
+        pMap->HashTable[dwHashIndex] = pvIdentifier;
+        pMap->ItemCount++;
+        return true;
+    }
+
+    // Failed
+    return false;
+}
+
+void Map_Free(PCASC_MAP pMap)
+{
+    if(pMap != NULL)
+    {
+        CASC_FREE(pMap);
+    }
+}