]> pd.if.org Git - zpackage/blob - lib/jsw/jsw_hlib.c
6cc961ae791bebaa5f46d1f4c395d22e4c3c7e03
[zpackage] / lib / jsw / jsw_hlib.c
1 /*
2   Hash table library using separate chaining
3
4     > Created (Julienne Walker): August 7, 2005
5     > Modified (Julienne Walker): August 11, 2005
6       Added a cast for malloc to enable clean
7       compilation as C++
8 */
9 #include "jsw_hlib.h"
10
11 #ifdef __cplusplus
12 #include <cstdlib>
13
14 using std::malloc;
15 using std::free;
16 #else
17 #include <stdlib.h>
18 #endif
19
20 typedef struct jsw_node {
21   void            *key;  /* Key used for searching */
22   void            *item; /* Actual content of a node */
23   struct jsw_node *next; /* Next link in the chain */
24 } jsw_node_t;
25
26 typedef struct jsw_head {
27   jsw_node_t *first;     /* First link in the chain */
28   size_t      size;      /* Length of the chain */
29 } jsw_head_t;
30
31 struct jsw_hash {
32   jsw_head_t **table;    /* Dynamic chained hash table */
33   size_t       size;     /* Current item count */
34   size_t       capacity; /* Current table size */
35   size_t       curri;    /* Current index for traversal */
36   jsw_node_t  *currl;    /* Current link for traversal */
37   hash_f       hash;     /* User defined key hash function */
38   cmp_f        cmp;      /* User defined key comparison function */
39   keydup_f     keydup;   /* User defined key copy function */
40   itemdup_f    itemdup;  /* User defined item copy function */
41   keyrel_f     keyrel;   /* User defined key delete function */
42   itemrel_f    itemrel;  /* User defined item delete function */
43 };
44
45 static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
46 {
47   jsw_node_t *node = (jsw_node_t *)malloc ( sizeof *node );
48
49   if ( node == NULL )
50     return NULL;
51
52   node->key = key;
53   node->item = item;
54   node->next = next;
55
56   return node;
57 }
58
59 static jsw_head_t *new_chain ( void )
60 {
61   jsw_head_t *chain = (jsw_head_t *)malloc ( sizeof *chain );
62
63   if ( chain == NULL )
64     return NULL;
65
66   chain->first = NULL;
67   chain->size = 0;
68
69   return chain;
70 }
71
72 /*
73   Create a new hash table with a capacity of size, and
74   user defined functions for handling keys and items.
75
76   Returns: An empty hash table, or NULL on failure.
77 */
78 jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
79   keydup_f keydup, itemdup_f itemdup,
80   keyrel_f keyrel, itemrel_f itemrel )
81 {
82   jsw_hash_t *htab = (jsw_hash_t *)malloc ( sizeof *htab );
83   size_t i;
84
85   if ( htab == NULL )
86     return NULL;
87
88   htab->table = (jsw_head_t **)malloc ( size * sizeof *htab->table );
89
90   if ( htab->table == NULL ) {
91     free ( htab );
92     return NULL;
93   }
94
95   /* Empty chains have no head */
96   for ( i = 0; i < size; i++ )
97     htab->table[i] = NULL;
98
99   htab->size = 0;
100   htab->capacity = size;
101   htab->curri = 0;
102   htab->currl = NULL;
103   htab->hash = hash;
104   htab->cmp = cmp;
105   htab->keydup = keydup;
106   htab->itemdup = itemdup;
107   htab->keyrel = keyrel;
108   htab->itemrel = itemrel;
109
110   return htab;
111 }
112
113 /* Release all memory used by the hash table */
114 void jsw_hdelete ( jsw_hash_t *htab )
115 {
116   size_t i;
117
118   /* Release each chain individually */
119   for ( i = 0; i < htab->capacity; i++ ) {
120     jsw_node_t *save, *it;
121
122     if ( htab->table[i] == NULL )
123       continue;
124
125     it = htab->table[i]->first;
126
127     for ( ; it != NULL; it = save ) {
128       save = it->next;
129       htab->keyrel ( it->key );
130       htab->itemrel ( it->item );
131       free ( it );
132     }
133
134     free ( htab->table[i] );
135   }
136
137   /* Release the hash table */
138   free ( htab->table );
139   free ( htab );
140 }
141
142 /*
143   Find an item with the selected key
144
145   Returns: The item, or NULL if not found
146 */
147 void *jsw_hfind ( jsw_hash_t *htab, void *key )
148 {
149   unsigned h = htab->hash ( key ) % htab->capacity;
150
151   /* Search the chain only if it exists */
152   if ( htab->table[h] != NULL ) {
153     jsw_node_t *it = htab->table[h]->first;
154
155     for ( ; it != NULL; it = it->next ) {
156       if ( htab->cmp ( key, it->key ) == 0 )
157         return it->item;
158     }
159   }
160
161   return NULL;
162 }
163
164 /*
165   Insert an item with the selected key
166
167   Returns: non-zero for success, zero for failure
168 */
169 int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
170 {
171   unsigned h = htab->hash ( key ) % htab->capacity;
172   void *dupkey, *dupitem;
173   jsw_node_t *new_item;
174
175   /* Disallow duplicate keys */
176   if ( jsw_hfind ( htab, key ) != NULL )
177     return 0;
178
179   /* Attempt to create a new item */
180   dupkey = htab->keydup ( key );
181   dupitem = htab->itemdup ( item );
182
183   new_item = new_node ( dupkey, dupitem, NULL );
184
185   if ( new_item == NULL )
186     return 0;
187
188   /* Create a chain if the bucket is empty */
189   if ( htab->table[h] == NULL ) {
190     htab->table[h] = new_chain();
191
192     if ( htab->table[h] == NULL ) {
193       htab->keyrel ( new_item->key );
194       htab->itemrel ( new_item->item );
195       free ( new_item );
196       return 0;
197     }
198   }
199
200   /* Insert at the front of the chain */
201   new_item->next = htab->table[h]->first;
202   htab->table[h]->first = new_item;
203
204   ++htab->table[h]->size;
205   ++htab->size;
206
207   return 1;
208 }
209
210 /*
211   Remove an item with the selected key
212
213   Returns: non-zero for success, zero for failure
214 */
215 int jsw_herase ( jsw_hash_t *htab, void *key )
216 {
217   unsigned h = htab->hash ( key ) % htab->capacity;
218   jsw_node_t *save, *it;
219
220   if ( htab->table[h] == NULL )
221     return 0;
222
223   it = htab->table[h]->first;
224
225   /* Remove the first node in the chain? */
226   if ( htab->cmp ( key, it->key ) == 0 ) {
227     htab->table[h]->first = it->next;
228
229     /* Release the node's memory */
230     htab->keyrel ( it->key );
231     htab->itemrel ( it->item );
232     free ( it );
233
234     /* Remove the chain if it's empty */
235     if ( htab->table[h]->first == NULL ) {
236       free ( htab->table[h] );
237       htab->table[h] = NULL;
238     }
239     else
240       --htab->table[h]->size;
241   }
242   else {
243     /* Search for the node */
244     while ( it->next != NULL ) {
245       if ( htab->cmp ( key, it->next->key ) == 0 )
246         break;
247
248       it = it->next;
249     }
250
251     /* Not found? */
252     if ( it->next == NULL )
253       return 0;
254
255     save = it->next;
256     it->next = it->next->next;
257
258     /* Release the node's memory */
259     htab->keyrel ( save->key );
260     htab->itemrel ( save->item );
261     free ( save );
262
263     --htab->table[h]->size;
264   }
265
266   /* Erasure invalidates traversal markers */
267   jsw_hreset ( htab );
268
269   --htab->size;
270
271   return 1;
272 }
273
274 /*
275   Grow or shrink the table, this is a slow operation
276   
277   Returns: non-zero for success, zero for failure
278 */
279 int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
280 {
281   jsw_hash_t *new_htab;
282   jsw_node_t *it;
283   size_t i;
284
285   /* Build a new hash table, then assign it to the old one */
286   new_htab = jsw_hnew ( new_size, htab->hash, htab->cmp,
287     htab->keydup, htab->itemdup, htab->keyrel, htab->itemrel );
288
289   if ( new_htab == NULL )
290     return 0;
291
292   for ( i = 0; i < htab->capacity; i++ ) {
293     if ( htab->table[i] == NULL )
294       continue;
295
296     for ( it = htab->table[i]->first; it != NULL; it = it->next )
297       jsw_hinsert ( new_htab, it->key, it->item );
298   }
299
300   /* A hash table holds copies, so release the old table */
301   jsw_hdelete ( htab );
302   htab = new_htab;
303
304   return 1;
305 }
306
307 /* Reset the traversal markers to the beginning */
308 void jsw_hreset ( jsw_hash_t *htab )
309 {
310   size_t i;
311
312   htab->curri = 0;
313   htab->currl = NULL;
314
315   /* Find the first non-empty bucket */
316   for ( i = 0; i < htab->capacity; i++ ) {
317     if ( htab->table[i] != NULL )
318       break;
319   }
320
321   htab->curri = i;
322
323   /* Set the link marker if the table was not empty */
324   if ( i != htab->capacity )
325     htab->currl = htab->table[i]->first;
326 }
327
328 /* Traverse forward by one key */
329 int jsw_hnext ( jsw_hash_t *htab )
330 {
331   if ( htab->currl != NULL ) {
332     htab->currl = htab->currl->next;
333
334     /* At the end of the chain? */
335     if ( htab->currl == NULL ) {
336       /* Find the next chain */
337       while ( ++htab->curri < htab->capacity ) {
338         if ( htab->table[htab->curri] != NULL )
339           break;
340       }
341
342       /* No more chains? */
343       if ( htab->curri == htab->capacity )
344         return 0;
345
346       htab->currl = htab->table[htab->curri]->first;
347     }
348   }
349
350   return 1;
351 }
352
353 /* Get the current key */
354 const void *jsw_hkey ( jsw_hash_t *htab )
355 {
356   return htab->currl != NULL ? htab->currl->key : NULL;
357 }
358
359 /* Get the current item */
360 void *jsw_hitem ( jsw_hash_t *htab )
361 {
362   return htab->currl != NULL ? htab->currl->item : NULL;
363 }
364
365 /* Current number of items in the table */
366 size_t jsw_hsize ( jsw_hash_t *htab )
367 {
368   return htab->size;
369 }
370
371 /* Total allowable number of items without resizing */
372 size_t jsw_hcapacity ( jsw_hash_t *htab )
373 {
374   return htab->capacity;
375 }
376
377 /* Get statistics for the hash table */
378 jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )
379 {
380   jsw_hstat_t *stat;
381   double sum = 0, used = 0;
382   size_t i;
383
384   /* No stats for an empty table */
385   if ( htab->size == 0 )
386     return NULL;
387
388   stat = (jsw_hstat_t *)malloc ( sizeof *stat );
389
390   if ( stat == NULL )
391     return NULL;
392
393   stat->lchain = 0;
394   stat->schain = (size_t)-1;
395
396   for ( i = 0; i < htab->capacity; i++ ) {
397     if ( htab->table[i] != NULL ) {
398       sum += htab->table[i]->size;
399
400       ++used; /* Non-empty buckets */
401
402       if ( htab->table[i]->size > stat->lchain )
403         stat->lchain = htab->table[i]->size;
404
405       if ( htab->table[i]->size < stat->schain )
406         stat->schain = htab->table[i]->size;
407     }
408   }
409
410   stat->load = used / htab->capacity;
411   stat->achain = sum / used;
412
413   return stat;
414 }