[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 <crt_externs.h>
@@ -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 <[e-mail]> writes:
>
> |How about Hash::Type class as an API for rb_hash_type?
>
> Depends on API, and performance.
>
> 							matz.
>