ref: 99c17feac1cd1e5bb7d0b1d3b3793e2416f6f917
parent: ff650e3049019496422fa3a437531a43567e5307
author: JeffBezanson <jeff.bezanson@gmail.com>
date: Wed May 20 14:52:09 EDT 2009
made cons hashing tail recursive on cdrs plus one more test
--- a/femtolisp/equal.c
+++ b/femtolisp/equal.c
@@ -308,21 +308,24 @@
return h;
case TAG_CONS:
- if (bound <= 0) {
- *oob = 1;
- return 1;
- }
- h = bounded_hash(car_(a), bound/2, oob);
- // bounds balancing: try to share the bounds efficiently
- // between the car and cdr so we can hash better when a list is
- // car-shallow and cdr-deep (a common case) or vice-versa.
- if (*oob)
- bound/=2;
- else
- bound--;
- h = MIX(h, bounded_hash(cdr_(a), bound, &oob2)+2);
- // recursive OOB propagation. otherwise this case is slow:
- // (hash '#2=('#0=(#1=(#1#) . #0#) . #2#))
+ do {
+ if (bound <= 0) {
+ *oob = 1;
+ return h;
+ }
+ h = MIX(h, bounded_hash(car_(a), bound/2, &oob2));
+ // bounds balancing: try to share the bounds efficiently
+ // so we can hash better when a list is cdr-deep (a common case)
+ if (oob2)
+ bound/=2;
+ else
+ bound--;
+ // recursive OOB propagation. otherwise this case is slow:
+ // (hash '#2=((#0=(#1=(#1#) . #0#)) . #2#))
+ *oob = *oob || oob2;
+ a = cdr_(a);
+ } while (iscons(a));
+ h = MIX(h, bounded_hash(a, bound-1, &oob2)+2);
*oob = *oob || oob2;
return h;
}
--- a/femtolisp/unittest.lsp
+++ b/femtolisp/unittest.lsp
@@ -131,6 +131,14 @@
(hash '#1=((1 . #1#) (2 . #1#) . #1#)))))
(assert (equal?
+ (hash '(#0=(#0#) 0))
+ (hash '(#1=(((((#1#))))) 0))))
+
+(assert (not (equal?
+ (hash '(#0=(#0#) 0))
+ (hash '(#1=(((((#1#))))) 1)))))
+
+(assert (equal?
(hash #0=[1 [2 [#0#]] 3])
(hash #1=[1 [2 [[1 [2 [#1#]] 3]]] 3])))