moved osrf_hash code to osrf_big_hash as the Judy big hash implementation
[Evergreen.git] / OpenSRF / src / libstack / osrf_hash.c
index 819b979..968e9b9 100644 (file)
@@ -2,25 +2,85 @@
 
 osrfHash* osrfNewHash() {
        osrfHash* hash = safe_malloc(sizeof(osrfHash));
-       hash->hash = (Pvoid_t) NULL;
+       hash->hash              = osrfNewList();
        hash->freeItem = NULL;
+       hash->size              = 0;
        return hash;
 }
 
+
+/* algorithm proposed by Donald E. Knuth 
+ * in The Art Of Computer Programming Volume 3 (more or less..)*/
+static unsigned int osrfHashMakeKey(char* str) {
+       if(!str) return 0;
+       unsigned int len = strlen(str);
+       unsigned int h = len;
+       unsigned int i    = 0;
+       for(i = 0; i < len; str++, i++)
+               h = ((h << 5) ^ (h >> 27)) ^ (*str);
+       return (h & 0x7FF);
+}
+
+
+/* returns the index of the item and points l to the sublist the item
+ * lives in if the item and points n to the hashnode the item 
+ * lives in if the item is found.  Otherwise -1 is returned */
+static unsigned int osrfHashFindItem( osrfHash* hash, char* key, osrfList** l, osrfHashNode** n ) {
+       if(!(hash && key)) return -1;
+
+       int i = osrfHashMakeKey(key);
+       osrfList* list = osrfListGetIndex( hash->hash, i );
+       if( !list ) { return -1; }
+
+
+       int k;
+       osrfHashNode* node = NULL;
+       for( k = 0; k < list->size; k++ ) {
+               node = osrfListGetIndex(list, k);
+               if( node && node->key && !strcmp(node->key, key) )
+                       break;
+               node = NULL;
+       }
+
+       if(!node) return -1;
+
+       if(l) *l = list;
+       if(n) *n = node;
+       return k;
+}
+
+osrfHashNode* osrfNewHashNode(char* key, void* item) {
+       if(!(key && item)) return NULL;
+       osrfHashNode* n = safe_malloc(sizeof(osrfHashNode));
+       n->key = strdup(key);
+       n->item = item;
+       return n;
+}
+
+void osrfHashNodeFree(osrfHashNode* node) {
+       if(!node) return;
+       free(node->key);
+       free(node);
+}
+
 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
        if(!(hash && item && key )) return NULL;
 
-       Word_t* value;
        VA_LIST_TO_STRING(key);
-       uint8_t idx[strlen(VA_BUF) + 1];
-       strcpy( idx, VA_BUF );
-
        void* olditem = osrfHashRemove( hash, VA_BUF );
+       int bucketkey = osrfHashMakeKey(VA_BUF);
+
+       osrfList* bucket;
+       if( !(bucket = osrfListGetIndex(hash->hash, bucketkey)) ) {
+               bucket = osrfNewList();
+               osrfListSet( hash->hash, bucket, bucketkey );
+       }
 
-       JSLI(value, hash->hash, idx);
-       if(value) *value = (Word_t) item;
+       osrfHashNode* node = osrfNewHashNode(VA_BUF, item);
+       osrfListPushFirst( bucket, node );
+
+       hash->size++;
        return olditem;
-       
 }
 
 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
@@ -28,61 +88,51 @@ void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
 
        VA_LIST_TO_STRING(key);
 
-       Word_t* value;
-       uint8_t idx[strlen(VA_BUF) + 1];
-       strcpy( idx, VA_BUF );
-       void* item = NULL;
-       int retcode;
-
-       JSLG( value, hash->hash,  idx);
+       osrfList* list = NULL;
+       osrfHashNode* node;
+       int index = osrfHashFindItem( hash, (char*) VA_BUF, &list, &node );
+       if( index == -1 ) return NULL;
 
-       if( value ) {
-               item = (void*) *value;
-               if(item) {
-                       if( hash->freeItem ) {
-                               hash->freeItem( (char*) idx, item ); 
-                               item = NULL;
-                       }
-               }
-       }
+       osrfListRemove( list, index );
+       hash->size--;
 
+       void* item = NULL;
+       if(hash->freeItem) 
+               hash->freeItem((char*) VA_BUF, node->item);
+        else item = node->item;
 
