1 #include <opensrf/osrf_hash.h>
3 struct _osrfHashNodeStruct {
7 typedef struct _osrfHashNodeStruct osrfHashNode;
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 */
14 #define OSRF_HASH_NODE_FREE(h, n) \
16 if(h->freeItem) h->freeItem(n->key, n->item);\
17 free(n->key); free(n); \
20 static osrfHashNode* osrfNewHashNode(char* key, void* item);
21 static void* osrfHashNodeFree(osrfHash*, osrfHashNode*);
23 osrfHash* osrfNewHash() {
25 OSRF_MALLOC(hash, sizeof(osrfHash));
26 hash->hash = osrfNewList();
27 hash->freeItem = NULL;
29 hash->keys = osrfNewStringArray(64);
33 /* algorithm proposed by Donald E. Knuth
34 * in The Art Of Computer Programming Volume 3 (more or less..)*/
36 static unsigned int osrfHashMakeKey(char* str) {
38 unsigned int len = strlen(str);
41 for(i = 0; i < len; str++, i++)
42 h = ((h << 5) ^ (h >> 27)) ^ (*str);
43 return (h & (OSRF_HASH_LIST_SIZE-1));
48 /* macro version of the above function */
49 #define OSRF_HASH_MAKE_KEY(str,num) \
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));\
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;
70 OSRF_HASH_MAKE_KEY(key,i);
72 osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
73 if( !list ) { return -1; }
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) )
91 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
92 if(!(key && item)) return NULL;
94 OSRF_MALLOC(n, sizeof(osrfHashNode));
100 static void* osrfHashNodeFree(osrfHash* hash, osrfHashNode* node) {
101 if(!(node && hash)) return NULL;
104 hash->freeItem( node->key, node->item );
105 else item = node->item;
111 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
112 if(!(hash && item && key )) return NULL;
114 VA_LIST_TO_STRING(key);
115 void* olditem = osrfHashRemove( hash, VA_BUF );
117 unsigned int bucketkey = 0;
118 OSRF_HASH_MAKE_KEY(VA_BUF,bucketkey);
121 if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
122 bucket = osrfNewList();
123 osrfListSet( hash->hash, bucket, bucketkey );
126 osrfHashNode* node = osrfNewHashNode(VA_BUF, item);
127 osrfListPushFirst( bucket, node );
129 if(!osrfStringArrayContains(hash->keys, VA_BUF))
130 osrfStringArrayAdd( hash->keys, VA_BUF );
136 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
137 if(!(hash && key )) return NULL;
139 VA_LIST_TO_STRING(key);
141 osrfList* list = NULL;
143 int index = osrfHashFindItem( hash, (char*) VA_BUF, &list, &node );
144 if( index == -1 ) return NULL;
146 osrfListRemove( list, index );
149 void* item = osrfHashNodeFree(hash, node);
150 osrfStringArrayRemove(hash->keys, VA_BUF);
155 void* osrfHashGet( osrfHash* hash, const char* key, ... ) {
156 if(!(hash && key )) return NULL;
157 VA_LIST_TO_STRING(key);
159 osrfHashNode* node = NULL;
160 int index = osrfHashFindItem( hash, (char*) VA_BUF, NULL, &node );
161 if( index == -1 ) return NULL;
166 osrfStringArray* osrfHashKeysInc( osrfHash* hash ) {
167 if(!hash) return NULL;
171 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
172 if(!hash) return NULL;
177 osrfStringArray* strings = osrfNewStringArray(8);
179 for( i = 0; i != hash->hash->size; i++ ) {
180 list = OSRF_LIST_GET_INDEX( hash->hash, i );
182 for( k = 0; k != list->size; k++ ) {
183 node = OSRF_LIST_GET_INDEX( list, k );
184 if( node ) osrfStringArrayAdd( strings, node->key );
193 unsigned long osrfHashGetCount( osrfHash* hash ) {
198 void osrfHashFree( osrfHash* hash ) {
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);
216 osrfListFree(hash->hash);
217 OSRF_STRING_ARRAY_FREE(hash->keys);
223 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
224 if(!hash) return NULL;
225 osrfHashIterator* itr;
226 OSRF_MALLOC(itr, sizeof(osrfHashIterator));
231 itr->keys = osrfHashKeysInc(hash);
235 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
236 if(!(itr && itr->hash)) return NULL;
237 if( itr->currentIdx >= itr->keys->size ) return NULL;
239 // Copy the string to iter->current
240 const char * curr = osrfStringArrayGetString(itr->keys, itr->currentIdx++);
241 size_t new_len = strlen(curr);
242 if( new_len >= itr->currsize ) {
243 // We need a bigger buffer
245 if(0 == itr->currsize) itr->currsize = 64; //default size
248 } while( new_len >= itr->currsize );
252 itr->current = safe_malloc(itr->currsize);
254 strcpy(itr->current, curr);
256 char* val = osrfHashGet( itr->hash, itr->current );
260 void osrfHashIteratorFree( osrfHashIterator* itr ) {
266 void osrfHashIteratorReset( osrfHashIterator* itr ) {
268 itr->current[0] = '\0';
269 itr->keys = osrfHashKeysInc(itr->hash);
274 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
275 return ( itr->currentIdx < itr->keys->size ) ? 1 : 0;