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