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 hsh according to code
[
key,
- Orders hsh according to code
-
- value
]
. If no block is given the sort order
- value
-
- 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)