commit: Have list hashes depend on the order of the contents, as is the case for vectors.
changeset: 4398:479443c0f95a6291466173eb0254f61681654c9c
tag: tip
user: Aidan Kehoe <kehoea(a)parhasard.net>
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>
* 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>
* 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>
+
+ * 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>
* 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>
+
+ * 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>
* 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