[macruby-changes] [5042] MacRuby/trunk

source_changes at macosforge.org source_changes at macosforge.org
Thu Dec 16 21:19:22 PST 2010


Revision: 5042
          http://trac.macosforge.org/projects/ruby/changeset/5042
Author:   lsansonetti at apple.com
Date:     2010-12-16 21:19:18 -0800 (Thu, 16 Dec 2010)
Log Message:
-----------
implement a better RubyHash hashing function for arrays, as the CF one isn't good enough

Modified Paths:
--------------
    MacRuby/trunk/NSArray.m
    MacRuby/trunk/array.h
    MacRuby/trunk/hash.c
    MacRuby/trunk/hash.h

Modified: MacRuby/trunk/NSArray.m
===================================================================
--- MacRuby/trunk/NSArray.m	2010-12-17 04:18:01 UTC (rev 5041)
+++ MacRuby/trunk/NSArray.m	2010-12-17 05:19:18 UTC (rev 5042)
@@ -13,6 +13,7 @@
 #include "objc.h"
 #include "vm.h"
 #include "array.h"
+#include "hash.h"
 
 VALUE rb_cArray;
 VALUE rb_cNSArray;
@@ -1459,3 +1460,33 @@
 
     return values;
 }
+
+// A very naive hashing function for arrays, which hashes the array's length,
+// then first and last elements (in case the array has more than 4 elements).
+// We cannot rely on the CoreFoundation hashing function for arrays as it's
+// simply returning the number of elements, and can trigger huge performance
+// problems when using same-sized arrays as keys in Hash objects.
+unsigned long
+rb_ary_hash(VALUE ary)
+{
+    const long len = RARRAY_LEN(ary);
+    unsigned long hash = 0;
+    if (len > 0) {
+	VALUE elem = RARRAY_AT(ary, 0);
+	if (elem == ary) {
+	    // recursive array
+	    return (unsigned long)rb_cRubyArray;
+	}
+	hash += rb_hash_code(elem);
+	if (len > 4) {
+	    elem = RARRAY_AT(ary, len - 1);
+	    if (elem == ary) {
+		// recursive array
+		return (unsigned long)rb_cRubyArray;
+	    }
+	    hash = (hash >> 3) ^ rb_hash_code(elem);
+	}
+	hash += len;
+    }
+    return hash;
+}

Modified: MacRuby/trunk/array.h
===================================================================
--- MacRuby/trunk/array.h	2010-12-17 04:18:01 UTC (rev 5041)
+++ MacRuby/trunk/array.h	2010-12-17 05:19:18 UTC (rev 5042)
@@ -178,6 +178,8 @@
 VALUE rary_and(VALUE ary1, SEL sel, VALUE ary2);
 VALUE rary_or(VALUE ary1, SEL sel, VALUE ary2);
 
+unsigned long rb_ary_hash(VALUE ary);
+
 #if defined(__cplusplus)
 } // extern "C"
 #endif

Modified: MacRuby/trunk/hash.c
===================================================================
--- MacRuby/trunk/hash.c	2010-12-17 04:18:01 UTC (rev 5041)
+++ MacRuby/trunk/hash.c	2010-12-17 05:19:18 UTC (rev 5042)
@@ -18,6 +18,7 @@
 #include "objc.h"
 #include "vm.h"
 #include "hash.h"
+#include "array.h"
 #include "class.h"
 
 static VALUE rhash_try_convert(VALUE, SEL, VALUE);
@@ -36,22 +37,44 @@
 static SEL selDefault = 0;
 static SEL selHash = 0;
 
-VALUE
-rb_hash(VALUE obj)
+unsigned long
+rb_hash_code(VALUE obj)
 {
+    switch (TYPE(obj)) {
+	case T_FIXNUM:
+	case T_FLOAT:
+	case T_SYMBOL:
+	case T_NIL:
+	case T_FALSE:
+	case T_TRUE:
+	    return (unsigned long)obj;
+
+	case T_STRING:
+	    return rb_str_hash(obj);
+
+	case T_ARRAY:
+	    return rb_ary_hash(obj);
+    }
+
     VALUE v = rb_vm_call(obj, selHash, 0, NULL);
 retry:
     switch (TYPE(v)) {
 	case T_FIXNUM:
-	    return v;
+	    return FIX2LONG(v);
 	case T_BIGNUM:
-	    return LONG2FIX(((long *)(RBIGNUM_DIGITS(v)))[0]);
+	    return ((unsigned long *)(RBIGNUM_DIGITS(v)))[0];
 	default:
 	    v = rb_to_int(v);
 	    goto retry;
     }
 }
 
+VALUE
+rb_hash(VALUE obj)
+{
+    return LONG2NUM(rb_hash_code(obj));
+}
+
 typedef int st_foreach_func(st_data_t, st_data_t, st_data_t);
 
 struct foreach_safe_arg {
@@ -90,40 +113,13 @@
     if (a == b) {
 	return 0;
     }
-    const int type = TYPE(a);
-    switch (type) {
-	case T_FIXNUM:
-	case T_FLOAT:
-	case T_SYMBOL:
-	    if (type == TYPE(b)) {
-		return a != b;
-	    }
-	    break;
-
-	case T_STRING:
-	    return rb_str_cmp(a, b);
-    }
-
     return !rb_eql(a, b);
 }
 
 static int
 rb_any_hash(VALUE a)
 {
-    switch (TYPE(a)) {
-	case T_FIXNUM:
-	case T_FLOAT:
-	case T_SYMBOL:
-	case T_NIL:
-	case T_FALSE:
-	case T_TRUE:
-	    return (int)a;
-
-	case T_STRING:
-	    return (int)rb_str_hash(a);
-    }
-
-    return (int)FIX2LONG(rb_hash(a));
+    return (int)rb_hash_code(a);
 }
 
 static const struct st_hash_type objhash = {

Modified: MacRuby/trunk/hash.h
===================================================================
--- MacRuby/trunk/hash.h	2010-12-17 04:18:01 UTC (rev 5041)
+++ MacRuby/trunk/hash.h	2010-12-17 05:19:18 UTC (rev 5042)
@@ -103,6 +103,8 @@
 VALUE rhash_has_key(VALUE hash, SEL sel, VALUE key);
 VALUE rhash_set_default(VALUE hash, SEL sel, VALUE ifnone);
 
+unsigned long rb_hash_code(VALUE obj);
+
 #if defined(__cplusplus)
 } // extern "C"
 #endif
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.macosforge.org/pipermail/macruby-changes/attachments/20101216/fe95aafc/attachment.html>


More information about the macruby-changes mailing list