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
  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 }