changeset: 4398:479443c0f95a6291466173eb0254f61681654c9c tag: tip user: Aidan Kehoe <kehoea(a)parhasard.net&gt; date: Wed Jan 16 15:20:51 2008 +0100 files: src/ChangeLog src/elhash.c tests/ChangeLog tests/automated/hash-table-tests.el description: 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(a)parhasard.net&gt; * 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(a)parhasard.net&gt; * automated/hash-table-tests.el: Assert that two short lists with the same contents in distinct orders hash differently. diff -r 9e28067e3083ce90cdd48370cd9f7947862681f9 -r 479443c0f95a6291466173eb0254f61681654c9c src/ChangeLog --- 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-15 Aidan Kehoe <kehoea＠parhasa +2008-01-16 Aidan Kehoe <kehoea(a)parhasard.net&gt; + + * 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(a)parhasard.net&gt; * print.c (prin1_to_string): New. diff -r 9e28067e3083ce90cdd48370cd9f7947862681f9 -r 479443c0f95a6291466173eb0254f61681654c9c src/elhash.c --- 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 ＠＠ internal_hash (Lisp_Object obj, int dept { if (depth > 5) return 0; - 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)); + + if (CONSP(obj)) + { + 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)) { diff -r 9e28067e3083ce90cdd48370cd9f7947862681f9 -r 479443c0f95a6291466173eb0254f61681654c9c tests/ChangeLog --- 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-15 Aidan Kehoe <kehoea＠parhasa +2008-01-16 Aidan Kehoe <kehoea(a)parhasard.net&gt; + + * 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(a)parhasard.net&gt; * automated/lisp-tests.el (literal-with-uninterned): diff -r 9e28067e3083ce90cdd48370cd9f7947862681f9 -r 479443c0f95a6291466173eb0254f61681654c9c tests/automated/hash-table-tests.el --- 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)))) _______________________________________________ XEmacs-Patches mailing list XEmacs-Patches(a)xemacs.org http://calypso.tux.org/cgi-bin/mailman/listinfo/xemacs-patches