Ensure that a hash reorganization doesn't take place

during a traversal, which could cause items to be visited
twice or skipped.

* gc.c (full_gc): Changed from static to exter (full_gc): Changed to
internal linkage.

* gc.h (full_gc): Declared.

* hash.c (struct hash): New member, usecount.
(struct hash_iter): New member, next.
(reachable_iters): New static variable.
(hash_mark): Reset the usecount of every reachable hash table.
(hash_iter_mark): Add every reachable iterator to reachable_iters
list.
(make_hash, make_similar_hash, copy_hash): Initialize usecount.
(gethash_c): Do not call hash_grow if usecount is nonzero.
(hash_begin): Initialize next field of hash_iter to null.
Increment use count on hash table.
(hash_next): When traversal ends, release use count, and
null out the hash table reference.
(do_weak_tables): New static function.
(do_iters): New static function.
(hash_process_weak): Weak hash processing logic moved
to do_weak_tables. Also calls do_iters.

* txr.1: Describe hash table traversal, and the assurances
and caveats about inserting and deleting items.

1 files changed, 33 insertions, 0 deletions

diff --git a/txr.1 b/txr.1
index 512f2b82..78df5c9e 100644
--- a/txr.1
+++ b/txr.1
@@ -19455,6 +19455,36 @@ function instead.
 In addition to storing key-value pairs, a hash table can have a piece of
 information associated with it, called the user data.
 
+A hash table can be traversed to visit all of the keys and data.  The order of
+traversal bears no relation to the order of insertion, or to any properties of
+the key type.
+
+During an open traversal, new keys can be inserted into a hash table or deleted
+from it while a a traversal is in progress. Insertion of a new key during
+traversal will not cause any existing key to be visited twice or to be skipped;
+however, it is not specified whether the new key will be traversed. Similarly,
+if a key is deleted during traversal, and that key has not yet been visited, it
+is not specified whether it will be visited during the remainder of the
+traversal.
+
+An open traversal of a hash table is performed by the
+.code maphash
+function and the
+.code dohash
+operator. The traversal is open because code supplied by the program
+is evaluated for each entry.
+
+The functions
+.codn hash-keys ,
+.codn hash-values ,
+.codn hash-pairs ,
+and
+.code hash-alist also perform an open traversal, because they return
+lazy lists. The traversal isn't complete until the returned lazy list
+is fully instantiated. In the meanwhile, the
+\*(TX program can mutate the hash table from which the lazy list
+is being generated.
+
 .coNP Function @ hash-construct
 .synb
 .mets (hash-construct < hash-args << key-val-pairs )
@@ -19888,6 +19918,9 @@ then the corresponding entries from
 each list pairwise correspond to the pairs in
 .metn hash .
 
+The list returned by each of these functions is lazy, and hence constitutes
+an open traversal of the hash table.
+
 .coNP Operator @ dohash
 .synb
 .mets (dohash ( < key-var < value-var < hash-form <> [ result-form ])