1 #include <opensrf/osrf_hash.h>
3 osrfHash* osrfNewHash() {
5 OSRF_MALLOC(hash, sizeof(osrfHash));
6 hash->hash = osrfNewList();
7 hash->keys = osrfNewStringArray(64);
12 /* algorithm proposed by Donald E. Knuth
13 * in The Art Of Computer Programming Volume 3 (more or less..)*/
15 static unsigned int osrfHashMakeKey(char* str) {
17 unsigned int len = strlen(str);
20 for(i = 0; i < len; str++, i++)
21 h = ((h << 5) ^ (h >> 27)) ^ (*str);
22 return (h & (OSRF_HASH_LIST_SIZE-1));
27 /* macro version of the above function */
28 #define OSRF_HASH_MAKE_KEY(str,num) \
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));\
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;
49 OSRF_HASH_MAKE_KEY(key,i);
51 osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
52 if( !list ) { return -1; }
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) )
70 osrfHashNode* osrfNewHashNode(char* key, void* item) {
71 if(!(key && item)) return NULL;
73 OSRF_MALLOC(n, sizeof(osrfHashNode));
79 void* osrfHashNodeFree(osrfHash* hash, osrfHashNode* node) {
80 if(!(node && hash)) return NULL;
83 hash->freeItem( node->key, node->item );
84 else item = node->item;
90 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
91 if(!(hash && item && key )) return NULL;
93 VA_LIST_TO_STRING(key);
94 void* olditem = osrfHashRemove( hash, VA_BUF );
96 unsigned int bucketkey = 0;
97 OSRF_HASH_MAKE_KEY(VA_BUF,bucketkey);
100 if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
101 bucket = osrfNewList();
102 osrfListSet( hash->hash, bucket, bucketkey );
105 osrfHashNode* node = osrfNewHashNode(VA_BUF, item);
106 osrfListPushFirst( bucket, node );
108 if(!osrfStringArrayContains(hash->keys, VA_BUF))
109 osrfStringArrayAdd( hash->keys, VA_BUF );
115 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
116 if(!(hash && key )) return NULL;
118 VA_LIST_TO_STRING(key);
120 osrfList* list = NULL;
122 int index = osrfHashFindItem( hash, (char*) VA_BUF, &list, &node );
123 if( index == -1 ) return NULL;
125 osrfListRemove( list, index );
128 void* item = osrfHashNodeFree(hash, node);
129 osrfStringArrayRemove(hash->keys, VA_BUF);
134 void* osrfHashGet( osrfHash* hash, const char* key, ... ) {
135 if(!(hash && key )) return NULL;
136 VA_LIST_TO_STRING(key);
138 osrfHashNode* node = NULL;
139 int index = osrfHashFindItem( hash, (char*) VA_BUF, NULL, &node );
140 if( index == -1 ) return NULL;
145 osrfStringArray* osrfHashKeysInc( osrfHash* hash ) {
146 if(!hash) return NULL;
150 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
151 if(!hash) return NULL;
156 osrfStringArray* strings = osrfNewStringArray(8);
158 for( i = 0; i != hash->hash->size; i++ ) {
159 list = OSRF_LIST_GET_INDEX( hash->hash, i );
161 for( k = 0; k != list->size; k++ ) {
162 node = OSRF_LIST_GET_INDEX( list, k );
163 if( node ) osrfStringArrayAdd( strings, node->key );
172 unsigned long osrfHashGetCount( osrfHash* hash ) {
177 void osrfHashFree( osrfHash* hash ) {
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);
195 osrfListFree(hash->hash);
196 OSRF_STRING_ARRAY_FREE(hash->keys);
202 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
203 if(!hash) return NULL;
204 osrfHashIterator* itr;
205 OSRF_MALLOC(itr, sizeof(osrfHashIterator));
208 itr->keys = osrfHashKeysInc(hash);
212 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
213 if(!(itr && itr->hash)) return NULL;
214 if( itr->currentIdx >= itr->keys->size ) return NULL;
216 itr->current = strdup(osrfStringArrayGetString(itr->keys, itr->currentIdx++));
217 char* val = osrfHashGet( itr->hash, itr->current );
221 void osrfHashIteratorFree( osrfHashIterator* itr ) {
227 void osrfHashIteratorReset( osrfHashIterator* itr ) {
230 itr->keys = osrfHashKeysInc(itr->hash);
236 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
237 return ( itr->currentIdx < itr->keys->size ) ? 1 : 0;