moved osrf_hash code to osrf_big_hash as the Judy big hash implementation
[Evergreen.git] / 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