diff options
| -rw-r--r-- | ChangeLog | 9 | ||||
| -rw-r--r-- | hash.c | 13 |
2 files changed, 18 insertions, 4 deletions
@@ -1,5 +1,14 @@ 2015-06-18 Kaz Kylheku <kaz@kylheku.com> + Improvements in equal hashing function. + + * hash.c (equal_hash): For conses and vectors, ensure that + distinct permutations lead to different hash codes. This is done by + accumulating the partial hash with a multiplier, rather than just + adding subhashes. + +2015-06-18 Kaz Kylheku <kaz@kylheku.com> + Library .txr files become .tl and are autoloaded. * lisplib.c (ver_set_entries, ver_instantiate, @@ -126,7 +126,8 @@ static cnum equal_hash(val obj) case LIT: return hash_c_str(litptr(obj)) & NUM_MAX; case CONS: - return (equal_hash(obj->c.car) + equal_hash(obj->c.cdr)) & NUM_MAX; + return (equal_hash(obj->c.car) + + 32 * (equal_hash(obj->c.cdr) & (NUM_MAX / 16))) & NUM_MAX; case STR: return hash_c_str(obj->st.str) & NUM_MAX; case CHR: @@ -151,13 +152,17 @@ static cnum equal_hash(val obj) cnum i, h = equal_hash(obj->v.vec[vec_length]); cnum len = c_num(length); - for (i = 0; i < len; i++) - h = (h + equal_hash(obj->v.vec[i])) & NUM_MAX; + for (i = 0; i < len; i++) { + h = 32 * (h & (NUM_MAX / 16)); + h += equal_hash(obj->v.vec[i]); + h &= NUM_MAX; + } return h; } case LCONS: - return (equal_hash(car(obj)) + equal_hash(cdr(obj))) & NUM_MAX; + return (equal_hash(car(obj)) + + 32 * (equal_hash(cdr(obj)) & (NUM_MAX / 16))) & NUM_MAX; case LSTR: lazy_str_force(obj); return equal_hash(obj->ls.prefix); |