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