OpenSRF/src/libstack/osrf_hash.c

   1 #include "osrf_hash.h"
   2
   3 osrfHash* osrfNewHash() {
   4         osrfHash* hash = safe_malloc(sizeof(osrfHash));
   5         hash->hash              = osrfNewList();
   6         hash->freeItem = NULL;
   7         hash->size              = 0;
   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 static unsigned int osrfHashMakeKey(char* str) {
  15         if(!str) return 0;
  16         unsigned int len = strlen(str);
  17         unsigned int h = len;
  18         unsigned int i    = 0;
  19         for(i = 0; i < len; str++, i++)
  20                 h = ((h << 5) ^ (h >> 27)) ^ (*str);
  21         return (h & 0x7FF);
  22 }
  23
  24
  25 /* returns the index of the item and points l to the sublist the item
  26  * lives in if the item and points n to the hashnode the item
  27  * lives in if the item is found.  Otherwise -1 is returned */
  28 static unsigned int osrfHashFindItem( osrfHash* hash, char* key, osrfList** l, osrfHashNode** n ) {
  29         if(!(hash && key)) return -1;
  30
  31         int i = osrfHashMakeKey(key);
  32         osrfList* list = osrfListGetIndex( hash->hash, i );
  33         if( !list ) { return -1; }
  34
  35
  36         int k;
  37         osrfHashNode* node = NULL;
  38         for( k = 0; k < list->size; k++ ) {
  39                 node = osrfListGetIndex(list, k);
  40                 if( node && node->key && !strcmp(node->key, key) )
  41                         break;
  42                 node = NULL;
  43         }
  44
  45         if(!node) return -1;
  46
  47         if(l) *l = list;
  48         if(n) *n = node;
  49         return k;
  50 }
  51
  52 osrfHashNode* osrfNewHashNode(char* key, void* item) {
  53         if(!(key && item)) return NULL;
  54         osrfHashNode* n = safe_malloc(sizeof(osrfHashNode));
  55         n->key = strdup(key);
  56         n->item = item;
  57         return n;
  58 }
  59
  60 void osrfHashNodeFree(osrfHashNode* node) {
  61         if(!node) return;
  62         free(node->key);
  63         free(node);
  64 }
  65
  66 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
  67         if(!(hash && item && key )) return NULL;
  68
  69         VA_LIST_TO_STRING(key);
  70         void* olditem = osrfHashRemove( hash, VA_BUF );
  71         int bucketkey = osrfHashMakeKey(VA_BUF);
  72
  73         osrfList* bucket;
  74         if( !(bucket = osrfListGetIndex(hash->hash, bucketkey)) ) {
  75                 bucket = osrfNewList();
  76                 osrfListSet( hash->hash, bucket, bucketkey );
  77         }
  78
  79         osrfHashNode* node = osrfNewHashNode(VA_BUF, item);
  80         osrfListPushFirst( bucket, node );
  81
  82         hash->size++;
  83         return olditem;
  84 }
  85
  86 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
  87         if(!(hash && key )) return NULL;
  88
  89         VA_LIST_TO_STRING(key);
  90
  91         osrfList* list = NULL;
  92         osrfHashNode* node;
  93         int index = osrfHashFindItem( hash, (char*) VA_BUF, &list, &node );
  94         if( index == -1 ) return NULL;
  95
  96         osrfListRemove( list, index );
  97         hash->size--;
  98
  99         void* item = NULL;
 100         if(hash->freeItem)
 101                 hash->freeItem((char*) VA_BUF, node->item);
 102          else item = node->item;
 103
 104         osrfHashNodeFree(node);
 105         return item;
 106 }
 107
 108
 109 void* osrfHashGet( osrfHash* hash, const char* key, ... ) {
 110         if(!(hash && key )) return NULL;
 111         VA_LIST_TO_STRING(key);
 112
 113         osrfHashNode* node = NULL;
 114         int index = osrfHashFindItem( hash, (char*) VA_BUF, NULL, &node );
 115         if( index == -1 ) return NULL;
 116         return node->item;
 117 }
 118
 119
 120 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
 121         if(!hash) return NULL;
 122
 123         int i, k;
 124         osrfList* list;
 125         osrfHashNode* node;
 126         osrfStringArray* strings = osrfNewStringArray(8);
 127
 128         for( i = 0; i != hash->hash->size; i++ ) {
 129                 list = osrfListGetIndex( hash->hash, i );
 130                 if(list) {
 131                         for( k = 0; k != list->size; k++ ) {
 132                                 node = osrfListGetIndex( list, k );
 133                                 if( node ) osrfStringArrayAdd( strings, node->key );
 134                         }
 135                 }
 136         }
 137
 138         return strings;
 139 }
 140
 141
 142 unsigned long osrfHashGetCount( osrfHash* hash ) {
 143         if(!hash) return -1;
 144         return hash->size;
 145 }
 146
 147 void osrfHashFree( osrfHash* hash ) {
 148         if(!hash) return;
 149
 150         int i, j;
 151         osrfList* list;
 152         osrfHashNode* node;
 153
 154         for( i = 0; i != hash->hash->size; i++ ) {
 155                 if( ( list = osrfListGetIndex( hash->hash, i )) ) {
 156                         for( j = 0; j != list->size; j++ ) {
 157                                 if( (node = osrfListGetIndex( list, j )) ) {
 158                                         if( hash->freeItem )
 159                                                 hash->freeItem( node->key, node->item );
 160                                         osrfHashNodeFree(node);
 161                                 }
 162                         }
 163                         osrfListFree(list);
 164                 }
 165         }
 166
 167         osrfListFree(hash->hash);
 168         free(hash);
 169 }
 170
 171
 172
 173 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
 174         if(!hash) return NULL;
 175         osrfHashIterator* itr = safe_malloc(sizeof(osrfHashIterator));
 176         itr->hash = hash;
 177         itr->current = NULL;
 178         itr->keys = osrfHashKeys(hash);
 179         return itr;
 180 }
 181
 182 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
 183         if(!(itr && itr->hash)) return NULL;
 184         if( itr->currentIdx >= itr->keys->size ) return NULL;
 185         free(itr->current);
 186         itr->current = strdup(
 187                         osrfStringArrayGetString(itr->keys, itr->currentIdx++));
 188         char* val = osrfHashGet( itr->hash, itr->current );
 189         return val;
 190 }
 191
 192 void osrfHashIteratorFree( osrfHashIterator* itr ) {
 193         if(!itr) return;
 194         free(itr->current);
 195         osrfStringArrayFree(itr->keys);
 196         free(itr);
 197 }
 198
 199 void osrfHashIteratorReset( osrfHashIterator* itr ) {
 200         if(!itr) return;
 201         free(itr->current);
 202         osrfStringArrayFree(itr->keys);
 203         itr->keys = osrfHashKeys(itr->hash);
 204         itr->currentIdx = 0;
 205         itr->current = NULL;
 206 }
 207
 208
 209