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