1 files changed, 106 insertions, 0 deletions
diff --git a/dep/CascLib/src/common/IndexMap.h b/dep/CascLib/src/common/IndexMap.h
new file mode 100644
index 00000000000..fe6b007cc7e
--- /dev/null
+++ b/dep/CascLib/src/common/IndexMap.h
@@ -0,0 +1,106 @@
+/*****************************************************************************/
+/* IndexMap.h                             Copyright (c) Ladislav Zezula 2019 */
+/*---------------------------------------------------------------------------*/
+/* Interface of index-based map for CascLib. This is a map type created      */
+/* on top of an array of contant-size objects, that is already sorted.       */
+/*---------------------------------------------------------------------------*/
+/*   Date    Ver   Who  Comment                                              */
+/* --------  ----  ---  -------                                              */
+/* 29.04.19  1.00  Lad  The first version of Index.h                         */
+/*****************************************************************************/
+
+#ifndef __CASC_INDEX_MAP_H__
+#define __CASC_INDEX_MAP_H__
+
+//-----------------------------------------------------------------------------
+// Structures
+
+class CASC_INDEX_MAP
+{
+    public:
+
+    int Create(size_t MaxItems, size_t ObjectLength_, size_t KeyLength_, size_t KeyOffset_)
+    {
+        DWORD IndexBitSize = 8;
+
+        // Determine the index size
+        if(MaxItems >= 0x10000)
+            IndexBitSize = 16;
+        if(MaxItems >= 0x100000)
+            IndexBitSize = 20;
+
+        // Save the values
+        IndexTableSize = (1 << IndexBitSize);
+        IndexTableMask = IndexTableSize - 1;
+        ObjectLength = ObjectLength_;
+        KeyOffset = KeyOffset_;
+        KeyLength = KeyLength_;
+
+        // Allocate the new index object
+        IndexTable = CASC_ALLOC(void *, IndexTableSize);
+        if(IndexTable != NULL)
+        {
+            memset(IndexTable, 0, IndexTableSize * sizeof(void *));
+            return ERROR_SUCCESS;
+        }
+
+        return ERROR_NOT_ENOUGH_MEMORY;
+    }
+
+    void * FindObject(void * pvKey)
+    {
+        LPBYTE StartObject;
+        DWORD StartIndex;
+
+        // Verify pointer to the map
+        if(IndexTable != NULL)
+        {
+            // Retrieve the index from the key
+            StartIndex = KeyToIndex(pvKey);
+            StartObject = (LPBYTE)IndexTable[StartIndex];
+            if(StartObject == NULL)
+                return NULL;
+
+            // Enumerate the array as long as the index matches
+            do
+            {
+                // Compare the key
+                if(!memcmp(StartObject + KeyOffset, pvKey, KeyLength))
+                    return StartObject;
+
+                // Key mismatch -> go next object
+                StartObject = StartObject + ObjectLength;
+            }
+            while(KeyToIndex(StartObject + KeyOffset) == StartIndex);
+        }
+
+        // Not found
+        return NULL;
+    }
+
+    protected:
+
+    inline DWORD KeyToIndex(void * pvKey)
+    {
+        return *((PDWORD)pvKey) & IndexTableMask;
+    }
+
+    void ** IndexTable;                         // Pointer table. Each entry, if non-NULL, contains a pointer to the first object
+                                                // into a sorted array. Search function must then match the entire key.
+                                                // In case of no match, the search process must go to the next-in-array object.
+    size_t ObjectLength;                        // Length of the single object
+    size_t KeyOffset;                           // How far is the key from the begin of the structure (in bytes)
+    size_t KeyLength;                           // Length of the key
+    DWORD  IndexTableSize;                      // Size of the IndexTableSize, in bytes
+    DWORD  IndexTableMask;                      // Bit mask for conversion from hash to index
+};
+
+typedef CASC_INDEX_MAP *PCASC_INDEX_MAP;
+
+//-----------------------------------------------------------------------------
+// Functions
+
+bool IndexMap_InsertObject(PCASC_INDEX_MAP pIndexMap, void * pvNewObject, void * pvKey);
+void IndexMap_Free(PCASC_INDEX_MAP pIndexMap);
+
+#endif // __CASC_INDEX_MAP_H__