From: "Mauricio Fernández" <batsman.geo@...>
Date: 2002-09-02T08:22:00+09:00
Subject: Judy inside st_*


--fUYQa+Pmc3FrFX/N
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline


Attached is my latest development on the new st_* routines based on 
JudyL arrays. It is now nearly as fast as the standard hashing method,
and there shouldn't be many bugs left.

I won't be able to work on this for a while as I'm moving to
Stuttgart (Germany) tomorrow from Madrid (Spain), and I don't know when
I'll get a computer...

BTW, I've seen there's a Ruby Users Group in B.-W. :-)

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com
  
Linux: Where Don't We Want To Go Today?
	-- Submitted by Pancrazio De Mauro, paraphrasing some well-known sales talk

--fUYQa+Pmc3FrFX/N
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="ruby-judy-0.0.2.patch"

diff -rwdu ruby/configure.in ruby-judy/configure.in
--- ruby/configure.in	Sun Aug 11 23:43:24 2002
+++ ruby-judy/configure.in	Wed Aug 28 12:20:31 2002
@@ -281,6 +281,7 @@
 AC_CHECK_LIB(crypt, crypt)
 AC_CHECK_LIB(dl, dlopen)	# Dynamic linking for SunOS/Solaris and SYSV
 AC_CHECK_LIB(dld, shl_load)	# Dynamic linking for HP-UX
+AC_CHECK_LIB(Judy, JudyLIns)	# Judy 
 
 dnl Checks for header files.
 AC_HEADER_DIRENT
