pd.if.org Git - jsw/blob - jsw_hlib.c

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