;;; (unless (string= (gethash hash ht) string)
;;; (format t "collision: ~S ~S~%" string (gethash hash ht)))
;;; (setf (gethash hash ht) string))))
-;;; (format t "final count=~D~%" (hash-table-count ht)))
+;;; (format t "final count=~W~%" (hash-table-count ht)))
(defun %sxhash-simple-string (x)
(declare (optimize speed))
(defun sxhash (x)
(labels ((sxhash-number (x)
(etypecase x
- (fixnum (sxhash x)) ; through DEFTRANSFORM
+ (fixnum (sxhash x)) ; through DEFTRANSFORM
(integer (sb!bignum:sxhash-bignum x))
(single-float (sxhash x)) ; through DEFTRANSFORM
(double-float (sxhash x)) ; through DEFTRANSFORM
(class-name (layout-class (%instance-layout x)))))
309518995))
(symbol (sxhash x)) ; through DEFTRANSFORM
- (number (sxhash-number x))
(array
(typecase x
(simple-string (sxhash x)) ; through DEFTRANSFORM
(character
(logxor 72185131
(sxhash (char-code x)))) ; through DEFTRANSFORM
+ ;; general, inefficient case of NUMBER
+ (number (sxhash-number x))
(t 42))))
(sxhash-recurse x)))
\f
(mixf result (number-psxhash (realpart key)))
(mixf result (number-psxhash (imagpart key)))
result))))))
-
-;;; SXHASH and PSXHASH should distribute hash values well over the
-;;; space of possible values, so that collisions between the hash values
-;;; of unequal objects should be very uncommon.
-;;;
-;;; FIXME: These tests should be enabled once the rest of the system is
-;;; stable. (For now, I don't want to mess with things like making sure
-;;; that bignums are hashed uniquely.)
-;;;#!+sb-test
-#+nil
-(let* ((test-cases `((0 . 1)
- (0 . 1)
- (1 . 0)
- ((1 . 0) (0 . 0))
- ((0 . 1) (0 . 0))
- ((0 . 0) (1 . 0))
- ((0 . 0) (0 . 1))
- #((1 . 0) (0 . 0))
- #((0 . 1) (0 . 0))
- #((0 . 0) (1 . 0))
- #((0 . 0) (0 . 1))
- #((1 . 0) (0 . 0))
- #((0 1) (0 0))
- #((0 0) (1 0))
- #((0 0) (0 1))
- #(#(1 0) (0 0))
- #(#(0 1) (0 0))
- #(#(0 0) (1 0))
- #(#(0 0) (0 1))
- #(#*00 #*10)
- #(#(0 0) (0 1.0d0))
- #(#(-0.0d0 0) (1.0 0))
- ;; KLUDGE: Some multi-dimensional array test cases would
- ;; be good here too, but currently SBCL isn't smart enough
- ;; to dump them as literals, and I'm too lazy to make
- ;; code to create them at run time. -- WHN 20000111
- 44 44.0 44.0d0
- 44 44.0 44.0d0
- -44 -44.0 -44.0d0
- 0 0.0 0.0d0
- -0 -0.0 -0.0d0
- -121 -121.0 -121.0d0
- 3/4 0.75 0.75d0
- -3/4 -0.75 -0.75d0
- 44.1 44.1d0
- 45 45.0 45.0d0
- ,(expt 2 33) ,(expt 2.0 33) ,(expt 2.0d0 33)
- ,(- (expt 1/2 50)) ,(- (expt 0.5 50)) ,(- (expt 0.5d0 50))
- ,(- (expt 1/2 50)) ,(- (expt 0.5 50)) ,(- (expt 0.5d0 50))
- #c(1.0 2.0) #c(1 2.0) #c(1.5 -3/2) #c(3/2 -3/2) #c(0 1)
- #c(1.0 2.0) #c(1 2.0) #c(1.5 -3/2) #c(3/2 -3/2) #c(0 1)
- ,(make-hash-table)
- ,(make-hash-table :test 'equal)
- "abc" "ABC" "aBc" 'abc #(#\a #\b #\c) #(a b c) #("A" b c)
- "abcc"
- "" #* #() () (()) #(()) (#())
- "" #* #() () (()) #(()) (#())
- #\x #\X #\*
- #\x #\X #\*)))
- (dolist (i test-cases)
- (unless (typep (sxhash i) '(and fixnum unsigned-byte))
- (error "bad SXHASH behavior for ~S" i))
- (unless (typep (psxhash i) '(and fixnum unsigned-byte))
- (error "bad PSXHASH behavior for ~S" i))
- (dolist (j test-cases)
- (flet ((t->boolean (x) (if x t nil)))
- ;; Note: It's possible that a change to the hashing algorithm could
- ;; leave it correct but still cause this test to bomb by causing an
- ;; unlucky random collision. That's not very likely (since there are
- ;; (EXPT 2 29) possible hash values and only on the order of 100 test
- ;; cases, but it's probably worth checking if you are getting a
- ;; mystifying error from this test.
- (unless (eq (t->boolean (equal i j))
- (t->boolean (= (sxhash i) (sxhash j))))
- (error "bad SXHASH behavior for ~S ~S" i j))
- (unless (eq (t->boolean (equalp i j))
- (t->boolean (= (psxhash i) (psxhash j))))
- (error "bad PSXHASH behavior for ~S ~S" i j))))))
-
-;;; FIXME: Test that the the hash functions can deal with common cases without
-;;; consing.
-;(defun consless-test ()
-; (dotimes (j 100000)
-; (dolist (i '("yo" #(1 2 3) #2A((1 2) (1 2)) (1 2 (3)) 1 1.0 1.0d0))
-; (psxhash i))))