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         osrfHashNode* node = find_item( hash, key, NULL );
 257         if( !node ) return NULL;
 258         return node->item;
 259 }
 260
 261 void* osrfHashGetFmt( osrfHash* hash, const char* key, ... ) {
 262         if(!(hash && key )) return NULL;
 263         VA_LIST_TO_STRING(key);
 264
 265         osrfHashNode* node = find_item( hash, (char*) VA_BUF, NULL );
 266         if( !node ) return NULL;
 267         return node->item;
 268 }
 269
 270 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
 271         if(!hash) return NULL;
 272
 273         osrfHashNode* node;
 274         osrfStringArray* strings = osrfNewStringArray( hash->size );
 275
 276         // Add every key on the linked list
 277
 278         node = hash->first_key;
 279         while( node ) {
 280                 if( node->key )  // should always be true
 281                         osrfStringArrayAdd( strings, node->key );
 282                 node = node->next;
 283         }
 284
 285         return strings;
 286 }
 287
 288
 289 unsigned long osrfHashGetCount( osrfHash* hash ) {
 290         if(!hash) return -1;
 291         return hash->size;
 292 }
 293
 294 void osrfHashFree( osrfHash* hash ) {
 295         if(!hash) return;
 296
 297         int i, j;
 298         osrfList* list;
 299         osrfHashNode* node;
 300
 301         for( i = 0; i != hash->hash->size; i++ ) {
 302                 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
 303                         for( j = 0; j != list->size; j++ ) {
 304                                 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
 305                                         OSRF_HASH_NODE_FREE(hash, node);
 306                                 }
 307                         }
 308                         osrfListFree(list);
 309                 }
 310         }
 311
 312         osrfListFree(hash->hash);
 313         free(hash);
 314 }
 315
 316 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
 317         if(!hash) return NULL;
 318         osrfHashIterator* itr;
 319         OSRF_MALLOC(itr, sizeof(osrfHashIterator));
 320         itr->hash = hash;
 321         itr->curr_node = NULL;
 322         return itr;
 323 }
 324
 325 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
 326         if(!(itr && itr->hash)) return NULL;
 327
 328         // Advance to the next node in the linked list
 329
 330         if( NULL == itr->curr_node )
 331                 itr->curr_node = itr->hash->first_key;
 332         else
 333                 itr->curr_node = itr->curr_node->next;
 334
 335         if( itr->curr_node )
 336                 return itr->curr_node->item;
 337         else
 338                 return NULL;
 339 }
 340
 341 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
 342         if( itr && itr->curr_node )
 343                 return itr->curr_node->key;
 344         else
 345                 return NULL;
 346 }
 347
 348 void osrfHashIteratorFree( osrfHashIterator* itr ) {
 349         if(itr)
 350                 free(itr);
 351 }
 352
 353 void osrfHashIteratorReset( osrfHashIterator* itr ) {
 354         if(!itr) return;
 355         itr->curr_node = NULL;
 356 }
 357
 358
 359 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
 360         if( !itr )
 361                 return 0;
 362         else if( itr->curr_node )
 363                 return itr->curr_node->next ? 1 : 0;
 364         else
 365                 return itr->hash->first_key ? 1 : 0;
 366 }