Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / hashtable.c
Commit [+]AuthorDateLineData
9d2e6ef9 scottc1998-09-29 22:36:29 +00001
9d2e6ef9 scottc1998-09-29 22:36:29 +00002#include <sys/types.h>
3#include <string.h>
4#include <stdlib.h>
5#include <stdio.h>
6
7#include "WUtil.h"
8
9d2e6ef9 scottc1998-09-29 22:36:29 +00009#define INITIAL_CAPACITY 23
10
9d2e6ef9 scottc1998-09-29 22:36:29 +000011#if defined(__GNUC__) && !defined(__STRICT_ANSI__)
12# define INLINE inline
13#else
14# define INLINE
15#endif
16
9d2e6ef9 scottc1998-09-29 22:36:29 +000017typedef struct HashItem {
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020018 const void *key;
19 const void *data;
6830b057 dan2004-10-12 21:28:27 +000020
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020021 struct HashItem *next; /* collided item list */
9d2e6ef9 scottc1998-09-29 22:36:29 +000022} HashItem;
23
9d2e6ef9 scottc1998-09-29 22:36:29 +000024typedef struct W_HashTable {
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020025 WMHashTableCallbacks callbacks;
9d2e6ef9 scottc1998-09-29 22:36:29 +000026
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020027 unsigned itemCount;
28 unsigned size; /* table size */
9d2e6ef9 scottc1998-09-29 22:36:29 +000029
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020030 HashItem **table;
9d2e6ef9 scottc1998-09-29 22:36:29 +000031} HashTable;
32
9d2e6ef9 scottc1998-09-29 22:36:29 +000033#define HASH(table, key) (((table)->callbacks.hash ? \
6830b057 dan2004-10-12 21:28:27 +000034 (*(table)->callbacks.hash)(key) : hashPtr(key)) % (table)->size)
9d2e6ef9 scottc1998-09-29 22:36:29 +000035
36#define DUPKEY(table, key) ((table)->callbacks.retainKey ? \
6830b057 dan2004-10-12 21:28:27 +000037 (*(table)->callbacks.retainKey)(key) : (key))
9d2e6ef9 scottc1998-09-29 22:36:29 +000038
39#define RELKEY(table, key) if ((table)->callbacks.releaseKey) \
6830b057 dan2004-10-12 21:28:27 +000040 (*(table)->callbacks.releaseKey)(key)
9d2e6ef9 scottc1998-09-29 22:36:29 +000041
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020042static INLINE unsigned hashString(const char *key)
9d2e6ef9 scottc1998-09-29 22:36:29 +000043{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020044 unsigned ret = 0;
45 unsigned ctr = 0;
9d2e6ef9 scottc1998-09-29 22:36:29 +000046
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020047 while (*key) {
48 ret ^= *(char *)key++ << ctr;
49 ctr = (ctr + 1) % sizeof(char *);
50 }
6830b057 dan2004-10-12 21:28:27 +000051
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020052 return ret;
9d2e6ef9 scottc1998-09-29 22:36:29 +000053}
54
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020055static INLINE unsigned hashPtr(const void *key)
9d2e6ef9 scottc1998-09-29 22:36:29 +000056{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020057 return ((size_t) key / sizeof(char *));
9d2e6ef9 scottc1998-09-29 22:36:29 +000058}
59
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020060static void rellocateItem(WMHashTable * table, HashItem * item)
9d2e6ef9 scottc1998-09-29 22:36:29 +000061{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020062 unsigned h;
9d2e6ef9 scottc1998-09-29 22:36:29 +000063
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020064 h = HASH(table, item->key);
9d2e6ef9 scottc1998-09-29 22:36:29 +000065
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020066 item->next = table->table[h];
67 table->table[h] = item;
9d2e6ef9 scottc1998-09-29 22:36:29 +000068}
69
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020070static void rebuildTable(WMHashTable * table)
9d2e6ef9 scottc1998-09-29 22:36:29 +000071{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020072 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);
9d2e6ef9 scottc1998-09-29 22:36:29 +000095}
96
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020097WMHashTable *WMCreateHashTable(WMHashTableCallbacks callbacks)
9d2e6ef9 scottc1998-09-29 22:36:29 +000098{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020099 HashTable *table;
6830b057 dan2004-10-12 21:28:27 +0000100
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200101 table = wmalloc(sizeof(HashTable));
102 memset(table, 0, sizeof(HashTable));
6830b057 dan2004-10-12 21:28:27 +0000103
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200104 table->callbacks = callbacks;
6830b057 dan2004-10-12 21:28:27 +0000105
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200106 table->size = INITIAL_CAPACITY;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000107
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200108 table->table = wmalloc(sizeof(HashItem *) * table->size);
109 memset(table->table, 0, sizeof(HashItem *) * table->size);
6830b057 dan2004-10-12 21:28:27 +0000110
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200111 return table;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000112}
113
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200114void WMResetHashTable(WMHashTable * table)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000115{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200116 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);
9d2e6ef9 scottc1998-09-29 22:36:29 +0000137}
138
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200139void WMFreeHashTable(WMHashTable * table)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000140{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200141 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);
9d2e6ef9 scottc1998-09-29 22:36:29 +0000155}
156
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200157unsigned WMCountHashTable(WMHashTable * table)
2d5a0620 dan2001-09-06 00:55:18 +0000158{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200159 return table->itemCount;
2d5a0620 dan2001-09-06 00:55:18 +0000160}
161
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200162void *WMHashGet(WMHashTable * table, const void *key)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000163{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200164 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;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000189}
190
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200191Bool WMHashGetItemAndKey(WMHashTable * table, const void *key, void **retItem, void **retKey)
49e59ab3 dan2001-09-10 03:56:00 +0000192{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200193 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 }
49e59ab3 dan2001-09-10 03:56:00 +0000223}
224
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200225void *WMHashInsert(WMHashTable * table, const void *key, const void *data)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000226{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200227 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) {
9d2e6ef9 scottc1998-09-29 22:36:29 +0000275#ifdef DEBUG0
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200276 printf("rebuilding hash table...\n");
9d2e6ef9 scottc1998-09-29 22:36:29 +0000277#endif
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200278 rebuildTable(table);
9d2e6ef9 scottc1998-09-29 22:36:29 +0000279#ifdef DEBUG0
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200280 printf("finished rebuild.\n");
9d2e6ef9 scottc1998-09-29 22:36:29 +0000281#endif
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200282 }
6830b057 dan2004-10-12 21:28:27 +0000283
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200284 return NULL;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000285}
286
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200287static HashItem *deleteFromList(HashTable * table, HashItem * item, const void *key)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000288{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200289 HashItem *next;
6830b057 dan2004-10-12 21:28:27 +0000290
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200291 if (item == NULL)
292 return NULL;
6830b057 dan2004-10-12 21:28:27 +0000293
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200294 if ((table->callbacks.keyIsEqual && (*table->callbacks.keyIsEqual) (key, item->key))
295 || (!table->callbacks.keyIsEqual && key == item->key)) {
6830b057 dan2004-10-12 21:28:27 +0000296
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200297 next = item->next;
298 RELKEY(table, item->key);
299 wfree(item);
6830b057 dan2004-10-12 21:28:27 +0000300
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200301 table->itemCount--;
6830b057 dan2004-10-12 21:28:27 +0000302
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200303 return next;
304 }
6830b057 dan2004-10-12 21:28:27 +0000305
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200306 item->next = deleteFromList(table, item->next, key);
9d2e6ef9 scottc1998-09-29 22:36:29 +0000307
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200308 return item;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000309}
310
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200311void WMHashRemove(WMHashTable * table, const void *key)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000312{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200313 unsigned h;
6830b057 dan2004-10-12 21:28:27 +0000314
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200315 h = HASH(table, key);
6830b057 dan2004-10-12 21:28:27 +0000316
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200317 table->table[h] = deleteFromList(table, table->table[h], key);
9d2e6ef9 scottc1998-09-29 22:36:29 +0000318}
319
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200320WMHashEnumerator WMEnumerateHashTable(WMHashTable * table)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000321{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200322 WMHashEnumerator enumerator;
6830b057 dan2004-10-12 21:28:27 +0000323
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200324 enumerator.table = table;
325 enumerator.index = 0;
326 enumerator.nextItem = table->table[0];
6830b057 dan2004-10-12 21:28:27 +0000327
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200328 return enumerator;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000329}
330
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200331void *WMNextHashEnumeratorItem(WMHashEnumerator * enumerator)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000332{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200333 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;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000354}
355
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200356void *WMNextHashEnumeratorKey(WMHashEnumerator * enumerator)
a7ec9dab dan2001-01-11 02:35:21 +0000357{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200358 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;
a7ec9dab dan2001-01-11 02:35:21 +0000379}
380
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200381Bool WMNextHashEnumeratorItemAndKey(WMHashEnumerator * enumerator, void **item, void **key)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000382{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200383 /* 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;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000407}
408
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200409static Bool compareStrings(const char *key1, const char *key2)
9d2e6ef9 scottc1998-09-29 22:36:29 +0000410{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200411 return strcmp(key1, key2) == 0;
9d2e6ef9 scottc1998-09-29 22:36:29 +0000412}
413
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200414typedef unsigned (*hashFunc) (const void *);
415typedef Bool(*isEqualFunc) (const void *, const void *);
416typedef void *(*retainFunc) (const void *);
417typedef void (*releaseFunc) (const void *);
9d2e6ef9 scottc1998-09-29 22:36:29 +0000418
419const WMHashTableCallbacks WMIntHashCallbacks = {
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200420 NULL,
421 NULL,
422 NULL,
423 NULL
9d2e6ef9 scottc1998-09-29 22:36:29 +0000424};
425
426const WMHashTableCallbacks WMStringHashCallbacks = {
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200427 (hashFunc) hashString,
428 (isEqualFunc) compareStrings,
429 (retainFunc) wstrdup,
430 (releaseFunc) wfree
9d2e6ef9 scottc1998-09-29 22:36:29 +0000431};
432
9d2e6ef9 scottc1998-09-29 22:36:29 +0000433const WMHashTableCallbacks WMStringPointerHashCallbacks = {
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200434 (hashFunc) hashString,
435 (isEqualFunc) compareStrings,
436 NULL,
437 NULL
9d2e6ef9 scottc1998-09-29 22:36:29 +0000438};