From: "Thies C. Arntzen" Date: 2006-08-13T01:55:13+09:00 Subject: 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 hsh according to code [ key, + * value ]. 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)