PATCH to make internal Hash class retain order...

Hi there -

beeing new to ruby (thru rails) and coming from a strong php background

i really miss beeing able to retain order in a Hash. i know that this
has been discussed in the past i also understand that i can always
write my own OrderedHash implemenation in user-space. -but- as a) i
love to poke around b) userspace was too slow for some of my problems
-and- c) it's always best to to let "code speak" i decided to "scratch
my itch" and wrote a patch (against 1.8.4) that will:

* remember the order in which elements have been added to a Hash (at
the cost of 2 extra pointers in every hash-bucket + 2 extra pointers
per hash-table)
* use this order for iterating (st_foreach will use this order)
* implement a call Hash.order! allows the user to change the internal
order;-)

y = { 'd' => '4', 'a' => '1', 'b' => '2', 'c' => '3' }
puts y.inspect

y.order!
puts y.inspect

y.order! {|a,b| b[1] <=> a[1]}
puts y.inspect

will now get you:
{"d"=>"4", "a"=>"1", "b"=>"2", "c"=>"3"}
{"a"=>"1", "b"=>"2", "c"=>"3", "d"=>"4"}
{"d"=>"4", "c"=>"3", "b"=>"2", "a"=>"1"}


please bear with me as i'm not fully used to all the conventions you
use in the code - also this has only seen minimal testing...

suggestions welcome!

regards, tc

--- snipp --

diff -ru ruby-1.8.4/hash.c ruby-thies/hash.c
--- ruby-1.8.4/hash.c	2005-07-19 10:25:37.000000000 +0200
+++ ruby-thies/hash.c	2006-08-12 17:28:56.000000000 +0200
@@ -1195,6 +1195,46 @@
     return entries;
 }

+/*
+ *  call-seq:
+ *     hsh.order!                  => hash
+ *     hsh.order! {|a,b| block }  => hash
+ *
+ *  Orders <i>hsh</i> according to code <code>[</code> <i>key,
+ *  value</i> <code>]</code>. If no block is given the sort order
+ *  defaults to the keyorder.
+ *
+ *     h = { "b" => 30, "c" => 10, "a" => 20  }
+ *     h.order!                       #=> { "c" => 10, "a" => 20, "b"
=> 30 }
+ *     h.order! {|a,b| a[0]<=>b[0]}   #=> { "a" => 20, "b" => 30, "c"
=> 10 }
+ *
+ */
+
+static VALUE
+rb_hash_order(hash)
+    VALUE hash;
+{
+    VALUE *keyorder;
+    VALUE entries = rb_hash_to_a(hash);
+    int i;
+
+    rb_ary_sort_bang(entries);
+
+    keyorder = ALLOC_N(VALUE, RARRAY(entries)->len);
+    if (! keyorder) {
+	return 0;
+    }
+
+    for (i = 0; i < RARRAY(entries)->len; i++) {
+    	keyorder[i] = RARRAY(RARRAY(entries)->ptr[i])->ptr[0];
+    }
+
+    st_reorder(RHASH(hash)->tbl, keyorder);
+    free(keyorder);
+
+    return hash;
+}
+
 static int
 inspect_i(key, value, str)
     VALUE key, value, str;
@@ -2449,6 +2489,7 @@
     rb_define_method(rb_cHash,"each_key", rb_hash_each_key, 0);
     rb_define_method(rb_cHash,"each_pair", rb_hash_each_pair, 0);
     rb_define_method(rb_cHash,"sort", rb_hash_sort, 0);
+    rb_define_method(rb_cHash,"order!", rb_hash_order, 0);

     rb_define_method(rb_cHash,"keys", rb_hash_keys, 0);
     rb_define_method(rb_cHash,"values", rb_hash_values, 0);
diff -ru ruby-1.8.4/rubytest.rb ruby-thies/rubytest.rb
--- ruby-1.8.4/rubytest.rb	2005-02-06 18:03:32.000000000 +0100
+++ ruby-thies/rubytest.rb	2006-08-12 15:04:15.000000000 +0200
@@ -42,6 +42,7 @@
     print "test succeeded\n"
     exit 0
   end
+  puts line
   error << line if line =~ %r:^(sample/test.rb|not):
 end
 print error
Only in ruby-thies: signal.o
Only in ruby-thies: sprintf.o
diff -ru ruby-1.8.4/st.c ruby-thies/st.c
--- ruby-1.8.4/st.c	2005-12-20 05:13:21.000000000 +0100
+++ ruby-thies/st.c	2006-08-12 18:05:55.000000000 +0200
@@ -13,11 +13,25 @@

 typedef struct st_table_entry st_table_entry;

