[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