\f
;;;; utilities
-(eval-when (:compile-toplevel :load-toplevel :execute)
- (defconstant max-hash sb!xc:most-positive-fixnum))
-
;;; Code for detecting concurrent accesses to the same table from
;;; multiple threads. Only compiled in when the :SB-HASH-TABLE-DEBUG
;;; feature is enabled. The main reason for the existence of this code
(setf (,thread-slot-accessor ,hash-table) nil)))
(body-fun)))))))
-(deftype hash ()
- `(integer 0 ,max-hash))
-
-;;; FIXME: Does this always make a nonnegative FIXNUM? If so, then
-;;; explain why. If not (or if the reason it always makes a
-;;; nonnegative FIXNUM is only the accident that pointers in supported
-;;; architectures happen to be in the lower half of the address
-;;; space), then fix it.
-#!-sb-fluid (declaim (inline pointer-hash))
-(defun pointer-hash (key)
- (declare (values hash))
- (truly-the hash (%primitive sb!c:make-fixnum key)))
-
#!-sb-fluid (declaim (inline eq-hash))
(defun eq-hash (key)
(declare (values hash (member t nil)))
(t
(eq-hash key))))
-(defun ceil-power-of-two (num)
- (declare (type index num))
- (ash 1 (integer-length num)))
-
(declaim (inline index-for-hashing))
-(defun index-for-hashing (index length)
- (declare (type index index length))
+(defun index-for-hashing (hash length)
+ (declare (type hash hash length))
;; We're using power of two tables which obviously are very
;; sensitive to the exact values of the low bits in the hash
;; value. Do a little shuffling of the value to mix the high bits in
;; there too.
- (logand (1- length)
- (+ (logxor #b11100101010001011010100111
- index)
- (ash index -6)
- (ash index -15)
- (ash index -23))))
+ (truly-the index
+ (logand (1- length)
+ (+ (logxor #b11100101010001011010100111
+ hash)
+ (ash hash -3)
+ (ash hash -12)
+ (ash hash -20)))))
\f
;;;; user-defined hash table tests
-(defvar *hash-table-tests* nil)
+(defvar *user-hash-table-tests* nil)
-(defun define-hash-table-test (name test-fun hash-fun)
- #!+sb-doc
- "Define a new kind of hash table test."
- (declare (type symbol name)
- (type function test-fun hash-fun))
- (setf *hash-table-tests*
- (cons (list name test-fun hash-fun)
- (remove name *hash-table-tests* :test #'eq :key #'car)))
+(defun register-hash-table-test (name hash-fun)
+ (declare (symbol name) (function hash-fun))
+ (unless (fboundp name)
+ (error "Cannot register ~S has a hash table test: undefined function."
+ name))
+ (with-single-package-locked-error
+ (:symbol name "defining ~S as a hash table test")
+ (let* ((test-fun (fdefinition name))
+ (this (list name test-fun hash-fun))
+ (spec (assoc name *user-hash-table-tests*)))
+ (cond (spec
+ (unless (and (eq (second spec) test-fun)
+ (eq (third spec) hash-fun))
+ (style-warn "Redefining hash table test ~S." name)
+ (setf (cdr spec) (cdr this))))
+ (t
+ (push this *user-hash-table-tests*)))))
name)
+
+(defmacro define-hash-table-test (name hash-function)
+ #!+sb-doc
+ "Defines NAME as a new kind of hash table test for use with the :TEST
+argument to MAKE-HASH-TABLE, and associates a default HASH-FUNCTION with it.
+
+NAME must be a symbol naming a global two argument equivalence predicate.
+Afterwards both 'NAME and #'NAME can be used with :TEST argument. In both
+cases HASH-TABLE-TEST will return the symbol NAME.
+
+HASH-FUNCTION must be a symbol naming a global hash function consistent with
+the predicate, or be a LAMBDA form implementing one in the current lexical
+environment. The hash function must compute the same hash code for any two
+objects for which NAME returns true, and subsequent calls with already hashed
+objects must always return the same hash code.
+
+Note: The :HASH-FUNCTION keyword argument to MAKE-HASH-TABLE can be used to
+override the specified default hash-function.
+
+Attempting to define NAME in a locked package as hash-table test causes a
+package lock violation.
+
+Examples:
+
+ ;;; 1.
+
+ ;; We want to use objects of type FOO as keys (by their
+ ;; names.) EQUALP would work, but would make the names
+ ;; case-insensitive -- which we don't want.
+ (defstruct foo (name nil :type (or null string)))
+
+ ;; Define an equivalence test function and a hash function.
+ (defun foo-name= (f1 f2) (equal (foo-name f1) (foo-name f2)))
+ (defun sxhash-foo-name (f) (sxhash (foo-name f)))
+
+ (define-hash-table-test foo-name= sxhash-foo-name)
+
+ ;; #'foo-name would work too.
+ (defun make-foo-table () (make-hash-table :test 'foo-name=))
+
+ ;;; 2.
+
+ (defun == (x y) (= x y))
+
+ (define-hash-table-test ==
+ (lambda (x)
+ ;; Hash codes must be consistent with test, so
+ ;; not (SXHASH X), since
+ ;; (= 1 1.0) => T
+ ;; (= (SXHASH 1) (SXHASH 1.0)) => NIL
+ ;; Note: this doesn't deal with complex numbers or
+ ;; bignums too large to represent as double floats.
+ (sxhash (coerce x 'double-float))))
+
+ ;; #'== would work too
+ (defun make-number-table () (make-hash-table :test '==))
+"
+ (check-type name symbol)
+ (if (member name '(eq eql equal equalp))
+ (error "Cannot redefine standard hash table test ~S." name)
+ (cond ((symbolp hash-function)
+ `(register-hash-table-test ',name (symbol-function ',hash-function)))
+ ((and (consp hash-function) (eq 'lambda (car hash-function)))
+ `(register-hash-table-test ',name #',hash-function))
+ (t
+ (error "Malformed HASH-FUNCTION: ~S" hash-function)))))
\f
;;;; construction and simple accessors
(defconstant +min-hash-table-size+ 16)
(defconstant +min-hash-table-rehash-threshold+ (float 1/16 1.0))
-(defun make-hash-table (&key (test 'eql)
+(defun make-hash-table (&key
+ (test 'eql)
(size +min-hash-table-size+)
(rehash-size 1.5)
(rehash-threshold 1)
+ (hash-function nil)
(weakness nil)
(synchronized))
#!+sb-doc
"Create and return a new hash table. The keywords are as follows:
- :TEST -- Indicates what kind of test to use.
- :SIZE -- A hint as to how many elements will be put in this hash
- table.
- :REHASH-SIZE -- Indicates how to expand the table when it fills up.
- If an integer, add space for that many elements. If a floating
- point number (which must be greater than 1.0), multiply the size
- by that amount.
- :REHASH-THRESHOLD -- Indicates how dense the table can become before
- forcing a rehash. Can be any positive number <=1, with density
- approaching zero as the threshold approaches 0. Density 1 means an
- average of one entry per bucket.
- :WEAKNESS -- If NIL (the default) it is a normal non-weak hash table.
- If one of :KEY, :VALUE, :KEY-AND-VALUE, :KEY-OR-VALUE it is a weak
- hash table.
- Depending on the type of weakness the lack of references to the
- key and the value may allow for removal of the entry. If WEAKNESS
- is :KEY and the key would otherwise be garbage the entry is eligible
- for removal from the hash table. Similarly, if WEAKNESS is :VALUE
- the life of an entry depends on its value's references. If WEAKNESS
- is :KEY-AND-VALUE and either the key or the value would otherwise be
- garbage the entry can be removed. If WEAKNESS is :KEY-OR-VALUE and
- both the key and the value would otherwise be garbage the entry can
- be removed.
- :SYNCHRONIZED -- If NIL (the default), the hash-table may have
- multiple concurrent readers, but results are undefined if a
- thread writes to the hash-table concurrently with another
- reader or writer. If T, all concurrent accesses are safe, but
- note that CLHS 3.6 (Traversal Rules and Side Effects) remains
- in force. See also: SB-EXT:WITH-LOCKED-HASH-TABLE. This keyword
- argument is experimental, and may change incompatibly or be
- removed in the future."
+
+ :TEST
+ Determines how keys are compared. Must a designator for one of the
+ standard hash table tests, or a hash table test defined using
+ SB-EXT:DEFINE-HASH-TABLE-TEST. Additionally, when an explicit
+ HASH-FUNCTION is provided (see below), any two argument equivalence
+ predicate can be used as the TEST.
+
+ :SIZE
+ A hint as to how many elements will be put in this hash table.
+
+ :REHASH-SIZE
+ Indicates how to expand the table when it fills up. If an integer, add
+ space for that many elements. If a floating point number (which must be
+ greater than 1.0), multiply the size by that amount.
+
+ :REHASH-THRESHOLD
+ Indicates how dense the table can become before forcing a rehash. Can be
+ any positive number <=1, with density approaching zero as the threshold
+ approaches 0. Density 1 means an average of one entry per bucket.
+
+ :HASH-FUNCTION
+ If NIL (the default), a hash function based on the TEST argument is used,
+ which then must be one of the standardized hash table test functions, or
+ one for which a default hash function has been defined using
+ SB-EXT:DEFINE-HASH-TABLE-TEST. If HASH-FUNCTION is specified, the TEST
+ argument can be any two argument predicate consistent with it. The
+ HASH-FUNCTION is expected to return a non-negative fixnum hash code.
+
+ :WEAKNESS
+ When :WEAKNESS is not NIL, garbage collection may remove entries from the
+ hash table. The value of :WEAKNESS specifies how the presence of a key or
+ value in the hash table preserves their entries from garbage collection.
+
+ Valid values are:
+
+ :KEY means that the key of an entry must be live to guarantee that the
+ entry is preserved.
+
+ :VALUE means that the value of an entry must be live to guarantee that
+ the entry is preserved.
+
+ :KEY-AND-VALUE means that both the key and the value must be live to
+ guarantee that the entry is preserved.
+
+ :KEY-OR-VALUE means that either the key or the value must be live to
+ guarantee that the entry is preserved.
+
+ NIL (the default) means that entries are always preserved.
+
+ :SYNCHRONIZED
+ If NIL (the default), the hash-table may have multiple concurrent readers,
+ but results are undefined if a thread writes to the hash-table
+ concurrently with another reader or writer. If T, all concurrent accesses
+ are safe, but note that CLHS 3.6 (Traversal Rules and Side Effects)
+ remains in force. See also: SB-EXT:WITH-LOCKED-HASH-TABLE. This keyword
+ argument is experimental, and may change incompatibly or be removed in the
+ future."
(declare (type (or function symbol) test))
(declare (type unsigned-byte size))
(multiple-value-bind (test test-fun hash-fun)
((or (eq test #'equalp) (eq test 'equalp))
(values 'equalp #'equalp #'equalp-hash))
(t
- ;; FIXME: I'd like to remove *HASH-TABLE-TESTS* stuff.
- ;; Failing that, I'd like to rename it to
- ;; *USER-HASH-TABLE-TESTS*.
- (dolist (info *hash-table-tests*
- (error "unknown :TEST for MAKE-HASH-TABLE: ~S"
- test))
+ ;; FIXME: It would be nice to have a compiler-macro
+ ;; that resolved this at compile time: we could grab
+ ;; the alist cell in a LOAD-TIME-VALUE, etc.
+ (dolist (info *user-hash-table-tests*
+ (if hash-function
+ (if (functionp test)
+ (values (%fun-name test) test nil)
+ (values test (%coerce-callable-to-fun test) nil))
+ (error "Unknown :TEST for MAKE-HASH-TABLE: ~S"
+ test)))
(destructuring-bind (test-name test-fun hash-fun) info
(when (or (eq test test-name) (eq test test-fun))
(return (values test-name test-fun hash-fun)))))))
+ (when hash-function
+ (setf hash-fun
+ ;; Quickly check if the function has return return type which
+ ;; guarantees that the secondary return value is always NIL:
+ ;; (VALUES * &OPTIONAL), (VALUES * NULL ...) or (VALUES *
+ ;; &OPTIONAL NULL ...)
+ (let* ((actual (%coerce-callable-to-fun hash-function))
+ (type-spec (%fun-type actual))
+ (return-spec (when (consp type-spec)
+ (caddr type-spec)))
+ (extra-vals (when (consp return-spec)
+ (cddr return-spec))))
+ (if (and (consp extra-vals)
+ (or (eq 'null (car extra-vals))
+ (and (eq '&optional (car extra-vals))
+ (or (not (cdr extra-vals))
+ (eq 'null (cadr extra-vals))))))
+ actual
+ ;; If there is a potential secondary value, make sure we
+ ;; don't accidentally claim EQ based hashing...
+ (lambda (object)
+ (declare (optimize (safety 0) (speed 3)))
+ (values (funcall actual object) nil))))))
(let* ((size (max +min-hash-table-size+
(min size
;; SIZE is just a hint, so if the user asks
;; Note that this has not yet been audited for
;; correctness. It just seems to work. -- CSR, 2002-11-02
(scaled-size (truncate (/ (float size+1) rehash-threshold)))
- (length (ceil-power-of-two (max scaled-size
- (1+ +min-hash-table-size+))))
+ (length (power-of-two-ceiling (max scaled-size
+ (1+ +min-hash-table-size+))))
(index-vector (make-array length
:element-type
'(unsigned-byte #.sb!vm:n-word-bits)
(setf (fdocumentation 'hash-table-rehash-threshold 'function)
"Return the rehash-threshold HASH-TABLE was created with.")
+#!+sb-doc
+(setf (fdocumentation 'hash-table-synchronized-p 'function)
+ "Returns T if HASH-TABLE is synchronized.")
+
(defun hash-table-size (hash-table)
#!+sb-doc
"Return a size that can be used with MAKE-HASH-TABLE to create a hash
(old-hash-vector (hash-table-hash-vector table))
(old-size (length old-next-vector))
(new-size
- (ceil-power-of-two
+ (power-of-two-ceiling
(let ((rehash-size (hash-table-rehash-size table)))
(etypecase rehash-size
(fixnum
(hash-table-needs-rehash-p hash-table)))
(declare (inline rehash-p rehash-without-growing-p))
(cond ((rehash-p)
- ;; Use recursive spinlocks since for weak tables the
- ;; spinlock has already been acquired. GC must be inhibited
- ;; to prevent the GC from seeing a rehash in progress.
- (sb!thread::with-recursive-system-spinlock
- ((hash-table-spinlock hash-table) :without-gcing t)
+ ;; Use recursive locks since for weak tables the lock has
+ ;; already been acquired. GC must be inhibited to prevent
+ ;; the GC from seeing a rehash in progress.
+ (sb!thread::with-recursive-system-lock
+ ((hash-table-lock hash-table) :without-gcing t)
;; Repeat the condition inside the lock to ensure that if
;; two reader threads enter MAYBE-REHASH at the same time
;; only one rehash is performed.
(when (rehash-p)
(rehash hash-table))))
((rehash-without-growing-p)
- (sb!thread::with-recursive-system-spinlock
- ((hash-table-spinlock hash-table) :without-gcing t)
+ (sb!thread::with-recursive-system-lock
+ ((hash-table-lock hash-table) :without-gcing t)
(when (rehash-without-growing-p)
(rehash-without-growing hash-table)))))))
&body body)
(declare (type (member :read :write) operation))
(with-unique-names (body-fun)
- `(with-concurrent-access-check ,hash-table ,operation
- (flet ((,body-fun ()
+ `(flet ((,body-fun ()
+ (with-concurrent-access-check ,hash-table ,operation
(locally (declare (inline ,@inline))
- ,@body)))
- (if (hash-table-weakness ,hash-table)
- (sb!thread::with-recursive-system-spinlock
- ((hash-table-spinlock ,hash-table) :without-gcing t)
- (,body-fun))
- (with-pinned-objects ,pin
- (if ,synchronized
- ;; We use a "system" spinlock here because it is very
- ;; slightly faster, as it doesn't re-enable interrupts.
- (sb!thread::with-recursive-system-spinlock
- ((hash-table-spinlock ,hash-table))
- (,body-fun))
- (,body-fun))))))))
+ ,@body))))
+ (if (hash-table-weakness ,hash-table)
+ (sb!thread::with-recursive-system-lock
+ ((hash-table-lock ,hash-table) :without-gcing t)
+ (,body-fun))
+ (with-pinned-objects ,pin
+ (if ,synchronized
+ ;; We use a "system" lock here because it is very
+ ;; slightly faster, as it doesn't re-enable
+ ;; interrupts.
+ (sb!thread::with-recursive-system-lock
+ ((hash-table-lock ,hash-table))
+ (,body-fun))
+ (,body-fun)))))))
(defun gethash (key hash-table &optional default)
#!+sb-doc
;; redo the lookup if the GC epoch counter has changed.
;; -- JES, 2007-09-30
`(if (and (not ,foundp)
- (not (eql start-epoch sb!kernel::*gc-epoch*)))
+ (not (eq start-epoch sb!kernel::*gc-epoch*)))
(go start)
(return-from %gethash3 (values ,value ,foundp))))
(overflow ()
(declare (type hash-table hash-table)
(values (member t nil)))
(with-hash-table-locks (hash-table :inline (%remhash) :pin (key))
- ;; For now, just clear the cache
- (setf (hash-table-cache hash-table) nil)
+ ;; For now, just clear the cache
+ (setf (hash-table-cache hash-table) nil)
(%remhash key hash-table)))
(defun clrhash (hash-table)
#!+sb-doc
"This removes all the entries from HASH-TABLE and returns the hash
table itself."
- (with-hash-table-locks (hash-table)
- (let* ((kv-vector (hash-table-table hash-table))
- (next-vector (hash-table-next-vector hash-table))
- (hash-vector (hash-table-hash-vector hash-table))
- (size (length next-vector))
- (index-vector (hash-table-index-vector hash-table)))
- ;; Disable GC tricks.
- (set-header-data kv-vector sb!vm:vector-normal-subtype)
- ;; Mark all slots as empty by setting all keys and values to magic
- ;; tag.
- (aver (eq (aref kv-vector 0) hash-table))
- (fill kv-vector +empty-ht-slot+ :start 2)
- ;; Set up the free list, all free.
- (do ((i 1 (1+ i)))
- ((>= i (1- size)))
- (setf (aref next-vector i) (1+ i)))
- (setf (aref next-vector (1- size)) 0)
- (setf (hash-table-next-free-kv hash-table) 1)
- ;; Clear the index-vector.
- (fill index-vector 0)
- ;; Clear the hash-vector.
- (when hash-vector
- (fill hash-vector +magic-hash-vector-value+)))
- (setf (hash-table-cache hash-table) nil)
- (setf (hash-table-number-entries hash-table) 0)
- hash-table))
+ (when (plusp (hash-table-number-entries hash-table))
+ (with-hash-table-locks (hash-table)
+ (let* ((kv-vector (hash-table-table hash-table))
+ (next-vector (hash-table-next-vector hash-table))
+ (hash-vector (hash-table-hash-vector hash-table))
+ (size (length next-vector))
+ (index-vector (hash-table-index-vector hash-table)))
+ ;; Disable GC tricks.
+ (set-header-data kv-vector sb!vm:vector-normal-subtype)
+ ;; Mark all slots as empty by setting all keys and values to magic
+ ;; tag.
+ (aver (eq (aref kv-vector 0) hash-table))
+ (fill kv-vector +empty-ht-slot+ :start 2)
+ ;; Set up the free list, all free.
+ (do ((i 1 (1+ i)))
+ ((>= i (1- size)))
+ (setf (aref next-vector i) (1+ i)))
+ (setf (aref next-vector (1- size)) 0)
+ (setf (hash-table-next-free-kv hash-table) 1)
+ ;; Clear the index-vector.
+ (fill index-vector 0)
+ ;; Clear the hash-vector.
+ (when hash-vector
+ (fill hash-vector +magic-hash-vector-value+)))
+ (setf (hash-table-cache hash-table) nil)
+ (setf (hash-table-number-entries hash-table) 0)))
+ hash-table)
\f
;;;; MAPHASH
projects / sbcl.git / blobdiff