+ `(loop for ,var across (sset-vector ,sset)
+ do (unless (member ,var '(0 +deleted+))
+ ,@body)
+ finally (return ,result)))
+
+;;; Primary hash.
+(declaim (inline sset-hash1))
+(defun sset-hash1 (element)
+ #+sb-xc-host
+ (let ((result (sset-element-number element)))
+ ;; This is performance critical, and it's not certain that the host
+ ;; compiler does modular arithmetic optimization. Instad use
+ ;; something that most CL implementations will do efficiently.
+ (the fixnum (logxor (the fixnum result)
+ (the fixnum (ash result -9))
+ (the fixnum (ash result -5)))))
+ #-sb-xc-host
+ (let ((result (sset-element-number element)))
+ (declare (type sb!vm:word result))
+ ;; We only use the low-order bits.
+ (macrolet ((set-result (form)
+ `(setf result (ldb (byte #.sb!vm:n-word-bits 0) ,form))))
+ (set-result (+ result (ash result -19)))
+ (set-result (logxor result (ash result -13)))
+ (set-result (+ result (ash result -9)))
+ (set-result (logxor result (ash result -5)))
+ (set-result (+ result (ash result -2)))
+ (logand sb!xc:most-positive-fixnum result))))
+
+;;; Secondary hash (for double hash probing). Needs to return an odd
+;;; number.
+(declaim (inline sset-hash2))
+(defun sset-hash2 (element)
+ (let ((number (sset-element-number element)))
+ (declare (fixnum number))
+ (logior 1 number)))
+
+;;; Double the size of the hash vector of SET.
+(defun sset-grow (set)
+ (let* ((vector (sset-vector set))
+ (new-vector (make-array (if (zerop (length vector))
+ 2
+ (* (length vector) 2))
+ :initial-element 0)))
+ (setf (sset-vector set) new-vector
+ (sset-free set) (length new-vector)
+ (sset-count set) 0)
+ (loop for element across vector
+ do (unless (member element '(0 +deleted+))
+ (sset-adjoin element set)))))
+
+;;; Rehash the sset when the proportion of free cells in the set is
+;;; lower than this.
+(eval-when (:compile-toplevel :load-toplevel :execute)
+ (defconstant +sset-rehash-threshold+ 1/4))