From: "Lourens Naudé" Date: 2009-11-08T01:40:52+09:00 Subject: [ruby-core:26593] Re: HashWithIndifferentAccess to core Hi, I've been toying with allowing custom hashing from the Ruby side for the past 2 days and have a semi-functional version (patch attached against subversion trunk 25671 - http://gist.github.com/228773), however my lack of VM control frame knowledge pretty much blocks progress atm. Experimental API : Hash#index_with(Object) The general expected contract being the object implements 2 methods, hash(a) and compare(a,b) Here's a rough HashWithIndifferentAccess ( referenced as "hwia" moving forward) implementation : module Hwia def hash(obj) case obj when Symbol, String obj.to_s.hash else obj.hash end end def compare(a,b) if String === a && Symbol === b || String === b && Symbol === a a.to_s <=> b.to_s else a <=> b end end extend self end h = { "foo" => "bar" } h.index_with(Hwia) h[:foo] # "bar" Hash#custom_index? #=> true | false Hash#indexed_with #=> Object Given the arguments accepted by st_hash_type members being restricted to 1 and 2 arguments respectively, I opted for falling back to the current ruby control frame after consulting with Aman Gupta, who also uses this in perftools.rb to get to self : rb_thread_t *th = GET_THREAD(); VALUE hash = th->cfp->self; Which works OK initially, but results in 2) Error: test_index_with(TestHash): TypeError: wrong argument type TestHash (expected Hash) test/ruby/test_hash.rb:906:in `test_index_with' after passing through rb_hash_aref in : h.index_with(Hwia) assert_equal Hwia, h.indexed_with assert h.custom_index? h["foo"] # fails as th->cfp->self becomes TestHash in that scope. Any thoughts / feedback much appreciated.Apologies for the naming confusion in the original mailing list post as well. The current source tree is available at : http://github.com/methodmissing/ruby/tree/custom_hashing - Lourens methodmissing:ruby lourens$ git diff --patch-with-stat github/ trunk..HEAD gc.c | 1 + hash.c | 70 +++++++++++++++++++++++++++++++++++++++ +++++++- include/ruby/ruby.h | 2 + test/ruby/test_hash.rb | 36 ++++++++++++++++++++++++ 4 files changed, 107 insertions(+), 2 deletions(-) diff --git a/gc.c b/gc.c index 7711101..55cdb85 100644 --- a/gc.c +++ b/gc.c @@ -1697,6 +1697,7 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev) case T_HASH: mark_hash(objspace, obj->as.hash.ntbl, lev); + gc_mark(objspace, obj->as.hash.index_with, lev); ptr = obj->as.hash.ifnone; goto again; diff --git a/hash.c b/hash.c index ef8b9a8..66280b6 100644 --- a/hash.c +++ b/hash.c @@ -14,6 +14,7 @@ #include "ruby/ruby.h" #include "ruby/st.h" #include "ruby/util.h" +#include "vm_core.h" #ifdef __APPLE__ #include @@ -33,7 +34,7 @@ rb_hash_freeze(VALUE hash) VALUE rb_cHash; static VALUE envtbl; -static ID id_hash, id_yield, id_default; +static ID id_hash, id_yield, id_default, id_compare; static int rb_any_cmp(VALUE a, VALUE b) @@ -99,11 +100,37 @@ rb_any_hash(VALUE a) return (st_index_t)RSHIFT(hnum, 1); } +static int +rb_custom_cmp(VALUE a, VALUE b) +{ + rb_thread_t *th = GET_THREAD(); + VALUE hash = th->cfp->self; + Check_Type(hash, T_HASH); + return FIX2INT(rb_funcall(RHASH(hash)->index_with, id_compare, 2, a, b)); +} + +static st_index_t +rb_custom_hash(VALUE a) +{ + st_index_t hnum; + rb_thread_t *th = GET_THREAD(); + VALUE hash = th->cfp->self; + Check_Type(hash, T_HASH); + hnum = FIX2LONG(rb_funcall(RHASH(hash)->index_with, id_hash, 1, a)); + hnum <<= 1; + return (st_index_t)RSHIFT(hnum, 1); +} + static const struct st_hash_type objhash = { rb_any_cmp, rb_any_hash, }; +static const struct st_hash_type customhash = { + rb_custom_cmp, + rb_custom_hash, +}; + static const struct st_hash_type identhash = { st_numcmp, st_numhash, @@ -219,6 +246,7 @@ hash_alloc(VALUE klass) OBJSETUP(hash, klass, T_HASH); hash->ifnone = Qnil; + hash->index_with = Qnil; return (VALUE)hash; } @@ -241,6 +269,7 @@ rb_hash_dup(VALUE hash) FL_SET(ret, HASH_PROC_DEFAULT); } ret->ifnone = RHASH(hash)->ifnone; + ret->index_with = RHASH(hash)->index_with; return (VALUE)ret; } @@ -492,7 +521,6 @@ VALUE rb_hash_aref(VALUE hash, VALUE key) { VALUE val; - if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) { return rb_funcall(hash, id_default, 1, key); } @@ -1080,6 +1108,7 @@ rb_hash_replace(VALUE hash, VALUE hash2) } rb_hash_foreach(hash2, replace_i, hash); RHASH(hash)->ifnone = RHASH(hash2)->ifnone; + RHASH(hash)->index_with = RHASH(hash2)->index_with; if (FL_TEST(hash2, HASH_PROC_DEFAULT)) { FL_SET(hash, HASH_PROC_DEFAULT); } @@ -1852,6 +1881,37 @@ rb_hash_compare_by_id_p(VALUE hash) return Qfalse; } +static VALUE +rb_hash_index_with(VALUE hash, VALUE idx) +{ + if (rb_respond_to(idx, id_hash) && rb_respond_to(idx, id_compare)){ + rb_hash_modify(hash); + RHASH(hash)->index_with = idx; + RHASH(hash)->ntbl->type = &customhash; + rb_hash_rehash(hash); + return hash; + }else{ + rb_raise(rb_eRuntimeError, "a custom hashing scheme should implement #hash(a) and #compare(a,b)"); + } +} + +static VALUE +rb_hash_custom_index_p(VALUE hash) +{ + if (!RHASH(hash)->ntbl) + return Qfalse; + if (RHASH(hash)->ntbl->type == &customhash) { + return Qtrue; + } + return Qfalse; +} + +static VALUE +rb_hash_indexed_with(VALUE hash) +{ + return RHASH(hash)->index_with; +} + static int path_tainted = -1; static char **origenviron; @@ -2647,6 +2707,7 @@ Init_Hash(void) id_hash = rb_intern("hash"); id_yield = rb_intern("yield"); id_default = rb_intern("default"); + id_compare = rb_intern("compare"); rb_cHash = rb_define_class("Hash", rb_cObject); @@ -2716,6 +2777,11 @@ Init_Hash(void) rb_define_method(rb_cHash,"compare_by_identity", rb_hash_compare_by_id, 0); rb_define_method(rb_cHash,"compare_by_identity?", rb_hash_compare_by_id_p, 0); + rb_define_method(rb_cHash,"index_with", rb_hash_index_with, 1); + rb_define_method(rb_cHash,"indexed_with", rb_hash_indexed_with, 0); + + rb_define_method(rb_cHash,"custom_index?", rb_hash_custom_index_p, 0); +#define RHASH_IDX_WITH(h) (RHASH(h)->index_with) #define RHASH_SIZE(h) (RHASH(h)->ntbl ? RHASH(h)->ntbl- >num_entries : 0) #define RHASH_EMPTY_P(h) (RHASH_SIZE(h) == 0) diff --git a/test/ruby/test_hash.rb b/test/ruby/test_hash.rb index c860b25..4e3f7f9 100644 --- a/test/ruby/test_hash.rb +++ b/test/ruby/test_hash.rb @@ -871,4 +871,40 @@ class TestHash < Test::Unit::TestCase def o.hash; 2<<100; end assert_equal({x=>1}.hash, {x=>1}.hash) end + + module Hwia + def hash(obj) + case obj + when Symbol, String + obj.to_s.hash + else + obj.hash + end + end + + def compare(a,b) + if String === a && Symbol === b || String === b && Symbol === a + a.to_s <=> b.to_s + else + a <=> b + end + end + extend self + end + + def test_index_with + a = "foo" + assert(!{}.custom_index?) + h = { a => "bar" } + assert_equal nil, h.indexed_with + assert_raises(RuntimeError) do + h.index_with(Object.new) + end + h.index_with(Hwia) + assert_equal Hwia, h.indexed_with + assert h.custom_index? + h["foo"] + #assert_equal "bar", h["foo"] + #assert_equal "bar", h[:foo] + end end On 2009/11/07, at 13:10, Yukihiro Matsumoto wrote: > Hi, > > In message "Re: [ruby-core:26584] Re: HashWithIndifferentAccess to > core" > on Sat, 7 Nov 2009 20:06:07 +0900, Yugui writes: > > |How about Hash::Type class as an API for rb_hash_type? > > Depends on API, and performance. > > matz. >