- (values t (member t nil)))
- (without-gcing
- (cond ((= (get-header-data (hash-table-table hash-table))
- sb!vm:vector-must-rehash-subtype)
- (rehash-without-growing hash-table))
- ((not (zerop (hash-table-needing-rehash hash-table)))
- (flush-needing-rehash hash-table)))
- ;; Search for key in the hash table.
- (multiple-value-bind (hashing eq-based)
- (funcall (hash-table-hash-fun hash-table) key)
- (declare (type hash hashing))
- (let* ((index-vector (hash-table-index-vector hash-table))
- (length (length index-vector))
- (index (rem hashing length))
- (next (aref index-vector index))
- (table (hash-table-table hash-table))
- (next-vector (hash-table-next-vector hash-table))
- (hash-vector (hash-table-hash-vector hash-table))
- (test-fun (hash-table-test-fun hash-table)))
- (declare (type index index))
- ;; Search next-vector chain for a matching key.
- (if (or eq-based (not hash-vector))
- (do ((next next (aref next-vector next)))
- ((zerop next) (values default nil))
- (declare (type index next))
- (when (eq key (aref table (* 2 next)))
- (return (values (aref table (1+ (* 2 next))) t))))
- (do ((next next (aref next-vector next)))
- ((zerop next) (values default nil))
- (declare (type index next))
- (when (and (= hashing (aref hash-vector next))
- (funcall test-fun key (aref table (* 2 next))))
- ;; Found.
- (return (values (aref table (1+ (* 2 next))) t)))))))))
+ (values t (member t nil)))
+ (gethash3 key hash-table default))
+
+(declaim (maybe-inline %gethash3))
+(defun %gethash3 (key hash-table default)
+ (declare (type hash-table hash-table)
+ (optimize speed)
+ (values t (member t nil)))
+ (tagbody
+ start
+ (let ((start-epoch sb!kernel::*gc-epoch*))
+ (macrolet ((result (value foundp)
+ ;; When the table has multiple concurrent readers,
+ ;; it's possible that there was a GC after this
+ ;; thread called MAYBE-REHASH from %GETHASH3, and
+ ;; some other thread then rehashed the table. If
+ ;; this happens, we might not find the key even if
+ ;; it's in the table. To protect against this,
+ ;; 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*)))
+ (go start)
+ (return-from %gethash3 (values ,value ,foundp))))
+ (overflow ()
+ ;; The next-vector chain is circular. This is caused
+ ;; caused by thread-unsafe mutations of the table.
+ `(signal-corrupt-hash-table hash-table)))
+ (maybe-rehash hash-table nil)
+ ;; Note that it's OK for a GC + a REHASH-WITHOUT-GROWING to
+ ;; be triggered by another thread after this point, since the
+ ;; GC epoch check will catch it.
+ (let ((cache (hash-table-cache hash-table))
+ (table (hash-table-table hash-table)))
+ ;; First check the cache. Use EQ here for speed.
+ (if (and cache
+ (< cache (length table))
+ (eq (aref table cache) key))
+ (let ((value (aref table (1+ cache))))
+ (result value t))
+ ;; Search for key in the hash table.
+ (multiple-value-bind (hashing eq-based)
+ (funcall (hash-table-hash-fun hash-table) key)
+ (declare (type hash hashing))
+ (let* ((index-vector (hash-table-index-vector hash-table))
+ (length (length index-vector))
+ (index (index-for-hashing hashing length))
+ (next (aref index-vector index))
+ (next-vector (hash-table-next-vector hash-table))
+ (hash-vector (hash-table-hash-vector hash-table))
+ (test-fun (hash-table-test-fun hash-table)))
+ (declare (type index index))
+ ;; Search next-vector chain for a matching key.
+ (if (or eq-based (not hash-vector))
+ (do ((next next (aref next-vector next))
+ (i 0 (1+ i)))
+ ((zerop next) (result default nil))
+ (declare (type index/2 next i))
+ (when (> i length)
+ (overflow))
+ (when (eq key (aref table (* 2 next)))
+ (update-hash-table-cache hash-table (* 2 next))
+ (let ((value (aref table (1+ (* 2 next)))))
+ (result value t))))
+ (do ((next next (aref next-vector next))
+ (i 0 (1+ i)))
+ ((zerop next) (result default nil))
+ (declare (type index/2 next i))
+ (when (> i length)
+ (overflow))
+ (when (and (= hashing (aref hash-vector next))
+ (funcall test-fun key
+ (aref table (* 2 next))))
+ ;; Found.
+ (update-hash-table-cache hash-table (* 2 next))
+ (let ((value (aref table (1+ (* 2 next)))))
+ (result value t)))))))))))))
+
+(defun gethash3 (key hash-table default)
+ "Three argument version of GETHASH"
+ (declare (type hash-table hash-table))
+ (with-hash-table-locks (hash-table (%gethash3) key)
+ (%gethash3 key hash-table default)))