src/libstack/osrf_hash.c

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