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));\
60 /** Installs a callback function for freeing stored items
62 void osrfHashSetCallback( osrfHash* hash, void (*callback) (char* key, void* item) )
64 if( hash ) hash->freeItem = callback;
67 /* returns the index of the item and points l to the sublist the item
68 * lives in if the item and points n to the hashnode the item
69 * lives in if the item is found. Otherwise -1 is returned */
70 static unsigned int osrfHashFindItem( osrfHash* hash, char* key, osrfList** l, osrfHashNode** n ) {
71 if(!(hash && key)) return -1;
75 OSRF_HASH_MAKE_KEY(key,i);
77 osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
78 if( !list ) { return -1; }
81 osrfHashNode* node = NULL;
82 for( k = 0; k < list->size; k++ ) {
83 node = OSRF_LIST_GET_INDEX(list, k);
84 if( node && node->key && !strcmp(node->key, key) )
96 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
97 if(!(key && item)) return NULL;
99 OSRF_MALLOC(n, sizeof(osrfHashNode));
100 n->key = strdup(key);
105 static void* osrfHashNodeFree(osrfHash* hash, osrfHashNode* node) {
106 if(!(node && hash)) return NULL;
109 hash->freeItem( node->key, node->item );
110 else item = node->item;
116 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
117 if(!(hash && item && key )) return NULL;
119 VA_LIST_TO_STRING(key);
120 void* olditem = osrfHashRemove( hash, VA_BUF );
122 unsigned int bucketkey = 0;
123 OSRF_HASH_MAKE_KEY(VA_BUF,bucketkey);
126 if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
127 bucket = osrfNewList();
128 osrfListSet( hash->hash, bucket, bucketkey );
131 osrfHashNode* node = osrfNewHashNode(VA_BUF, item);
132 osrfListPushFirst( bucket, node );
134 if(!osrfStringArrayContains(hash->keys, VA_BUF))
135 osrfStringArrayAdd( hash->keys, VA_BUF );
141 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
142 if(!(hash && key )) return NULL;
144 VA_LIST_TO_STRING(key);
146 osrfList* list = NULL;
148 int index = osrfHashFindItem( hash, (char*) VA_BUF, &list, &node );
149 if( index == -1 ) return NULL;
151 osrfListRemove( list, index );
154 void* item = osrfHashNodeFree(hash, node);
155 osrfStringArrayRemove(hash->keys, VA_BUF);
160 void* osrfHashGet( osrfHash* hash, const char* key, ... ) {
161 if(!(hash && key )) return NULL;
162 VA_LIST_TO_STRING(key);
164 osrfHashNode* node = NULL;
165 int index = osrfHashFindItem( hash, (char*) VA_BUF, NULL, &node );
166 if( index == -1 ) return NULL;
171 osrfStringArray* osrfHashKeysInc( osrfHash* hash ) {
172 if(!hash) return NULL;
176 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
177 if(!hash) return NULL;
182 osrfStringArray* strings = osrfNewStringArray(8);
184 for( i = 0; i != hash->hash->size; i++ ) {
185 list = OSRF_LIST_GET_INDEX( hash->hash, i );
187 for( k = 0; k != list->size; k++ ) {
188 node = OSRF_LIST_GET_INDEX( list, k );
189 if( node ) osrfStringArrayAdd( strings, node->key );
198 unsigned long osrfHashGetCount( osrfHash* hash ) {
203 void osrfHashFree( osrfHash* hash ) {
210 for( i = 0; i != hash->hash->size; i++ ) {
211 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
212 for( j = 0; j != list->size; j++ ) {
213 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
214 OSRF_HASH_NODE_FREE(hash, node);
221 osrfListFree(hash->hash);
222 OSRF_STRING_ARRAY_FREE(hash->keys);
228 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
229 if(!hash) return NULL;
230 osrfHashIterator* itr;
231 OSRF_MALLOC(itr, sizeof(osrfHashIterator));
236 itr->keys = osrfHashKeysInc(hash);
240 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
241 if(!(itr && itr->hash)) return NULL;
242 if( itr->currentIdx >= itr->keys->size ) return NULL;
244 // Copy the string to iter->current
245 const char * curr = osrfStringArrayGetString(itr->keys, itr->currentIdx++);
246 size_t new_len = strlen(curr);
247 if( new_len >= itr->currsize ) {
248 // We need a bigger buffer
250 if(0 == itr->currsize) itr->currsize = 64; //default size
253 } while( new_len >= itr->currsize );
257 itr->current = safe_malloc(itr->currsize);
259 strcpy(itr->current, curr);
261 char* val = osrfHashGet( itr->hash, itr->current );
265 void osrfHashIteratorFree( osrfHashIterator* itr ) {
271 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
272 if( ! itr ) return NULL;
276 void osrfHashIteratorReset( osrfHashIterator* itr ) {
278 if(itr->current) itr->current[0] = '\0';
279 itr->keys = osrfHashKeysInc(itr->hash);
284 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
285 return ( itr->currentIdx < itr->keys->size ) ? 1 : 0;