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