;; then add that amount. If a floating point number, then multiply
;; it by that.
(rehash-size (missing-arg) :type (or index (single-float (1.0)))
- :read-only t)
+ :read-only t)
;; how full the hash table has to get before we rehash
(rehash-threshold (missing-arg) :type (single-float (0.0) 1.0) :read-only t)
;; The number of entries before a rehash, just one less than the
;; Index into the Next vector chaining together free slots in the KV
;; vector.
(next-free-kv 0 :type index)
+ ;; A cache that is either nil or is an index into the hash table
+ ;; that should be checked first
+ (cache nil :type (or null index))
;; The index vector. This may be larger than the hash size to help
;; reduce collisions.
- (index-vector (missing-arg) :type (simple-array (unsigned-byte 32) (*)))
+ (index-vector (missing-arg)
+ :type (simple-array (unsigned-byte #.sb!vm:n-word-bits) (*)))
;; This table parallels the KV vector, and is used to chain together
;; the hash buckets, the free list, and the values needing rehash, a
;; slot will only ever be in one of these lists.
- (next-vector (missing-arg) :type (simple-array (unsigned-byte 32) (*)))
+ (next-vector (missing-arg)
+ :type (simple-array (unsigned-byte #.sb!vm:n-word-bits) (*)))
;; This table parallels the KV table, and can be used to store the
;; hash associated with the key, saving recalculation. Could be
;; useful for EQL, and EQUAL hash tables. This table is not needed
- ;; for EQ hash tables, and when present the value of #x8000000
- ;; represents EQ-based hashing on the respective key.
- (hash-vector nil :type (or null (simple-array (unsigned-byte 32) (*)))))
+ ;; for EQ hash tables, and when present the value of
+ ;; +MAGIC-HASH-VECTOR-VALUE+ represents EQ-based hashing on the
+ ;; respective key.
+ (hash-vector nil :type (or null (simple-array (unsigned-byte
+ #.sb!vm:n-word-bits) (*))))
+ ;; This lock is acquired by %PUTHASH, REMHASH, CLRHASH and GETHASH.
+ (spinlock (sb!thread::make-spinlock)))
+
+;; as explained by pmai on openprojects #lisp IRC 2002-07-30: #x80000000
+;; is bigger than any possible nonEQ hash value, and thus indicates an
+;; empty slot; and EQ hash tables don't use HASH-TABLE-HASH-VECTOR.
+;; The previous sentence was written when SBCL was 32-bit only. The value
+;; now depends on the word size. It is propagated to C in genesis because
+;; the generational garbage collector needs to know it.
+(defconstant +magic-hash-vector-value+ (ash 1 (1- sb!vm:n-word-bits)))
+
\f
(defmacro-mundanely with-hash-table-iterator ((function hash-table) &body body)
#!+sb-doc
the second and third values are the key and the value of the next object."
(let ((n-function (gensym "WITH-HASH-TABLE-ITERATOR-")))
`(let ((,n-function
- (let* ((table ,hash-table)
- (length (length (hash-table-next-vector table)))
- (index 1))
- (declare (type (mod #.(floor most-positive-fixnum 2)) index))
- (labels
- ((,function ()
- ;; (We grab the table again on each iteration just in
- ;; case it was rehashed by a PUTHASH.)
- (let ((kv-vector (hash-table-table table)))
- (do ()
- ((>= index length) (values nil))
- (let ((key (aref kv-vector (* 2 index)))
- (value (aref kv-vector (1+ (* 2 index)))))
- (incf index)
- (unless (and (eq key +empty-ht-slot+)
- (eq value +empty-ht-slot+))
- (return (values t key value))))))))
- #',function))))
+ (let* ((table ,hash-table)
+ (length (length (hash-table-next-vector table)))
+ (index 1))
+ (declare (type (mod #.(floor most-positive-fixnum 2)) index))
+ (labels
+ ((,function ()
+ ;; (We grab the table again on each iteration just in
+ ;; case it was rehashed by a PUTHASH.)
+ (let ((kv-vector (hash-table-table table)))
+ (do ()
+ ((>= index length) (values nil))
+ (let ((key (aref kv-vector (* 2 index)))
+ (value (aref kv-vector (1+ (* 2 index)))))
+ (incf index)
+ (unless (and (eq key +empty-ht-slot+)
+ (eq value +empty-ht-slot+))
+ (return (values t key value))))))))
+ #',function))))
(macrolet ((,function () '(funcall ,n-function)))
- ,@body))))
+ ,@body))))
projects / sbcl.git / blobdiff