+#define ST_APPEND_TO_GLOBAL_ORDER(tbl, entry)\
+	(entry)->gnext = NULL;\
+	(entry)->gprev = (tbl)->tail;\
+	if ((entry)->gprev) {\
+		(entry)->gprev->gnext = (entry);\
+	}\
+	(tbl)->tail = (entry);\
+	if (! (tbl)->head) {\
+		(tbl)->head = (entry);\
+	}
+
+
 struct st_table_entry {
     unsigned int hash;
     st_data_t key;
     st_data_t record;
     st_table_entry *next;
+    st_table_entry *gprev;
+    st_table_entry *gnext;
 };

 #define ST_DEFAULT_MAX_DENSITY 5
@@ -135,6 +149,52 @@
 }
 #endif

+static int
+st_unlink_entry(table, entry)
+    st_table *table;
+    st_table_entry *entry;
+{
+    int i;
+    st_table_entry *last, *ptr;
+
+    for (i = 0; i < table->num_bins; i++) {
+	last = NULL;
+        ptr = table->bins[i];
+        while (ptr) {
+	    if (ptr == entry) break; /* found */
+	    last = ptr;
+	    ptr = ptr->next;
+   	}
+	if (! ptr) continue; /* correct bin it yet to be found */
+
+	if (last) {
+	    last->next = ptr->next;
+	} else {
+	    table->bins[i] = ptr->next;
+	}
+
+	if (table->head == ptr) {
+		table->head = ptr->gnext;
+	}
+	if (table->tail == ptr) {
+		table->tail = ptr->gprev;
+	}
+
+	if (ptr->gnext) {
+		ptr->gnext->gprev = ptr->gprev;
+	}
+
+	if (ptr->gprev) {
+		ptr->gprev->gnext = ptr->gnext;
+	}
+
+        table->num_entries--;
+	return 1;
+    }
+    return 0;
+}
+
+
 st_table*
 st_init_table_with_size(type, size)
     struct st_hash_type *type;
@@ -157,6 +217,8 @@
     tbl->num_bins = size;
     tbl->bins = (st_table_entry **)Calloc(size,
sizeof(st_table_entry*));

+    tbl->head = tbl->tail = NULL;
+
     return tbl;
 }

@@ -269,6 +331,7 @@
     entry->record = value;\
     entry->next = table->bins[bin_pos];\
     table->bins[bin_pos] = entry;\
+    ST_APPEND_TO_GLOBAL_ORDER(table, entry)\
     table->num_entries++;\
 } while (0)

@@ -339,39 +402,74 @@
 {
     st_table *new_table;
     st_table_entry *ptr, *entry;
-    int i, num_bins = old_table->num_bins;
+    int num_bins = old_table->num_bins;
+    unsigned int bin_pos;

-    new_table = alloc(st_table);
+    new_table = st_init_table_with_size(old_table->type,
old_table->num_bins);
     if (new_table == 0) {
 	return 0;
     }

-    *new_table = *old_table;
-    new_table->bins = (st_table_entry**)
-	Calloc((unsigned)num_bins, sizeof(st_table_entry*));
+    ptr = old_table->head;
+    while (ptr) {
+	entry = alloc(st_table_entry);
+	if (! entry) {
+	    st_free_table(new_table); /* safe as new_table is consistent */
+	    return 0;
+	}
+	*entry = *ptr;
+	bin_pos = entry->hash % num_bins;
+	entry->next = new_table->bins[bin_pos];
+	new_table->bins[bin_pos] = entry;
+	ST_APPEND_TO_GLOBAL_ORDER(new_table, entry);
+	new_table->num_entries++;

-    if (new_table->bins == 0) {
-	free(new_table);
-	return 0;
+	ptr = ptr->gnext;
     }

-    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;
-	    }
-	    *entry = *ptr;
-	    entry->next = new_table->bins[i];
-	    new_table->bins[i] = entry;
-	    ptr = ptr->next;
+    return new_table;
+}
+
+void
+st_reorder(table, keylist)
+    st_table *table;
+    st_data_t *keylist;
+{
+    st_table buf_table, *org_table;
+    st_table_entry *entry;
+    st_data_t key;
+    unsigned int i, hash_val, bin_pos;
+
+    /*
+     * "algorithmus":
+     * 1 remeber old table content
+     * 2 reinitialize old_table to be empty
+     * 3 refill old table in corrent order (supplied by keylist) using

the old content
+     */
+
+    buf_table = *table;
+    org_table = &buf_table;
+
+    table->num_entries = 0;
+    table->bins = (st_table_entry **)Calloc(table->num_bins,
sizeof(st_table_entry*));
+    table->head = table->tail = NULL;
+
+    for (i = 0; i < org_table->num_entries; i++) {
+	key = keylist[i];
+	hash_val = do_hash(key, org_table);
+	FIND_ENTRY(org_table, entry, hash_val, bin_pos);
+	if (! entry) {
+	    /* should not happen */
+	    printf("uoooo...\n");
 	}
+
+	entry->next = table->bins[bin_pos];
+	table->bins[bin_pos] = entry;
+	ST_APPEND_TO_GLOBAL_ORDER(table, entry);
+	table->num_entries++;
     }
-    return new_table;
+
+    free(org_table->bins);
 }

 int
