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