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 table
->size
= newSize
;
86 for (i
= 0; i
< oldSize
; i
++) {
87 while (oldArray
[i
] != NULL
) {
88 next
= oldArray
[i
]->next
;
89 rellocateItem(table
, oldArray
[i
]);
96 WMHashTable
*WMCreateHashTable(WMHashTableCallbacks callbacks
)
100 table
= wmalloc(sizeof(HashTable
));
101 memset(table
, 0, sizeof(HashTable
));
103 table
->callbacks
= callbacks
;
105 table
->size
= INITIAL_CAPACITY
;
107 table
->table
= wmalloc(sizeof(HashItem
*) * table
->size
);
108 memset(table
->table
, 0, sizeof(HashItem
*) * table
->size
);
113 void WMResetHashTable(WMHashTable
* table
)
115 HashItem
*item
, *tmp
;
118 for (i
= 0; i
< table
->size
; i
++) {
119 item
= table
->table
[i
];
122 RELKEY(table
, item
->key
);
128 table
->itemCount
= 0;
130 if (table
->size
> INITIAL_CAPACITY
) {
132 table
->size
= INITIAL_CAPACITY
;
133 table
->table
= wmalloc(sizeof(HashItem
*) * table
->size
);
135 memset(table
->table
, 0, sizeof(HashItem
*) * table
->size
);
138 void WMFreeHashTable(WMHashTable
* table
)
140 HashItem
*item
, *tmp
;
143 for (i
= 0; i
< table
->size
; i
++) {
144 item
= table
->table
[i
];
147 RELKEY(table
, item
->key
);
156 unsigned WMCountHashTable(WMHashTable
* table
)
158 return table
->itemCount
;
161 void *WMHashGet(WMHashTable
* table
, const void *key
)
166 h
= HASH(table
, key
);
167 item
= table
->table
[h
];
169 if (table
->callbacks
.keyIsEqual
) {
171 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
178 if (key
== item
->key
) {
185 return (void *)item
->data
;
190 Bool
WMHashGetItemAndKey(WMHashTable
* table
, const void *key
, void **retItem
, void **retKey
)
195 h
= HASH(table
, key
);
196 item
= table
->table
[h
];
198 if (table
->callbacks
.keyIsEqual
) {
200 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
207 if (key
== item
->key
) {
215 *retKey
= (void *)item
->key
;
217 *retItem
= (void *)item
->data
;
224 void *WMHashInsert(WMHashTable
* table
, const void *key
, const void *data
)
230 h
= HASH(table
, key
);
231 /* look for the entry */
232 item
= table
->table
[h
];
233 if (table
->callbacks
.keyIsEqual
) {
235 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
243 if (key
== item
->key
) {
256 RELKEY(table
, item
->key
);
257 item
->key
= DUPKEY(table
, key
);
263 nitem
= wmalloc(sizeof(HashItem
));
264 nitem
->key
= DUPKEY(table
, key
);
266 nitem
->next
= table
->table
[h
];
267 table
->table
[h
] = nitem
;
272 /* OPTIMIZE: put this in an idle handler. */
273 if (table
->itemCount
> table
->size
) {
275 printf("rebuilding hash table...\n");
279 printf("finished rebuild.\n");
286 static HashItem
*deleteFromList(HashTable
* table
, HashItem
* item
, const void *key
)
293 if ((table
->callbacks
.keyIsEqual
&& (*table
->callbacks
.keyIsEqual
) (key
, item
->key
))
294 || (!table
->callbacks
.keyIsEqual
&& key
== item
->key
)) {
297 RELKEY(table
, item
->key
);
305 item
->next
= deleteFromList(table
, item
->next
, key
);
310 void WMHashRemove(WMHashTable
* table
, const void *key
)
314 h
= HASH(table
, key
);
316 table
->table
[h
] = deleteFromList(table
, table
->table
[h
], key
);
319 WMHashEnumerator
WMEnumerateHashTable(WMHashTable
* table
)
321 WMHashEnumerator enumerator
;
323 enumerator
.table
= table
;
324 enumerator
.index
= 0;
325 enumerator
.nextItem
= table
->table
[0];
330 void *WMNextHashEnumeratorItem(WMHashEnumerator
* enumerator
)
332 const void *data
= NULL
;
334 /* this assumes the table doesn't change between
335 * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
337 if (enumerator
->nextItem
== NULL
) {
338 HashTable
*table
= enumerator
->table
;
339 while (++enumerator
->index
< table
->size
) {
340 if (table
->table
[enumerator
->index
] != NULL
) {
341 enumerator
->nextItem
= table
->table
[enumerator
->index
];
347 if (enumerator
->nextItem
) {
348 data
= ((HashItem
*) enumerator
->nextItem
)->data
;
349 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
355 void *WMNextHashEnumeratorKey(WMHashEnumerator
* enumerator
)
357 const void *key
= NULL
;
359 /* this assumes the table doesn't change between
360 * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
362 if (enumerator
->nextItem
== NULL
) {
363 HashTable
*table
= enumerator
->table
;
364 while (++enumerator
->index
< table
->size
) {
365 if (table
->table
[enumerator
->index
] != NULL
) {
366 enumerator
->nextItem
= table
->table
[enumerator
->index
];
372 if (enumerator
->nextItem
) {
373 key
= ((HashItem
*) enumerator
->nextItem
)->key
;
374 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
380 Bool
WMNextHashEnumeratorItemAndKey(WMHashEnumerator
* enumerator
, void **item
, void **key
)
382 /* this assumes the table doesn't change between
383 * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
385 if (enumerator
->nextItem
== NULL
) {
386 HashTable
*table
= enumerator
->table
;
387 while (++enumerator
->index
< table
->size
) {
388 if (table
->table
[enumerator
->index
] != NULL
) {
389 enumerator
->nextItem
= table
->table
[enumerator
->index
];
395 if (enumerator
->nextItem
) {
397 *item
= (void *)((HashItem
*) enumerator
->nextItem
)->data
;
399 *key
= (void *)((HashItem
*) enumerator
->nextItem
)->key
;
400 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
408 static Bool
compareStrings(const char *key1
, const char *key2
)
410 return strcmp(key1
, key2
) == 0;
413 typedef unsigned (*hashFunc
) (const void *);
414 typedef Bool(*isEqualFunc
) (const void *, const void *);
415 typedef void *(*retainFunc
) (const void *);
416 typedef void (*releaseFunc
) (const void *);
418 const WMHashTableCallbacks WMIntHashCallbacks
= {
425 const WMHashTableCallbacks WMStringHashCallbacks
= {
426 (hashFunc
) hashString
,
427 (isEqualFunc
) compareStrings
,
428 (retainFunc
) wstrdup
,
432 const WMHashTableCallbacks WMStringPointerHashCallbacks
= {
433 (hashFunc
) hashString
,
434 (isEqualFunc
) compareStrings
,