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
));
102 table
->callbacks
= callbacks
;
104 table
->size
= INITIAL_CAPACITY
;
106 table
->table
= wmalloc(sizeof(HashItem
*) * table
->size
);
111 void WMResetHashTable(WMHashTable
* table
)
113 HashItem
*item
, *tmp
;
116 for (i
= 0; i
< table
->size
; i
++) {
117 item
= table
->table
[i
];
120 RELKEY(table
, item
->key
);
126 table
->itemCount
= 0;
128 if (table
->size
> INITIAL_CAPACITY
) {
130 table
->size
= INITIAL_CAPACITY
;
131 table
->table
= wmalloc(sizeof(HashItem
*) * table
->size
);
133 memset(table
->table
, 0, sizeof(HashItem
*) * table
->size
);
137 void WMFreeHashTable(WMHashTable
* table
)
139 HashItem
*item
, *tmp
;
142 for (i
= 0; i
< table
->size
; i
++) {
143 item
= table
->table
[i
];
146 RELKEY(table
, item
->key
);
155 unsigned WMCountHashTable(WMHashTable
* table
)
157 return table
->itemCount
;
160 void *WMHashGet(WMHashTable
* table
, const void *key
)
165 h
= HASH(table
, key
);
166 item
= table
->table
[h
];
168 if (table
->callbacks
.keyIsEqual
) {
170 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
177 if (key
== item
->key
) {
184 return (void *)item
->data
;
189 Bool
WMHashGetItemAndKey(WMHashTable
* table
, const void *key
, void **retItem
, void **retKey
)
194 h
= HASH(table
, key
);
195 item
= table
->table
[h
];
197 if (table
->callbacks
.keyIsEqual
) {
199 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
206 if (key
== item
->key
) {
214 *retKey
= (void *)item
->key
;
216 *retItem
= (void *)item
->data
;
223 void *WMHashInsert(WMHashTable
* table
, const void *key
, const void *data
)
229 h
= HASH(table
, key
);
230 /* look for the entry */
231 item
= table
->table
[h
];
232 if (table
->callbacks
.keyIsEqual
) {
234 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
242 if (key
== item
->key
) {
255 RELKEY(table
, item
->key
);
256 item
->key
= DUPKEY(table
, key
);
262 nitem
= wmalloc(sizeof(HashItem
));
263 nitem
->key
= DUPKEY(table
, key
);
265 nitem
->next
= table
->table
[h
];
266 table
->table
[h
] = nitem
;
271 /* OPTIMIZE: put this in an idle handler. */
272 if (table
->itemCount
> table
->size
) {
274 printf("rebuilding hash table...\n");
278 printf("finished rebuild.\n");
285 static HashItem
*deleteFromList(HashTable
* table
, HashItem
* item
, const void *key
)
292 if ((table
->callbacks
.keyIsEqual
&& (*table
->callbacks
.keyIsEqual
) (key
, item
->key
))
293 || (!table
->callbacks
.keyIsEqual
&& key
== item
->key
)) {
296 RELKEY(table
, item
->key
);
304 item
->next
= deleteFromList(table
, item
->next
, key
);
309 void WMHashRemove(WMHashTable
* table
, const void *key
)
313 h
= HASH(table
, key
);
315 table
->table
[h
] = deleteFromList(table
, table
->table
[h
], key
);
318 WMHashEnumerator
WMEnumerateHashTable(WMHashTable
* table
)
320 WMHashEnumerator enumerator
;
322 enumerator
.table
= table
;
323 enumerator
.index
= 0;
324 enumerator
.nextItem
= table
->table
[0];
329 void *WMNextHashEnumeratorItem(WMHashEnumerator
* enumerator
)
331 const void *data
= NULL
;
333 /* this assumes the table doesn't change between
334 * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
336 if (enumerator
->nextItem
== NULL
) {
337 HashTable
*table
= enumerator
->table
;
338 while (++enumerator
->index
< table
->size
) {
339 if (table
->table
[enumerator
->index
] != NULL
) {
340 enumerator
->nextItem
= table
->table
[enumerator
->index
];
346 if (enumerator
->nextItem
) {
347 data
= ((HashItem
*) enumerator
->nextItem
)->data
;
348 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
354 void *WMNextHashEnumeratorKey(WMHashEnumerator
* enumerator
)
356 const void *key
= NULL
;
358 /* this assumes the table doesn't change between
359 * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
361 if (enumerator
->nextItem
== NULL
) {
362 HashTable
*table
= enumerator
->table
;
363 while (++enumerator
->index
< table
->size
) {
364 if (table
->table
[enumerator
->index
] != NULL
) {
365 enumerator
->nextItem
= table
->table
[enumerator
->index
];
371 if (enumerator
->nextItem
) {
372 key
= ((HashItem
*) enumerator
->nextItem
)->key
;
373 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
379 Bool
WMNextHashEnumeratorItemAndKey(WMHashEnumerator
* enumerator
, void **item
, void **key
)
381 /* this assumes the table doesn't change between
382 * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
384 if (enumerator
->nextItem
== NULL
) {
385 HashTable
*table
= enumerator
->table
;
386 while (++enumerator
->index
< table
->size
) {
387 if (table
->table
[enumerator
->index
] != NULL
) {
388 enumerator
->nextItem
= table
->table
[enumerator
->index
];
394 if (enumerator
->nextItem
) {
396 *item
= (void *)((HashItem
*) enumerator
->nextItem
)->data
;
398 *key
= (void *)((HashItem
*) enumerator
->nextItem
)->key
;
399 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
407 static Bool
compareStrings(const char *key1
, const char *key2
)
409 return strcmp(key1
, key2
) == 0;
412 typedef unsigned (*hashFunc
) (const void *);
413 typedef Bool(*isEqualFunc
) (const void *, const void *);
414 typedef void *(*retainFunc
) (const void *);
415 typedef void (*releaseFunc
) (const void *);
417 const WMHashTableCallbacks WMIntHashCallbacks
= {
424 const WMHashTableCallbacks WMStringHashCallbacks
= {
425 (hashFunc
) hashString
,
426 (isEqualFunc
) compareStrings
,
427 (retainFunc
) wstrdup
,
431 const WMHashTableCallbacks WMStringPointerHashCallbacks
= {
432 (hashFunc
) hashString
,
433 (isEqualFunc
) compareStrings
,