moved osrf_hash code to osrf_big_hash as the Judy big hash implementation
authorerickson <erickson@dcc99617-32d9-48b4-a31d-7c20da2025e4>
Mon, 13 Mar 2006 22:23:53 +0000 (22:23 +0000)
committererickson <erickson@dcc99617-32d9-48b4-a31d-7c20da2025e4>
Mon, 13 Mar 2006 22:23:53 +0000 (22:23 +0000)
osrf_hash is now a custom hash

git-svn-id: svn://svn.open-ils.org/ILS/trunk@3350 dcc99617-32d9-48b4-a31d-7c20da2025e4

OpenSRF/src/Makefile
OpenSRF/src/libstack/Makefile
OpenSRF/src/libstack/osrf_big_hash.c [new file with mode: 0644]
OpenSRF/src/libstack/osrf_big_hash.h [new file with mode: 0644]
OpenSRF/src/libstack/osrf_hash.c
OpenSRF/src/libstack/osrf_hash.h

index 138ba3c..90f353a 100644 (file)
@@ -33,6 +33,7 @@ OPENSRF_TARGETS =     libtransport/transport_session.o \
                        libstack/osrf_list.o \
                        libstack/osrf_big_list.o \
                        libstack/osrf_hash.o \
+                       libstack/osrf_big_hash.o \
                        utils/socket_bundle.o \
                        utils/string_array.o \
                        utils/utils.o \
@@ -57,6 +58,7 @@ OPENSRF_HEADERS =     libtransport/transport_session.h \
                        libstack/osrf_list.h \
                        libstack/osrf_big_list.h \
                        libstack/osrf_hash.h \
+                       libstack/osrf_big_hash.h \
                        utils/socket_bundle.h \
                        utils/string_array.h \
                        utils/utils.h \
index 5d56669..1de68e4 100644 (file)
@@ -18,6 +18,7 @@ TARGETS = osrf_message.o \
                         osrf_list.o \
                         osrf_big_list.o \
                         osrf_hash.o \
+                        osrf_big_hash.o \
                         xml_utils.o
 
 HEADERS = osrf_message.h \
@@ -33,6 +34,7 @@ HEADERS = osrf_message.h \
                         osrf_list.h \
                         osrf_big_list.h \
                         osrf_hash.h \
+                        osrf_big_hash.h \
                         xml_utils.h
 
 all: xml_utils.o $(TARGETS) copy 
@@ -57,6 +59,7 @@ osrf_cache.o: osrf_cache.c osrf_cache.h
 osrf_list.o:   osrf_list.c osrf_list.h
 osrf_big_list.o:       osrf_big_list.c osrf_big_list.h
 osrf_hash.o:   osrf_hash.c osrf_hash.h
+osrf_big_hash.o:       osrf_big_hash.c osrf_big_hash.h
 
 
 clean:
