Mercurial > hg > xemacs-beta
changeset 4398:479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
src/ChangeLog addition:
2008-01-16 Aidan Kehoe <kehoea@parhasard.net>
* elhash.c (internal_hash):
Make short lists with the same contents in a different order hash
distinctly. Gives better performance for things like three-element
lists describing colours. Thank you Sebastian Freundt!
tests/ChangeLog addition:
2008-01-16 Aidan Kehoe <kehoea@parhasard.net>
* automated/hash-table-tests.el:
Assert that two short lists with the same contents in distinct
orders hash differently.
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Wed, 16 Jan 2008 15:20:51 +0100 |
| parents | 9e28067e3083 |
| children | e5b3c4dbc8a2 |
| files | src/ChangeLog src/elhash.c tests/ChangeLog tests/automated/hash-table-tests.el |
| diffstat | 4 files changed, 40 insertions(+), 5 deletions(-) [+] |
line wrap: on
line diff
--- a/src/ChangeLog Wed Jan 16 00:19:59 2008 +0100 +++ b/src/ChangeLog Wed Jan 16 15:20:51 2008 +0100 @@ -1,3 +1,10 @@ +2008-01-16 Aidan Kehoe <kehoea@parhasard.net> + + * elhash.c (internal_hash): + Make short lists with the same contents in a different order hash + distinctly. Gives better performance for things like three-element + lists describing colours. Thank you Sebastian Freundt! + 2008-01-15 Aidan Kehoe <kehoea@parhasard.net> * print.c (prin1_to_string): New.
--- a/src/elhash.c Wed Jan 16 00:19:59 2008 +0100 +++ b/src/elhash.c Wed Jan 16 15:20:51 2008 +0100 @@ -1719,12 +1719,33 @@ { if (depth > 5) return 0; - if (CONSP (obj)) + + if (CONSP(obj)) { - /* no point in worrying about tail recursion, since we're not - going very deep */ - return HASH2 (internal_hash (XCAR (obj), depth + 1), - internal_hash (XCDR (obj), depth + 1)); + Hashcode hash, h; + int s; + + depth += 1; + + if (!CONSP(XCDR(obj))) + { + /* special case for '(a . b) conses */ + return HASH2(internal_hash(XCAR(obj), depth), + internal_hash(XCDR(obj), depth)); + } + + /* Don't simply tail recurse; we want to hash lists with the + same contents in distinct orders differently. */ + hash = internal_hash(XCAR(obj), depth); + + obj = XCDR(obj); + for (s = 1; s < 6 && CONSP(obj); obj = XCDR(obj), s++) + { + h = internal_hash(XCAR(obj), depth); + hash = HASH3(hash, h, s); + } + + return hash; } if (STRINGP (obj)) {
--- a/tests/ChangeLog Wed Jan 16 00:19:59 2008 +0100 +++ b/tests/ChangeLog Wed Jan 16 15:20:51 2008 +0100 @@ -1,3 +1,9 @@ +2008-01-16 Aidan Kehoe <kehoea@parhasard.net> + + * automated/hash-table-tests.el: + Assert that two short lists with the same contents in distinct + orders hash differently. + 2008-01-15 Aidan Kehoe <kehoea@parhasard.net> * automated/lisp-tests.el (literal-with-uninterned):
--- a/tests/automated/hash-table-tests.el Wed Jan 16 00:19:59 2008 +0100 +++ b/tests/automated/hash-table-tests.el Wed Jan 16 15:20:51 2008 +0100 @@ -281,3 +281,4 @@ ;;; Test sxhash (Assert (= (sxhash "foo") (sxhash "foo"))) (Assert (= (sxhash '(1 2 3)) (sxhash '(1 2 3)))) +(Assert (/= (sxhash '(1 2 3)) (sxhash '(3 2 1))))