@@ -381,39 +479,26 @@
     st_data_t *value;
 {
     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];

-    if (ptr == 0) {
-	if (value != 0) *value = 0;
-	return 0;
+    while (ptr) {
+	if (EQUAL(table, ptr->key, *key)) break;
+	ptr = ptr->next;
     }

-    if (EQUAL(table, *key, ptr->key)) {
-	table->bins[hash_val] = ptr->next;
-	table->num_entries--;
+    if (ptr) {
+	st_unlink_entry(table, ptr);
 	if (value != 0) *value = ptr->record;
 	*key = ptr->key;
 	free(ptr);
 	return 1;
+    } else {
+	if (value != 0) *value = 0;
+	return 0;
     }
-
-    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);
-	    return 1;
-	}
-    }
-
-    return 0;
 }

 int
@@ -429,22 +514,21 @@
     hash_val = do_hash_bin(*key, table);
     ptr = table->bins[hash_val];

-    if (ptr == 0) {
-	if (value != 0) *value = 0;
-	return 0;
+    while (ptr) {
+	if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) break;
+	ptr = ptr->next;
     }

-    for(; ptr != 0; ptr = ptr->next) {
-	if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
-	    table->num_entries--;
-	    *key = ptr->key;
-	    if (value != 0) *value = ptr->record;
-	    ptr->key = ptr->record = never;
-	    return 1;
-	}
+    if (ptr) {
+	table->num_entries--;
+	if (value != 0) *value = ptr->record;
+	*key = ptr->key;
+	free(ptr);
+	return 1;
+    } else {
+	if (value != 0) *value = 0;
+	return 0;
     }
-
-    return 0;
 }

 static int
@@ -472,46 +556,40 @@
     int (*func)();
     st_data_t arg;
 {
-    st_table_entry *ptr, *last, *tmp;
+    st_table_entry *ptr, *tmp;
     enum st_retval retval;
-    int i;
-
-    for(i = 0; i < table->num_bins; i++) {
-	last = 0;
-	for(ptr = table->bins[i]; ptr != 0;) {
-	    retval = (*func)(ptr->key, ptr->record, arg);
-	    switch (retval) {
-	    case ST_CHECK:	/* check if hash is modified during iteration */
-	        tmp = 0;
-		if (i < table->num_bins) {
-		    for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
-			if (tmp == ptr) break;
-		    }
-		}
-		if (!tmp) {
-		    /* call func with error notice */
-		    return 1;
-		}
-		/* fall through */
-	    case ST_CONTINUE:
-		last = ptr;
-		ptr = ptr->next;
-		break;
-	    case ST_STOP:
-	        return 0;
-	    case ST_DELETE:
-		tmp = ptr;
-		if (last == 0) {
-		    table->bins[i] = ptr->next;
-		}
-		else {
-		    last->next = ptr->next;
-		}
-		ptr = ptr->next;
-		free(tmp);
-		table->num_entries--;
-	    }
-	}
+
+    ptr = table->head;
+    while (ptr) {
+        retval = (*func)(ptr->key, ptr->record, arg);
+        switch (retval) {
+        case ST_CHECK: /* check if hash is modified during iteration
*/
+            tmp = table->head;
+            while (tmp) {
+                if (tmp == ptr) break; /* current element is still
there - good */
+                tmp = tmp->gnext;
+            }
+            if (! tmp) {
+	        /* call func with error notice */
+                return 1;
+            }
+            /* fall through */
+        case ST_CONTINUE:
+            ptr = ptr->gnext;
+            break;
+        case ST_STOP:
+            return 0;
+        case ST_DELETE:
+	    tmp = ptr;
+	    ptr = ptr->gnext;
+	    st_unlink_entry(table, tmp);
+            free(tmp);
+            break;
+        default:
+ 	    /* should never happen! */
+            printf("uhh? retval=%d\n", retval);
+            exit(-10);
+        }
     }
     return 0;
 }
diff -ru ruby-1.8.4/st.h ruby-thies/st.h
--- ruby-1.8.4/st.h	2005-02-08 01:50:33.000000000 +0100
+++ ruby-thies/st.h	2006-08-12 17:51:50.000000000 +0200
@@ -21,6 +21,8 @@
     int num_bins;
     int num_entries;
     struct st_table_entry **bins;
+    struct st_table_entry *head;
+    struct st_table_entry *tail;
 };

 #define st_is_member(table,key) st_lookup(table,key,(st_data_t *)0)
@@ -53,6 +55,7 @@
 void st_free_table _((st_table *));
 void st_cleanup_safe _((st_table *, st_data_t));
 st_table *st_copy _((st_table *));
+void st_reorder _((st_table *, st_data_t *));

 #define ST_NUMCMP	((int (*)()) 0)
 #define ST_NUMHASH	((int (*)()) -2)