src/libopensrf/osrf_hash.c

   1 #include <opensrf/osrf_hash.h>
   2
   3 struct _osrfHashNodeStruct {
   4         char* key;
   5         void* item;
   6 };
   7 typedef struct _osrfHashNodeStruct osrfHashNode;
   8
   9 /* 0x100 is a good size for small hashes */
  10 //#define OSRF_HASH_LIST_SIZE 0x100  /* size of the main hash list */
  11 #define OSRF_HASH_LIST_SIZE 0x10  /* size of the main hash list */
  12
  13 /* used internally */
  14 #define OSRF_HASH_NODE_FREE(h, n) \
  15         if(h && n) { \
  16                 if(h->freeItem) h->freeItem(n->key, n->item);\
  17                 free(n->key); free(n); \
  18 }
  19
  20 static osrfHashNode* osrfNewHashNode(char* key, void* item);
  21 static void* osrfHashNodeFree(osrfHash*, osrfHashNode*);
  22
  23 osrfHash* osrfNewHash() {
  24         osrfHash* hash;
  25         OSRF_MALLOC(hash, sizeof(osrfHash));
  26         hash->hash              = osrfNewList();
  27         hash->freeItem  = NULL;
  28         hash->size      = 0;
  29         hash->keys              = osrfNewStringArray(64);
  30         return hash;
  31 }
  32
  33 /* algorithm proposed by Donald E. Knuth
  34  * in The Art Of Computer Programming Volume 3 (more or less..)*/
  35 /*
  36 static unsigned int osrfHashMakeKey(char* str) {
  37         if(!str) return 0;
  38         unsigned int len = strlen(str);
  39         unsigned int h = len;
  40         unsigned int i = 0;
  41         for(i = 0; i < len; str++, i++)
  42                 h = ((h << 5) ^ (h >> 27)) ^ (*str);
  43         return (h & (OSRF_HASH_LIST_SIZE-1));
  44 }
  45 */
  46
  47
  48 /* macro version of the above function */
  49 #define OSRF_HASH_MAKE_KEY(str,num) \
  50    do {\
  51       char* __k = str;\
  52       unsigned int __len = strlen(__k); \
  53       unsigned int __h = __len;\
  54       unsigned int __i = 0;\
  55       for(__i = 0; __i < __len; __k++, __i++)\
  56          __h = ((__h << 5) ^ (__h >> 27)) ^ (*__k);\
  57       num = (__h & (OSRF_HASH_LIST_SIZE-1));\
  58    } while(0)
  59
  60 /** Installs a callback function for freeing stored items
  61     */
  62 void osrfHashSetCallback( osrfHash* hash, void (*callback) (char* key, void* item) )
  63 {
  64         if( hash ) hash->freeItem = callback;
  65 }
  66
  67 /* returns the index of the item and points l to the sublist the item
  68  * lives in if the item and points n to the hashnode the item
  69  * lives in if the item is found.  Otherwise -1 is returned */
  70 static unsigned int osrfHashFindItem( osrfHash* hash, char* key, osrfList** l, osrfHashNode** n ) {
  71         if(!(hash && key)) return -1;
  72
  73
  74         unsigned int i = 0;
  75         OSRF_HASH_MAKE_KEY(key,i);
  76
  77         osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
  78         if( !list ) { return -1; }
  79
  80         int k;
  81         osrfHashNode* node = NULL;
  82         for( k = 0; k < list->size; k++ ) {
  83                 node = OSRF_LIST_GET_INDEX(list, k);
  84                 if( node && node->key && !strcmp(node->key, key) )
  85                         break;
  86                 node = NULL;
  87         }
  88
  89         if(!node) return -1;
  90
  91         if(l) *l = list;
  92         if(n) *n = node;
  93         return k;
  94 }
  95
  96 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
  97         if(!(key && item)) return NULL;
  98         osrfHashNode* n;
  99         OSRF_MALLOC(n, sizeof(osrfHashNode));
 100         n->key = strdup(key);
 101         n->item = item;
 102         return n;
 103 }
 104
 105 static void* osrfHashNodeFree(osrfHash* hash, osrfHashNode* node) {
 106         if(!(node && hash)) return NULL;
 107         void* item = NULL;
 108         if( hash->freeItem )
 109                 hash->freeItem( node->key, node->item );
 110         else item = node->item;
 111         free(node->key);
 112         free(node);
 113         return item;
 114 }
 115
 116 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
 117         if(!(hash && item && key )) return NULL;
 118
 119         VA_LIST_TO_STRING(key);
 120         void* olditem = osrfHashRemove( hash, VA_BUF );
 121
 122         unsigned int bucketkey = 0;
 123         OSRF_HASH_MAKE_KEY(VA_BUF,bucketkey);
 124
 125         osrfList* bucket;
 126         if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
 127                 bucket = osrfNewList();
 128                 osrfListSet( hash->hash, bucket, bucketkey );
 129         }
 130
 131         osrfHashNode* node = osrfNewHashNode(VA_BUF, item);
 132         osrfListPushFirst( bucket, node );
 133
 134         if(!osrfStringArrayContains(hash->keys, VA_BUF))
 135                 osrfStringArrayAdd( hash->keys, VA_BUF );
 136
 137         hash->size++;
 138         return olditem;
 139 }
 140
 141 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
 142         if(!(hash && key )) return NULL;
 143
 144         VA_LIST_TO_STRING(key);
 145
 146         osrfList* list = NULL;
 147         osrfHashNode* node;
 148         int index = osrfHashFindItem( hash, (char*) VA_BUF, &list, &node );
 149         if( index == -1 ) return NULL;
 150
 151         osrfListRemove( list, index );
 152         hash->size--;
 153
 154         void* item = osrfHashNodeFree(hash, node);
 155         osrfStringArrayRemove(hash->keys, VA_BUF);
 156         return item;
 157 }
 158
 159
 160 void* osrfHashGet( osrfHash* hash, const char* key, ... ) {
 161         if(!(hash && key )) return NULL;
 162         VA_LIST_TO_STRING(key);
 163
 164         osrfHashNode* node = NULL;
 165         int index = osrfHashFindItem( hash, (char*) VA_BUF, NULL, &node );
 166         if( index == -1 ) return NULL;
 167         return node->item;
 168 }
 169
 170
 171 osrfStringArray* osrfHashKeysInc( osrfHash* hash ) {
 172         if(!hash) return NULL;
 173         return hash->keys;
 174 }
 175
 176 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
 177         if(!hash) return NULL;
 178
 179         int i, k;
 180         osrfList* list;
 181         osrfHashNode* node;
 182         osrfStringArray* strings = osrfNewStringArray(8);
 183
 184         for( i = 0; i != hash->hash->size; i++ ) {
 185                 list = OSRF_LIST_GET_INDEX( hash->hash, i );
 186                 if(list) {
 187                         for( k = 0; k != list->size; k++ ) {
 188                                 node = OSRF_LIST_GET_INDEX( list, k );
 189                                 if( node ) osrfStringArrayAdd( strings, node->key );
 190                         }
 191                 }
 192         }
 193
 194         return strings;
 195 }
 196
 197
 198 unsigned long osrfHashGetCount( osrfHash* hash ) {
 199         if(!hash) return -1;
 200         return hash->size;
 201 }
 202
 203 void osrfHashFree( osrfHash* hash ) {
 204         if(!hash) return;
 205
 206         int i, j;
 207         osrfList* list;
 208         osrfHashNode* node;
 209
 210         for( i = 0; i != hash->hash->size; i++ ) {
 211                 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
 212                         for( j = 0; j != list->size; j++ ) {
 213                                 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
 214                                         OSRF_HASH_NODE_FREE(hash, node);
 215                                 }
 216                         }
 217                         osrfListFree(list);
 218                 }
 219         }
 220
 221         osrfListFree(hash->hash);
 222     OSRF_STRING_ARRAY_FREE(hash->keys);
 223         free(hash);
 224 }
 225
 226
 227
 228 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
 229         if(!hash) return NULL;
 230         osrfHashIterator* itr;
 231         OSRF_MALLOC(itr, sizeof(osrfHashIterator));
 232         itr->hash = hash;
 233         itr->currentIdx = 0;
 234         itr->current = NULL;
 235         itr->currsize = 0;
 236         itr->keys = osrfHashKeysInc(hash);
 237         return itr;
 238 }
 239
 240 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
 241         if(!(itr && itr->hash)) return NULL;
 242         if( itr->currentIdx >= itr->keys->size ) return NULL;
 243
 244         // Copy the string to iter->current
 245         const char * curr = osrfStringArrayGetString(itr->keys, itr->currentIdx++);
 246         size_t new_len = strlen(curr);
 247         if( new_len >= itr->currsize ) {
 248                 // We need a bigger buffer
 249
 250                 if(0 == itr->currsize) itr->currsize = 64; //default size
 251                 do {
 252                         itr->currsize *= 2;
 253                 } while( new_len >= itr->currsize );
 254
 255                 if(itr->current)
 256                         free(itr->current);
 257                 itr->current = safe_malloc(itr->currsize);
 258         }
 259         strcpy(itr->current, curr);
 260
 261         char* val = osrfHashGet( itr->hash, itr->current );
 262         return val;
 263 }
 264
 265 void osrfHashIteratorFree( osrfHashIterator* itr ) {
 266         if(!itr) return;
 267         free(itr->current);
 268         free(itr);
 269 }
 270
 271 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
 272     if( ! itr ) return NULL;
 273     return itr->current;
 274 }
 275
 276 void osrfHashIteratorReset( osrfHashIterator* itr ) {
 277         if(!itr) return;
 278     if(itr->current) itr->current[0] = '\0';
 279         itr->keys = osrfHashKeysInc(itr->hash);
 280         itr->currentIdx = 0;
 281 }
 282
 283
 284 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
 285         return ( itr->currentIdx < itr->keys->size ) ? 1 : 0;
 286 }