diff --git a/OpenSRF/src/libstack/osrf_big_hash.c b/OpenSRF/src/libstack/osrf_big_hash.c
new file mode 100644 (file)
index 0000000..41d5131
--- /dev/null
@@ -0,0 +1,173 @@
+#include "osrf_big_hash.h"
+
+osrfBigHash* osrfNewBigHash() {
+       osrfBigHash* hash = safe_malloc(sizeof(osrfBigHash));
+       hash->hash = (Pvoid_t) NULL;
+       hash->freeItem = NULL;
+       return hash;
+}
+
+void* osrfBigHashSet( osrfBigHash* 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 = osrfBigHashRemove( hash, VA_BUF );
+
+       JSLI(value, hash->hash, idx);
+       if(value) *value = (Word_t) item;
+       return olditem;
+       
+}
+
+void* osrfBigHashRemove( osrfBigHash* 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 );
+       void* item = NULL;
+       int retcode;
+
+       JSLG( value, hash->hash,  idx);
+
+       if( value ) {
+               item = (void*) *value;
+               if(item) {
+                       if( hash->freeItem ) {
+                               hash->freeItem( (char*) idx, item ); 
+                               item = NULL;
+                       }
+               }
+       }
+
+
+       JSLD( retcode, hash->hash, idx );
+
+       return item;
+}
+
+
+void* osrfBigHashGet( osrfBigHash* 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;
+}
+
+
+osrfStringArray* osrfBigHashKeys( osrfBigHash* hash ) {
+       if(!hash) return NULL;
+
+       Word_t* value;
+       uint8_t idx[OSRF_HASH_MAXKEY];
+       strcpy(idx, "");
+       char* key;
+       osrfStringArray* strings = osrfNewStringArray(8);
+
+       JSLF( value, hash->hash, idx );
+
+       while( value ) {
+               key = (char*) idx;
+               osrfStringArrayAdd( strings, key );
+               JSLN( value, hash->hash, idx );
+       }
+
+       return strings;
+}
+
+
+unsigned long osrfBigHashGetCount( osrfBigHash* 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;
+}
+
+void osrfBigHashFree( osrfBigHash* hash ) {
+       if(!hash) return;
+
+       int i;
+       osrfStringArray* keys = osrfBigHashKeys( hash );
+
+       for( i = 0; i != keys->size; i++ )  {
+               char* key = (char*) osrfStringArrayGetString( keys, i );
+               osrfBigHashRemove( hash, key );
+       }
+
+       osrfStringArrayFree(keys);
+       free(hash);
+}
+
+
+
+osrfBigHashIterator* osrfNewBigHashIterator( osrfBigHash* hash ) {
+       if(!hash) return NULL;
+       osrfBigHashIterator* itr = safe_malloc(sizeof(osrfBigHashIterator));
+       itr->hash = hash;
+       itr->current = NULL;
+       return itr;
+}
+
+void* osrfBigHashIteratorNext( osrfBigHashIterator* 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;
+
+}
+
+void osrfBigHashIteratorFree( osrfBigHashIterator* itr ) {
+       if(!itr) return;
+       free(itr->current);
+       free(itr);
+}
+
+void osrfBigHashIteratorReset( osrfBigHashIterator* itr ) {
+       if(!itr) return;
+       free(itr->current);
+       itr->current = NULL;
+}
+
+
+
diff --git a/OpenSRF/src/libstack/osrf_big_hash.h b/OpenSRF/src/libstack/osrf_big_hash.h
new file mode 100644 (file)
index 0000000..22e0a46
--- /dev/null
@@ -0,0 +1,87 @@
+#ifndef OSRF_HASH_H
+#define OSRF_HASH_H
+
+#include <Judy.h>
+#include "opensrf/utils.h"
+#include "opensrf/string_array.h"
+
+#define OSRF_HASH_MAXKEY 256
+
+struct __osrfBigHashStruct {
+       Pvoid_t hash;                                                   /* the hash */
+       void (*freeItem) (char* key, void* item);       /* callback for freeing stored items */
+};
+typedef struct __osrfBigHashStruct osrfBigHash;
+
+
+struct __osrfBigHashIteratorStruct {
+       char* current;
+       osrfBigHash* hash;
+};
+typedef struct __osrfBigHashIteratorStruct osrfBigHashIterator;
+
+/**
+  Allocates a new hash object
+  */
+osrfBigHash* osrfNewBigHash();
+
+/**
+  Sets the given key with the given item
+  if "freeItem" is defined and an item already exists at the given location, 
+  then old item is freed and the new item is put into place.
+  if "freeItem" is not defined and an item already exists, the old item
+  is returned.
+  @return The old item if exists and there is no 'freeItem', returns NULL
+  otherwise
+  */
+void* osrfBigHashSet( osrfBigHash* hash, void* item, const char* key, ... );
+
+/**
+  Removes an item from the hash.
+  if 'freeItem' is defined it is used and NULL is returned,
+  else the freed item is returned
+  */
+void* osrfBigHashRemove( osrfBigHash* hash, const char* key, ... );
+
+void* osrfBigHashGet( osrfBigHash* hash, const char* key, ... );
+
+
+/**
+  @return A list of strings representing the keys of the hash. 
+  caller is responsible for freeing the returned string array 
+  with osrfStringArrayFree();
+  */
+osrfStringArray* osrfBigHashKeys( osrfBigHash* hash );
+
+/**
+  Frees a hash
+  */
+void osrfBigHashFree( osrfBigHash* hash );
+
+/**
+  @return The number of items in the hash
+  */
+unsigned long osrfBigHashGetCount( osrfBigHash* hash );
+
+
+
+
+/**
+  Creates a new list iterator with the given list
+  */
+osrfBigHashIterator* osrfNewBigHashIterator( osrfBigHash* hash );
+
+/**
+  Returns the next non-NULL item in the list, return NULL when
+  the end of the list has been reached
+  */
+void* osrfBigHashIteratorNext( osrfBigHashIterator* itr );
+
+/**
+  Deallocates the given list
+  */
+void osrfBigHashIteratorFree( osrfBigHashIterator* itr );
+
+void osrfBigHashIteratorReset( osrfBigHashIterator* itr );
+
+#endif
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;
 }
 
index 0290e23..e176b51 100644 (file)
@@ -1,25 +1,41 @@
 #ifndef OSRF_HASH_H
 #define OSRF_HASH_H
 
-#include <Judy.h>
 #include "opensrf/utils.h"
 #include "opensrf/string_array.h"
+#include "osrf_list.h"
 
 #define OSRF_HASH_MAXKEY 256
 
+#define OSRF_HASH_KEY_MASK 0x7FF  /* hash keys are a maximun of 2047 in size */
+#define OSRF_HASH_KEY_SIZE 2048  /* size of the container list for the keys */
+
+
 struct __osrfHashStruct {
-       Pvoid_t hash;                                                   /* the hash */
+       osrfList* hash; /* this hash */
        void (*freeItem) (char* key, void* item);       /* callback for freeing stored items */
+       unsigned int size;
 };
 typedef struct __osrfHashStruct osrfHash;
 
+struct _osrfHashNodeStruct {
+       char* key;
+       void* item;
+};
+typedef struct _osrfHashNodeStruct osrfHashNode;
+
 
 struct __osrfHashIteratorStruct {
        char* current;
+       int currentIdx;
        osrfHash* hash;
+       osrfStringArray* keys;
 };
 typedef struct __osrfHashIteratorStruct osrfHashIterator;
 
+osrfHashNode* osrfNewHashNode(char* key, void* item);
+void osrfHashNodeFree(osrfHashNode*);
+
 /**
   Allocates a new hash object
   */