Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / hashtable.c
bloba85f0ee204e658ba697395619650ea538bf3a63e
2 #include <sys/types.h>
3 #include <string.h>
4 #include <stdlib.h>
5 #include <stdio.h>
7 #include "WUtil.h"
9 #define INITIAL_CAPACITY 23
11 #if defined(__GNUC__) && !defined(__STRICT_ANSI__)
12 # define INLINE inline
13 #else
14 # define INLINE
15 #endif
17 typedef struct HashItem {
18 const void *key;
19 const void *data;
21 struct HashItem *next; /* collided item list */
22 } HashItem;
24 typedef struct W_HashTable {
25 WMHashTableCallbacks callbacks;
27 unsigned itemCount;
28 unsigned size; /* table size */
30 HashItem **table;
31 } HashTable;
33 #define HASH(table, key) (((table)->callbacks.hash ? \
34 (*(table)->callbacks.hash)(key) : hashPtr(key)) % (table)->size)
36 #define DUPKEY(table, key) ((table)->callbacks.retainKey ? \
37 (*(table)->callbacks.retainKey)(key) : (key))
39 #define RELKEY(table, key) if ((table)->callbacks.releaseKey) \
40 (*(table)->callbacks.releaseKey)(key)
42 static INLINE unsigned hashString(const char *key)
43 {
44 unsigned ret = 0;
45 unsigned ctr = 0;
47 while (*key) {
48 ret ^= *(char *)key++ << ctr;
49 ctr = (ctr + 1) % sizeof(char *);
50 }
52 return ret;
53 }
55 static INLINE unsigned hashPtr(const void *key)
56 {
57 return ((size_t) key / sizeof(char *));
58 }
60 static void rellocateItem(WMHashTable * table, HashItem * item)
61 {
62 unsigned h;
64 h = HASH(table, item->key);
66 item->next = table->table[h];
67 table->table[h] = item;
68 }
70 static void rebuildTable(WMHashTable * table)
71 {
72 HashItem *next;
73 HashItem **oldArray;
74 int i;
75 int oldSize;
76 int newSize;
78 oldArray = table->table;
79 oldSize = table->size;
81 newSize = table->size * 2;
83 table->table = wmalloc(sizeof(char *) * newSize);
84 memset(table->table, 0, sizeof(char *) * newSize);
85 table->size = newSize;
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 }
97 WMHashTable *WMCreateHashTable(WMHashTableCallbacks callbacks)
98 {
99 HashTable *table;
101 table = wmalloc(sizeof(HashTable));
102 memset(table, 0, sizeof(HashTable));
104 table->callbacks = callbacks;
106 table->size = INITIAL_CAPACITY;
108 table->table = wmalloc(sizeof(HashItem *) * table->size);
109 memset(table->table, 0, sizeof(HashItem *) * table->size);
111 return table;
114 void WMResetHashTable(WMHashTable * table)
116 HashItem *item, *tmp;
117 int i;
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;
129 table->itemCount = 0;
131 if (table->size > INITIAL_CAPACITY) {
132 wfree(table->table);
133 table->size = INITIAL_CAPACITY;
134 table->table = wmalloc(sizeof(HashItem *) * table->size);
136 memset(table->table, 0, sizeof(HashItem *) * table->size);
139 void WMFreeHashTable(WMHashTable * table)
141 HashItem *item, *tmp;
142 int i;
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;
153 wfree(table->table);
154 wfree(table);
157 unsigned WMCountHashTable(WMHashTable * table)
159 return table->itemCount;
162 void *WMHashGet(WMHashTable * table, const void *key)
164 unsigned h;
165 HashItem *item;
167 h = HASH(table, key);
168 item = table->table[h];
170 if (table->callbacks.keyIsEqual) {
171 while (item) {
172 if ((*table->callbacks.keyIsEqual) (key, item->key)) {
173 break;
175 item = item->next;
177 } else {
178 while (item) {
179 if (key == item->key) {
180 break;
182 item = item->next;
185 if (item)
186 return (void *)item->data;
187 else
188 return NULL;
191 Bool WMHashGetItemAndKey(WMHashTable * table, const void *key, void **retItem, void **retKey)
193 unsigned h;
194 HashItem *item;
196 h = HASH(table, key);
197 item = table->table[h];
199 if (table->callbacks.keyIsEqual) {
200 while (item) {
201 if ((*table->callbacks.keyIsEqual) (key, item->key)) {
202 break;
204 item = item->next;
206 } else {
207 while (item) {
208 if (key == item->key) {
209 break;
211 item = item->next;
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;
225 void *WMHashInsert(WMHashTable * table, const void *key, const void *data)
227 unsigned h;
228 HashItem *item;
229 int replacing = 0;
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;
240 item = item->next;
242 } else {
243 while (item) {
244 if (key == item->key) {
245 replacing = 1;
246 break;
248 item = item->next;
252 if (replacing) {
253 const void *old;
255 old = item->data;
256 item->data = data;
257 RELKEY(table, item->key);
258 item->key = DUPKEY(table, key);
260 return (void *)old;
261 } else {
262 HashItem *nitem;
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;
270 table->itemCount++;
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
284 return NULL;
287 static HashItem *deleteFromList(HashTable * table, HashItem * item, const void *key)
289 HashItem *next;
291 if (item == NULL)
292 return NULL;
294 if ((table->callbacks.keyIsEqual && (*table->callbacks.keyIsEqual) (key, item->key))
295 || (!table->callbacks.keyIsEqual && key == item->key)) {
297 next = item->next;
298 RELKEY(table, item->key);
299 wfree(item);
301 table->itemCount--;
303 return next;
306 item->next = deleteFromList(table, item->next, key);
308 return item;
311 void WMHashRemove(WMHashTable * table, const void *key)
313 unsigned h;
315 h = HASH(table, key);
317 table->table[h] = deleteFromList(table, table->table[h], key);
320 WMHashEnumerator WMEnumerateHashTable(WMHashTable * table)
322 WMHashEnumerator enumerator;
324 enumerator.table = table;
325 enumerator.index = 0;
326 enumerator.nextItem = table->table[0];
328 return enumerator;
331 void *WMNextHashEnumeratorItem(WMHashEnumerator * enumerator)
333 const void *data = NULL;
335 /* this assumes the table doesn't change between
336 * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
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;
348 if (enumerator->nextItem) {
349 data = ((HashItem *) enumerator->nextItem)->data;
350 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
353 return (void *)data;
356 void *WMNextHashEnumeratorKey(WMHashEnumerator * enumerator)
358 const void *key = NULL;
360 /* this assumes the table doesn't change between
361 * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
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;
373 if (enumerator->nextItem) {
374 key = ((HashItem *) enumerator->nextItem)->key;
375 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
378 return (void *)key;
381 Bool WMNextHashEnumeratorItemAndKey(WMHashEnumerator * enumerator, void **item, void **key)
383 /* this assumes the table doesn't change between
384 * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
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;
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;
403 return True;
406 return False;
409 static Bool compareStrings(const char *key1, const char *key2)
411 return strcmp(key1, key2) == 0;
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 *);
419 const WMHashTableCallbacks WMIntHashCallbacks = {
420 NULL,
421 NULL,
422 NULL,
423 NULL
424 };
426 const WMHashTableCallbacks WMStringHashCallbacks = {
427 (hashFunc) hashString,
428 (isEqualFunc) compareStrings,
429 (retainFunc) wstrdup,
430 (releaseFunc) wfree
431 };
433 const WMHashTableCallbacks WMStringPointerHashCallbacks = {
434 (hashFunc) hashString,
435 (isEqualFunc) compareStrings,
436 NULL,
437 NULL
438 };