diff -rwdu ruby/hash.c ruby-judy/hash.c
--- ruby/hash.c	Wed Jul 31 00:30:17 2002
+++ ruby-judy/hash.c	Fri Aug 30 10:44:30 2002
@@ -125,11 +125,10 @@
 {
     int status;
     st_table *tbl = RHASH(arg->hash)->tbl;
-    struct st_table_entry **bins = tbl->bins;
 
     if (key == Qundef) return ST_CONTINUE;
     status = (*arg->func)(key, value, arg->arg);
-    if (RHASH(arg->hash)->tbl != tbl || RHASH(arg->hash)->tbl->bins != bins){
+    if (RHASH(arg->hash)->tbl != tbl){
 	rb_raise(rb_eIndexError, "rehash occurred during iteration");
     }
     return status;
@@ -280,10 +279,12 @@
 {
     st_table *tbl;
 
+#ifndef HAVE_LIBJUDY
     tbl = st_init_table_with_size(&objhash, RHASH(hash)->tbl->num_entries);
     st_foreach(RHASH(hash)->tbl, rb_hash_rehash_i, tbl);
     st_free_table(RHASH(hash)->tbl);
     RHASH(hash)->tbl = tbl;
+#endif
 
     return hash;
 }
@@ -544,9 +545,12 @@
     VALUE hash, key, val;
 {
     rb_hash_modify(hash);
-    if (TYPE(key) != T_STRING || st_lookup(RHASH(hash)->tbl, key, 0)) {
+	if ( TYPE(key) != T_STRING ) {
 	st_insert(RHASH(hash)->tbl, key, val);
     }
+	else if ( st_update_if_present(RHASH(hash)->tbl, key, val) ) {
+	/* do nothing, as it was already in and has been updated*/
+    }
     else {
 	st_add_direct(RHASH(hash)->tbl, rb_str_new4(key), val);
     }
diff -rwdu ruby/st.c ruby-judy/st.c
--- ruby/st.c	Wed Jul 31 00:30:20 2002
+++ ruby-judy/st.c	Sun Sep  1 00:39:37 2002
@@ -11,27 +11,18 @@
 #include <malloc.h>
 #endif
 
+#include <Judy.h>
+
+#define HASH_LOG
+
 typedef struct st_table_entry st_table_entry;
 
 struct st_table_entry {
-    unsigned int hash;
     char *key;
     char *record;
     st_table_entry *next;
 };
 
-#define ST_DEFAULT_MAX_DENSITY 5
-#define ST_DEFAULT_INIT_TABLE_SIZE 11
-
-    /*
-     * DEFAULT_MAX_DENSITY is the default for the largest we allow the
-     * average number of items per bin before increasing the number of
-     * bins
-     *
-     * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
-     * allocated initially
-     *
-     */
 static int numcmp();
 static int numhash();
 static struct st_hash_type type_numhash = {
@@ -66,73 +57,14 @@
 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
 
 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
-#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
-
-/*
- * MINSIZE is the minimum size of a dictionary.
- */
-
-#define MINSIZE 8
-
-/*
-Table of prime numbers 2^n+a, 2<=n<=30.
-*/
-static long primes[] = {
-	8 + 3,
-	16 + 3,
-	32 + 5,
-	64 + 3,
-	128 + 3,
-	256 + 27,
-	512 + 9,
-	1024 + 9,
-	2048 + 5,
-	4096 + 3,
-	8192 + 27,
-	16384 + 43,
-	32768 + 3,
-	65536 + 45,
-	131072 + 29,
-	262144 + 3,
-	524288 + 21,
-	1048576 + 7,
-	2097152 + 17,
-	4194304 + 15,
-	8388608 + 9,
-	16777216 + 43,
-	33554432 + 35,
-	67108864 + 15,
-	134217728 + 29,
-	268435456 + 3,
-	536870912 + 11,
-	1073741824 + 85,
-	0
-};
+#define do_hash_bin(key,table) (do_hash(key, table) % HASHSIZE)
 
-static int
-new_size(size)
-    int size;
-{
-    int i;
+#define HASHARRAY(table,code) ((table)->PJLArray[(code) % HASHSIZE])
+#define HASHINDEX(code) ((code)/HASHSIZE)
+#define HASHNODE(ppv) (* (st_table_entry **)ppv)
+#define NEWNODE(ppv) *(ppv) = calloc(1, sizeof(st_table_entry))
 
-#if 0
-    for (i=3; i<31; i++) {
-	if ((1<<i) > size) return 1<<i;
-    }
-    return -1;
-#else
-    int newsize;
 
-    for (i = 0, newsize = MINSIZE;
-	 i < sizeof(primes)/sizeof(primes[0]);
-	 i++, newsize <<= 1)
-    {
-	if (newsize > size) return primes[i];
-    }
-    /* Ran out of polynomials */
-    return -1;			/* should raise exception */
-#endif
-}
 
 #ifdef HASH_LOG
 static int collision = 0;
@@ -153,6 +85,12 @@
     int size;
 {
     st_table *tbl;
+    int i;
+   
+    tbl = alloc(st_table);
+    //FIXME: optimize
+    for ( i = 0; i < HASHSIZE; i++ )
+        tbl->PJLArray[i] = 0;
 
 #ifdef HASH_LOG
     if (init_st == 0) {
@@ -161,13 +99,8 @@
     }
 #endif
 
-    size = new_size(size);	/* round up to prime number */
-
-    tbl = alloc(st_table);
     tbl->type = type;
     tbl->num_entries = 0;
-    tbl->num_bins = size;
-    tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
 
     return tbl;
 }
@@ -211,21 +144,28 @@
 {
     register st_table_entry *ptr, *next;
     int i;
+    PPvoid_t PValue;
+    Word_t Index, Useless;
+    st_table_entry *pNode, *pTmp;
 
-    for(i = 0; i < table->num_bins; i++) {
-	ptr = table->bins[i];
-	while (ptr != 0) {
-	    next = ptr->next;
-	    free(ptr);
-	    ptr = next;
+    for(i = 0; i < HASHSIZE; i++) {
+		Index = 0;
+		JLF( PValue, table->PJLArray[i], Index);
+		while (PValue) {
+			// go through all the positions inside the Judy array
+			pNode = HASHNODE(PValue);
+			while (pNode) {   // clear the collision list
+				pTmp = pNode;
+				pNode = pNode->next;
+				free(pTmp);	
 	}
+			JLN( PValue, table->PJLArray[i], Index);
     }
-    free(table->bins);
-    free(table);
+		JLFA( Useless, table->PJLArray[i] );
 }
 
-#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
-((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
+ 	free(table);
+}
 
 #ifdef HASH_LOG
 #define COLLISION collision++
@@ -234,14 +174,25 @@
 #endif
 
 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
-    bin_pos = hash_val%(table)->num_bins;\
-    ptr = (table)->bins[bin_pos];\
-    if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
+    PPvoid_t PValue;\
+	\
+	bin_pos = HASHINDEX(hash_val);\
+	/*FIXME: error handling? */\
+	/*FIXME: is JLG really faster than JudyLGet?*/\
+    JLG(PValue,HASHARRAY(table,hash_val), bin_pos);\
+	if (PValue) {\
+		ptr = HASHNODE(PValue);\
+		if ( ptr ) {\
+				if ( EQUAL(table, ptr->key, key) ) \
+					break;\
 	COLLISION;\
-	while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
-	    ptr = ptr->next;\
+				for ( ptr = ptr->next; ptr; ptr = ptr->next)\
+					if ( EQUAL(table, ptr->key, key) ) \
+						break;\
 	}\
-	ptr = ptr->next;\
+	}\
+	else {\
+		ptr = 0;\
     }\
 } while (0)
 
@@ -269,18 +220,15 @@
 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
 do {\
     st_table_entry *entry;\
-    if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
-	rehash(table);\
-        bin_pos = hash_val % table->num_bins;\
-    }\
+	PPvoid_t PValue;\
     \
-    entry = alloc(st_table_entry);\
+    JLI( PValue, HASHARRAY(table,hash_val), bin_pos );\
     \
-    entry->hash = hash_val;\
+	entry = alloc(st_table_entry);\
     entry->key = key;\
     entry->record = value;\
-    entry->next = table->bins[bin_pos];\
-    table->bins[bin_pos] = entry;\
+	entry->next = HASHNODE(PValue);\
+	*PValue = entry;\
     table->num_entries++;\
 } while (0)
 
@@ -292,12 +240,59 @@
 {
     unsigned int hash_val, bin_pos;
     register st_table_entry *ptr;
+	PPvoid_t PValue;
+
+
+    hash_val = do_hash(key, table);
+	JLI( PValue, HASHARRAY(table, hash_val), HASHINDEX(hash_val) );
+	if ( *PValue ) {
+		ptr = HASHNODE(PValue);
+		/* we layout the code this way to be able to count collisions */
+		if ( ptr ) {
+			if (EQUAL(table, ptr->key, key) ) {
+				ptr->record = value;
+				return 1;
+			}  
+			COLLISION;
+			for ( ptr = ptr->next; ptr; ptr = ptr->next )
+				if ( EQUAL(table, ptr->key, key) ) {
+					ptr->record = value;
+					return 1;
+				}
+		}
+		/* if it gets here, either the has was empty or no element had 
+		 * the same key */
+		ptr = alloc(st_table_entry);
+		ptr->key = key;
+		ptr->record = value;
+		ptr->next = *PValue;
+		*PValue = ptr;
+		++table->num_entries;
+		return 0;
+    }
+    else {
+		*PValue = alloc(st_table_entry);
+		HASHNODE(PValue)->key = key;
+		HASHNODE(PValue)->record = value;
+		HASHNODE(PValue)->next = 0;
+		++table->num_entries;
+		return 0;
+    }
+}
+
+int
+st_update_if_present(table, key, value)
+    st_table *table;
+    register char *key;
+    char *value;
+{
+    unsigned int hash_val, bin_pos;
+    register st_table_entry *ptr;
 
     hash_val = do_hash(key, table);
     FIND_ENTRY(table, ptr, hash_val, bin_pos);
 
     if (ptr == 0) {
-	ADD_DIRECT(table, key, value, hash_val, bin_pos);
 	return 0;
     }
     else {
@@ -315,72 +310,46 @@
     unsigned int hash_val, bin_pos;
 
     hash_val = do_hash(key, table);
-    bin_pos = hash_val % table->num_bins;
+	bin_pos = HASHINDEX(hash_val);
     ADD_DIRECT(table, key, value, hash_val, bin_pos);
 }
 
-static void
-rehash(table)
-    register st_table *table;
-{
-    register st_table_entry *ptr, *next, **new_bins;
-    int i, old_num_bins = table->num_bins, new_num_bins;
-    unsigned int hash_val;
-
-    new_num_bins = new_size(old_num_bins+1);
-    new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
-
-    for(i = 0; i < old_num_bins; i++) {
-	ptr = table->bins[i];
-	while (ptr != 0) {
-	    next = ptr->next;
-	    hash_val = ptr->hash % new_num_bins;
-	    ptr->next = new_bins[hash_val];
-	    new_bins[hash_val] = ptr;
-	    ptr = next;
-	}
-    }
-    free(table->bins);
-    table->num_bins = new_num_bins;
-    table->bins = new_bins;
-}
-
 st_table*
 st_copy(old_table)
     st_table *old_table;
 {
     st_table *new_table;
-    st_table_entry *ptr, *entry;
-    int i, num_bins = old_table->num_bins;
+    st_table_entry *oldptr, *ptr, **entry;
+	PPvoid_t PValue;
+	Word_t Index;
+    int i;
 
-    new_table = alloc(st_table);
+    new_table = st_init_table( old_table->type );
     if (new_table == 0) {
 	return 0;
     }
 
-    *new_table = *old_table;
-    new_table->bins = (st_table_entry**)
-	Calloc((unsigned)num_bins, sizeof(st_table_entry*));
-
-    if (new_table->bins == 0) {
-	free(new_table);
-	return 0;
-    }
+    new_table->num_entries = old_table->num_entries;
 
-    for(i = 0; i < num_bins; i++) {
-	new_table->bins[i] = 0;
-	ptr = old_table->bins[i];
-	while (ptr != 0) {
-	    entry = alloc(st_table_entry);
-	    if (entry == 0) {
-		free(new_table->bins);
-		free(new_table);
-		return 0;
+    for(i = 0; i < HASHSIZE; i++) {
+		Index = 0;
+		JLF( PValue, old_table->PJLArray[i], Index );
+		while( PValue ) {
+			//FIXME: should assert( *PValue ); ?
+			JLI( entry, new_table->PJLArray[i], Index );
+			*entry = alloc(st_table_entry);
+			(*entry)->key = HASHNODE(PValue)->key;
+			(*entry)->record = HASHNODE(PValue)->record;
+			(*entry)->next = 0;
+			for (oldptr = HASHNODE(PValue)->next; oldptr; oldptr = oldptr->next) {
+				ptr = alloc(st_table_entry);
+				// FIXME: check error in memory allocation
+				ptr->key = oldptr->key;
+				ptr->record = oldptr->record;
+				ptr->next = *entry;
+				*entry = ptr;
 	    }
-	    *entry = *ptr;
-	    entry->next = new_table->bins[i];
-	    new_table->bins[i] = entry;
-	    ptr = ptr->next;
+			JLN( PValue, old_table->PJLArray[i], Index );
 	}
     }
     return new_table;
@@ -394,33 +363,27 @@
 {
     unsigned int hash_val;
     st_table_entry *tmp;
-    register st_table_entry *ptr;
-
-    hash_val = do_hash_bin(*key, table);
-    ptr = table->bins[hash_val];
+    register st_table_entry **ptr, *ptr2;
+	int useless;
 
+    hash_val = do_hash(*key, table);
+    JLG( ptr, HASHARRAY(table, hash_val), HASHINDEX(hash_val) );
     if (ptr == 0) {
 	if (value != 0) *value = 0;
 	return 0;
     }
 
-    if (EQUAL(table, *key, ptr->key)) {
-	table->bins[hash_val] = ptr->next;
-	table->num_entries--;
-	if (value != 0) *value = ptr->record;
-	*key = ptr->key;
-	free(ptr);
-	return 1;
-    }
-
-    for(; ptr->next != 0; ptr = ptr->next) {
-	if (EQUAL(table, ptr->next->key, *key)) {
-	    tmp = ptr->next;
-	    ptr->next = ptr->next->next;
-	    table->num_entries--;
-	    if (value != 0) *value = tmp->record;
-	    *key = tmp->key;
-	    free(tmp);
+	for( tmp = 0, ptr2 = *ptr; ptr2; tmp = ptr2, ptr2 = ptr2->next ) {
+		if (EQUAL(table, ptr2->key, *key)) {
+			if(value) *value = ptr2->record;
+			if(tmp) 
+				tmp->next = ptr2->next;
+			else // head of the list
+				*ptr = (*ptr)->next;
+			free( ptr2 );
+			if ( ! *ptr ) 
+				JLD( useless, HASHARRAY(table,hash_val), HASHINDEX(hash_val) );
+			--table->num_entries;
 	    return 1;
 	}
     }
@@ -437,15 +400,17 @@
 {
     unsigned int hash_val;
     register st_table_entry *ptr;
+	PPvoid_t pValue;
 
-    hash_val = do_hash_bin(*key, table);
-    ptr = table->bins[hash_val];
+    hash_val = do_hash(*key, table);
+    JLG( pValue, HASHARRAY(table,hash_val), HASHINDEX(hash_val) );
 
-    if (ptr == 0) {
+    if (pValue == 0) {
 	if (value != 0) *value = 0;
 	return 0;
     }
 
+	ptr = HASHNODE(pValue);
     for(; ptr != 0; ptr = ptr->next) {
 	if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
 	    table->num_entries--;
@@ -472,10 +437,10 @@
     st_table *table;
     char *never;
 {
-    int num_entries = table->num_entries;
+    //int num_entries = table->num_entries;
 
     st_foreach(table, delete_never, never);
-    table->num_entries = num_entries;
+    //table->num_entries = num_entries;
 }
 
 void
@@ -485,12 +450,21 @@
     char *arg;
 {
     st_table_entry *ptr, *last, *tmp;
+	PPvoid_t PValue;
+	Word_t Index;
     enum st_retval retval;
     int i;
 
-    for(i = 0; i < table->num_bins; i++) {
+    for(i = 0; i < HASHSIZE; i++) {
+		Index = 0;
+		if ( table->PJLArray[i] == 0 )  // empty JudyL array
+			continue; 
+		JLF( PValue, table->PJLArray[i], Index );
+		while ( PValue ) {
 	last = 0;
-	for(ptr = table->bins[i]; ptr != 0;) {
+			ptr = HASHNODE(PValue);
+			while ( ptr != 0 ) {
+				/*FIXME: sometimes crashes here with ptr->record == NULL !!!*/
 	    retval = (*func)(ptr->key, ptr->record, arg);
 	    switch (retval) {
 	    case ST_CONTINUE:
@@ -502,7 +476,7 @@
 	    case ST_DELETE:
 		tmp = ptr;
 		if (last == 0) {
-		    table->bins[i] = ptr->next;
+					    HASHNODE(PValue) = ptr->next;
 		}
 		else {
 		    last->next = ptr->next;
@@ -510,9 +484,11 @@
 		ptr = ptr->next;
 		free(tmp);
 		table->num_entries--;
-	    }
-	}
-    }
+	    		} // switch 
+	    	} // while to scan collision list
+			JLN( PValue, table->PJLArray[i], Index );
+		} // while to scan Judy array
+    } // for
 }
 
 static int
@@ -563,3 +539,7 @@
 {
     return n;
 }
+
+/*
+ * vim: ts=4:
+ */
diff -rwdu ruby/st.h ruby-judy/st.h
--- ruby/st.h	Wed Jan  5 05:37:12 2000
+++ ruby-judy/st.h	Sun Sep  1 00:44:07 2002
@@ -6,6 +6,8 @@
 
 #define ST_INCLUDED
 
+#include <Judy.h>
+
 typedef struct st_table st_table;
 
 struct st_hash_type {
@@ -13,11 +15,12 @@
     int (*hash)();
 };
 
+#define HASHSIZE 1
+
 struct st_table {
     struct st_hash_type *type;
-    int num_bins;
     int num_entries;
-    struct st_table_entry **bins;
+    Pvoid_t PJLArray[HASHSIZE];
 };
 
 #define st_is_member(table,key) st_lookup(table,key,(char **)0)
@@ -32,6 +35,7 @@
 st_table *st_init_strtable_with_size();
 int st_delete(), st_delete_safe();
 int st_insert(), st_lookup();
+int st_update_if_present();
 void st_foreach(), st_add_direct(), st_free_table(), st_cleanup_safe();
 st_table *st_copy();
 

--fUYQa+Pmc3FrFX/N--