X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Fhash-table.lisp;h=9f2a6b4325773ef5dad0e4f87d73c382a71c5268;hb=25fe91bf63fd473d9316675b0e0ca9be0079e9eb;hp=c352a17a7f819b4df7819988b70b97130d0fbbcb;hpb=4eb1a6d3ad2b7dcc19ac0ec979a1eb1eb049659a;p=sbcl.git

diff --git a/src/code/hash-table.lisp b/src/code/hash-table.lisp
index c352a17..9f2a6b4 100644
--- a/src/code/hash-table.lisp
+++ b/src/code/hash-table.lisp
@@ -28,7 +28,7 @@
   ;; 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
@@ -39,11 +39,13 @@
   (number-entries 0 :type index)
   ;; The Key-Value pair vector.
   (table (missing-arg) :type simple-vector)
-  ;; True if this is a weak hash table, meaning that key->value
-  ;; mappings will disappear if there are no other references to the
-  ;; key. Note: this only matters if the hash function indicates that
-  ;; the hashing is EQ based.
-  (weak-p nil :type (member t nil))
+  ;; This slot is used to link weak hash tables during GC. When the GC
+  ;; isn't running it is always NIL.
+  (next-weak-hash-table nil :type null)
+  ;; Non-NIL if this is some kind of weak hash table. For details see
+  ;; the docstring of MAKE-HASH-TABLE.
+  (weakness nil :type (member nil :key :value :key-or-value :key-and-value)
+            :read-only t)
   ;; Index into the next-vector, chaining together buckets that need
   ;; to be rehashed because their hashing is EQ based and the key has
   ;; been moved by the garbage collector.
@@ -51,19 +53,37 @@
   ;; 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)))
+
 
 (defmacro-mundanely with-hash-table-iterator ((function hash-table) &body body)
   #!+sb-doc
@@ -75,23 +95,23 @@
    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))))