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