src/code/hash-table.lisp

   1 ;;;; the needed-on-the-cross-compilation-host part of HASH-TABLE
   2 ;;;; implementation
   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
  15 ;;; HASH-TABLE is implemented as a STRUCTURE-OBJECT.
  16 (sb!xc:defstruct (hash-table (:copier nil)
  17                              (:constructor %make-hash-table
  18                                (test
  19                                 test-fun
  20                                 hash-fun
  21                                 rehash-size
  22                                 rehash-threshold
  23                                 rehash-trigger
  24                                 table
  25                                 weakness
  26                                 index-vector
  27                                 next-vector
  28                                 hash-vector
  29                                 synchronized-p)))
  30   ;; The type of hash table this is. Only used for printing and as
  31   ;; part of the exported interface.
  32   (test nil :type symbol :read-only t)
  33   ;; The function used to compare two keys. Returns T if they are the
  34   ;; same and NIL if not.
  35   (test-fun nil :type function :read-only t)
  36   ;; The function used to compute the hashing of a key. Returns two
  37   ;; values: the index hashing and T if that might change with the
  38   ;; next GC.
  39   (hash-fun nil :type function :read-only t)
  40   ;; How much to grow the hash table by when it fills up. If an index,
  41   ;; then add that amount. If a floating point number, then multiply
  42   ;; it by that.
  43   (rehash-size nil :type (or index (single-float (1.0)))
  44                :read-only t)
  45   ;; How full the hash table has to get before we rehash
  46   (rehash-threshold nil :type (single-float (0.0) 1.0) :read-only t)
  47   ;; The number of entries before a rehash, just one less than the
  48   ;; size of the next-vector, hash-vector, and half the size of the
  49   ;; kv-vector.
  50   (rehash-trigger nil :type index)
  51   ;; The current number of entries in the table.
  52   (number-entries 0 :type index)
  53   ;; The Key-Value pair vector.
  54   (table nil :type simple-vector)
  55   ;; This slot is used to link weak hash tables during GC. When the GC
  56   ;; isn't running it is always NIL.
  57   (next-weak-hash-table nil :type null)
  58   ;; Non-NIL if this is some kind of weak hash table. For details see
  59   ;; the docstring of MAKE-HASH-TABLE.
  60   (weakness nil :type (member nil :key :value :key-or-value :key-and-value)
  61             :read-only t)
  62   ;; Index into the Next vector chaining together free slots in the KV
  63   ;; vector.
  64   (next-free-kv 0 :type index)
  65   ;; A cache that is either nil or is an index into the hash table
  66   ;; that should be checked first
  67   (cache nil :type (or null index))
  68   ;; The index vector. This may be larger than the hash size to help
  69   ;; reduce collisions.
  70   (index-vector nil :type (simple-array sb!vm:word (*)))
  71   ;; This table parallels the KV vector, and is used to chain together
  72   ;; the hash buckets and the free list. A slot will only ever be in
  73   ;; one of these lists.
  74   (next-vector nil :type (simple-array sb!vm:word (*)))
  75   ;; This table parallels the KV table, and can be used to store the
  76   ;; hash associated with the key, saving recalculation. Could be
  77   ;; useful for EQL, and EQUAL hash tables. This table is not needed
  78   ;; for EQ hash tables, and when present the value of
  79   ;; +MAGIC-HASH-VECTOR-VALUE+ represents EQ-based hashing on the
  80   ;; respective key.
  81   (hash-vector nil :type (or null (simple-array sb!vm:word (*))))
  82   ;; Used for locking GETHASH/(SETF GETHASH)/REMHASH
  83   (lock (sb!thread:make-mutex :name "hash-table lock")
  84         :type sb!thread:mutex :read-only t)
  85   ;; The GC will set this to T if it moves an EQ-based key. This used
  86   ;; to be signaled by a bit in the header of the kv vector, but that
  87   ;; implementation caused some concurrency issues when we stopped
  88   ;; inhibiting GC during hash-table lookup.
  89   (needs-rehash-p nil :type (member nil t))
  90   ;; Has user requested synchronization?
  91   (synchronized-p nil :type (member nil t) :read-only t)
  92   ;; For detecting concurrent accesses.
  93   #!+sb-hash-table-debug
  94   (signal-concurrent-access t :type (member nil t))
  95   #!+sb-hash-table-debug
  96   (reading-thread nil)
  97   #!+sb-hash-table-debug
  98   (writing-thread nil))
  99
 100 ;; as explained by pmai on openprojects #lisp IRC 2002-07-30: #x80000000
 101 ;; is bigger than any possible nonEQ hash value, and thus indicates an
 102 ;; empty slot; and EQ hash tables don't use HASH-TABLE-HASH-VECTOR.
 103 ;; The previous sentence was written when SBCL was 32-bit only. The value
 104 ;; now depends on the word size. It is propagated to C in genesis because
 105 ;; the generational garbage collector needs to know it.
 106 (defconstant +magic-hash-vector-value+ (ash 1 (1- sb!vm:n-word-bits)))
 107
 108 (defmacro-mundanely with-locked-hash-table ((hash-table) &body body)
 109   #!+sb-doc
 110   "Limits concurrent accesses to HASH-TABLE for the duration of BODY.
 111 If HASH-TABLE is synchronized, BODY will execute with exclusive
 112 ownership of the table. If HASH-TABLE is not synchronized, BODY will
 113 execute with other WITH-LOCKED-HASH-TABLE bodies excluded -- exclusion
 114 of hash-table accesses not surrounded by WITH-LOCKED-HASH-TABLE is
 115 unspecified."
 116   ;; Needless to say, this also excludes some internal bits, but
 117   ;; getting there is too much detail when "unspecified" says what
 118   ;; is important -- unpredictable, but harmless.
 119   `(sb!thread::with-recursive-lock ((hash-table-lock ,hash-table))
 120      ,@body))
 121
 122 (defmacro-mundanely with-locked-system-table ((hash-table) &body body)
 123   `(sb!thread::with-recursive-system-lock
 124        ((hash-table-lock ,hash-table))
 125      ,@body))
 126
 127 ;;; Return an association list representing the same data as HASH-TABLE.
 128 (defun %hash-table-alist (hash-table)
 129   (let ((result nil))
 130     (maphash (lambda (key value)
 131                (push (cons key value) result))
 132              hash-table)
 133     result))