e00f09c0921228a8a9acd3a3167bce693d583591
[OpenSRF.git] / src / libopensrf / osrf_hash.c
1 #include <opensrf/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 }