Update of /cvsroot/sbcl/sbcl/src/code
In directory fdv4jf1.ch3.sourceforge.com:/tmp/cvs-serv28702/src/code
* Based on old SB-INT:DEFINE-HASH-TABLE-TEST, but:
** macro, not a function.
** only two arguments: name of the test function, and the hash function
(which can also be a lambda form.)
** :TEST accepts both 'NAME, and #'NAME as well.
** pick up redefinitions of the test and hash-function without
re-executing the D-H-T-T form.
** protected by package locks.
* MAKE-HASH-TABLE :HASH-FUNCTION supported as well. EQ-based hashing
not legal for user-provided hash functions, accidents prevented by
wrapping functions which may return a true secondary value in
* Documentation -- other hash-table extensions as well.
* Documentation generation improvements:
** use the shortest package name available -- CL:FOO, not
** kludge around texi2pdf making &key and company bold
** add exceptions so that we don't format words ANSI and CLHS
as lowecase symbols.
RCS file: /cvsroot/sbcl/sbcl/src/code/fdefinition.lisp,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -d -r1.23 -r1.24
--- fdefinition.lisp 14 Jul 2005 16:30:34 -0000 1.23
+++ fdefinition.lisp 21 May 2009 09:56:16 -0000 1.24
@@ -235,6 +235,23 @@
"Set NAME's global function definition."
(declare (type function new-value) (optimize (safety 1)))
(with-single-package-locked-error (:symbol name "setting fdefinition of ~A")
+ ;; Check for hash-table stuff. Woe onto him that mixes encapsulation
+ ;; with this.
+ (when (and (symbolp name) (fboundp name)
+ (boundp '*user-hash-table-tests*))
+ (let ((old (symbol-function name)))
+ (declare (special *user-hash-table-tests*))
+ (dolist (spec *user-hash-table-tests*)
+ (cond ((eq old (second spec))
+ ;; test-function
+ (setf (second spec) new-value))
+ ((eq old (third spec))
+ ;; hash-function
+ (setf (third spec) new-value))))))
+ ;; FIXME: This is a good hook to have, but we should probably
+ ;; reserve it for users.
(let ((fdefn (fdefinition-object name t)))
;; *SETF-FDEFINITION-HOOK* won't be bound when initially running
;; top level forms in the kernel core startup.
RCS file: /cvsroot/sbcl/sbcl/src/code/target-hash-table.lisp,v
retrieving revision 1.51
retrieving revision 1.52
diff -u -d -r1.51 -r1.52
--- target-hash-table.lisp 21 Dec 2008 15:03:11 -0000 1.51
+++ target-hash-table.lisp 21 May 2009 09:56:16 -0000 1.52
@@ -126,62 +126,157 @@
;;;; 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)
- "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."
+ (: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))))
+ (push this *user-hash-table-tests*)))))
+(defmacro define-hash-table-test (name hash-function)
+ "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.
+ ;;; 1.
+ ;; We want to use objects of type FOO as keys (by their
+ ;; names.) EQUALP would work, but would make the names
+ ;; case-insensitive -- wich 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))
+ (error "Malformed HASH-FUNCTION: ~S" hash-function)))))
;;;; 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)
+ (hash-function nil)
"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
- :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."
+ 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.
+ A hint as to how many elements will be put in this hash table.
+ 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.
+ 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.
+ 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.
+ 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.
+ 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
(declare (type (or function symbol) test))
(declare (type unsigned-byte size))
(multiple-value-bind (test test-fun hash-fun)
@@ -194,15 +289,42 @@
((or (eq test #'equalp) (eq test 'equalp))
(values 'equalp #'equalp #'equalp-hash))
- ;; 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"
+ ;; 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"
(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))))))
+ ;; 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+
;; SIZE is just a hint, so if the user asks
@@ -287,6 +409,10 @@
(setf (fdocumentation 'hash-table-rehash-threshold 'function)
"Return the rehash-threshold HASH-TABLE was created with.")
+(setf (fdocumentation 'hash-table-synchronized-p 'function)
+ "Returns T if HASH-TABLE is synchronized.")
(defun hash-table-size (hash-table)
"Return a size that can be used with MAKE-HASH-TABLE to create a hash