pd.if.org Git - zpackage/blob - 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 }