1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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__
|
