Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / hashtable.c
1
2 #include <sys/types.h>
3 #include <string.h>
4 #include <stdlib.h>
5 #include <stdio.h>
6
7 #include "WUtil.h"
8
9 #define INITIAL_CAPACITY 23
10
11 #if defined(__GNUC__) && !defined(__STRICT_ANSI__)
12 # define INLINE inline
13 #else
14 # define INLINE
15 #endif
16
17 typedef struct HashItem {
18 const void *key;
19 const void *data;
20
21 struct HashItem *next; /* collided item list */
22 } HashItem;
23
24 typedef struct W_HashTable {
25 WMHashTableCallbacks callbacks;
26
27 unsigned itemCount;
28 unsigned size; /* table size */
29
30 HashItem **table;
31 } HashTable;
32
33 #define HASH(table, key) (((table)->callbacks.hash ? \
34 (*(table)->callbacks.hash)(key) : hashPtr(key)) % (table)->size)
35
36 #define DUPKEY(table, key) ((table)->callbacks.retainKey ? \
37 (*(table)->callbacks.retainKey)(key) : (key))
38
39 #define RELKEY(table, key) if ((table)->callbacks.releaseKey) \
40 (*(table)->callbacks.releaseKey)(key)
41
42 static INLINE unsigned hashString(const char *key)
43 {
44 unsigned ret = 0;
45 unsigned ctr = 0;
46
47 while (*key) {
48 ret ^= *(char *)key++ << ctr;
49 ctr = (ctr + 1) % sizeof(char *);
50 }
51
52 return ret;
53 }
54
55 static INLINE unsigned hashPtr(const void *key)
56 {
57 return ((size_t) key / sizeof(char *));
58 }
59
60 static void rellocateItem(WMHashTable * table, HashItem * item)
61 {
62 unsigned h;
63
64 h = HASH(table, item->key);
65
66 item->next = table->table[h];
67 table->table[h] = item;
68 }
69
70 static void rebuildTable(WMHashTable * table)
71 {
72 HashItem *next;
73 HashItem **oldArray;
74 int i;
75 int oldSize;
76 int newSize;
77
78 oldArray = table->table;
79 oldSize = table->size;
80
81 newSize = table->size * 2;
82
83 table->table = wmalloc(sizeof(char *) * newSize);
84 memset(table->table, 0, sizeof(char *) * newSize);
85 table->size = newSize;
86
87 for (i = 0; i < oldSize; i++) {
88 while (oldArray[i] != NULL) {
89 next = oldArray[i]->next;
90 rellocateItem(table, oldArray[i]);
91 oldArray[i] = next;
92 }
93 }
94 wfree(oldArray);
95 }
96
97 WMHashTable *WMCreateHashTable(WMHashTableCallbacks callbacks)
98 {
99 HashTable *table;
100
101 table = wmalloc(sizeof(HashTable));
102 memset(table, 0, sizeof(HashTable));
103
104 table->callbacks = callbacks;
105
106 table->size = INITIAL_CAPACITY;
107
108 table->table = wmalloc(sizeof(HashItem *) * table->size);
109 memset(table->table, 0, sizeof(HashItem *) * table->size);
110
111 return table;
112 }
113
114 void WMResetHashTable(WMHashTable * table)
115 {
116 HashItem *item, *tmp;
117 int i;
118
119 for (i = 0; i < table->size; i++) {
120 item = table->table[i];
121 while (item) {
122 tmp = item->next;
123 RELKEY(table, item->key);
124 wfree(item);
125 item = tmp;
126 }
127 }
128
129 table->itemCount = 0;
130
131 if (table->size > INITIAL_CAPACITY) {
132 wfree(table->table);
133 table->size = INITIAL_CAPACITY;
134 table->table = wmalloc(sizeof(HashItem *) * table->size);
135 }
136 memset(table->table, 0, sizeof(HashItem *) * table->size);
137 }
138
139 void WMFreeHashTable(WMHashTable * table)
140 {
141 HashItem *item, *tmp;
142 int i;
143
144 for (i = 0; i < table->size; i++) {
145 item = table->table[i];
146 while (item) {
147 tmp = item->next;
148 RELKEY(table, item->key);
149 wfree(item);
150 item = tmp;
151 }
152 }
153 wfree(table->table);
154 wfree(table);
155 }
156
157 unsigned WMCountHashTable(WMHashTable * table)
158 {
159 return table->itemCount;
160 }
161
162 void *WMHashGet(WMHashTable * table, const void *key)
163 {
164 unsigned h;
165 HashItem *item;
166
167 h = HASH(table, key);
168 item = table->table[h];
169
170 if (table->callbacks.keyIsEqual) {
171 while (item) {
172 if ((*table->callbacks.keyIsEqual) (key, item->key)) {
173 break;
174 }
175 item = item->next;
176 }
177 } else {
178 while (item) {
179 if (key == item->key) {
180 break;
181 }
182 item = item->next;
183 }
184 }
185 if (item)
186 return (void *)item->data;
187 else
188 return NULL;
189 }
190
191 Bool WMHashGetItemAndKey(WMHashTable * table, const void *key, void **retItem, void **retKey)
192 {
193 unsigned h;
194 HashItem *item;
195
196 h = HASH(table, key);
197 item = table->table[h];
198
199 if (table->callbacks.keyIsEqual) {
200 while (item) {
201 if ((*table->callbacks.keyIsEqual) (key, item->key)) {
202 break;
203 }
204 item = item->next;
205 }
206 } else {
207 while (item) {
208 if (key == item->key) {
209 break;
210 }
211 item = item->next;
212 }
213 }
214 if (item) {
215 if (retKey)
216 *retKey = (void *)item->key;
217 if (retItem)
218 *retItem = (void *)item->data;
219 return True;
220 } else {
221 return False;
222 }
223 }
224
225 void *WMHashInsert(WMHashTable * table, const void *key, const void *data)
226 {
227 unsigned h;
228 HashItem *item;
229 int replacing = 0;
230
231 h = HASH(table, key);
232 /* look for the entry */
233 item = table->table[h];
234 if (table->callbacks.keyIsEqual) {
235 while (item) {
236 if ((*table->callbacks.keyIsEqual) (key, item->key)) {
237 replacing = 1;
238 break;
239 }
240 item = item->next;
241 }
242 } else {
243 while (item) {
244 if (key == item->key) {
245 replacing = 1;
246 break;
247 }
248 item = item->next;
249 }
250 }
251
252 if (replacing) {
253 const void *old;
254
255 old = item->data;
256 item->data = data;
257 RELKEY(table, item->key);
258 item->key = DUPKEY(table, key);
259
260 return (void *)old;
261 } else {
262 HashItem *nitem;
263
264 nitem = wmalloc(sizeof(HashItem));
265 nitem->key = DUPKEY(table, key);
266 nitem->data = data;
267 nitem->next = table->table[h];
268 table->table[h] = nitem;
269
270 table->itemCount++;
271 }
272
273 /* OPTIMIZE: put this in an idle handler. */
274 if (table->itemCount > table->size) {
275 #ifdef DEBUG0
276 printf("rebuilding hash table...\n");
277 #endif
278 rebuildTable(table);
279 #ifdef DEBUG0
280 printf("finished rebuild.\n");
281 #endif
282 }
283
284 return NULL;
285 }
286
287 static HashItem *deleteFromList(HashTable * table, HashItem * item, const void *key)
288 {
289 HashItem *next;
290
291 if (item == NULL)
292 return NULL;
293
294 if ((table->callbacks.keyIsEqual && (*table->callbacks.keyIsEqual) (key, item->key))
295 || (!table->callbacks.keyIsEqual && key == item->key)) {
296
297 next = item->next;
298 RELKEY(table, item->key);
299 wfree(item);
300
301 table->itemCount--;
302
303 return next;
304 }
305
306 item->next = deleteFromList(table, item->next, key);
307
308 return item;
309 }
310
311 void WMHashRemove(WMHashTable * table, const void *key)
312 {
313 unsigned h;
314
315 h = HASH(table, key);
316
317 table->table[h] = deleteFromList(table, table->table[h], key);
318 }
319
320 WMHashEnumerator WMEnumerateHashTable(WMHashTable * table)
321 {
322 WMHashEnumerator enumerator;
323
324 enumerator.table = table;
325 enumerator.index = 0;
326 enumerator.nextItem = table->table[0];
327
328 return enumerator;
329 }
330
331 void *WMNextHashEnumeratorItem(WMHashEnumerator * enumerator)
332 {
333 const void *data = NULL;
334
335 /* this assumes the table doesn't change between
336 * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
337
338 if (enumerator->nextItem == NULL) {
339 HashTable *table = enumerator->table;
340 while (++enumerator->index < table->size) {
341 if (table->table[enumerator->index] != NULL) {
342 enumerator->nextItem = table->table[enumerator->index];
343 break;
344 }
345 }
346 }
347
348 if (enumerator->nextItem) {
349 data = ((HashItem *) enumerator->nextItem)->data;
350 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
351 }
352
353 return (void *)data;
354 }
355
356 void *WMNextHashEnumeratorKey(WMHashEnumerator * enumerator)
357 {
358 const void *key = NULL;
359
360 /* this assumes the table doesn't change between
361 * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
362
363 if (enumerator->nextItem == NULL) {
364 HashTable *table = enumerator->table;
365 while (++enumerator->index < table->size) {
366 if (table->table[enumerator->index] != NULL) {
367 enumerator->nextItem = table->table[enumerator->index];
368 break;
369 }
370 }
371 }
372
373 if (enumerator->nextItem) {
374 key = ((HashItem *) enumerator->nextItem)->key;
375 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
376 }
377
378 return (void *)key;
379 }
380
381 Bool WMNextHashEnumeratorItemAndKey(WMHashEnumerator * enumerator, void **item, void **key)
382 {
383 /* this assumes the table doesn't change between
384 * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
385
386 if (enumerator->nextItem == NULL) {
387 HashTable *table = enumerator->table;
388 while (++enumerator->index < table->size) {
389 if (table->table[enumerator->index] != NULL) {
390 enumerator->nextItem = table->table[enumerator->index];
391 break;
392 }
393 }
394 }
395
396 if (enumerator->nextItem) {
397 if (item)
398 *item = (void *)((HashItem *) enumerator->nextItem)->data;
399 if (key)
400 *key = (void *)((HashItem *) enumerator->nextItem)->key;
401 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
402
403 return True;
404 }
405
406 return False;
407 }
408
409 static Bool compareStrings(const char *key1, const char *key2)
410 {
411 return strcmp(key1, key2) == 0;
412 }
413
414 typedef unsigned (*hashFunc) (const void *);
415 typedef Bool(*isEqualFunc) (const void *, const void *);
416 typedef void *(*retainFunc) (const void *);
417 typedef void (*releaseFunc) (const void *);
418
419 const WMHashTableCallbacks WMIntHashCallbacks = {
420 NULL,
421 NULL,
422 NULL,
423 NULL
424 };
425
426 const WMHashTableCallbacks WMStringHashCallbacks = {
427 (hashFunc) hashString,
428 (isEqualFunc) compareStrings,
429 (retainFunc) wstrdup,
430 (releaseFunc) wfree
431 };
432
433 const WMHashTableCallbacks WMStringPointerHashCallbacks = {
434 (hashFunc) hashString,
435 (isEqualFunc) compareStrings,
436 NULL,
437 NULL
438 };