wmaker-check: rewrote parsing of structure fields for callback checker
[wmaker-crm.git] / WINGs / hashtable.c
blob2620c784840e23f878ba95cdfbf40615fb8396a9
1 #include <config.h>
3 #include <sys/types.h>
4 #include <string.h>
5 #include <stdlib.h>
6 #include <stdio.h>
8 #include "WUtil.h"
10 #define INITIAL_CAPACITY 23
13 typedef struct HashItem {
14 const void *key;
15 const void *data;
17 struct HashItem *next; /* collided item list */
18 } HashItem;
20 typedef struct W_HashTable {
21 WMHashTableCallbacks callbacks;
23 unsigned itemCount;
24 unsigned size; /* table size */
26 HashItem **table;
27 } HashTable;
29 #define HASH(table, key) (((table)->callbacks.hash ? \
30 (*(table)->callbacks.hash)(key) : hashPtr(key)) % (table)->size)
32 #define DUPKEY(table, key) ((table)->callbacks.retainKey ? \
33 (*(table)->callbacks.retainKey)(key) : (key))
35 #define RELKEY(table, key) if ((table)->callbacks.releaseKey) \
36 (*(table)->callbacks.releaseKey)(key)
38 static inline unsigned hashString(const void *param)
40 const char *key = param;
41 unsigned ret = 0;
42 unsigned ctr = 0;
44 while (*key) {
45 ret ^= *key++ << ctr;
46 ctr = (ctr + 1) % sizeof(char *);
49 return ret;
52 static inline unsigned hashPtr(const void *key)
54 return ((size_t) key / sizeof(char *));
57 static void rellocateItem(WMHashTable * table, HashItem * item)
59 unsigned h;
61 h = HASH(table, item->key);
63 item->next = table->table[h];
64 table->table[h] = item;
67 static void rebuildTable(WMHashTable * table)
69 HashItem *next;
70 HashItem **oldArray;
71 int i;
72 int oldSize;
73 int newSize;
75 oldArray = table->table;
76 oldSize = table->size;
78 newSize = table->size * 2;
80 table->table = wmalloc(sizeof(char *) * newSize);
81 table->size = newSize;
83 for (i = 0; i < oldSize; i++) {
84 while (oldArray[i] != NULL) {
85 next = oldArray[i]->next;
86 rellocateItem(table, oldArray[i]);
87 oldArray[i] = next;
90 wfree(oldArray);
93 WMHashTable *WMCreateHashTable(const WMHashTableCallbacks callbacks)
95 HashTable *table;
97 table = wmalloc(sizeof(HashTable));
99 table->callbacks = callbacks;
101 table->size = INITIAL_CAPACITY;
103 table->table = wmalloc(sizeof(HashItem *) * table->size);
105 return table;
108 void WMResetHashTable(WMHashTable * table)
110 HashItem *item, *tmp;
111 int i;
113 for (i = 0; i < table->size; i++) {
114 item = table->table[i];
115 while (item) {
116 tmp = item->next;
117 RELKEY(table, item->key);
118 wfree(item);
119 item = tmp;
123 table->itemCount = 0;
125 if (table->size > INITIAL_CAPACITY) {
126 wfree(table->table);
127 table->size = INITIAL_CAPACITY;
128 table->table = wmalloc(sizeof(HashItem *) * table->size);
129 } else {
130 memset(table->table, 0, sizeof(HashItem *) * table->size);
134 void WMFreeHashTable(WMHashTable * table)
136 HashItem *item, *tmp;
137 int i;
139 for (i = 0; i < table->size; i++) {
140 item = table->table[i];
141 while (item) {
142 tmp = item->next;
143 RELKEY(table, item->key);
144 wfree(item);
145 item = tmp;
148 wfree(table->table);
149 wfree(table);
152 unsigned WMCountHashTable(WMHashTable * table)
154 return table->itemCount;
157 static HashItem *hashGetItem(WMHashTable *table, const void *key)
159 unsigned h;
160 HashItem *item;
162 h = HASH(table, key);
163 item = table->table[h];
165 if (table->callbacks.keyIsEqual) {
166 while (item) {
167 if ((*table->callbacks.keyIsEqual) (key, item->key)) {
168 break;
170 item = item->next;
172 } else {
173 while (item) {
174 if (key == item->key) {
175 break;
177 item = item->next;
180 return item;
183 void *WMHashGet(WMHashTable * table, const void *key)
185 HashItem *item;
187 item = hashGetItem(table, key);
188 if (!item)
189 return NULL;
190 return (void *)item->data;
193 Bool WMHashGetItemAndKey(WMHashTable * table, const void *key, void **retItem, void **retKey)
195 HashItem *item;
197 item = hashGetItem(table, key);
198 if (!item)
199 return False;
201 if (retKey)
202 *retKey = (void *)item->key;
203 if (retItem)
204 *retItem = (void *)item->data;
205 return True;
208 void *WMHashInsert(WMHashTable * table, const void *key, const void *data)
210 unsigned h;
211 HashItem *item;
212 int replacing = 0;
214 h = HASH(table, key);
215 /* look for the entry */
216 item = table->table[h];
217 if (table->callbacks.keyIsEqual) {
218 while (item) {
219 if ((*table->callbacks.keyIsEqual) (key, item->key)) {
220 replacing = 1;
221 break;
223 item = item->next;
225 } else {
226 while (item) {
227 if (key == item->key) {
228 replacing = 1;
229 break;
231 item = item->next;
235 if (replacing) {
236 const void *old;
238 old = item->data;
239 item->data = data;
240 RELKEY(table, item->key);
241 item->key = DUPKEY(table, key);
243 return (void *)old;
244 } else {
245 HashItem *nitem;
247 nitem = wmalloc(sizeof(HashItem));
248 nitem->key = DUPKEY(table, key);
249 nitem->data = data;
250 nitem->next = table->table[h];
251 table->table[h] = nitem;
253 table->itemCount++;
256 /* OPTIMIZE: put this in an idle handler. */
257 if (table->itemCount > table->size) {
258 #ifdef DEBUG0
259 printf("rebuilding hash table...\n");
260 #endif
261 rebuildTable(table);
262 #ifdef DEBUG0
263 printf("finished rebuild.\n");
264 #endif
267 return NULL;
270 static HashItem *deleteFromList(HashTable * table, HashItem * item, const void *key)
272 HashItem *next;
274 if (item == NULL)
275 return NULL;
277 if ((table->callbacks.keyIsEqual && (*table->callbacks.keyIsEqual) (key, item->key))
278 || (!table->callbacks.keyIsEqual && key == item->key)) {
280 next = item->next;
281 RELKEY(table, item->key);
282 wfree(item);
284 table->itemCount--;
286 return next;
289 item->next = deleteFromList(table, item->next, key);
291 return item;
294 void WMHashRemove(WMHashTable * table, const void *key)
296 unsigned h;
298 h = HASH(table, key);
300 table->table[h] = deleteFromList(table, table->table[h], key);
303 WMHashEnumerator WMEnumerateHashTable(WMHashTable * table)
305 WMHashEnumerator enumerator;
307 enumerator.table = table;
308 enumerator.index = 0;
309 enumerator.nextItem = table->table[0];
311 return enumerator;
314 void *WMNextHashEnumeratorItem(WMHashEnumerator * enumerator)
316 const void *data = NULL;
318 /* this assumes the table doesn't change between
319 * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
321 if (enumerator->nextItem == NULL) {
322 HashTable *table = enumerator->table;
323 while (++enumerator->index < table->size) {
324 if (table->table[enumerator->index] != NULL) {
325 enumerator->nextItem = table->table[enumerator->index];
326 break;
331 if (enumerator->nextItem) {
332 data = ((HashItem *) enumerator->nextItem)->data;
333 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
336 return (void *)data;
339 void *WMNextHashEnumeratorKey(WMHashEnumerator * enumerator)
341 const void *key = NULL;
343 /* this assumes the table doesn't change between
344 * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
346 if (enumerator->nextItem == NULL) {
347 HashTable *table = enumerator->table;
348 while (++enumerator->index < table->size) {
349 if (table->table[enumerator->index] != NULL) {
350 enumerator->nextItem = table->table[enumerator->index];
351 break;
356 if (enumerator->nextItem) {
357 key = ((HashItem *) enumerator->nextItem)->key;
358 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
361 return (void *)key;
364 Bool WMNextHashEnumeratorItemAndKey(WMHashEnumerator * enumerator, void **item, void **key)
366 /* this assumes the table doesn't change between
367 * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
369 if (enumerator->nextItem == NULL) {
370 HashTable *table = enumerator->table;
371 while (++enumerator->index < table->size) {
372 if (table->table[enumerator->index] != NULL) {
373 enumerator->nextItem = table->table[enumerator->index];
374 break;
379 if (enumerator->nextItem) {
380 if (item)
381 *item = (void *)((HashItem *) enumerator->nextItem)->data;
382 if (key)
383 *key = (void *)((HashItem *) enumerator->nextItem)->key;
384 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
386 return True;
389 return False;
392 static Bool compareStrings(const void *param1, const void *param2)
394 const char *key1 = param1;
395 const char *key2 = param2;
397 return strcmp(key1, key2) == 0;
400 typedef void *(*retainFunc) (const void *);
401 typedef void (*releaseFunc) (const void *);
403 const WMHashTableCallbacks WMIntHashCallbacks = {
404 NULL,
405 NULL,
406 NULL,
407 NULL
410 const WMHashTableCallbacks WMStringHashCallbacks = {
411 hashString,
412 compareStrings,
413 (retainFunc) wstrdup,
414 (releaseFunc) wfree
417 const WMHashTableCallbacks WMStringPointerHashCallbacks = {
418 hashString,
419 compareStrings,
420 NULL,
421 NULL