13 #define INITIAL_CAPACITY 23
16 #if defined(__GNUC__) && !defined(__STRICT_ANSI__)
17 # define INLINE inline
23 typedef struct HashItem
{
27 struct HashItem
*next
; /* collided item list */
31 typedef struct W_HashTable
{
32 WMHashTableCallbacks callbacks
;
35 unsigned size
; /* table size */
43 #define HASH(table, key) (((table)->callbacks.hash ? \
44 (*(table)->callbacks.hash)(key) : hashPtr(key)) % (table)->size)
46 #define DUPKEY(table, key) ((table)->callbacks.retainKey ? \
47 (*(table)->callbacks.retainKey)(key) : (key))
49 #define RELKEY(table, key) if ((table)->callbacks.releaseKey) \
50 (*(table)->callbacks.releaseKey)(key)
55 static INLINE
unsigned
56 hashString(const char *key
)
62 ret
^= *(char*)key
++ << ctr
;
63 ctr
= (ctr
+ 1) % sizeof (char *);
71 static INLINE
unsigned
72 hashPtr(const void *key
)
74 return ((size_t)key
/ sizeof(char*));
81 rellocateItem(WMHashTable
*table
, HashItem
*item
)
85 h
= HASH(table
, item
->key
);
87 item
->next
= table
->table
[h
];
88 table
->table
[h
] = item
;
93 rebuildTable(WMHashTable
*table
)
101 oldArray
= table
->table
;
102 oldSize
= table
->size
;
104 newSize
= table
->size
*2;
106 table
->table
= wmalloc(sizeof(char*)*newSize
);
107 memset(table
->table
, 0, sizeof(char*)*newSize
);
108 table
->size
= newSize
;
110 for (i
= 0; i
< oldSize
; i
++) {
111 while (oldArray
[i
]!=NULL
) {
112 next
= oldArray
[i
]->next
;
113 rellocateItem(table
, oldArray
[i
]);
123 WMCreateHashTable(WMHashTableCallbacks callbacks
)
127 table
= wmalloc(sizeof(HashTable
));
128 memset(table
, 0, sizeof(HashTable
));
130 table
->callbacks
= callbacks
;
132 table
->size
= INITIAL_CAPACITY
;
134 table
->table
= wmalloc(sizeof(HashItem
*)*table
->size
);
135 memset(table
->table
, 0, sizeof(HashItem
*)*table
->size
);
142 WMResetHashTable(WMHashTable
*table
)
144 HashItem
*item
, *tmp
;
147 for (i
= 0; i
< table
->size
; i
++) {
148 item
= table
->table
[i
];
157 table
->itemCount
= 0;
159 if (table
->size
> INITIAL_CAPACITY
) {
161 table
->size
= INITIAL_CAPACITY
;
162 table
->table
= wmalloc(sizeof(HashItem
*)*table
->size
);
164 memset(table
->table
, 0, sizeof(HashItem
*)*table
->size
);
169 WMFreeHashTable(WMHashTable
*table
)
171 HashItem
*item
, *tmp
;
174 for (i
= 0; i
< table
->size
; i
++) {
175 item
= table
->table
[i
];
178 RELKEY(table
, item
->key
);
189 WMCountHashTable(WMHashTable
*table
)
191 return table
->itemCount
;
196 WMHashGet(WMHashTable
*table
, const void *key
)
201 h
= HASH(table
, key
);
202 item
= table
->table
[h
];
204 if (table
->callbacks
.keyIsEqual
) {
206 if ((*table
->callbacks
.keyIsEqual
)(key
, item
->key
)) {
213 if (key
== item
->key
) {
220 return (void*)item
->data
;
228 WMHashInsert(WMHashTable
*table
, const void *key
, const void *data
)
234 h
= HASH(table
, key
);
235 /* look for the entry */
236 item
= table
->table
[h
];
237 if (table
->callbacks
.keyIsEqual
) {
239 if ((*table
->callbacks
.keyIsEqual
)(key
, item
->key
)) {
247 if (key
== item
->key
) {
260 RELKEY(table
, item
->key
);
261 item
->key
= DUPKEY(table
, key
);
267 nitem
= wmalloc(sizeof(HashItem
));
268 nitem
->key
= DUPKEY(table
, key
);
270 nitem
->next
= table
->table
[h
];
271 table
->table
[h
] = nitem
;
276 /* OPTIMIZE: put this in an idle handler.*/
277 if (table
->itemCount
> table
->size
) {
279 printf("rebuilding hash table...\n");
283 printf("finished rebuild.\n");
292 deleteFromList(HashTable
*table
, HashItem
*item
, const void *key
)
299 if ((table
->callbacks
.keyIsEqual
300 && (*table
->callbacks
.keyIsEqual
)(key
, item
->key
))
301 || (!table
->callbacks
.keyIsEqual
&& key
==item
->key
)) {
304 RELKEY(table
, item
->key
);
312 item
->next
= deleteFromList(table
, item
->next
, key
);
319 WMHashRemove(WMHashTable
*table
, const void *key
)
323 h
= HASH(table
, key
);
325 table
->table
[h
] = deleteFromList(table
, table
->table
[h
], key
);
330 WMEnumerateHashTable(WMHashTable
*table
)
332 WMHashEnumerator enumerator
;
334 enumerator
.table
= table
;
335 enumerator
.index
= 0;
336 enumerator
.nextItem
= table
->table
[0];
344 WMNextHashEnumeratorItem(WMHashEnumerator
*enumerator
)
346 const void *data
= NULL
;
348 /* this assumes the table doesn't change between
349 * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
351 if (enumerator
->nextItem
==NULL
) {
352 HashTable
*table
= enumerator
->table
;
353 while (++enumerator
->index
< table
->size
) {
354 if (table
->table
[enumerator
->index
]!=NULL
) {
355 enumerator
->nextItem
= table
->table
[enumerator
->index
];
361 if (enumerator
->nextItem
) {
362 data
= ((HashItem
*)enumerator
->nextItem
)->data
;
363 enumerator
->nextItem
= ((HashItem
*)enumerator
->nextItem
)->next
;
371 WMNextHashEnumeratorKey(WMHashEnumerator
*enumerator
)
373 const void *key
= NULL
;
375 /* this assumes the table doesn't change between
376 * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
378 if (enumerator
->nextItem
==NULL
) {
379 HashTable
*table
= enumerator
->table
;
380 while (++enumerator
->index
< table
->size
) {
381 if (table
->table
[enumerator
->index
]!=NULL
) {
382 enumerator
->nextItem
= table
->table
[enumerator
->index
];
388 if (enumerator
->nextItem
) {
389 key
= ((HashItem
*)enumerator
->nextItem
)->key
;
390 enumerator
->nextItem
= ((HashItem
*)enumerator
->nextItem
)->next
;
398 WMNextHashEnumeratorItemAndKey(WMHashEnumerator
*enumerator
,
399 void **item
, void **key
)
401 const void *data
= NULL
;
403 /* this assumes the table doesn't change between
404 * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
406 if (enumerator
->nextItem
==NULL
) {
407 HashTable
*table
= enumerator
->table
;
408 while (++enumerator
->index
< table
->size
) {
409 if (table
->table
[enumerator
->index
]!=NULL
) {
410 enumerator
->nextItem
= table
->table
[enumerator
->index
];
416 if (enumerator
->nextItem
) {
417 *item
= (void*)((HashItem
*)enumerator
->nextItem
)->data
;
418 *key
= (void*)((HashItem
*)enumerator
->nextItem
)->key
;
419 enumerator
->nextItem
= ((HashItem
*)enumerator
->nextItem
)->next
;
429 compareStrings(const char *key1
, const char *key2
)
431 return strcmp(key1
, key2
)==0;
435 typedef unsigned (*hashFunc
)(const void*);
436 typedef Bool (*isEqualFunc
)(const void*, const void*);
437 typedef void* (*retainFunc
)(const void*);
438 typedef void (*releaseFunc
)(const void*);
441 const WMHashTableCallbacks WMIntHashCallbacks
= {
448 const WMHashTableCallbacks WMStringHashCallbacks
= {
449 (hashFunc
)hashString
,
450 (isEqualFunc
)compareStrings
,
457 const WMHashTableCallbacks WMStringPointerHashCallbacks
= {
458 (hashFunc
)hashString
,
459 (isEqualFunc
)compareStrings
,