src/code/target-hash-table.lisp

   1 ;;;; that part of the implementation of HASH-TABLE which lives solely
   2 ;;;; on the target system, not on the cross-compilation host
   3
   4 ;;;; This software is part of the SBCL system. See the README file for
   5 ;;;; more information.
   6 ;;;;
   7 ;;;; This software is derived from the CMU CL system, which was
   8 ;;;; written at Carnegie Mellon University and released into the
   9 ;;;; public domain. The software is in the public domain and is
  10 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
  11 ;;;; files for more information.
  12
  13 (in-package "SB!IMPL")
  14 \f
  15 ;;;; utilities
  16
  17 (eval-when (:compile-toplevel :load-toplevel :execute)
  18   (defconstant max-hash sb!xc:most-positive-fixnum))
  19
  20 ;;; Code for detecting concurrent accesses to the same table from
  21 ;;; multiple threads. Only compiled in when the :SB-HASH-TABLE-DEBUG
  22 ;;; feature is enabled. The main reason for the existence of this code
  23 ;;; is to detect thread-unsafe uses of hash-tables in sbcl itself,
  24 ;;; where debugging anythign can be impossible after an important
  25 ;;; internal hash-table has been corrupted. It's plausible that this
  26 ;;; could be useful for some user code too, but the runtime cost is
  27 ;;; really too high to enable it by default.
  28 (defmacro with-concurrent-access-check (hash-table &body body)
  29   (declare (ignorable hash-table))
  30   #!-sb-hash-table-debug
  31   `(progn ,@body)
  32   #!+sb-hash-table-debug
  33   (once-only ((hash-table hash-table))
  34     `(progn
  35        (flet ((body-fun ()
  36                 ,@body)
  37               (error-fun ()
  38                 ;; Don't signal more errors for this table.
  39                 (setf (hash-table-concurrent-access-error ,hash-table) nil)
  40                 (error "Concurrent access to ~A" ,hash-table)))
  41          (if (hash-table-concurrent-access-error ,hash-table)
  42              (let ((thread (hash-table-accessing-thread ,hash-table)))
  43                (unwind-protect
  44                     (progn
  45                       (when (and thread
  46                                  (not (eql thread sb!thread::*current-thread*)))
  47                         (error-fun))
  48                       (setf (hash-table-accessing-thread ,hash-table)
  49                             sb!thread::*current-thread*)
  50                       (body-fun))
  51                  (unless (eql (hash-table-accessing-thread ,hash-table)
  52                               sb!thread::*current-thread*)
  53                    (error-fun))
  54                  (setf (hash-table-accessing-thread ,hash-table) thread)))
  55              (body-fun))))))
  56
  57 (deftype hash ()
  58   `(integer 0 ,max-hash))
  59
  60 ;;; FIXME: Does this always make a nonnegative FIXNUM? If so, then
  61 ;;; explain why. If not (or if the reason it always makes a
  62 ;;; nonnegative FIXNUM is only the accident that pointers in supported
  63 ;;; architectures happen to be in the lower half of the address
  64 ;;; space), then fix it.
  65 #!-sb-fluid (declaim (inline pointer-hash))
  66 (defun pointer-hash (key)
  67   (declare (values hash))
  68   (truly-the hash (%primitive sb!c:make-fixnum key)))
  69
  70 #!-sb-fluid (declaim (inline eq-hash))
  71 (defun eq-hash (key)
  72   (declare (values hash (member t nil)))
  73   (values (pointer-hash key)
  74           (oddp (get-lisp-obj-address key))))
  75
  76 #!-sb-fluid (declaim (inline equal-hash))
  77 (defun equal-hash (key)
  78   (declare (values hash (member t nil)))
  79   (typecase key
  80     ;; For some types the definition of EQUAL implies a special hash
  81     ((or string cons number bit-vector pathname)
  82      (values (sxhash key) nil))
  83     ;; Otherwise use an EQ hash, rather than SXHASH, since the values
  84     ;; of SXHASH will be extremely badly distributed due to the
  85     ;; requirements of the spec fitting badly with our implementation
  86     ;; strategy.
  87     (t
  88      (eq-hash key))))
  89
  90 #!-sb-fluid (declaim (inline eql-hash))
  91 (defun eql-hash (key)
  92   (declare (values hash (member t nil)))
  93   (if (numberp key)
  94       (equal-hash key)
  95       (eq-hash key)))
  96
  97 (defun equalp-hash (key)
  98   (declare (values hash (member t nil)))
  99   (typecase key
 100     ;; Types requiring special treatment. Note that PATHNAME and
 101     ;; HASH-TABLE are caught by the STRUCTURE-OBJECT test.
 102     ((or array cons number character structure-object)
 103      (values (psxhash key) nil))
 104     (t
 105      (eq-hash key))))
 106
 107 (defun ceil-power-of-two (num)
 108   (declare (type index num))
 109   (ash 1 (integer-length num)))
 110
 111 (declaim (inline index-for-hashing))
 112 (defun index-for-hashing (index length)
 113   (declare (type index index length))
 114   ;; We're using power of two tables which obviously are very
 115   ;; sensitive to the exact values of the low bits in the hash
 116   ;; value. Do a little shuffling of the value to mix the high bits in
 117   ;; there too.
 118   (logand (1- length)
 119           (+ (logxor #b11100101010001011010100111
 120                      index)
 121              (ash index -6)
 122              (ash index -15)
 123              (ash index -23))))
 124
 125 \f
 126 ;;;; user-defined hash table tests
 127
 128 (defvar *hash-table-tests* nil)
 129
 130 (defun define-hash-table-test (name test-fun hash-fun)
 131   #!+sb-doc
 132   "Define a new kind of hash table test."
 133   (declare (type symbol name)
 134            (type function test-fun hash-fun))
 135   (setf *hash-table-tests*
 136         (cons (list name test-fun hash-fun)
 137               (remove name *hash-table-tests* :test #'eq :key #'car)))
 138   name)
 139 \f
 140 ;;;; construction and simple accessors
 141
 142 (defconstant +min-hash-table-size+ 16)
 143 (defconstant +min-hash-table-rehash-threshold+ (float 1/16 1.0))
 144
 145 (defun make-hash-table (&key (test 'eql)
 146                         (size +min-hash-table-size+)
 147                         (rehash-size 1.5)
 148                         (rehash-threshold 1)
 149                         (weakness nil))
 150   #!+sb-doc
 151   "Create and return a new hash table. The keywords are as follows:
 152      :TEST -- Indicates what kind of test to use.
 153      :SIZE -- A hint as to how many elements will be put in this hash
 154        table.
 155      :REHASH-SIZE -- Indicates how to expand the table when it fills up.
 156        If an integer, add space for that many elements. If a floating
 157        point number (which must be greater than 1.0), multiply the size
 158        by that amount.
 159      :REHASH-THRESHOLD -- Indicates how dense the table can become before
 160        forcing a rehash. Can be any positive number <=1, with density
 161        approaching zero as the threshold approaches 0. Density 1 means an
 162        average of one entry per bucket.
 163      :WEAKNESS -- IF NIL (the default) it is a normal non-weak hash table.
 164        If one of :KEY, :VALUE, :KEY-AND-VALUE, :KEY-OR-VALUE it is a weak
 165        hash table.
 166        Depending on the type of weakness the lack of references to the
 167        key and the value may allow for removal of the entry. If WEAKNESS
 168        is :KEY and the key would otherwise be garbage the entry is eligible
 169        for removal from the hash table. Similarly, if WEAKNESS is :VALUE
 170        the life of an entry depends on its value's references. If WEAKNESS
 171        is :KEY-AND-VALUE and either the key or the value would otherwise be
 172        garbage the entry can be removed. If WEAKNESS is :KEY-OR-VALUE and
 173        both the key and the value would otherwise be garbage the entry can
 174        be removed."
 175   (declare (type (or function symbol) test))
 176   (declare (type unsigned-byte size))
 177   (multiple-value-bind (test test-fun hash-fun)
 178       (cond ((or (eq test #'eq) (eq test 'eq))
 179              (values 'eq #'eq #'eq-hash))
 180             ((or (eq test #'eql) (eq test 'eql))
 181              (values 'eql #'eql #'eql-hash))
 182             ((or (eq test #'equal) (eq test 'equal))
 183              (values 'equal #'equal #'equal-hash))
 184             ((or (eq test #'equalp) (eq test 'equalp))
 185              (values 'equalp #'equalp #'equalp-hash))
 186             (t
 187              ;; FIXME: I'd like to remove *HASH-TABLE-TESTS* stuff.
 188              ;; Failing that, I'd like to rename it to
 189              ;; *USER-HASH-TABLE-TESTS*.
 190              (dolist (info *hash-table-tests*
 191                       (error "unknown :TEST for MAKE-HASH-TABLE: ~S"
 192                              test))
 193                (destructuring-bind (test-name test-fun hash-fun) info
 194                  (when (or (eq test test-name) (eq test test-fun))
 195                    (return (values test-name test-fun hash-fun)))))))
 196     (let* ((size (max +min-hash-table-size+
 197                       (min size
 198                            ;; SIZE is just a hint, so if the user asks
 199                            ;; for a SIZE which'd be too big for us to
 200                            ;; easily implement, we bump it down.
 201                            (floor array-dimension-limit 1024))))
 202            (rehash-size (if (integerp rehash-size)
 203                             rehash-size
 204                             (float rehash-size 1.0)))
 205            ;; FIXME: Original REHASH-THRESHOLD default should be 1.0,
 206            ;; not 1, to make it easier for the compiler to avoid
 207            ;; boxing.
 208            (rehash-threshold (max +min-hash-table-rehash-threshold+
 209                                   (float rehash-threshold 1.0)))
 210            (size+1 (1+ size))       ; The first element is not usable.
 211            ;; KLUDGE: The most natural way of expressing the below is
 212            ;; (round (/ (float size+1) rehash-threshold)), and indeed
 213            ;; it was expressed like that until 0.7.0. However,
 214            ;; MAKE-HASH-TABLE is called very early in cold-init, and
 215            ;; the SPARC has no primitive instructions for rounding,
 216            ;; but only for truncating; therefore, we fudge this issue
 217            ;; a little. The other uses of truncate, below, similarly
 218            ;; used to be round. -- CSR, 2002-10-01
 219            ;;
 220            ;; Note that this has not yet been audited for
 221            ;; correctness. It just seems to work. -- CSR, 2002-11-02
 222            (scaled-size (truncate (/ (float size+1) rehash-threshold)))
 223            (length (ceil-power-of-two (max scaled-size
 224                                            (1+ +min-hash-table-size+))))
 225            (index-vector (make-array length
 226                                      :element-type
 227                                      '(unsigned-byte #.sb!vm:n-word-bits)
 228                                      :initial-element 0))
 229            ;; Needs to be the half the length of the KV vector to link
 230            ;; KV entries - mapped to indeces at 2i and 2i+1 -
 231            ;; together.
 232            (next-vector (make-array size+1
 233                                     :element-type
 234                                     '(unsigned-byte #.sb!vm:n-word-bits)))
 235            (kv-vector (make-array (* 2 size+1)
 236                                   :initial-element +empty-ht-slot+))
 237            (table (%make-hash-table
 238                    :test test
 239                    :test-fun test-fun
 240                    :hash-fun hash-fun
 241                    :rehash-size rehash-size
 242                    :rehash-threshold rehash-threshold
 243                    :rehash-trigger size
 244                    :table kv-vector
 245                    :weakness weakness
 246                    :index-vector index-vector
 247                    :next-vector next-vector
 248                    :hash-vector
 249                    (unless (eq test 'eq)
 250                      (make-array size+1
 251                                  :element-type '(unsigned-byte
 252                                                  #.sb!vm:n-word-bits)
 253                                  :initial-element +magic-hash-vector-value+))
 254                    :spinlock (sb!thread::make-spinlock))))
 255       (declare (type index size+1 scaled-size length))
 256       ;; Set up the free list, all free. These lists are 0 terminated.
 257       (do ((i 1 (1+ i)))
 258           ((>= i size))
 259         (setf (aref next-vector i) (1+ i)))
 260       (setf (aref next-vector size) 0)
 261       (setf (hash-table-next-free-kv table) 1)
 262       (setf (aref kv-vector 0) table)
 263       table)))
 264
 265 (defun hash-table-count (hash-table)
 266   #!+sb-doc
 267   "Return the number of entries in the given HASH-TABLE."
 268   (declare (type hash-table hash-table)
 269            (values index))
 270   (hash-table-number-entries hash-table))
 271
 272 #!+sb-doc
 273 (setf (fdocumentation 'hash-table-rehash-size 'function)
 274       "Return the rehash-size HASH-TABLE was created with.")
 275
 276 #!+sb-doc
 277 (setf (fdocumentation 'hash-table-rehash-threshold 'function)
 278       "Return the rehash-threshold HASH-TABLE was created with.")
 279
 280 (defun hash-table-size (hash-table)
 281   #!+sb-doc
 282   "Return a size that can be used with MAKE-HASH-TABLE to create a hash
 283    table that can hold however many entries HASH-TABLE can hold without
 284    having to be grown."
 285   (hash-table-rehash-trigger hash-table))
 286
 287 #!+sb-doc
 288 (setf (fdocumentation 'hash-table-test 'function)
 289       "Return the test HASH-TABLE was created with.")
 290
 291 #!+sb-doc
 292 (setf (fdocumentation 'hash-table-weakness 'function)
 293       "Return the WEAKNESS of HASH-TABLE which is one of NIL, :KEY,
 294 :VALUE, :KEY-AND-VALUE, :KEY-OR-VALUE.")
 295
 296 ;;; Called when we detect circular chains in a hash-table.
 297 (defun signal-corrupt-hash-table (hash-table)
 298   (error "Corrupt NEXT-chain in ~A. This is probably caused by ~
 299 multiple threads accessing the same hash-table without locking."
 300          hash-table))
 301
 302 \f
 303 ;;;; accessing functions
 304
 305 ;;; Make new vectors for the table, extending the table based on the
 306 ;;; rehash-size.
 307 (defun rehash (table)
 308   (declare (type hash-table table))
 309   (aver *gc-inhibit*)
 310   (let* ((old-kv-vector (hash-table-table table))
 311          (old-next-vector (hash-table-next-vector table))
 312          (old-hash-vector (hash-table-hash-vector table))
 313          (old-size (length old-next-vector))
 314          (new-size
 315           (ceil-power-of-two
 316            (let ((rehash-size (hash-table-rehash-size table)))
 317              (etypecase rehash-size
 318                (fixnum
 319                 (+ rehash-size old-size))
 320                (float
 321                 (the index (truncate (* rehash-size old-size))))))))
 322          (new-kv-vector (make-array (* 2 new-size)
 323                                     :initial-element +empty-ht-slot+))
 324          (new-next-vector
 325           (make-array new-size
 326                       :element-type '(unsigned-byte #.sb!vm:n-word-bits)
 327                       :initial-element 0))
 328          (new-hash-vector
 329           (when old-hash-vector
 330             (make-array new-size
 331                         :element-type '(unsigned-byte #.sb!vm:n-word-bits)
 332                         :initial-element +magic-hash-vector-value+)))
 333          (new-length new-size)
 334          (new-index-vector
 335           (make-array new-length
 336                       :element-type '(unsigned-byte #.sb!vm:n-word-bits)
 337                       :initial-element 0)))
 338     (declare (type index new-size new-length old-size))
 339
 340     ;; Disable GC tricks on the OLD-KV-VECTOR.
 341     (set-header-data old-kv-vector sb!vm:vector-normal-subtype)
 342
 343     ;; Non-empty weak hash tables always need GC support.
 344     (when (and (hash-table-weakness table) (plusp (hash-table-count table)))
 345       (set-header-data new-kv-vector sb!vm:vector-valid-hashing-subtype))
 346
 347     ;; FIXME: here and in several other places in the hash table code,
 348     ;; loops like this one are used when FILL or REPLACE would be
 349     ;; appropriate.  why are standard CL functions not used?
 350     ;; Performance issues?  General laziness?  -- NJF, 2004-03-10
 351
 352     ;; Copy over the kv-vector. The element positions should not move
 353     ;; in case there are active scans.
 354     (dotimes (i (* old-size 2))
 355       (declare (type index i))
 356       (setf (aref new-kv-vector i) (aref old-kv-vector i)))
 357
 358     ;; Copy over the hash-vector.
 359     (when old-hash-vector
 360       (dotimes (i old-size)
 361         (setf (aref new-hash-vector i) (aref old-hash-vector i))))
 362
 363     (setf (hash-table-next-free-kv table) 0)
 364     ;; Rehash all the entries; last to first so that after the pushes
 365     ;; the chains are first to last.
 366     (do ((i (1- new-size) (1- i)))
 367         ((zerop i))
 368       (declare (type index/2 i))
 369       (let ((key (aref new-kv-vector (* 2 i)))
 370             (value (aref new-kv-vector (1+ (* 2 i)))))
 371         (cond ((and (eq key +empty-ht-slot+)
 372                     (eq value +empty-ht-slot+))
 373                ;; Slot is empty, push it onto the free list.
 374                (setf (aref new-next-vector i)
 375                      (hash-table-next-free-kv table))
 376                (setf (hash-table-next-free-kv table) i))
 377               ((and new-hash-vector
 378                     (not (= (aref new-hash-vector i)
 379                             +magic-hash-vector-value+)))
 380                ;; Can use the existing hash value (not EQ based)
 381                (let* ((hashing (aref new-hash-vector i))
 382                       (index (index-for-hashing hashing new-length))
 383                       (next (aref new-index-vector index)))
 384                  (declare (type index index)
 385                           (type hash hashing))
 386                  ;; Push this slot into the next chain.
 387                  (setf (aref new-next-vector i) next)
 388                  (setf (aref new-index-vector index) i)))
 389               (t
 390                ;; EQ base hash.
 391                ;; Enable GC tricks.
 392                (set-header-data new-kv-vector
 393                                 sb!vm:vector-valid-hashing-subtype)
 394                (let* ((hashing (pointer-hash key))
 395                       (index (index-for-hashing hashing new-length))
 396                       (next (aref new-index-vector index)))
 397                  (declare (type index index)
 398                           (type hash hashing))
 399                  ;; Push this slot onto the next chain.
 400                  (setf (aref new-next-vector i) next)
 401                  (setf (aref new-index-vector index) i))))))
 402     (setf (hash-table-table table) new-kv-vector)
 403     (setf (hash-table-index-vector table) new-index-vector)
 404     (setf (hash-table-next-vector table) new-next-vector)
 405     (setf (hash-table-hash-vector table) new-hash-vector)
 406     ;; Fill the old kv-vector with 0 to help the conservative GC. Even
 407     ;; if nothing else were zeroed, it's important to clear the
 408     ;; special first cells in old-kv-vector.
 409     (fill old-kv-vector 0)
 410     (setf (hash-table-rehash-trigger table) new-size)
 411     (setf (hash-table-needs-rehash-p table) nil))
 412   (values))
 413
 414 ;;; Use the same size as before, re-using the vectors.
 415 (defun rehash-without-growing (table)
 416   (declare (type hash-table table))
 417   (aver *gc-inhibit*)
 418   (let* ((kv-vector (hash-table-table table))
 419          (next-vector (hash-table-next-vector table))
 420          (hash-vector (hash-table-hash-vector table))
 421          (size (length next-vector))
 422          (index-vector (hash-table-index-vector table))
 423          (length (length index-vector)))
 424     (declare (type index size length))
 425
 426     ;; Non-empty weak hash tables always need GC support.
 427     (unless (and (hash-table-weakness table) (plusp (hash-table-count table)))
 428       ;; Disable GC tricks, they will be re-enabled during the re-hash
 429       ;; if necessary.
 430       (set-header-data kv-vector sb!vm:vector-normal-subtype))
 431
 432     ;; Rehash all the entries.
 433     (setf (hash-table-next-free-kv table) 0)
 434     (dotimes (i size)
 435       (setf (aref next-vector i) 0))
 436     (dotimes (i length)
 437       (setf (aref index-vector i) 0))
 438     (do ((i (1- size) (1- i)))
 439         ((zerop i))
 440       (declare (type index/2 i))
 441       (let ((key (aref kv-vector (* 2 i)))
 442             (value (aref kv-vector (1+ (* 2 i)))))
 443         (cond ((and (eq key +empty-ht-slot+)
 444                     (eq value +empty-ht-slot+))
 445                ;; Slot is empty, push it onto free list.
 446                (setf (aref next-vector i) (hash-table-next-free-kv table))
 447                (setf (hash-table-next-free-kv table) i))
 448               ((and hash-vector (not (= (aref hash-vector i)
 449                                         +magic-hash-vector-value+)))
 450                ;; Can use the existing hash value (not EQ based)
 451                (let* ((hashing (aref hash-vector i))
 452                       (index (index-for-hashing hashing length))
 453                       (next (aref index-vector index)))
 454                  (declare (type index index))
 455                  ;; Push this slot into the next chain.
 456                  (setf (aref next-vector i) next)
 457                  (setf (aref index-vector index) i)))
 458               (t
 459                ;; EQ base hash.
 460                ;; Enable GC tricks.
 461                (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype)
 462                (let* ((hashing (pointer-hash key))
 463                       (index (index-for-hashing hashing length))
 464                       (next (aref index-vector index)))
 465                  (declare (type index index)
 466                           (type hash hashing))
 467                  ;; Push this slot into the next chain.
 468                  (setf (aref next-vector i) next)
 469                  (setf (aref index-vector index) i)))))))
 470   ;; Clear the rehash bit only at the very end, otherwise another thread
 471   ;; might see a partially rehashed table as a normal one.
 472   (setf (hash-table-needs-rehash-p table) nil)
 473   (values))
 474
 475 (declaim (inline maybe-rehash))
 476 (defun maybe-rehash (hash-table ensure-free-slot-p)
 477   (when (hash-table-weakness hash-table)
 478     (aver *gc-inhibit*))
 479   (flet ((rehash-p ()
 480            (and ensure-free-slot-p
 481                 (zerop (hash-table-next-free-kv hash-table))))
 482          (rehash-without-growing-p ()
 483            (hash-table-needs-rehash-p hash-table)))
 484     (declare (inline rehash-p rehash-without-growing-p))
 485     (cond ((rehash-p)
 486            ;; Use recursive spinlocks since for weak tables the
 487            ;; spinlock has already been acquired. GC must be inhibited
 488            ;; to prevent the GC from seeing a rehash in progress.
 489            (sb!thread::with-recursive-system-spinlock
 490                ((hash-table-spinlock hash-table) :without-gcing t)
 491              ;; Repeat the condition inside the lock to ensure that if
 492              ;; two reader threads enter MAYBE-REHASH at the same time
 493              ;; only one rehash is performed.
 494              (when (rehash-p)
 495                (rehash hash-table))))
 496           ((rehash-without-growing-p)
 497            (sb!thread::with-recursive-system-spinlock
 498                ((hash-table-spinlock hash-table) :without-gcing t)
 499              (when (rehash-without-growing-p)
 500                (rehash-without-growing hash-table)))))))
 501
 502 (declaim (inline update-hash-table-cache))
 503 (defun update-hash-table-cache (hash-table index)
 504   (unless (hash-table-weakness hash-table)
 505     (setf (hash-table-cache hash-table) index)))
 506
 507 (defmacro with-hash-table-locks ((hash-table inline &rest pin-objects)
 508                                  &body body)
 509   `(with-concurrent-access-check ,hash-table
 510      ;; Inhibit GC for the duration of BODY if the GC might mutate the
 511      ;; HASH-TABLE in some way (currently true only if the table is
 512      ;; weak). We also need to lock the table to ensure that two
 513      ;; concurrent writers can't create a cyclical vector that would
 514      ;; cause scav_weak_hash_table_chain to loop.
 515      ;;
 516      ;; Otherwise we can avoid the 2x-3x overhead, and just pin the key.
 517      (if (hash-table-weakness ,hash-table)
 518          (sb!thread::with-recursive-system-spinlock
 519              ((hash-table-spinlock hash-table) :without-gcing t)
 520            ,@body)
 521          (with-pinned-objects ,pin-objects
 522            (locally
 523                ;; Inline the implementation function on the fast path
 524                ;; only. (On the slow path it'll just bloat the
 525                ;; generated code with no benefit).
 526                (declare (inline ,@inline))
 527              ,@body)))))
 528
 529 (defun gethash (key hash-table &optional default)
 530   #!+sb-doc
 531   "Finds the entry in HASH-TABLE whose key is KEY and returns the associated
 532    value and T as multiple values, or returns DEFAULT and NIL if there is no
 533    such entry. Entries can be added using SETF."
 534   (declare (type hash-table hash-table)
 535            (values t (member t nil)))
 536   (gethash3 key hash-table default))
 537
 538 (declaim (maybe-inline %gethash3))
 539 (defun %gethash3 (key hash-table default)
 540   (declare (type hash-table hash-table)
 541            (optimize speed)
 542            (values t (member t nil)))
 543   (tagbody
 544    start
 545      (let ((start-epoch sb!kernel::*gc-epoch*))
 546        (macrolet ((result (value foundp)
 547                     ;; When the table has multiple concurrent readers,
 548                     ;; it's possible that there was a GC after this
 549                     ;; thread called MAYBE-REHASH from %GETHASH3, and
 550                     ;; some other thread then rehashed the table. If
 551                     ;; this happens, we might not find the key even if
 552                     ;; it's in the table. To protect against this,
 553                     ;; redo the lookup if the GC epoch counter has changed.
 554                     ;; -- JES,  2007-09-30
 555                     `(if (and (not ,foundp)
 556                               (not (eql start-epoch sb!kernel::*gc-epoch*)))
 557                          (go start)
 558                          (return-from %gethash3 (values ,value ,foundp))))
 559                   (overflow ()
 560                     ;; The next-vector chain is circular. This is caused
 561                     ;; caused by thread-unsafe mutations of the table.
 562                     `(signal-corrupt-hash-table hash-table)))
 563          (maybe-rehash hash-table nil)
 564          ;; Note that it's OK for a GC + a REHASH-WITHOUT-GROWING to
 565          ;; be triggered by another thread after this point, since the
 566          ;; GC epoch check will catch it.
 567          (let ((cache (hash-table-cache hash-table))
 568                (table (hash-table-table hash-table)))
 569            ;; First check the cache.  Use EQ here for speed.
 570            (if (and cache
 571                     (< cache (length table))
 572                     (eq (aref table cache) key))
 573                (let ((value (aref table (1+ cache))))
 574                  (result value t))
 575                ;; Search for key in the hash table.
 576                (multiple-value-bind (hashing eq-based)
 577                    (funcall (hash-table-hash-fun hash-table) key)
 578                  (declare (type hash hashing))
 579                  (let* ((index-vector (hash-table-index-vector hash-table))
 580                         (length (length index-vector))
 581                         (index (index-for-hashing hashing length))
 582                         (next (aref index-vector index))
 583                         (next-vector (hash-table-next-vector hash-table))
 584                         (hash-vector (hash-table-hash-vector hash-table))
 585                         (test-fun (hash-table-test-fun hash-table)))
 586                    (declare (type index index))
 587                    ;; Search next-vector chain for a matching key.
 588                    (if (or eq-based (not hash-vector))
 589                        (do ((next next (aref next-vector next))
 590                             (i 0 (1+ i)))
 591                            ((zerop next) (result default nil))
 592                          (declare (type index/2 next i))
 593                          (when (> i length)
 594                            (overflow))
 595                          (when (eq key (aref table (* 2 next)))
 596                            (update-hash-table-cache hash-table (* 2 next))
 597                            (let ((value (aref table (1+ (* 2 next)))))
 598                              (result value t))))
 599                        (do ((next next (aref next-vector next))
 600                             (i 0 (1+ i)))
 601                            ((zerop next) (result default nil))
 602                          (declare (type index/2 next i))
 603                          (when (> i length)
 604                            (overflow))
 605                          (when (and (= hashing (aref hash-vector next))
 606                                     (funcall test-fun key
 607                                              (aref table (* 2 next))))
 608                            ;; Found.
 609                            (update-hash-table-cache hash-table (* 2 next))
 610                            (let ((value (aref table (1+ (* 2 next)))))
 611                              (result value t)))))))))))))
 612
 613 (defun gethash3 (key hash-table default)
 614   "Three argument version of GETHASH"
 615   (declare (type hash-table hash-table))
 616   (with-hash-table-locks (hash-table (%gethash3) key)
 617     (%gethash3 key hash-table default)))
 618
 619 ;;; so people can call #'(SETF GETHASH)
 620 (defun (setf gethash) (new-value key table &optional default)
 621   (declare (ignore default))
 622   (%puthash key table new-value))
 623
 624 (declaim (maybe-inline %%puthash))
 625 (defun %%puthash (key hash-table value)
 626   (declare (optimize speed))
 627   ;; We need to rehash here so that a current key can be found if it
 628   ;; exists. Check that there is room for one more entry. May not be
 629   ;; needed if the key is already present.
 630   (maybe-rehash hash-table t)
 631   ;; Search for key in the hash table.
 632   (multiple-value-bind (hashing eq-based)
 633       (funcall (hash-table-hash-fun hash-table) key)
 634     (declare (type hash hashing))
 635     (let* ((index-vector (hash-table-index-vector hash-table))
 636            (length (length index-vector))
 637            (index (index-for-hashing hashing length))
 638            (next (aref index-vector index))
 639            (kv-vector (hash-table-table hash-table))
 640            (next-vector (hash-table-next-vector hash-table))
 641            (hash-vector (hash-table-hash-vector hash-table))
 642            (test-fun (hash-table-test-fun hash-table)))
 643       (declare (type index index next))
 644       (when (hash-table-weakness hash-table)
 645         (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype))
 646       (cond ((or eq-based (not hash-vector))
 647              (when eq-based
 648                (set-header-data kv-vector
 649                                 sb!vm:vector-valid-hashing-subtype))
 650              ;; Search next-vector chain for a matching key.
 651              (do ((next next (aref next-vector next))
 652                   (i 0 (1+ i)))
 653                  ((zerop next))
 654                (declare (type index/2 next i))
 655                (when (> i length)
 656                  (signal-corrupt-hash-table hash-table))
 657                (when (eq key (aref kv-vector (* 2 next)))
 658                  ;; Found, just replace the value.
 659                  (update-hash-table-cache hash-table (* 2 next))
 660                  (setf (aref kv-vector (1+ (* 2 next))) value)
 661                  (return-from %%puthash value))))
 662             (t
 663              ;; Search next-vector chain for a matching key.
 664              (do ((next next (aref next-vector next))
 665                   (i 0 (1+ i)))
 666                  ((zerop next))
 667                (declare (type index/2 next i))
 668                (when (> i length)
 669                  (signal-corrupt-hash-table hash-table))
 670                (when (and (= hashing (aref hash-vector next))
 671                           (funcall test-fun key
 672                                    (aref kv-vector (* 2 next))))
 673                  ;; Found, just replace the value.
 674                  (update-hash-table-cache hash-table (* 2 next))
 675                  (setf (aref kv-vector (1+ (* 2 next))) value)
 676                  (return-from %%puthash value)))))
 677       ;; Pop a KV slot off the free list
 678       (let ((free-kv-slot (hash-table-next-free-kv hash-table)))
 679         (declare (type index/2 free-kv-slot))
 680         ;; Double-check for overflow.
 681         (aver (not (zerop free-kv-slot)))
 682         (setf (hash-table-next-free-kv hash-table)
 683               (aref next-vector free-kv-slot))
 684         (incf (hash-table-number-entries hash-table))
 685         (update-hash-table-cache hash-table (* 2 free-kv-slot))
 686         (setf (aref kv-vector (* 2 free-kv-slot)) key)
 687         (setf (aref kv-vector (1+ (* 2 free-kv-slot))) value)
 688         ;; Setup the hash-vector if necessary.
 689         (when hash-vector
 690           (if (not eq-based)
 691               (setf (aref hash-vector free-kv-slot) hashing)
 692               (aver (= (aref hash-vector free-kv-slot)
 693                        +magic-hash-vector-value+))))
 694         ;; Push this slot into the next chain.
 695         (setf (aref next-vector free-kv-slot) next)
 696         (setf (aref index-vector index) free-kv-slot)))
 697     value))
 698
 699 (defun %puthash (key hash-table value)
 700   (declare (type hash-table hash-table))
 701   (aver (hash-table-index-vector hash-table))
 702   (let ((cache (hash-table-cache hash-table))
 703         (kv-vector (hash-table-table hash-table)))
 704     ;; Check the cache
 705     (if (and cache
 706              (< cache (length kv-vector))
 707              (eq (aref kv-vector cache) key))
 708         ;; If cached, just store here
 709         (setf (aref kv-vector (1+ cache)) value)
 710         ;; Otherwise do things the hard way
 711         (with-hash-table-locks (hash-table (%%puthash) key)
 712           (%%puthash key hash-table value)))))
 713
 714 (declaim (maybe-inline %remhash))
 715 (defun %remhash (key hash-table)
 716   ;; We need to rehash here so that a current key can be found if it
 717   ;; exists.
 718   ;;
 719   ;; Note that if a GC happens after MAYBE-REHASH returns and another
 720   ;; thread the accesses the table (triggering a rehash), we might not
 721   ;; find the key even if it is in the table. But that's ok, since the
 722   ;; only concurrent case that we safely allow is multiple readers
 723   ;; with no writers.
 724   (maybe-rehash hash-table nil)
 725   ;; Search for key in the hash table.
 726   (multiple-value-bind (hashing eq-based)
 727       (funcall (hash-table-hash-fun hash-table) key)
 728     (declare (type hash hashing))
 729     (let* ((index-vector (hash-table-index-vector hash-table))
 730            (length (length index-vector))
 731            (index (index-for-hashing hashing length))
 732            (next (aref index-vector index))
 733            (table (hash-table-table hash-table))
 734            (next-vector (hash-table-next-vector hash-table))
 735            (hash-vector (hash-table-hash-vector hash-table))
 736            (test-fun (hash-table-test-fun hash-table)))
 737       (declare (type index index)
 738                (type index/2 next))
 739       (flet ((clear-slot (chain-vector prior-slot-location slot-location)
 740                (declare (type index/2 slot-location))
 741                ;; Mark slot as empty.
 742                (setf (aref table (* 2 slot-location)) +empty-ht-slot+
 743                      (aref table (1+ (* 2 slot-location))) +empty-ht-slot+)
 744                ;; Update the prior pointer in the chain to skip this.
 745                (setf (aref chain-vector prior-slot-location)
 746                      (aref next-vector slot-location))
 747                ;; Push KV slot onto free chain.
 748                (setf (aref next-vector slot-location)
 749                      (hash-table-next-free-kv hash-table))
 750                (setf (hash-table-next-free-kv hash-table) slot-location)
 751                (when hash-vector
 752                  (setf (aref hash-vector slot-location)
 753                        +magic-hash-vector-value+))
 754                (decf (hash-table-number-entries hash-table))
 755                t))
 756         (cond ((zerop next)
 757                nil)
 758               ((if (or eq-based (not hash-vector))
 759                    (eq key (aref table (* 2 next)))
 760                    (and (= hashing (aref hash-vector next))
 761                         (funcall test-fun key (aref table (* 2 next)))))
 762                (clear-slot index-vector index next))
 763               ;; Search next-vector chain for a matching key.
 764               ((or eq-based (not hash-vector))
 765                ;; EQ based
 766                (do ((prior next next)
 767                     (i 0 (1+ i))
 768                     (next (aref next-vector next) (aref next-vector next)))
 769                    ((zerop next) nil)
 770                  (declare (type index next))
 771                  (when (> i length)
 772                    (signal-corrupt-hash-table hash-table))
 773                  (when (eq key (aref table (* 2 next)))
 774                    (return-from %remhash (clear-slot next-vector prior next)))))
 775               (t
 776                ;; not EQ based
 777                (do ((prior next next)
 778                     (i 0 (1+ i))
 779                     (next (aref next-vector next) (aref next-vector next)))
 780                    ((zerop next) nil)
 781                  (declare (type index/2 next))
 782                  (when (> i length)
 783                    (signal-corrupt-hash-table hash-table))
 784                  (when (and (= hashing (aref hash-vector next))
 785                             (funcall test-fun key (aref table (* 2 next))))
 786                    (return-from %remhash
 787                      (clear-slot next-vector prior next))))))))))
 788
 789 (defun remhash (key hash-table)
 790   #!+sb-doc
 791   "Remove the entry in HASH-TABLE associated with KEY. Return T if there
 792    was such an entry, or NIL if not."
 793   (declare (type hash-table hash-table)
 794            (values (member t nil)))
 795   ;; For now, just clear the cache
 796   (setf (hash-table-cache hash-table) nil)
 797   (with-hash-table-locks (hash-table (%remhash) key)
 798     (%remhash key hash-table)))
 799
 800 (defun clrhash (hash-table)
 801   #!+sb-doc
 802   "This removes all the entries from HASH-TABLE and returns the hash table
 803    itself."
 804   (with-hash-table-locks (hash-table nil)
 805     (let* ((kv-vector (hash-table-table hash-table))
 806            (next-vector (hash-table-next-vector hash-table))
 807            (hash-vector (hash-table-hash-vector hash-table))
 808            (size (length next-vector))
 809            (index-vector (hash-table-index-vector hash-table)))
 810       ;; Disable GC tricks.
 811       (set-header-data kv-vector sb!vm:vector-normal-subtype)
 812       ;; Mark all slots as empty by setting all keys and values to magic
 813       ;; tag.
 814       (aver (eq (aref kv-vector 0) hash-table))
 815       (fill kv-vector +empty-ht-slot+ :start 2)
 816       ;; Set up the free list, all free.
 817       (do ((i 1 (1+ i)))
 818           ((>= i (1- size)))
 819         (setf (aref next-vector i) (1+ i)))
 820       (setf (aref next-vector (1- size)) 0)
 821       (setf (hash-table-next-free-kv hash-table) 1)
 822       ;; Clear the index-vector.
 823       (fill index-vector 0)
 824       ;; Clear the hash-vector.
 825       (when hash-vector
 826         (fill hash-vector +magic-hash-vector-value+)))
 827     (setf (hash-table-cache hash-table) nil)
 828     (setf (hash-table-number-entries hash-table) 0)
 829     hash-table))
 830
 831 \f
 832 ;;;; MAPHASH
 833
 834 ;;; FIXME: This should be made into a compiler transform for two reasons:
 835 ;;;   1. It would then be available for compiling the entire system,
 836 ;;;      not only parts of the system which are defined after DEFUN MAPHASH.
 837 ;;;   2. It could be conditional on compilation policy, so that
 838 ;;;      it could be compiled as a full call instead of an inline
 839 ;;;      expansion when SPACE>SPEED.
 840 (declaim (inline maphash))
 841 (defun maphash (function-designator hash-table)
 842   #!+sb-doc
 843   "For each entry in HASH-TABLE, call the designated two-argument
 844 function on the key and value of the entry. Return NIL.
 845
 846 Consequences are undefined if HASH-TABLE is mutated during the call to
 847 MAPHASH, except for changing or removing elements corresponding to the
 848 current key."
 849   ;; This essentially duplicates WITH-HASH-TABLE-ITERATOR, so
 850   ;; any changes here should be reflected there as well.
 851   (let ((fun (%coerce-callable-to-fun function-designator))
 852         (size (length (hash-table-next-vector hash-table))))
 853     (declare (type function fun))
 854     (do ((i 1 (1+ i)))
 855         ((>= i size))
 856       (declare (type index/2 i))
 857       (let* ((kv-vector (hash-table-table hash-table))
 858              (key (aref kv-vector (* 2 i)))
 859              (value (aref kv-vector (1+ (* 2 i)))))
 860         ;; We are running without locking or WITHOUT-GCING. For a weak
 861         ;; :VALUE hash table it's possible that the GC hit after KEY
 862         ;; was read and now the entry is gone. So check if either the
 863         ;; key or the value is empty.
 864         (unless (or (eq key +empty-ht-slot+)
 865                     (eq value +empty-ht-slot+))
 866           (funcall fun key value))))))
 867 \f
 868 ;;;; methods on HASH-TABLE
 869
 870 ;;; Return a list of keyword args and values to use for MAKE-HASH-TABLE
 871 ;;; when reconstructing HASH-TABLE.
 872 (defun %hash-table-ctor-args (hash-table)
 873   `(:test             ',(hash-table-test             hash-table)
 874     :size             ',(hash-table-size             hash-table)
 875     :rehash-size      ',(hash-table-rehash-size      hash-table)
 876     :rehash-threshold ',(hash-table-rehash-threshold hash-table)
 877     :weakness         ',(hash-table-weakness         hash-table)))
 878
 879 ;;; Return an association list representing the same data as HASH-TABLE.
 880 (defun %hash-table-alist (hash-table)
 881   (let ((result nil))
 882     (maphash (lambda (key value)
 883                (push (cons key value) result))
 884              hash-table)
 885     result))
 886
 887 ;;; Stuff an association list into HASH-TABLE. Return the hash table,
 888 ;;; so that we can use this for the *PRINT-READABLY* case in
 889 ;;; PRINT-OBJECT (HASH-TABLE T) without having to worry about LET
 890 ;;; forms and readable gensyms and stuff.
 891 (defun %stuff-hash-table (hash-table alist)
 892   (dolist (x alist)
 893     (setf (gethash (car x) hash-table) (cdr x)))
 894   hash-table)
 895
 896 (def!method print-object ((hash-table hash-table) stream)
 897   (declare (type stream stream))
 898   (cond ((or (not *print-readably*) (not *read-eval*))
 899          (print-unreadable-object (hash-table stream :type t :identity t)
 900            (format stream
 901                    ":TEST ~S :COUNT ~S"
 902                    (hash-table-test hash-table)
 903                    (hash-table-count hash-table))))
 904         (t
 905          (with-standard-io-syntax
 906           (format stream
 907                   "#.~W"
 908                   `(%stuff-hash-table (make-hash-table ,@(%hash-table-ctor-args
 909                                                           hash-table))
 910                                      ',(%hash-table-alist hash-table)))))))
 911
 912 (def!method make-load-form ((hash-table hash-table) &optional environment)
 913   (declare (ignore environment))
 914   (values `(make-hash-table ,@(%hash-table-ctor-args hash-table))
 915           `(%stuff-hash-table ,hash-table ',(%hash-table-alist hash-table))))
 916
 917 \f