Patch from Scott McKellar:
[OpenSRF.git] / 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 }