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
  61
  62 /* returns the index of the item and points l to the sublist the item
  63  * lives in if the item and points n to the hashnode the item
  64  * lives in if the item is found.  Otherwise -1 is returned */
  65 static unsigned int osrfHashFindItem( osrfHash* hash, char* key, osrfList** l, osrfHashNode** n ) {
  66         if(!(hash && key)) return -1;
  67
  68
  69         unsigned int i = 0;
  70         OSRF_HASH_MAKE_KEY(key,i);
  71
  72         osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
  73         if( !list ) { return -1; }
  74
  75         int k;
  76         osrfHashNode* node = NULL;
  77         for( k = 0; k < list->size; k++ ) {
  78                 node = OSRF_LIST_GET_INDEX(list, k);
  79                 if( node && node->key && !strcmp(node->key, key) )
  80                         break;
  81                 node = NULL;
  82         }
  83
  84         if(!node) return -1;
  85
  86         if(l) *l = list;
  87         if(n) *n = node;
  88         return k;
  89 }
  90
  91 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
  92         if(!(key && item)) return NULL;
  93         osrfHashNode* n;
  94         OSRF_MALLOC(n, sizeof(osrfHashNode));
  95         n->key = strdup(key);
  96         n->item = item;
  97         return n;
  98 }
  99
 100 static void* osrfHashNodeFree(osrfHash* hash, osrfHashNode* node) {
 101         if(!(node && hash)) return NULL;
 102         void* item = NULL;
 103         if( hash->freeItem )
 104                 hash->freeItem( node->key, node->item );
 105         else item = node->item;
 106         free(node->key);
 107         free(node);
 108         return item;
 109 }
 110
 111 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
 112         if(!(hash && item && key )) return NULL;
 113
 114         VA_LIST_TO_STRING(key);
 115         void* olditem = osrfHashRemove( hash, VA_BUF );
 116
 117         unsigned int bucketkey = 0;
 118         OSRF_HASH_MAKE_KEY(VA_BUF,bucketkey);
 119
 120         osrfList* bucket;
 121         if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
 122                 bucket = osrfNewList();
 123                 osrfListSet( hash->hash, bucket, bucketkey );
 124         }
 125
 126         osrfHashNode* node = osrfNewHashNode(VA_BUF, item);
 127         osrfListPushFirst( bucket, node );
 128
 129         if(!osrfStringArrayContains(hash->keys, VA_BUF))
 130                 osrfStringArrayAdd( hash->keys, VA_BUF );
 131
 132         hash->size++;
 133         return olditem;
 134 }
 135
 136 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
 137         if(!(hash && key )) return NULL;
 138
 139         VA_LIST_TO_STRING(key);
 140
 141         osrfList* list = NULL;
 142         osrfHashNode* node;
 143         int index = osrfHashFindItem( hash, (char*) VA_BUF, &list, &node );
 144         if( index == -1 ) return NULL;
 145
 146         osrfListRemove( list, index );
 147         hash->size--;
 148
 149         void* item = osrfHashNodeFree(hash, node);
 150         osrfStringArrayRemove(hash->keys, VA_BUF);
 151         return item;
 152 }
 153
 154
 155 void* osrfHashGet( osrfHash* hash, const char* key, ... ) {
 156         if(!(hash && key )) return NULL;
 157         VA_LIST_TO_STRING(key);
 158
 159         osrfHashNode* node = NULL;
 160         int index = osrfHashFindItem( hash, (char*) VA_BUF, NULL, &node );
 161         if( index == -1 ) return NULL;
 162         return node->item;
 163 }
 164
 165
 166 osrfStringArray* osrfHashKeysInc( osrfHash* hash ) {
 167         if(!hash) return NULL;
 168         return hash->keys;
 169 }
 170
 171 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
 172         if(!hash) return NULL;
 173
 174         int i, k;
 175         osrfList* list;
 176         osrfHashNode* node;
 177         osrfStringArray* strings = osrfNewStringArray(8);
 178
 179         for( i = 0; i != hash->hash->size; i++ ) {
 180                 list = OSRF_LIST_GET_INDEX( hash->hash, i );
 181                 if(list) {
 182                         for( k = 0; k != list->size; k++ ) {
 183                                 node = OSRF_LIST_GET_INDEX( list, k );
 184                                 if( node ) osrfStringArrayAdd( strings, node->key );
 185                         }
 186                 }
 187         }
 188
 189         return strings;
 190 }
 191
 192
 193 unsigned long osrfHashGetCount( osrfHash* hash ) {
 194         if(!hash) return -1;
 195         return hash->size;
 196 }
 197
 198 void osrfHashFree( osrfHash* hash ) {
 199         if(!hash) return;
 200
 201         int i, j;
 202         osrfList* list;
 203         osrfHashNode* node;
 204
 205         for( i = 0; i != hash->hash->size; i++ ) {
 206                 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
 207                         for( j = 0; j != list->size; j++ ) {
 208                                 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
 209                                         OSRF_HASH_NODE_FREE(hash, node);
 210                                 }
 211                         }
 212                         osrfListFree(list);
 213                 }
 214         }
 215
 216         osrfListFree(hash->hash);
 217     OSRF_STRING_ARRAY_FREE(hash->keys);
 218         free(hash);
 219 }
 220
 221
 222
 223 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
 224         if(!hash) return NULL;
 225         osrfHashIterator* itr;
 226         OSRF_MALLOC(itr, sizeof(osrfHashIterator));
 227         itr->hash = hash;
 228         itr->currentIdx = 0;
 229         itr->current = NULL;
 230         itr->keys = osrfHashKeysInc(hash);
 231         return itr;
 232 }
 233
 234 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
 235         if(!(itr && itr->hash)) return NULL;
 236         if( itr->currentIdx >= itr->keys->size ) return NULL;
 237         free(itr->current);
 238         itr->current = strdup(osrfStringArrayGetString(itr->keys, itr->currentIdx++));
 239         char* val = osrfHashGet( itr->hash, itr->current );
 240         return val;
 241 }
 242
 243 void osrfHashIteratorFree( osrfHashIterator* itr ) {
 244         if(!itr) return;
 245         free(itr->current);
 246         free(itr);
 247 }
 248
 249 void osrfHashIteratorReset( osrfHashIterator* itr ) {
 250         if(!itr) return;
 251         free(itr->current);
 252         itr->keys = osrfHashKeysInc(itr->hash);
 253         itr->currentIdx = 0;
 254         itr->current = NULL;
 255 }
 256
 257
 258 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
 259         return ( itr->currentIdx < itr->keys->size ) ? 1 : 0;
 260 }