-       JSLD( retcode, hash->hash, idx );
-
+       osrfHashNodeFree(node);
        return item;
 }
 
 
 void* osrfHashGet( osrfHash* hash, const char* key, ... ) {
        if(!(hash && key )) return NULL;
-
        VA_LIST_TO_STRING(key);
 
-       Word_t* value;
-       uint8_t idx[strlen(VA_BUF) + 1];
-       strcpy( idx, VA_BUF );
-
-       JSLG( value, hash->hash, idx );
-       if(value) return (void*) *value;
-       return NULL;
+       osrfHashNode* node = NULL;
+       int index = osrfHashFindItem( hash, (char*) VA_BUF, NULL, &node );
+       if( index == -1 ) return NULL;
+       return node->item;
 }
 
 
 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
        if(!hash) return NULL;
 
-       Word_t* value;
-       uint8_t idx[OSRF_HASH_MAXKEY];
-       strcpy(idx, "");
-       char* key;
+       int i, k;
+       osrfList* list;
+       osrfHashNode* node;
        osrfStringArray* strings = osrfNewStringArray(8);
 
-       JSLF( value, hash->hash, idx );
-
-       while( value ) {
-               key = (char*) idx;
-               osrfStringArrayAdd( strings, key );
-               JSLN( value, hash->hash, idx );
+       for( i = 0; i != hash->hash->size; i++ ) {
+               list = osrfListGetIndex( hash->hash, i );
+               if(list) {
+                       for( k = 0; k != list->size; k++ ) {
+                               node = osrfListGetIndex( list, k );     
+                               if( node ) osrfStringArrayAdd( strings, node->key );
+                       }
+               }
        }
 
        return strings;
@@ -91,34 +141,30 @@ osrfStringArray* osrfHashKeys( osrfHash* hash ) {
 
 unsigned long osrfHashGetCount( osrfHash* hash ) {
        if(!hash) return -1;
-
-       Word_t* value;
-       unsigned long count = 0;
-       uint8_t idx[OSRF_HASH_MAXKEY];
-
-       strcpy( (char*) idx, "");
-       JSLF(value, hash->hash, idx);
-
-       while(value) {
-               count++;
-               JSLN( value, hash->hash, idx );
-       }
-
-       return count;
+       return hash->size;
 }
 
 void osrfHashFree( osrfHash* hash ) {
        if(!hash) return;
 
-       int i;
-       osrfStringArray* keys = osrfHashKeys( hash );
-
-       for( i = 0; i != keys->size; i++ )  {
-               char* key = (char*) osrfStringArrayGetString( keys, i );
-               osrfHashRemove( hash, key );
+       int i, j;
+       osrfList* list;
+       osrfHashNode* node;
+
+       for( i = 0; i != hash->hash->size; i++ ) {
+               if( ( list = osrfListGetIndex( hash->hash, i )) ) {
+                       for( j = 0; j != list->size; j++ ) {
+                               if( (node = osrfListGetIndex( list, j )) ) {
+                                       if( hash->freeItem )
+                                               hash->freeItem( node->key, node->item );
+                                       osrfHashNodeFree(node);
+                               }
+                       }
+                       osrfListFree(list);
+               }
        }
 
-       osrfStringArrayFree(keys);
+       osrfListFree(hash->hash);
        free(hash);
 }
 
@@ -129,43 +175,33 @@ osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
        osrfHashIterator* itr = safe_malloc(sizeof(osrfHashIterator));
        itr->hash = hash;
        itr->current = NULL;
+       itr->keys = osrfHashKeys(hash);
        return itr;
 }
 
 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
        if(!(itr && itr->hash)) return NULL;
-
-       Word_t* value;
-       uint8_t idx[OSRF_HASH_MAXKEY];
-
-       if( itr->current == NULL ) { /* get the first item in the list */
-               strcpy(idx, "");
-               JSLF( value, itr->hash->hash, idx );
-
-       } else {
-               strcpy(idx, itr->current);
-               JSLN( value, itr->hash->hash, idx );
-       }
-
-       if(value) {
-               free(itr->current);
-               itr->current = strdup((char*) idx);
-               return (void*) *value;
-       }
-
-       return NULL;
-
+       if( itr->currentIdx >= itr->keys->size ) return NULL;
+       free(itr->current);
+       itr->current = strdup(
+                       osrfStringArrayGetString(itr->keys, itr->currentIdx++));
+       char* val = osrfHashGet( itr->hash, itr->current );
+       return val;
 }
 
 void osrfHashIteratorFree( osrfHashIterator* itr ) {
        if(!itr) return;
        free(itr->current);
+       osrfStringArrayFree(itr->keys);
        free(itr);
 }
 
 void osrfHashIteratorReset( osrfHashIterator* itr ) {
        if(!itr) return;
        free(itr->current);
+       osrfStringArrayFree(itr->keys);
+       itr->keys = osrfHashKeys(itr->hash);
+       itr->currentIdx = 0;
        itr->current = NULL;
 }