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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
/*
*
* File: hashtable.c
* ---------------
* David Wright
* 10/8/98
*
* See hashtable.h for function comments
* Implmentation is straight-forward, using a fixed dynamically allocated
* array for the buckets, and a DArray for each individual bucket
*/
#if !defined(UNDER_CE) && !defined(__KATANA__)
#include <assert.h>
#else
#define assert(a)
#endif
#include <stdlib.h>
#include <string.h>
#include "darray.h"
#include "hashtable.h"
#ifdef _MFC_MEM_DEBUG
#define _CRTDBG_MAP_ALLOC 1
#include <crtdbg.h>
#endif
#ifdef _NO_NOPORT_H_
#define gsimalloc malloc
#define gsifree free
#define gsirealloc realloc
#else
#include "nonport.h" //for gsimalloc/realloc/free
#endif
struct HashImplementation
{
DArray *buckets;
int nbuckets;
TableElementFreeFn freefn;
TableHashFn hashfn;
TableCompareFn compfn;
};
HashTable TableNew(int elemSize, int nBuckets,
TableHashFn hashFn, TableCompareFn compFn,
TableElementFreeFn freeFn)
{
return TableNew2(elemSize, nBuckets, 4, hashFn, compFn, freeFn);
}
HashTable TableNew2(int elemSize, int nBuckets, int nChains,
TableHashFn hashFn, TableCompareFn compFn,
TableElementFreeFn freeFn)
{
HashTable table;
int i;
assert(hashFn);
assert(compFn);
assert(elemSize);
assert(nBuckets);
table = (HashTable)gsimalloc(sizeof(struct HashImplementation));
assert(table);
table->buckets = (DArray *)gsimalloc(nBuckets * sizeof(DArray));
assert(table->buckets);
for (i = 0; i < nBuckets; i++) //ArrayNew will assert if allocation fails
table->buckets[i] = ArrayNew(elemSize, nChains, freeFn);
table->nbuckets = nBuckets;
table->freefn = freeFn;
table->compfn = compFn;
table->hashfn = hashFn;
return table;
}
void TableFree(HashTable table)
{
int i;
assert(table);
for (i = 0 ; i < table->nbuckets ; i++)
ArrayFree(table->buckets[i]);
gsifree(table->buckets);
gsifree(table);
}
int TableCount(HashTable table)
{
int i, count = 0;
for (i = 0 ; i < table->nbuckets ; i++)
count += ArrayLength(table->buckets[i]);
return count;
}
void TableEnter(HashTable table, const void *newElem)
{
int hash, itempos;
hash = table->hashfn(newElem, table->nbuckets);
itempos = ArraySearch(table->buckets[hash], newElem, table->compfn, 0,0);
if (itempos == NOT_FOUND)
ArrayAppend(table->buckets[hash], newElem);
else
ArrayReplaceAt(table->buckets[hash], newElem, itempos);
}
int TableRemove(HashTable table, const void *delElem)
{
int hash, itempos;
hash = table->hashfn(delElem, table->nbuckets);
itempos = ArraySearch(table->buckets[hash], delElem, table->compfn, 0,0);
if (itempos == NOT_FOUND)
return 0;
else
ArrayDeleteAt(table->buckets[hash], itempos);
return 1;
}
void *TableLookup(HashTable table, const void *elemKey)
{
int hash, itempos;
hash = table->hashfn(elemKey, table->nbuckets);
itempos = ArraySearch(table->buckets[hash], elemKey, table->compfn, 0,
0);
if (itempos == NOT_FOUND)
return NULL;
else
return ArrayNth(table->buckets[hash], itempos);
}
void TableMap(HashTable table, TableMapFn fn, void *clientData)
{
int i;
assert(fn);
for (i = 0 ; i < table->nbuckets ; i++)
ArrayMap(table->buckets[i], fn, clientData);
}
void TableMapSafe(HashTable table, TableMapFn fn, void *clientData)
{
int i;
assert(fn);
for (i = 0 ; i < table->nbuckets ; i++)
ArrayMapBackwards(table->buckets[i], fn, clientData);
}
void * TableMap2(HashTable table, TableMapFn2 fn, void *clientData)
{
int i;
void * pcurr;
assert(fn);
for (i = 0 ; i < table->nbuckets ; i++)
{
pcurr = ArrayMap2(table->buckets[i], fn, clientData);
if(pcurr)
return pcurr;
}
return NULL;
}
void * TableMapSafe2(HashTable table, TableMapFn2 fn, void *clientData)
{
int i;
void * pcurr;
assert(fn);
for (i = 0 ; i < table->nbuckets ; i++)
{
pcurr = ArrayMapBackwards2(table->buckets[i], fn, clientData);
if(pcurr)
return pcurr;
}
return NULL;
}
void TableClear(HashTable table)
{
int i;
for (i = 0 ; i < table->nbuckets ; i++)
ArrayClear(table->buckets[i]);
}
|
