src/libopensrf/osrf_hash.c

   1 /**
   2         @file osrf_hash.c
   3         @brief A hybrid between a hash table and a doubly linked list.
   4 */
   5
   6 /*
   7 Copyright (C) 2007, 2008  Georgia Public Library Service
   8 Bill Erickson <erickson@esilibrary.com>
   9
  10 This program is free software; you can redistribute it and/or
  11 modify it under the terms of the GNU General Public License
  12 as published by the Free Software Foundation; either version 2
  13 of the License, or (at your option) any later version.
  14
  15 This program is distributed in the hope that it will be useful,
  16 but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 GNU General Public License for more details.
  19 */
  20
  21 #include <opensrf/osrf_hash.h>
  22
  23 /**
  24         @brief A node storing a single item within an osrfHash.
  25 */
  26 struct _osrfHashNodeStruct {
  27         /** @brief String containing the key for the item */
  28         char* key;
  29         /** @brief Pointer to the stored item data */
  30         void* item;
  31         /** @brief Pointer to the next node in a doubly linked list */
  32         struct _osrfHashNodeStruct* prev;
  33         /** @brief Pointer to the previous node in a doubly linked list */
  34         struct _osrfHashNodeStruct* next;
  35 };
  36 typedef struct _osrfHashNodeStruct osrfHashNode;
  37
  38 /**
  39         @brief osrfHash structure
  40
  41         An osrfHash is partly a key/value store based on a hash table, and partly a linear
  42         structure implemented as a linked list.
  43
  44         The hash table is an array of pointers, managed by an osrfList.  Each pointer in that array
  45         points to another layer of osrfList, which stores pointers to osrfHashNodes for keys that
  46         hash to the same value.
  47
  48         Besides residing in this hash table structure, each osrfHashNode resides in a doubly
  49         linked list that includes all the osrfHashNodes in the osrfHash (except for any nodes
  50         that have been logically deleted).  New nodes are added to the end of the list.
  51
  52         The hash table supports lookups based on a key.
  53
  54         The linked list supports sequential traversal, reflecting the sequence in which the nodes
  55         were added.
  56 */
  57 struct _osrfHashStruct {
  58         /** @brief Pointer to the osrfList used as a hash table */
  59         osrfList* hash;
  60         /** @brief Callback function for freeing stored items */
  61         void (*freeItem) (char* key, void* item);
  62         /** @brief How many items are in the osrfHash */
  63         unsigned int size;
  64         /** @brief Pointer to the first node in the linked list */
  65         osrfHashNode* first_key;
  66         /** @brief Pointer to the last node in the linked list */
  67         osrfHashNode* last_key;
  68 };
  69
  70 /**
  71         @brief Maintains a position in an osrfHash, for traversing the linked list
  72 */
  73 struct _osrfHashIteratorStruct {
  74         /** @brief Pointer to the associated osrfHash */
  75         osrfHash* hash;
  76         /** @brief Pointer to the current osrfHashNode (the one previously returned, if any) */
  77         osrfHashNode* curr_node;
  78 };
  79
  80 /**
  81         @brief How many slots in the hash table.
  82
  83         Must be a power of 2, or the hashing algorithm won't work properly.
  84 */
  85 /* 0x100 is a good size for small hashes */
  86 //#define OSRF_HASH_LIST_SIZE 0x100  /* size of the main hash list */
  87 #define OSRF_HASH_LIST_SIZE 0x10  /* size of the main hash list */
  88
  89
  90 /* used internally */
  91 /**
  92         @brief Free an osrfHashNode, and its cargo, from within a given osrfHash.
  93         @param h Pointer to the osrfHash
  94         @param n Pointer to the osrfHashNode
  95
  96         If there is a callback function for freeing the item, call it.
  97
  98         We use this macro only when freeing an entire osrfHash.
  99 */
 100 #define OSRF_HASH_NODE_FREE(h, n) \
 101         if(h && n) { \
 102                 if(h->freeItem && n->key) h->freeItem(n->key, n->item);\
 103                 free(n->key); free(n); \
 104 }
 105
 106 /**
 107         @brief Create and initialize a new (and empty) osrfHash.
 108         @return Pointer to the newly created osrfHash.
 109
 110         The calling code is responsible for freeing the osrfHash.
 111 */
 112 osrfHash* osrfNewHash() {
 113         osrfHash* hash;
 114         OSRF_MALLOC(hash, sizeof(osrfHash));
 115         hash->hash              = osrfNewListSize( OSRF_HASH_LIST_SIZE );
 116         hash->first_key = NULL;
 117         hash->last_key  = NULL;
 118         return hash;
 119 }
 120
 121 static osrfHashNode* osrfNewHashNode(char* key, void* item);
 122
 123 /*
 124 static unsigned int osrfHashMakeKey(char* str) {
 125         if(!str) return 0;
 126         unsigned int len = strlen(str);
 127         unsigned int h = len;
 128         unsigned int i = 0;
 129         for(i = 0; i < len; str++, i++)
 130                 h = ((h << 5) ^ (h >> 27)) ^ (*str);
 131         return (h & (OSRF_HASH_LIST_SIZE-1));
 132 }
 133 */
 134
 135 /* macro version of the above function */
 136 /**
 137         @brief Hashing algorithm: derive a mangled number from a string.
 138         @param str Pointer to the string to be hashed.
 139         @param num A numeric variable to receive the resulting value.
 140
 141         This macro implements an algorithm proposed by Donald E. Knuth
 142         in The Art of Computer Programming Volume 3 (more or less..)
 143 */
 144 #define OSRF_HASH_MAKE_KEY(str,num) \
 145    do {\
 146       const char* k__ = str;\
 147       unsigned int len__ = strlen(k__); \
 148       unsigned int h__ = len__;\
 149       unsigned int i__ = 0;\
 150       for(i__ = 0; i__ < len__; k__++, i__++)\
 151          h__ = ((h__ << 5) ^ (h__ >> 27)) ^ (*k__);\
 152       num = (h__ & (OSRF_HASH_LIST_SIZE-1));\
 153    } while(0)
 154
 155 /**
 156         @brief Install a callback function for freeing a stored item.
 157         @param hash The osrfHash in which the callback function is to be installed.
 158         @param callback A function pointer.
 159
 160         The callback function must accept a key value and a void pointer, and return void.  The
 161         key value enables the callback function to treat different kinds of items differently,
 162         provided that it can distinguish them by key.
 163 */
 164 void osrfHashSetCallback( osrfHash* hash, void (*callback) (char* key, void* item) )
 165 {
 166         if( hash ) hash->freeItem = callback;
 167 }
 168
 169 /* Returns a pointer to the item's node if found; otherwise returns NULL. */
 170 /**
 171         @brief Search for a given key in an osrfHash.
 172         @param hash Pointer to the osrfHash.
 173         @param key The key to be sought.
 174         @param bucketkey Pointer through which we can report which slot the item belongs in.
 175         @return A pointer to the osrfHashNode where the item resides; or NULL, if it isn't there.
 176
 177         If the bucketkey parameter is not NULL, we update the index of the hash bucket where the
 178         item belongs (whether or not we actually found it).  In some cases this feedback enables the
 179         calling function to avoid hashing the same key twice.
 180 */
 181 static osrfHashNode* find_item( const osrfHash* hash,
 182                 const char* key, unsigned int* bucketkey ) {
 183
 184         // Find the sub-list in the hash table
 185
 186         if( hash->size < 6 && !bucketkey )
 187         {
 188                 // For only a few entries, when we don't need to identify
 189                 // the hash bucket, it's probably faster to search the
 190                 // linked list instead of hashing
 191
 192                 osrfHashNode* currnode = hash->first_key;
 193                 while( currnode && strcmp( currnode->key, key ) )
 194                          currnode = currnode->next;
 195
 196                 return currnode;
 197         }
 198
 199         unsigned int i = 0;
 200         OSRF_HASH_MAKE_KEY(key,i);
 201
 202         // If asked, report which slot the key hashes to
 203         if( bucketkey ) *bucketkey = i;
 204
 205         osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
 206         if( !list ) { return NULL; }
 207
 208         // Search the sub-list
 209
 210         int k;
 211         osrfHashNode* node = NULL;
 212         for( k = 0; k < list->size; k++ ) {
 213                 node = OSRF_LIST_GET_INDEX(list, k);
 214                 if( node && node->key && !strcmp(node->key, key) )
 215                         return node;
 216         }
 217
 218         return NULL;
 219 }
 220
 221 /**
 222         @brief Create and populate a new osrfHashNode.
 223         @param key The key string.
 224         @param item A pointer to the item associated with the key.
 225         @return A pointer to the newly created node.
 226 */
 227 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
 228         if(!(key && item)) return NULL;
 229         osrfHashNode* n;
 230         OSRF_MALLOC(n, sizeof(osrfHashNode));
 231         n->key = strdup(key);
 232         n->item = item;
 233         n->prev = NULL;
 234         n->prev = NULL;
 235         return n;
 236 }
 237
 238 /**
 239         @brief Store an item for a given key in an osrfHash.
 240         @param hash Pointer to the osrfHash in which the item is to be stored.
 241         @param item Pointer to the item to be stored.
 242         @param key A printf-style format string to be expanded into the key for the item.  Subsequent
 243                 parameters, if any, will be formatted and inserted into the expanded key.
 244         @return Pointer to an item previously stored for the same key, if any (see discussion).
 245
 246         If no item is already stored for the same key, osrfHashSet creates a new entry for it,
 247         and returns NULL.
 248
 249         If an item is already stored for the same key, osrfHashSet updates the entry in place.  The
 250         fate of the previously stored item varies.  If there is a callback defined for freeing the
 251         item, osrfHashSet calls it, and returns NULL.  Otherwise it returns a pointer to the
 252         previously stored item, so that the calling function can dispose of it.
 253
 254         osrfHashSet returns NULL if any of its first three parameters is NULL.
 255 */
 256 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
 257         if(!(hash && item && key )) return NULL;
 258
 259         unsigned int bucketkey;
 260
 261         VA_LIST_TO_STRING(key);
 262         osrfHashNode* node = find_item( hash, VA_BUF, &bucketkey );
 263         if( node ) {
 264
 265                 // We already have an item for this key.  Update it in place.
 266                 void* olditem = NULL;
 267
 268                 if( hash->freeItem ) {
 269                         hash->freeItem( node->key, node->item );
 270                 }
 271                 else
 272                         olditem = node->item;
 273
 274                 node->item = item;
 275                 return olditem;
 276         }
 277
 278         // There is no entry for this key.  Create a new one.
 279         osrfList* bucket;
 280         if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
 281                 bucket = osrfNewList();
 282                 osrfListSet( hash->hash, bucket, bucketkey );
 283         }
 284
 285         node = osrfNewHashNode(VA_BUF, item);
 286         osrfListPushFirst( bucket, node );
 287
 288         hash->size++;
 289
 290         // Add the new hash node to the end of the linked list
 291
 292         if( NULL == hash->first_key )
 293                 hash->first_key = hash->last_key = node;
 294         else {
 295                 node->prev = hash->last_key;
 296                 hash->last_key->next = node;
 297                 hash->last_key = node;
 298         }
 299
 300         return NULL;
 301 }
 302
 303 /**
 304         @brief Remove the item for a specified key from an osrfHash.
 305         @param hash Pointer to the osrfHash from which the item is to be removed.
 306         @param key A printf-style format string to be expanded into the key for the item.  Subsequent
 307                 parameters, if any, will be formatted and inserted into the expanded key.
 308         @return Pointer to the removed item, if any (see discussion).
 309
 310         If no entry is present for the specified key, osrfHashRemove returns NULL.
 311
 312         If there is such an entry, osrfHashRemove removes it.  The fate of the associated item
 313         varies.  If there is a callback function for freeing items, osrfHashRemove calls it, and
 314         returns NULL.  Otherwise it returns a pointer to the removed item, so that the calling
 315         code can dispose of it.
 316
 317         osrfHashRemove returns NULL if either of its first two parameters is NULL.
 318
 319         Note: the osrfHashNode for the removed item is logically deleted so that subsequent searches
 320         and traversals will ignore it.  However it is physically left in place so that an
 321         osrfHashIterator pointing to it can advance to the next node.  The downside of this
 322         design is that, if a lot of items are removed, the accumulation of logically deleted nodes
 323         will slow down searches.  In addition, the memory used by a logically deleted osrfHashNode
 324         remains allocated until the entire osrfHashNode is freed.
 325 */
 326 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
 327         if(!(hash && key )) return NULL;
 328
 329         VA_LIST_TO_STRING(key);
 330
 331         osrfHashNode* node = find_item( hash, VA_BUF, NULL );
 332         if( !node ) return NULL;
 333
 334         hash->size--;
 335
 336         void* item = NULL;  // to be returned
 337         if( hash->freeItem )
 338                 hash->freeItem( node->key, node->item );
 339         else
 340                 item = node->item;
 341
 342         // Mark the node as logically deleted
 343
 344         free(node->key);
 345         node->key = NULL;
 346         node->item = NULL;
 347
 348         // Make the node unreachable from the rest of the linked list.
 349         // We leave the next and prev pointers in place so that an
 350         // iterator parked here can find its way to an adjacent node.
 351
 352         if( node->prev )
 353                 node->prev->next = node->next;
 354         else
 355                 hash->first_key = node->next;
 356
 357         if( node->next )
 358                 node->next->prev = node->prev;
 359         else
 360                 hash->last_key = node->prev;
 361
 362         return item;
 363 }
 364
 365 /**
 366         @brief Extract the item for a specified key from an osrfHash.
 367         @param hash Pointer to the osrfHash from which the item is to be extracted.
 368         @param key A printf-style format string to be expanded into the key for the item.
 369                 Subsequent parameters, if any, will be formatted and inserted into the expanded key.
 370         @return Pointer to the extracted item, if any (see discussion).
 371
 372         osrfHashRemove removes a specified entry without destroying it, and returns a pointer
 373         to it.  If either of its first two parameters is NULL, or if no entry is present for the specified key, it returns NULL.
 374
 375         This function is identical to osrfHashRemove() except that it does not destroy the
 376         specified item.
 377 */
 378 void* osrfHashExtract( osrfHash* hash, const char* key, ... ) {
 379         if(!(hash && key )) return NULL;
 380
 381         VA_LIST_TO_STRING(key);
 382
 383         osrfHashNode* node = find_item( hash, VA_BUF, NULL );
 384         if( !node ) return NULL;
 385
 386         hash->size--;
 387
 388         void* item = node->item;  // to be returned
 389
 390         // Mark the node as logically deleted
 391         free(node->key);
 392         node->key = NULL;
 393         node->item = NULL;
 394
 395         // Make the node unreachable from the rest of the linked list.
 396         // We leave the next and prev pointers in place so that an
 397         // iterator parked here can find its way to an adjacent node.
 398         if( node->prev )
 399                 node->prev->next = node->next;
 400         else
 401                 hash->first_key = node->next;
 402
 403         if( node->next )
 404                 node->next->prev = node->prev;
 405         else
 406                 hash->last_key = node->prev;
 407
 408         return item;
 409 }
 410
 411 /**
 412         @brief Fetch the item stored in an osrfHash for a given key.
 413         @param hash Pointer to the osrfHash from which to fetch the item.
 414         @param key The key for the item sought.
 415         @return A pointer to the item, if it exists; otherwise NULL.
 416 */
 417 void* osrfHashGet( osrfHash* hash, const char* key ) {
 418         if(!(hash && key )) return NULL;
 419
 420         osrfHashNode* node = find_item( hash, key, NULL );
 421         if( !node ) return NULL;
 422         return node->item;
 423 }
 424
 425 /**
 426         @brief Fetch the item stored in an osrfHash for a given key.
 427         @param hash Pointer to the osrfHash from which to fetch the item.
 428         @param key A printf-style format string to be expanded into the key for the item.  Subsequent
 429                 parameters, if any, will be formatted and inserted into the expanded key.
 430         @return A pointer to the item, if it exists; otherwise NULL.
 431  */
 432 void* osrfHashGetFmt( osrfHash* hash, const char* key, ... ) {
 433         if(!(hash && key )) return NULL;
 434         VA_LIST_TO_STRING(key);
 435
 436         osrfHashNode* node = find_item( hash, (char*) VA_BUF, NULL );
 437         if( !node ) return NULL;
 438         return node->item;
 439 }
 440
 441 /**
 442         @brief Create an osrfStringArray containing all the keys in an osrfHash.
 443         @param hash Pointer to the osrfHash whose keys are to be extracted.
 444         @return A pointer to the newly created osrfStringArray.
 445
 446         The strings in the osrfStringArray are arranged in the sequence in which they were added to
 447         the osrfHash.
 448
 449         The calling code is responsible for freeing the osrfStringArray by calling
 450         osrfStringArrayFree().
 451
 452         osrfHashKeys returns NULL if its parameter is NULL.
 453 */
 454 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
 455         if(!hash) return NULL;
 456
 457         osrfHashNode* node;
 458         osrfStringArray* strings = osrfNewStringArray( hash->size );
 459
 460         // Add every key on the linked list
 461
 462         node = hash->first_key;
 463         while( node ) {
 464                 if( node->key )  // should always be true
 465                         osrfStringArrayAdd( strings, node->key );
 466                 node = node->next;
 467         }
 468
 469         return strings;
 470 }
 471
 472
 473 /**
 474         @brief Count the items an osrfHash.
 475         @param hash Pointer to the osrfHash whose items are to be counted.
 476         @return The number of items in the osrfHash.
 477
 478         If the parameter is NULL, osrfHashGetCount returns -1.
 479 */
 480 unsigned long osrfHashGetCount( osrfHash* hash ) {
 481         if(!hash) return -1;
 482         return hash->size;
 483 }
 484
 485 /**
 486         @brief Free an osrfHash and all of its contents.
 487         @param hash Pointer to the osrfHash to be freed.
 488
 489         If a callback function has been defined for freeing items, osrfHashFree calls it for
 490                 each stored item.
 491 */
 492 void osrfHashFree( osrfHash* hash ) {
 493         if(!hash) return;
 494
 495         int i, j;
 496         osrfList* list;
 497         osrfHashNode* node;
 498
 499         for( i = 0; i != hash->hash->size; i++ ) {
 500                 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
 501                         for( j = 0; j != list->size; j++ ) {
 502                                 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
 503                                         OSRF_HASH_NODE_FREE(hash, node);
 504                                 }
 505                         }
 506                         osrfListFree(list);
 507                 }
 508         }
 509
 510         osrfListFree(hash->hash);
 511         free(hash);
 512 }
 513
 514 /**
 515         @brief Create and initialize an osrfHashIterator for a given osrfHash.
 516         @param hash Pointer to the osrfHash with which the iterator will be associated.
 517         @return Pointer to the newly created osrfHashIterator.
 518
 519         An osrfHashIterator may be used to traverse the items stored in an osrfHash.
 520
 521         The calling code is responsible for freeing the osrfHashIterator by calling
 522         osrfHashIteratorFree().
 523 */
 524 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
 525         if(!hash) return NULL;
 526         osrfHashIterator* itr;
 527         OSRF_MALLOC(itr, sizeof(osrfHashIterator));
 528         itr->hash = hash;
 529         itr->curr_node = NULL;
 530         return itr;
 531 }
 532
 533 /**
 534         @brief Advance an osrfHashIterator to the next item in an osrfHash.
 535         @param itr Pointer to the osrfHashIterator to be advanced.
 536         @return A Pointer to the next stored item, if there is one; otherwise NULL.
 537
 538         The items are returned in the sequence in which their keys were added to the osrfHash.
 539 */
 540 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
 541         if(!(itr && itr->hash)) return NULL;
 542
 543         // Advance to the next node in the linked list
 544
 545         if( NULL == itr->curr_node )
 546                 itr->curr_node = itr->hash->first_key;
 547         else
 548                 itr->curr_node = itr->curr_node->next;
 549
 550         if( itr->curr_node )
 551                 return itr->curr_node->item;
 552         else
 553                 return NULL;
 554 }
 555
 556 /**
 557         @brief Fetch the key where an osrfHashIterator is currently positioned.
 558         @param itr Pointer to the osrfHashIterator.
 559         @return A const pointer to the key, if the iterator is currently positioned on an item;
 560                 otherwise NULL.
 561
 562         The key returned is the one associated with the previous call to osrfHashIteratorNext(),
 563         unless there has been a call to osrfHashIteratorReset() in the meanwhile.
 564 */
 565 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
 566         if( itr && itr->curr_node )
 567                 return itr->curr_node->key;
 568         else
 569                 return NULL;
 570 }
 571
 572 /**
 573         @brief Free an osrfHashIterator.
 574         @param itr Pointer to the osrfHashIterator to be freed.
 575 */
 576 void osrfHashIteratorFree( osrfHashIterator* itr ) {
 577         if(itr)
 578                 free(itr);
 579 }
 580
 581 /**
 582         @brief Restore an osrfHashIterator to its original pristine state.
 583         @param itr Pointer to the osrfHashIterator to be reset.
 584
 585         After resetting the iterator, the next call to osrfHashIteratorNext() will return a pointer
 586         to the first item in the list.
 587 */
 588 void osrfHashIteratorReset( osrfHashIterator* itr ) {
 589         if(!itr) return;
 590         itr->curr_node = NULL;
 591 }
 592
 593
 594 /**
 595         @brief Determine whether there is another entry in an osrfHash beyond the current
 596                 position of an osrfHashIterator.
 597         @param itr Pointer to the osrfHashIterator in question.
 598         @return A boolean: 1 if there is another entry beyond the current position, or 0 if the
 599                 iterator is already at the last entry (or at no entry).
 600 */
 601 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
 602         if( !itr || !itr->hash )
 603                 return 0;
 604         else if( itr->curr_node )
 605                 return itr->curr_node->next ? 1 : 0;
 606         else
 607                 return itr->hash->first_key ? 1 : 0;
 608 }