src/libopensrf/osrf_hash.c

   1 /*
   2 Copyright (C) 2007, 2008  Georgia Public Library Service
   3 Bill Erickson <erickson@esilibrary.com>
   4
   5 This program is free software; you can redistribute it and/or
   6 modify it under the terms of the GNU General Public License
   7 as published by the Free Software Foundation; either version 2
   8 of the License, or (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 -----------
  16
  17 An osrfHash is a hybrid between a hash table and a doubly linked
  18 list.  The hash table supports random lookups by key.  The list
  19 supports iterative traversals.  The sequence of entries in the
  20 list reflects the sequence in which the entries were added.
  21
  22 osrfHashIterators are somewhat unusual in that, if an iterator
  23 is positioned on a given entry, deletion of that entry does
  24 not invalidate the iterator.  The entry to which it points is
  25 logically but not physically deleted.  You can still advance
  26 the iterator to the next entry in the list.
  27
  28 */
  29
  30 #include <opensrf/osrf_hash.h>
  31
  32 struct _osrfHashNodeStruct {
  33         char* key;
  34         void* item;
  35         struct _osrfHashNodeStruct* prev;
  36         struct _osrfHashNodeStruct* next;
  37 };
  38 typedef struct _osrfHashNodeStruct osrfHashNode;
  39
  40 struct _osrfHashStruct {
  41         osrfList* hash; /* this hash */
  42         void (*freeItem) (char* key, void* item);       /* callback for freeing stored items */
  43         unsigned int size;
  44         osrfHashNode* first_key;
  45         osrfHashNode* last_key;
  46 };
  47
  48 struct _osrfHashIteratorStruct {
  49         osrfHash* hash;
  50         osrfHashNode* curr_node;
  51 };
  52
  53 /* 0x100 is a good size for small hashes */
  54 //#define OSRF_HASH_LIST_SIZE 0x100  /* size of the main hash list */
  55 #define OSRF_HASH_LIST_SIZE 0x10  /* size of the main hash list */
  56
  57
  58 /* used internally */
  59 #define OSRF_HASH_NODE_FREE(h, n) \
  60         if(h && n) { \
  61                 if(h->freeItem && n->key) h->freeItem(n->key, n->item);\
  62                 free(n->key); free(n); \
  63 }
  64
  65 osrfHash* osrfNewHash() {
  66         osrfHash* hash;
  67         OSRF_MALLOC(hash, sizeof(osrfHash));
  68         hash->hash              = osrfNewList();
  69         hash->first_key = NULL;
  70         hash->last_key  = NULL;
  71         return hash;
  72 }
  73
  74 static osrfHashNode* osrfNewHashNode(char* key, void* item);
  75
  76 /* algorithm proposed by Donald E. Knuth
  77  * in The Art Of Computer Programming Volume 3 (more or less..)*/
  78 /*
  79 static unsigned int osrfHashMakeKey(char* str) {
  80         if(!str) return 0;
  81         unsigned int len = strlen(str);
  82         unsigned int h = len;
  83         unsigned int i = 0;
  84         for(i = 0; i < len; str++, i++)
  85                 h = ((h << 5) ^ (h >> 27)) ^ (*str);
  86         return (h & (OSRF_HASH_LIST_SIZE-1));
  87 }
  88 */
  89
  90 /* macro version of the above function */
  91 #define OSRF_HASH_MAKE_KEY(str,num) \
  92    do {\
  93       const char* k__ = str;\
  94       unsigned int len__ = strlen(k__); \
  95       unsigned int h__ = len__;\
  96       unsigned int i__ = 0;\
  97       for(i__ = 0; i__ < len__; k__++, i__++)\
  98          h__ = ((h__ << 5) ^ (h__ >> 27)) ^ (*k__);\
  99       num = (h__ & (OSRF_HASH_LIST_SIZE-1));\
 100    } while(0)
 101
 102 /* Installs a callback function for freeing stored items */
 103 void osrfHashSetCallback( osrfHash* hash, void (*callback) (char* key, void* item) )
 104 {
 105         if( hash ) hash->freeItem = callback;
 106 }
 107
 108 /* Returns a pointer to the item's node if found; otherwise returns NULL. */
 109 static osrfHashNode* find_item( const osrfHash* hash,
 110                 const char* key, unsigned int* bucketkey ) {
 111
 112         // Find the sub-list in the hash table
 113
 114         if( hash->size < 6 && !bucketkey )
 115         {
 116                 // For only a few entries, when we don't need to identify
 117                 // the hash bucket, it's probably faster to search the
 118                 // linked list instead of hashing
 119
 120                 osrfHashNode* currnode = hash->first_key;
 121                 while( currnode && strcmp( currnode->key, key ) )
 122                          currnode = currnode->next;
 123
 124                 return currnode;
 125         }
 126
 127         unsigned int i = 0;
 128         OSRF_HASH_MAKE_KEY(key,i);
 129
 130         // If asked, report which slot the key hashes to
 131         if( bucketkey ) *bucketkey = i;
 132
 133         osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
 134         if( !list ) { return NULL; }
 135
 136         // Search the sub-list
 137
 138         int k;
 139         osrfHashNode* node = NULL;
 140         for( k = 0; k < list->size; k++ ) {
 141                 node = OSRF_LIST_GET_INDEX(list, k);
 142                 if( node && node->key && !strcmp(node->key, key) )
 143                         return node;
 144         }
 145
 146         return NULL;
 147 }
 148
 149 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
 150         if(!(key && item)) return NULL;
 151         osrfHashNode* n;
 152         OSRF_MALLOC(n, sizeof(osrfHashNode));
 153         n->key = strdup(key);
 154         n->item = item;
 155         n->prev = NULL;
 156         n->prev = NULL;
 157         return n;
 158 }
 159
 160 /* If an entry exists for a given key, update it; otherwise create it.
 161    If an entry exists, and there is no callback function to destroy it,
 162    return a pointer to it so that the calling code has the option of
 163    destroying it.  Otherwise return NULL.
 164 */
 165 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
 166         if(!(hash && item && key )) return NULL;
 167
 168         void* olditem = NULL;
 169         unsigned int bucketkey;
 170
 171         VA_LIST_TO_STRING(key);
 172         osrfHashNode* node = find_item( hash, VA_BUF, &bucketkey );
 173         if( node ) {
 174
 175                 // We already have an item for this key.  Update it in place.
 176                 if( hash->freeItem ) {
 177                         hash->freeItem( node->key, node->item );
 178                 }
 179                 else
 180                         olditem = node->item;
 181
 182                 node->item = item;
 183                 return olditem;
 184         }
 185
 186         osrfList* bucket;
 187         if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
 188                 bucket = osrfNewList();
 189                 osrfListSet( hash->hash, bucket, bucketkey );
 190         }
 191
 192         node = osrfNewHashNode(VA_BUF, item);
 193         osrfListPushFirst( bucket, node );
 194
 195         hash->size++;
 196
 197         // Add the new hash node to the end of the linked list
 198
 199         if( NULL == hash->first_key )
 200                 hash->first_key = hash->last_key = node;
 201         else {
 202                 node->prev = hash->last_key;
 203                 hash->last_key->next = node;
 204                 hash->last_key = node;
 205         }
 206
 207         return olditem;
 208 }
 209
 210 /* Delete the entry for a specified key.  If the entry exists,
 211    and there is no callback function to destroy the associated
 212    item, return a pointer to the formerly associated item.
 213    Otherwise return NULL.
 214 */
 215 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
 216         if(!(hash && key )) return NULL;
 217
 218         VA_LIST_TO_STRING(key);
 219
 220         osrfHashNode* node = find_item( hash, VA_BUF, NULL );
 221         if( !node ) return NULL;
 222
 223         hash->size--;
 224
 225         void* item = NULL;  // to be returned
 226         if( hash->freeItem )
 227                 hash->freeItem( node->key, node->item );
 228         else
 229                 item = node->item;
 230
 231         // Mark the node as logically deleted
 232
 233         free(node->key);
 234         node->key = NULL;
 235         node->item = NULL;
 236
 237         // Make the node unreachable from the rest of the linked list.
 238         // We leave the next and prev pointers in place so that an
 239         // iterator parked here can find its way to an adjacent node.
 240
 241         if( node->prev )
 242                 node->prev->next = node->next;
 243         else
 244                 hash->first_key = node->next;
 245
 246         if( node->next )
 247                 node->next->prev = node->prev;
 248         else
 249                 hash->last_key = node->prev;
 250
 251         return item;
 252 }
 253
 254
 255 void* osrfHashGet( osrfHash* hash, const char* key ) {
 256         if(!(hash && key )) return NULL;
 257         osrfHashNode* node = find_item( hash, key, NULL );
 258         if( !node ) return NULL;
 259         return node->item;
 260 }
 261
 262 void* osrfHashGetFmt( osrfHash* hash, const char* key, ... ) {
 263         if(!(hash && key )) return NULL;
 264         VA_LIST_TO_STRING(key);
 265
 266         osrfHashNode* node = find_item( hash, (char*) VA_BUF, NULL );
 267         if( !node ) return NULL;
 268         return node->item;
 269 }
 270
 271 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
 272         if(!hash) return NULL;
 273
 274         osrfHashNode* node;
 275         osrfStringArray* strings = osrfNewStringArray( hash->size );
 276
 277         // Add every key on the linked list
 278
 279         node = hash->first_key;
 280         while( node ) {
 281                 if( node->key )  // should always be true
 282                         osrfStringArrayAdd( strings, node->key );
 283                 node = node->next;
 284         }
 285
 286         return strings;
 287 }
 288
 289
 290 unsigned long osrfHashGetCount( osrfHash* hash ) {
 291         if(!hash) return -1;
 292         return hash->size;
 293 }
 294
 295 void osrfHashFree( osrfHash* hash ) {
 296         if(!hash) return;
 297
 298         int i, j;
 299         osrfList* list;
 300         osrfHashNode* node;
 301
 302         for( i = 0; i != hash->hash->size; i++ ) {
 303                 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
 304                         for( j = 0; j != list->size; j++ ) {
 305                                 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
 306                                         OSRF_HASH_NODE_FREE(hash, node);
 307                                 }
 308                         }
 309                         osrfListFree(list);
 310                 }
 311         }
 312
 313         osrfListFree(hash->hash);
 314         free(hash);
 315 }
 316
 317 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
 318         if(!hash) return NULL;
 319         osrfHashIterator* itr;
 320         OSRF_MALLOC(itr, sizeof(osrfHashIterator));
 321         itr->hash = hash;
 322         itr->curr_node = NULL;
 323         return itr;
 324 }
 325
 326 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
 327         if(!(itr && itr->hash)) return NULL;
 328
 329         // Advance to the next node in the linked list
 330
 331         if( NULL == itr->curr_node )
 332                 itr->curr_node = itr->hash->first_key;
 333         else
 334                 itr->curr_node = itr->curr_node->next;
 335
 336         if( itr->curr_node )
 337                 return itr->curr_node->item;
 338         else
 339                 return NULL;
 340 }
 341
 342 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
 343         if( itr && itr->curr_node )
 344                 return itr->curr_node->key;
 345         else
 346                 return NULL;
 347 }
 348
 349 void osrfHashIteratorFree( osrfHashIterator* itr ) {
 350         if(itr)
 351                 free(itr);
 352 }
 353
 354 void osrfHashIteratorReset( osrfHashIterator* itr ) {
 355         if(!itr) return;
 356         itr->curr_node = NULL;
 357 }
 358
 359
 360 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
 361         if( !itr )
 362                 return 0;
 363         else if( itr->curr_node )
 364                 return itr->curr_node->next ? 1 : 0;
 365         else
 366                 return itr->hash->first_key ? 1 : 0;
 367 }