10 #define INITIAL_CAPACITY 23
13 typedef struct HashItem
{
17 struct HashItem
*next
; /* collided item list */
20 typedef struct W_HashTable
{
21 WMHashTableCallbacks callbacks
;
24 unsigned size
; /* table size */
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
;
46 ctr
= (ctr
+ 1) % sizeof(char *);
52 static inline unsigned hashPtr(const void *key
)
54 return ((size_t) key
/ sizeof(char *));
57 static void rellocateItem(WMHashTable
* table
, HashItem
* item
)
61 h
= HASH(table
, item
->key
);
63 item
->next
= table
->table
[h
];
64 table
->table
[h
] = item
;
67 static void rebuildTable(WMHashTable
* table
)
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
]);
93 WMHashTable
*WMCreateHashTable(const WMHashTableCallbacks callbacks
)
97 table
= wmalloc(sizeof(HashTable
));
99 table
->callbacks
= callbacks
;
101 table
->size
= INITIAL_CAPACITY
;
103 table
->table
= wmalloc(sizeof(HashItem
*) * table
->size
);
108 void WMResetHashTable(WMHashTable
* table
)
110 HashItem
*item
, *tmp
;
113 for (i
= 0; i
< table
->size
; i
++) {
114 item
= table
->table
[i
];
117 RELKEY(table
, item
->key
);
123 table
->itemCount
= 0;
125 if (table
->size
> INITIAL_CAPACITY
) {
127 table
->size
= INITIAL_CAPACITY
;
128 table
->table
= wmalloc(sizeof(HashItem
*) * table
->size
);
130 memset(table
->table
, 0, sizeof(HashItem
*) * table
->size
);
134 void WMFreeHashTable(WMHashTable
* table
)
136 HashItem
*item
, *tmp
;
139 for (i
= 0; i
< table
->size
; i
++) {
140 item
= table
->table
[i
];
143 RELKEY(table
, item
->key
);
152 unsigned WMCountHashTable(WMHashTable
* table
)
154 return table
->itemCount
;
157 void *WMHashGet(WMHashTable
* table
, const void *key
)
162 h
= HASH(table
, key
);
163 item
= table
->table
[h
];
165 if (table
->callbacks
.keyIsEqual
) {
167 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
174 if (key
== item
->key
) {
181 return (void *)item
->data
;
186 Bool
WMHashGetItemAndKey(WMHashTable
* table
, const void *key
, void **retItem
, void **retKey
)
191 h
= HASH(table
, key
);
192 item
= table
->table
[h
];
194 if (table
->callbacks
.keyIsEqual
) {
196 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
203 if (key
== item
->key
) {
211 *retKey
= (void *)item
->key
;
213 *retItem
= (void *)item
->data
;
220 void *WMHashInsert(WMHashTable
* table
, const void *key
, const void *data
)
226 h
= HASH(table
, key
);
227 /* look for the entry */
228 item
= table
->table
[h
];
229 if (table
->callbacks
.keyIsEqual
) {
231 if ((*table
->callbacks
.keyIsEqual
) (key
, item
->key
)) {
239 if (key
== item
->key
) {
252 RELKEY(table
, item
->key
);
253 item
->key
= DUPKEY(table
, key
);
259 nitem
= wmalloc(sizeof(HashItem
));
260 nitem
->key
= DUPKEY(table
, key
);
262 nitem
->next
= table
->table
[h
];
263 table
->table
[h
] = nitem
;
268 /* OPTIMIZE: put this in an idle handler. */
269 if (table
->itemCount
> table
->size
) {
271 printf("rebuilding hash table...\n");
275 printf("finished rebuild.\n");
282 static HashItem
*deleteFromList(HashTable
* table
, HashItem
* item
, const void *key
)
289 if ((table
->callbacks
.keyIsEqual
&& (*table
->callbacks
.keyIsEqual
) (key
, item
->key
))
290 || (!table
->callbacks
.keyIsEqual
&& key
== item
->key
)) {
293 RELKEY(table
, item
->key
);
301 item
->next
= deleteFromList(table
, item
->next
, key
);
306 void WMHashRemove(WMHashTable
* table
, const void *key
)
310 h
= HASH(table
, key
);
312 table
->table
[h
] = deleteFromList(table
, table
->table
[h
], key
);
315 WMHashEnumerator
WMEnumerateHashTable(WMHashTable
* table
)
317 WMHashEnumerator enumerator
;
319 enumerator
.table
= table
;
320 enumerator
.index
= 0;
321 enumerator
.nextItem
= table
->table
[0];
326 void *WMNextHashEnumeratorItem(WMHashEnumerator
* enumerator
)
328 const void *data
= NULL
;
330 /* this assumes the table doesn't change between
331 * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
333 if (enumerator
->nextItem
== NULL
) {
334 HashTable
*table
= enumerator
->table
;
335 while (++enumerator
->index
< table
->size
) {
336 if (table
->table
[enumerator
->index
] != NULL
) {
337 enumerator
->nextItem
= table
->table
[enumerator
->index
];
343 if (enumerator
->nextItem
) {
344 data
= ((HashItem
*) enumerator
->nextItem
)->data
;
345 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
351 void *WMNextHashEnumeratorKey(WMHashEnumerator
* enumerator
)
353 const void *key
= NULL
;
355 /* this assumes the table doesn't change between
356 * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
358 if (enumerator
->nextItem
== NULL
) {
359 HashTable
*table
= enumerator
->table
;
360 while (++enumerator
->index
< table
->size
) {
361 if (table
->table
[enumerator
->index
] != NULL
) {
362 enumerator
->nextItem
= table
->table
[enumerator
->index
];
368 if (enumerator
->nextItem
) {
369 key
= ((HashItem
*) enumerator
->nextItem
)->key
;
370 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
376 Bool
WMNextHashEnumeratorItemAndKey(WMHashEnumerator
* enumerator
, void **item
, void **key
)
378 /* this assumes the table doesn't change between
379 * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
381 if (enumerator
->nextItem
== NULL
) {
382 HashTable
*table
= enumerator
->table
;
383 while (++enumerator
->index
< table
->size
) {
384 if (table
->table
[enumerator
->index
] != NULL
) {
385 enumerator
->nextItem
= table
->table
[enumerator
->index
];
391 if (enumerator
->nextItem
) {
393 *item
= (void *)((HashItem
*) enumerator
->nextItem
)->data
;
395 *key
= (void *)((HashItem
*) enumerator
->nextItem
)->key
;
396 enumerator
->nextItem
= ((HashItem
*) enumerator
->nextItem
)->next
;
404 static Bool
compareStrings(const void *param1
, const void *param2
)
406 const char *key1
= param1
;
407 const char *key2
= param2
;
409 return strcmp(key1
, key2
) == 0;
412 typedef void *(*retainFunc
) (const void *);
413 typedef void (*releaseFunc
) (const void *);
415 const WMHashTableCallbacks WMIntHashCallbacks
= {
422 const WMHashTableCallbacks WMStringHashCallbacks
= {
425 (retainFunc
) wstrdup
,
429 const WMHashTableCallbacks WMStringPointerHashCallbacks
= {