ruby-changes:10753
From: mame <ko1@a...>
Date: Sun, 15 Feb 2009 04:55:50 +0900 (JST)
Subject: [ruby-changes:10753] Ruby:r22317 (trunk): * string.c (rb_hash_uint32, rb_hash_uint, rb_hash_start, rb_hash_end),
mame 2009-02-15 04:55:34 +0900 (Sun, 15 Feb 2009) New Revision: 22317 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=22317 Log: * string.c (rb_hash_uint32, rb_hash_uint, rb_hash_start, rb_hash_end), include/ruby/intern.h: add Murmurhash API. [ruby-dev:37784] * complex.c (nucomp_hash), array.c (rb_ary_hash), time.c (time_hash), string.c (rb_str_hsah), object.c (rb_obj_hash), range.c (range_hash), struct.c (rb_struct_hash), hash.c (rb_any_hash), rational.c (nurat_hash): use Murmurhash. [ruby-dev:37784] Modified files: trunk/ChangeLog trunk/array.c trunk/complex.c trunk/gc.c trunk/hash.c trunk/include/ruby/intern.h trunk/object.c trunk/range.c trunk/rational.c trunk/string.c trunk/struct.c trunk/time.c Index: complex.c =================================================================== --- complex.c (revision 22316) +++ complex.c (revision 22317) @@ -22,7 +22,7 @@ VALUE rb_cComplex; static ID id_abs, id_abs2, id_arg, id_cmp, id_conj, id_convert, - id_denominator, id_divmod, id_equal_p, id_expt, id_floor, id_hash, + id_denominator, id_divmod, id_equal_p, id_expt, id_floor, id_idiv, id_inspect, id_negate, id_numerator, id_polar, id_quo, id_real_p, id_to_f, id_to_i, id_to_r, id_to_s; @@ -153,15 +153,12 @@ return rb_funcall(x, '-', 1, y); } -binop(xor, '^') - fun1(abs) fun1(abs2) fun1(arg) fun1(conj) fun1(denominator) fun1(floor) -fun1(hash) fun1(inspect) fun1(negate) fun1(numerator) @@ -857,8 +854,17 @@ static VALUE nucomp_hash(VALUE self) { + long v, h[3]; + VALUE n; + get_dat1(self); - return f_xor(f_hash(dat->real), f_hash(dat->imag)); + h[0] = rb_hash(rb_obj_class(self)); + n = rb_hash(dat->real); + h[1] = NUM2LONG(n); + n = rb_hash(dat->imag); + h[2] = NUM2LONG(n); + v = rb_memhash(h, sizeof(h)); + return LONG2FIX(v); } static VALUE @@ -1384,7 +1390,6 @@ id_equal_p = rb_intern("=="); id_expt = rb_intern("**"); id_floor = rb_intern("floor"); - id_hash = rb_intern("hash"); id_idiv = rb_intern("div"); id_inspect = rb_intern("inspect"); id_negate = rb_intern("-@"); Index: array.c =================================================================== --- array.c (revision 22316) +++ array.c (revision 22317) @@ -2771,12 +2771,12 @@ if (recur) { return LONG2FIX(0); } - h = RARRAY_LEN(ary); + h = rb_hash_start(RARRAY_LEN(ary)); for (i=0; i<RARRAY_LEN(ary); i++) { - h = (h << 1) | (h<0 ? 1 : 0); n = rb_hash(RARRAY_PTR(ary)[i]); - h ^= NUM2LONG(n); + h = rb_hash_uint(h, NUM2LONG(n)); } + h = rb_hash_end(h); return LONG2FIX(h); } Index: time.c =================================================================== --- time.c (revision 22316) +++ time.c (revision 22317) @@ -1183,7 +1183,7 @@ long hash; GetTimeval(time, tobj); - hash = tobj->ts.tv_sec ^ tobj->ts.tv_nsec; + hash = rb_hash_end(rb_hash_uint(rb_hash_start(tobj->ts.tv_sec), tobj->ts.tv_nsec)); return LONG2FIX(hash); } Index: include/ruby/intern.h =================================================================== --- include/ruby/intern.h (revision 22316) +++ include/ruby/intern.h (revision 22317) @@ -610,6 +610,10 @@ VALUE rb_str_append(VALUE, VALUE); VALUE rb_str_concat(VALUE, VALUE); int rb_memhash(const void *ptr, long len); +unsigned int rb_hash_start(unsigned int); +unsigned int rb_hash_uint32(unsigned int, unsigned int); +unsigned int rb_hash_uint(unsigned int, unsigned int); +unsigned int rb_hash_end(unsigned int); int rb_str_hash(VALUE); int rb_str_hash_cmp(VALUE,VALUE); int rb_str_comparable(VALUE, VALUE); Index: ChangeLog =================================================================== --- ChangeLog (revision 22316) +++ ChangeLog (revision 22317) @@ -1,3 +1,13 @@ +Sun Feb 15 04:48:08 2009 Yusuke Endoh <mame@t...> + + * string.c (rb_hash_uint32, rb_hash_uint, rb_hash_start, rb_hash_end), + include/ruby/intern.h: add Murmurhash API. [ruby-dev:37784] + + * complex.c (nucomp_hash), array.c (rb_ary_hash), time.c (time_hash), + string.c (rb_str_hsah), object.c (rb_obj_hash), range.c + (range_hash), struct.c (rb_struct_hash), hash.c (rb_any_hash), + rational.c (nurat_hash): use Murmurhash. [ruby-dev:37784] + Sun Feb 15 03:50:21 2009 Yusuke Endoh <mame@t...> * hash.c (rb_hash): always return a fixnum value because a return Index: string.c =================================================================== --- string.c (revision 22316) +++ string.c (revision 22317) @@ -1912,6 +1912,7 @@ #endif return h; } +#define murmur16(h) murmur_step(h, 16) static inline unsigned int murmur_finish(unsigned int h) @@ -2053,9 +2054,54 @@ return murmur_finish(h); } -int -rb_memhash(const void *ptr, long len) +unsigned int +rb_hash_uint32(unsigned int h, unsigned int i) { + return murmur_step(h + i, 16); +} + +unsigned int +rb_hash_uint(unsigned int h, unsigned int i) +{ + unsigned int v = 0; + h += i; +#ifdef WORDS_BIGENDIAN +#if SIZEOF_INT*CHAR_BIT > 12*8 + v = murmur16(v + (h >> 12*8)); +#endif +#if SIZEOF_INT*CHAR_BIT > 8*8 + v = murmur16(v + (h >> 8*8)); +#endif +#if SIZEOF_INT*CHAR_BIT > 4*8 + v = murmur16(v + (h >> 4*8)); +#endif +#endif + v = murmur16(v + h); +#ifndef WORDS_BIGENDIAN +#if SIZEOF_INT*CHAR_BIT > 4*8 + v = murmur16(v + (h >> 4*8)); +#endif +#if SIZEOF_INT*CHAR_BIT > 8*8 + v = murmur16(v + (h >> 8*8)); +#endif +#if SIZEOF_INT*CHAR_BIT > 12*8 + v = murmur16(v + (h >> 12*8)); +#endif +#endif + return v; +} + +unsigned int +rb_hash_end(unsigned int h) +{ + h = murmur_step(h, 10); + h = murmur_step(h, 17); + return h; +} + +unsigned int +rb_hash_start(unsigned int h) +{ static int hashseed_init = 0; static unsigned int hashseed; @@ -2064,10 +2110,16 @@ hashseed_init = 1; } - return hash(ptr, len, hashseed); + return hashseed + h; } int +rb_memhash(const void *ptr, long len) +{ + return hash(ptr, len, rb_hash_start(0)); +} + +int rb_str_hash(VALUE str) { int e = ENCODING_GET(str); Index: object.c =================================================================== --- object.c (revision 22316) +++ object.c (revision 22317) @@ -95,6 +95,14 @@ return Qfalse; } +VALUE +rb_obj_hash(VALUE obj) +{ + VALUE oid = rb_obj_id(obj); + unsigned h = rb_hash_end(rb_hash_start(NUM2LONG(oid))); + return LONG2NUM(h); +} + /* * call-seq: * !obj => true or false @@ -2505,6 +2513,7 @@ rb_define_method(rb_mKernel, "=~", rb_obj_match, 1); rb_define_method(rb_mKernel, "!~", rb_obj_not_match, 1); rb_define_method(rb_mKernel, "eql?", rb_obj_equal, 1); + rb_define_method(rb_mKernel, "hash", rb_obj_hash, 0); rb_define_method(rb_mKernel, "class", rb_obj_class, 0); rb_define_method(rb_mKernel, "clone", rb_obj_clone, 0); Index: range.c =================================================================== --- range.c (revision 22316) +++ range.c (revision 22317) @@ -213,14 +213,16 @@ static VALUE range_hash(VALUE range) { - long hash = EXCL(range); + unsigned hash = EXCL(range); VALUE v; + hash = rb_hash_start(hash); v = rb_hash(RANGE_BEG(range)); - hash ^= v << 1; + hash = rb_hash_uint(hash, NUM2LONG(v)); v = rb_hash(RANGE_END(range)); - hash ^= v << 9; - hash ^= EXCL(range) << 24; + hash = rb_hash_uint(hash, NUM2LONG(v)); + hash = rb_hash_uint(hash, EXCL(range) << 24); + hash = rb_hash_end(hash); return LONG2FIX(hash); } Index: struct.c =================================================================== --- struct.c (revision 22316) +++ struct.c (revision 22317) @@ -804,16 +804,17 @@ static VALUE rb_struct_hash(VALUE s) { - long i, h; + long i; + unsigned h; VALUE n; - h = rb_hash(rb_obj_class(s)); + h = rb_hash_start(rb_hash(rb_obj_class(s))); for (i = 0; i < RSTRUCT_LEN(s); i++) { - h = (h << 1) | (h<0 ? 1 : 0); n = rb_hash(RSTRUCT_PTR(s)[i]); - h ^= NUM2LONG(n); + h = rb_hash_uint(h, NUM2LONG(n)); } - return LONG2FIX(h); + h = rb_hash_end(h); + return INT2FIX(h); } /* Index: gc.c =================================================================== --- gc.c (revision 22316) +++ gc.c (revision 22317) @@ -2913,7 +2913,6 @@ OBJ_TAINT(nomem_error); OBJ_FREEZE(nomem_error); - rb_define_method(rb_mKernel, "hash", rb_obj_id, 0); rb_define_method(rb_mKernel, "__id__", rb_obj_id, 0); rb_define_method(rb_mKernel, "object_id", rb_obj_id, 0); Index: hash.c =================================================================== --- hash.c (revision 22316) +++ hash.c (revision 22317) @@ -84,7 +84,7 @@ case T_NIL: case T_FALSE: case T_TRUE: - hnum = (int)a; + hnum = rb_hash_end(rb_hash_start((unsigned int)a)); break; case T_STRING: Index: rational.c =================================================================== --- rational.c (revision 22316) +++ rational.c (revision 22317) @@ -27,7 +27,7 @@ VALUE rb_cRational; static ID id_abs, id_cmp, id_convert, id_equal_p, id_expt, id_floor, - id_hash, id_idiv, id_inspect, id_integer_p, id_negate, id_to_f, + id_idiv, id_inspect, id_integer_p, id_negate, id_to_f, id_to_i, id_to_s, id_truncate; #define f_boolcast(x) ((x) ? Qtrue : Qfalse) @@ -135,11 +135,8 @@ return rb_funcall(x, '-', 1, y); } -binop(xor, '^') - fun1(abs) fun1(floor) -fun1(hash) fun1(inspect) fun1(integer_p) fun1(negate) @@ -1161,8 +1158,17 @@ static VALUE nurat_hash(VALUE self) { + long v, h[3]; + VALUE n; + get_dat1(self); - return f_xor(f_hash(dat->num), f_hash(dat->den)); + h[0] = rb_hash(rb_obj_class(self)); + n = rb_hash(dat->num); + h[1] = NUM2LONG(n); + n = rb_hash(dat->den); + h[2] = NUM2LONG(n); + v = rb_memhash(h, sizeof(h)); + return LONG2FIX(v); } static VALUE @@ -1554,7 +1560,6 @@ id_equal_p = rb_intern("=="); id_expt = rb_intern("**"); id_floor = rb_intern("floor"); - id_hash = rb_intern("hash"); id_idiv = rb_intern("div"); id_inspect = rb_intern("inspect"); id_integer_p = rb_intern("integer?"); -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/