;;; desiderata:
;;; * Non-commutativity keeps us from hashing e.g. #(1 5) to the
;;; same value as #(5 1), and ending up in real trouble in some
-;;; special cases like bit vectors the way that CMUCL SXHASH 18b
+;;; special cases like bit vectors the way that CMUCL 18b SXHASH
;;; does. (Under CMUCL 18b, SXHASH of any bit vector is 1..)
-;;; * We'd like to scatter our hash values the entire possible range
+;;; * We'd like to scatter our hash values over the entire possible range
;;; of values instead of hashing small or common key values (like
;;; 2 and NIL and #\a) to small FIXNUMs the way that the CMUCL 18b
;;; SXHASH function does, again helping to avoid pathologies like
;; algorithms, but we're not pushing them hard enough here for them
;; to be cryptographically strong.)
(let* ((xy (+ (* x 3) y)))
- (declare (type (unsigned-byte 32) xy))
- (the (and fixnum unsigned-byte)
- (logand most-positive-fixnum
- (logxor 441516657
- xy
- (the fixnum (ash xy -5)))))))
+ (logand most-positive-fixnum
+ (logxor 441516657
+ xy
+ (ash xy -5)))))
\f
;;;; hashing strings
;;;;
(declare (type index count))
(let ((result 408967240))
(declare (type fixnum result))
- (dotimes (i count)
- (declare (type index i))
- (mixf result
- (the fixnum
- (ash (char-code (aref string i)) 5))))
+ (unless (typep string '(vector nil))
+ (dotimes (i count)
+ (declare (type index i))
+ (mixf result
+ (the fixnum
+ (ash (char-code (aref string i)) 5)))))
result))
;;; test:
;;; (let ((ht (make-hash-table :test 'equal)))
;;; (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))
;;;; the SXHASH function
(defun sxhash (x)
+ ;; profiling SXHASH is hard, but we might as well try to make it go
+ ;; fast, in case it is the bottleneck somwhere. -- CSR, 2003-03-14
+ (declare (optimize speed))
(labels ((sxhash-number (x)
(etypecase x
(fixnum (sxhash x)) ; through DEFTRANSFORM
(sxhash-recurse (x &optional (depthoid +max-hash-depthoid+))
(declare (type index depthoid))
(typecase x
- (list
+ (cons
(if (plusp depthoid)
(mix (sxhash-recurse (car x) (1- depthoid))
(sxhash-recurse (cdr x) (1- depthoid)))
261835505))
(instance
- (if (typep x 'structure-object)
+ (if (or (typep x 'structure-object) (typep x 'condition))
(logxor 422371266
(sxhash ; through DEFTRANSFORM
- (class-name (layout-class (%instance-layout x)))))
- 309518995))
+ (classoid-name
+ (layout-classoid (%instance-layout x)))))
+ (sxhash-instance x)))
(symbol (sxhash x)) ; through DEFTRANSFORM
(array
(typecase x
(simple-string (sxhash x)) ; through DEFTRANSFORM
(string (%sxhash-substring x))
- (bit-vector (let ((result 410823708))
- (declare (type fixnum result))
- (dotimes (i (min depthoid (length x)))
- (mixf result (aref x i)))
- result))
+ (simple-bit-vector (sxhash x)) ; through DEFTRANSFORM
+ (bit-vector
+ ;; FIXME: It must surely be possible to do better
+ ;; than this. The problem is that a non-SIMPLE
+ ;; BIT-VECTOR could be displaced to another, with a
+ ;; non-zero offset -- so that significantly more
+ ;; work needs to be done using the %RAW-BITS
+ ;; approach. This will probably do for now.
+ (sxhash-recurse (copy-seq x) depthoid))
(t (logxor 191020317 (sxhash (array-rank x))))))
(character
(logxor 72185131
(sxhash (char-code x)))) ; through DEFTRANSFORM
;; general, inefficient case of NUMBER
(number (sxhash-number x))
+ (generic-function (sxhash-instance x))
(t 42))))
(sxhash-recurse x)))
\f
(array (array-psxhash key depthoid))
(hash-table (hash-table-psxhash key))
(structure-object (structure-object-psxhash key depthoid))
- (list (list-psxhash key depthoid))
+ (cons (list-psxhash key depthoid))
(number (number-psxhash key))
(character (sxhash (char-upcase key)))
(t (sxhash key))))
(declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
(let* ((layout (%instance-layout key)) ; i.e. slot #0
(length (layout-length layout))
- (class (layout-class layout))
- (name (class-name class))
+ (classoid (layout-classoid layout))
+ (name (classoid-name classoid))
(result (mix (sxhash name) (the fixnum 79867))))
(declare (type fixnum result))
(dotimes (i (min depthoid (1- length)))
(etypecase key
(single-float (frob single-float))
(double-float (frob double-float))
- (short-float (frob short-float))
+ #!+long-float
(long-float (error "LONG-FLOAT not currently supported")))))
(rational (if (and (<= most-negative-double-float
key