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