X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Ftarget-hash-table.lisp;h=b98c33d4240ad5f93b2d24fbc919799bcd6f8360;hb=34664ac9b1d27f0dff2514c388cf10813a9b1108;hp=5adefc9a6a18a7b672146a45fb36d647c5dfcde3;hpb=4898ef32c639b1c7f4ee13a5ba566ce6debd03e6;p=sbcl.git

diff --git a/src/code/target-hash-table.lisp b/src/code/target-hash-table.lisp
index 5adefc9..b98c33d 100644
--- a/src/code/target-hash-table.lisp
+++ b/src/code/target-hash-table.lisp
@@ -82,10 +82,6 @@
 
 (defconstant +min-hash-table-size+ 16)
 (defconstant +min-hash-table-rehash-threshold+ (float 1/16 1.0))
-;; as explained by pmai on openprojects #lisp IRC 2002-07-30: #x80000000
-;; is bigger than any possible nonEQ hash value, and thus indicates an
-;; empty slot; and EQ hash tables don't use HASH-TABLE-HASH-VECTOR
-(defconstant +magic-hash-vector-value+ #x80000000)
 
 (defun make-hash-table (&key (test 'eql)
                              (size +min-hash-table-size+)
@@ -412,39 +408,62 @@
    such entry. Entries can be added using SETF."
   (declare (type hash-table hash-table)
            (values t (member t nil)))
+  (gethash3 key hash-table default))
+
+(defun gethash2 (key hash-table)
+  #!+sb-doc
+  "Two argument version of GETHASH"
+  (declare (type hash-table hash-table)
+           (values t (member t nil)))
+  (gethash3 key hash-table nil))
+
+(defun gethash3 (key hash-table default)
+  #!+sb-doc
+  "Three argument version of GETHASH"
+  (declare (type hash-table hash-table)
+           (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)))))))))
+
+   ;; First check the cache.  Use EQ here for speed.
+   (let ((cache (hash-table-cache hash-table))
+         (table (hash-table-table hash-table)))
+
+     (if (and cache (< cache (length table)) (eq (aref table cache) key))
+         (values (aref table (1+ cache)) 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 (rem 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)))
+                   ((zerop next) (values default nil))
+                 (declare (type index next))
+                 (when (eq key (aref table (* 2 next)))
+                   (setf (hash-table-cache hash-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.
+                 (setf (hash-table-cache hash-table) (* 2 next))
+                 (return (values (aref table (1+ (* 2 next))) t)))))))))))
 
 ;;; so people can call #'(SETF GETHASH)
 (defun (setf gethash) (new-value key table &optional default)
@@ -466,64 +485,75 @@
          ((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))
-            (kv-vector (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))
-
-       (cond ((or eq-based (not hash-vector))
-              (when eq-based
-                (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype))
-
-              ;; Search next-vector chain for a matching key.
-              (do ((next next (aref next-vector next)))
-                  ((zerop next))
-                (declare (type index next))
-                (when (eq key (aref kv-vector (* 2 next)))
-                  ;; Found, just replace the value.
-                  (setf (aref kv-vector (1+ (* 2 next))) value)
-                  (return-from %puthash value))))
-             (t
-              ;; Search next-vector chain for a matching key.
-              (do ((next next (aref next-vector next)))
-                  ((zerop next))
-                (declare (type index next))
-                (when (and (= hashing (aref hash-vector next))
-                           (funcall test-fun key
-                                    (aref kv-vector (* 2 next))))
-                  ;; Found, just replace the value.
-                  (setf (aref kv-vector (1+ (* 2 next))) value)
-                  (return-from %puthash value)))))
-
-       ;; Pop a KV slot off the free list
-       (let ((free-kv-slot (hash-table-next-free-kv hash-table)))
-         ;; Double-check for overflow.
-         (aver (not (zerop free-kv-slot)))
-         (setf (hash-table-next-free-kv hash-table)
-               (aref next-vector free-kv-slot))
-         (incf (hash-table-number-entries hash-table))
-
-         (setf (aref kv-vector (* 2 free-kv-slot)) key)
-         (setf (aref kv-vector (1+ (* 2 free-kv-slot))) value)
-
-         ;; Setup the hash-vector if necessary.
-         (when hash-vector
-           (if (not eq-based)
-               (setf (aref hash-vector free-kv-slot) hashing)
-               (aver (= (aref hash-vector free-kv-slot) +magic-hash-vector-value+))))
-
-         ;; Push this slot into the next chain.
-         (setf (aref next-vector free-kv-slot) next)
-         (setf (aref index-vector index) free-kv-slot)))))
+   (let ((cache (hash-table-cache hash-table))
+         (kv-vector (hash-table-table hash-table)))
+
+     ;; Check the cache
+     (if (and cache (< cache (length kv-vector)) (eq (aref kv-vector cache) key))
+         ;; If cached, just store here
+         (setf (aref kv-vector (1+ cache)) value)
+
+       ;; 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))
+                (kv-vector (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))
+
+           (cond ((or eq-based (not hash-vector))
+                  (when eq-based
+                    (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype))
+
+                  ;; Search next-vector chain for a matching key.
+                  (do ((next next (aref next-vector next)))
+                      ((zerop next))
+                    (declare (type index next))
+                    (when (eq key (aref kv-vector (* 2 next)))
+                      ;; Found, just replace the value.
+                      (setf (hash-table-cache hash-table) (* 2 next))
+                      (setf (aref kv-vector (1+ (* 2 next))) value)
+                      (return-from %puthash value))))
+                 (t
+                  ;; Search next-vector chain for a matching key.
+                  (do ((next next (aref next-vector next)))
+                      ((zerop next))
+                    (declare (type index next))
+                    (when (and (= hashing (aref hash-vector next))
+                               (funcall test-fun key
+                                        (aref kv-vector (* 2 next))))
+                      ;; Found, just replace the value.
+                      (setf (hash-table-cache hash-table) (* 2 next))
+                      (setf (aref kv-vector (1+ (* 2 next))) value)
+                      (return-from %puthash value)))))
+
+           ;; Pop a KV slot off the free list
+           (let ((free-kv-slot (hash-table-next-free-kv hash-table)))
+             ;; Double-check for overflow.
+             (aver (not (zerop free-kv-slot)))
+             (setf (hash-table-next-free-kv hash-table)
+                   (aref next-vector free-kv-slot))
+             (incf (hash-table-number-entries hash-table))
+
+             (setf (hash-table-cache hash-table) (* 2 free-kv-slot))
+             (setf (aref kv-vector (* 2 free-kv-slot)) key)
+             (setf (aref kv-vector (1+ (* 2 free-kv-slot))) value)
+
+             ;; Setup the hash-vector if necessary.
+             (when hash-vector
+               (if (not eq-based)
+                   (setf (aref hash-vector free-kv-slot) hashing)
+                 (aver (= (aref hash-vector free-kv-slot) +magic-hash-vector-value+))))
+
+             ;; Push this slot into the next chain.
+             (setf (aref next-vector free-kv-slot) next)
+             (setf (aref index-vector index) free-kv-slot)))))))
   value)
 
 (defun remhash (key hash-table)
@@ -541,6 +571,9 @@
          ((not (zerop (hash-table-needing-rehash hash-table)))
           (flush-needing-rehash hash-table)))
 
+   ;; For now, just clear the cache
+   (setf (hash-table-cache hash-table) nil)
+
    ;; Search for key in the hash table.
    (multiple-value-bind (hashing eq-based)
        (funcall (hash-table-hash-fun hash-table) key)
@@ -623,6 +656,7 @@
     ;; 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)
 
@@ -687,14 +721,12 @@
 
 (def!method print-object ((hash-table hash-table) stream)
   (declare (type stream stream))
-  (cond ((not *print-readably*)
+  (cond ((or (not *print-readably*) (not *read-eval*))
          (print-unreadable-object (hash-table stream :type t :identity t)
            (format stream
                    ":TEST ~S :COUNT ~S"
                    (hash-table-test hash-table)
                    (hash-table-count hash-table))))
-        ((not *read-eval*)
-         (error "can't print hash tables readably without *READ-EVAL*"))
         (t
          (with-standard-io-syntax
           (format stream