From a80596a56e47f3e66c4818419625a76bbdec215e Mon Sep 17 00:00:00 2001 From: Alexey Radul Date: Sun, 29 May 2011 22:37:59 +0100 Subject: [PATCH] Rewrite the hash table constructors section with more weakness options. Define and export key-ephemeral-eq and key-ephemeral-eqv tables as replacements for the key-weak versions. Punt descriptions of old hash table constructor procedures to the bottom of the section and say they are for backward compatibility. One may object to MAKE-KEY-EPHEMERAL-EQ-HASH-TABLE on the grounds that it invites a combinatorial explosion of names: make-key/datum-weak-eqv-hash-table make-datum-ephemeral-string-hash-table make-key&datum-ephemeral-equal-hash-table (!?) and so on ad nauseam. Where will it end? The criterion I used to decide which names to export and document and which names to leave alone and defer to the general HASH-TABLE/CONSTRUCTOR mechanism was simply to update the existing documentation. The manual already listed MAKE-WEAK-EQ-HASH-TABLE. It is now named MAKE-KEY-WEAK-EQ-HASH-TABLE, so that name is included. But really, a key-weak table is just a performance optimization over a key-ephemeral table, to save work when you know the data will not hold the keys strongly. So MAKE-KEY-EPHEMERAL-EQ-HASH-TABLE is in; it was, in fact, the reason I wanted Taylor to implement ephemerons in the first place. MAKE-KEY-EPHEMERAL-EQV-HASH-TABLE is in to preserve the symmetry between eq? and eqv? that was already present in the manual. But the rest of them are out, because they weren't there before. If datum-weak tables were so important that their constructor really must be given a name here, then (arguably) why were they not already implemented and documented? The fact that MIT Scheme only supported strong and key-weak tables for a long time suggests that those kinds are the most common, and therefore the most deserving of slots in the name space. --- doc/ref-manual/associations.texi | 75 ++++++++++++++++++++------------ src/runtime/hashtb.scm | 7 ++- src/runtime/runtime.pkg | 10 ++++- 3 files changed, 63 insertions(+), 29 deletions(-) diff --git a/doc/ref-manual/associations.texi b/doc/ref-manual/associations.texi index a2fb0667d..22211927f 100644 --- a/doc/ref-manual/associations.texi +++ b/doc/ref-manual/associations.texi @@ -372,7 +372,8 @@ entries for @var{y-key} exist. @cindex hash table Hash tables are a fast, powerful mechanism for storing large numbers of associations. MIT/GNU Scheme's hash tables feature automatic resizing, -customizable growth parameters, and customizable hash procedures. +customizable growth parameters, customizable hash procedures, and +many options for weak references to keys or data. The average times for the insertion, deletion, and lookup operations on a hash table are bounded by a constant. The space required by the table @@ -425,64 +426,67 @@ constructors are procedures that accept one optional argument, @cindex strongly held keys, of hash table @cindex weakly held keys, of hash table Hash tables are normally characterized by two things: the equivalence -predicate that is used to compare keys, and whether or not the table -allows its keys to be reclaimed by the garbage collector. If a table -prevents its keys from being reclaimed by the garbage collector, it is -said to hold its keys @dfn{strongly}; otherwise it holds its keys -@dfn{weakly} (@pxref{Weak References}). +predicate that is used to compare keys, and how the table allows its +keys and data to be reclaimed by the garbage collector. If a table +prevents its keys and data from being reclaimed by the garbage +collector, it is said to hold its keys and data @dfn{strongly}; other +arrangements are possible, where a table may hold keys or data +@dfn{weakly} or @dfn{ephemerally} (@pxref{Weak References}). @deffn procedure make-strong-eq-hash-table [initial-size] @findex eq? Returns a newly allocated hash table that accepts arbitrary objects as -keys, and compares those keys with @code{eq?}. The keys are held +keys, and compares those keys with @code{eq?}. The keys and data are held strongly. These are the fastest of the standard hash tables. @end deffn -@deffn procedure make-weak-eq-hash-table [initial-size] +@deffn procedure make-key-weak-eq-hash-table [initial-size] @findex eq? Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with @code{eq?}. The keys are held -weakly. +weakly, but the data are held strongly. Note that if a datum holds a +key strongly, the table will effectively hold that key strongly. @end deffn -@deffn procedure make-eq-hash-table [initial-size] +@deffn procedure make-key-ephemeral-eq-hash-table [initial-size] @findex eq? -This is an alias for @code{make-weak-eq-hash-table}. - -@strong{Warning}: This may become an alias -@code{make-strong-eq-hash-table} instead. We recommend that you use -@code{make-weak-eq-hash-table} explicitly for weak hash tables. +Returns a newly allocated hash table that accepts arbitrary objects as +keys, and compares those keys with @code{eq?}. The keys are held +weakly, even if some of the data should hold some of the keys +strongly. @end deffn @deffn procedure make-strong-eqv-hash-table [initial-size] @findex eqv? Returns a newly allocated hash table that accepts arbitrary objects as -keys, and compares those keys with @code{eqv?}. The keys are held +keys, and compares those keys with @code{eqv?}. The keys and data are held strongly. These hash tables are a little slower than those made by @code{make-strong-eq-hash-table}. @end deffn -@deffn procedure make-weak-eqv-hash-table [initial-size] +@deffn procedure make-key-weak-eqv-hash-table [initial-size] @findex eqv? Returns a newly allocated hash table that accepts arbitrary objects as keys, and compares those keys with @code{eqv?}. The keys are held -weakly, except that booleans, characters, numbers, and interned symbols -are held strongly. +weakly, except that booleans, characters, numbers, and interned +symbols are held strongly. The data are held strongly. Note that if +a datum holds a key strongly, the table will effectively hold that key +strongly. @end deffn -@deffn procedure make-eqv-hash-table [initial-size] +@deffn procedure make-key-ephemeral-eqv-hash-table [initial-size] @findex eqv? -This is an alias for @code{make-weak-eqv-hash-table}. - -@strong{Warning}: This may become an alias for -@code{make-strong-eqv-hash-table} instead. We recommend that you use -@code{make-weak-eqv-hash-table} explicitly for weak hash tables. +Returns a newly allocated hash table that accepts arbitrary objects as +keys, and compares those keys with @code{eqv?}. The keys are held +weakly, except that booleans, characters, numbers, and interned +symbols are held strongly. The keys are effectively held weakly even +if some of the data should hold some of the keys strongly. @end deffn @deffn procedure make-equal-hash-table [initial-size] @findex equal? Returns a newly allocated hash table that accepts arbitrary objects as -keys, and compares those keys with @code{equal?}. The keys are held +keys, and compares those keys with @code{equal?}. The keys and data are held strongly. These hash tables are quite a bit slower than those made by @code{make-strong-eq-hash-table}. @end deffn @@ -490,7 +494,7 @@ strongly. These hash tables are quite a bit slower than those made by @deffn procedure make-string-hash-table [initial-size] @findex string=? Returns a newly allocated hash table that accepts character strings as -keys, and compares them with @code{string=?}. The keys are held +keys, and compares them with @code{string=?}. The keys and data are held strongly. @end deffn @@ -656,6 +660,23 @@ collector. Otherwise, this procedure does nothing. In either case, it returns an unspecified result. @end deffn +The following procedures are provided only for backward compatibility. +They should be considered @strong{deprecated} and should not be used +in new programs. + +@deffn procedure make-weak-eq-hash-table [initial-size] +@deffnx procedure make-eq-hash-table [initial-size] +@findex eq? +These are aliases of @code{make-key-weak-eq-hash-table}. +@end deffn + +@deffn procedure make-weak-eqv-hash-table [initial-size] +@deffnx procedure make-eqv-hash-table [initial-size] +@findex eq? +These are aliases of @code{make-key-weak-eqv-hash-table}. +@end deffn + + @node Basic Hash Table Operations, Resizing of Hash Tables, Construction of Hash Tables, Hash Tables @subsection Basic Hash Table Operations diff --git a/src/runtime/hashtb.scm b/src/runtime/hashtb.scm index 6f8b12d30..756540613 100644 --- a/src/runtime/hashtb.scm +++ b/src/runtime/hashtb.scm @@ -1168,6 +1168,7 @@ USA. (define equal-hash-table-type) (define key-ephemeral-eq-hash-table-type) (define key-weak-eq-hash-table-type) +(define key-ephemeral-eqv-hash-table-type) (define key-weak-eqv-hash-table-type) (define string-hash-table-type) (define strong-eq-hash-table-type) @@ -1200,6 +1201,8 @@ USA. (open-type! eq-hash-mod eq? #t hash-table-entry-type:key-weak)) (set! key-weak-eqv-hash-table-type (make eqv-hash-mod eqv? #t hash-table-entry-type:key-weak)) + (set! key-ephemeral-eqv-hash-table-type + (make eqv-hash-mod eqv? #t hash-table-entry-type:key-ephemeral)) (set! string-hash-table-type (make string-hash-mod string=? #t hash-table-entry-type:strong)) (set! strong-eq-hash-table-type ;Open-coded @@ -1211,6 +1214,7 @@ USA. (define make-equal-hash-table) (define make-key-ephemeral-eq-hash-table) (define make-key-weak-eq-hash-table) +(define make-key-ephemeral-eqv-hash-table) (define make-key-weak-eqv-hash-table) (define make-string-hash-table) (define make-strong-eq-hash-table) @@ -1225,6 +1229,7 @@ USA. ;; This is done above. ;; (init make-key-ephemeral-eq-hash-table key-ephemeral-eq-hash-table-type) (init make-key-weak-eq-hash-table key-weak-eq-hash-table-type) + (init make-key-ephemeral-eqv-hash-table key-ephemeral-eqv-hash-table-type) (init make-key-weak-eqv-hash-table key-weak-eqv-hash-table-type) (init make-string-hash-table string-hash-table-type) (init make-strong-eq-hash-table strong-eq-hash-table-type) @@ -1387,4 +1392,4 @@ USA. ;; Must come before any hash table types are constructed or used. ;; This constructs an address hash table, however. (initialize-memoized-hash-table-types!) - (initialize-hash-table-type-constructors!)) \ No newline at end of file + (initialize-hash-table-type-constructors!)) diff --git a/src/runtime/runtime.pkg b/src/runtime/runtime.pkg index 8a7dd8801..2f7416fc9 100644 --- a/src/runtime/runtime.pkg +++ b/src/runtime/runtime.pkg @@ -2152,10 +2152,18 @@ USA. hash-table/size hash-table/type hash-table? + key-ephemeral-eq-hash-table-type + key-ephemeral-eqv-hash-table-type + key-weak-eq-hash-table-type + key-weak-eqv-hash-table-type make-equal-hash-table make-hash-table make-hash-table* make-hash-table-type + make-key-ephemeral-eq-hash-table + make-key-ephemeral-eqv-hash-table + make-key-weak-eq-hash-table + make-key-weak-eqv-hash-table make-string-hash-table make-strong-eq-hash-table make-strong-eqv-hash-table @@ -6014,4 +6022,4 @@ USA. stack-sampler:debug-internal-errors? stack-sampler:show-expressions? with-stack-sampling) - (initialization (initialize-package!))) \ No newline at end of file + (initialization (initialize-package!))) -- 2.25.1