9 #define INITIAL_CAPACITY 23
11 #if defined(__GNUC__) && !defined(__STRICT_ANSI__)
12 # define INLINE inline
17 typedef struct HashItem
{
21 struct HashItem
*next
; /* collided item list */
24 typedef struct W_HashTable
{
25 WMHashTableCallbacks callbacks
;
28 unsigned size
; /* table size */
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
)
48 ret
^= *(char *)key
++ << ctr
;
49 ctr
= (ctr
+ 1) % sizeof(char *);
55 static INLINE
unsigned hashPtr(const void *key
)
57 return ((size_t) key
/ sizeof(char *));
60 static void rellocateItem(WMHashTable
* table
, HashItem
* item
)
64 h
= HASH(table
, item
->key
);
66 item
->next
= table
->table
[h
];
67 table
->table
[h
] = item
;
70 static void rebuildTable(WMHashTable
* table
)
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
]);
97 WMHashTable
*WMCreateHashTable(WMHashTableCallbacks callbacks
)
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
);
114 void WMResetHashTable(WMHashTable
* table
)
116 HashItem
*item
, *tmp
;
119 for (i
= 0; i
< table
->size
; i
++) {
120 item
= table
->table
[i
];
123 RELKEY(table
, item
->key
);
129 table
->itemCount
= 0;
131 if (table
->size
> INITIAL_CAPACITY
) {
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
;
144 for (i
= 0; i
< table
->size
; i
++) {
145 item
= table
->table
[i
];
148 RELKEY(table
, item
->key
);
157 unsigned WMCountHashTable(WMHashTable
* table
)
159 return table
->itemCount
;
162 void *WMHashGet(WMHashTable
* table
, const void *key
)
167 h
= HASH(table
, key
);
168 item
= table
->table
[h
];
170 if (table
->callbacks
.keyIsEqual
) {
172 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
179 if (key
== item
->key
) {
186 return (void *)item
->data
;
191 Bool
WMHashGetItemAndKey(WMHashTable
* table
, const void *key
, void **retItem
, void **retKey
)
196 h
= HASH(table
, key
);
197 item
= table
->table
[h
];
199 if (table
->callbacks
.keyIsEqual
) {
201 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
208 if (key
== item
->key
) {
216 *retKey
= (void *)item
->key
;
218 *retItem
= (void *)item
->data
;
225 void *WMHashInsert(WMHashTable
* table
, const void *key
, const void *data
)
231 h
= HASH(table
, key
);
232 /* look for the entry */
233 item
= table
->table
[h
];
234 if (table
->callbacks
.keyIsEqual
) {
236 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
244 if (key
== item
->key
) {
257 RELKEY(table
, item
->key
);
258 item
->key
= DUPKEY(table
, key
);
264 nitem
= wmalloc(sizeof(HashItem
));
265 nitem
->key
= DUPKEY(table
, key
);
267 nitem
->next
= table
->table
[h
];
268 table
->table
[h
] = nitem
;
273 /* OPTIMIZE: put this in an idle handler. */
274 if (table
->itemCount
> table
->size
) {
276 printf("rebuilding hash table...\n");
280 printf("finished rebuild.\n");
287 static HashItem
*deleteFromList(HashTable
* table
, HashItem
* item
, const void *key
)
294 if ((table
->callbacks
.keyIsEqual
&& (*table
->callbacks
.keyIsEqual
) (key
, item
->key
))
295 || (!table
->callbacks
.keyIsEqual
&& key
== item
->key
)) {
298 RELKEY(table
, item
->key
);
306 item
->next
= deleteFromList(table
, item
->next
, key
);
311 void WMHashRemove(WMHashTable
* table
, const void *key
)
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];
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
];
348 if (enumerator
->nextItem
) {
349 data
= ((HashItem
*) enumerator
->nextItem
)->data
;
350 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
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
];
373 if (enumerator
->nextItem
) {
374 key
= ((HashItem
*) enumerator
->nextItem
)->key
;
375 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
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
];
396 if (enumerator
->nextItem
) {
398 *item
= (void *)((HashItem
*) enumerator
->nextItem
)->data
;
400 *key
= (void *)((HashItem
*) enumerator
->nextItem
)->key
;
401 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
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
= {
426 const WMHashTableCallbacks WMStringHashCallbacks
= {
427 (hashFunc
) hashString
,
428 (isEqualFunc
) compareStrings
,
429 (retainFunc
) wstrdup
,
433 const WMHashTableCallbacks WMStringPointerHashCallbacks
= {
434 (hashFunc
) hashString
,
435 (isEqualFunc
) compareStrings
,