Weak hashtables are association containers whose keys are held by weak references: registering a key into a weak hashtable does not prevent its garbage collection. A weak hashtable is a Scheme vector holding nulls or association lists; each vector slot is called bucket; the association lists have the spine composed of strong pairs, while the entries are weak pairs:
|-----|-----|-----|-----|-----| vector of buckets | v |-----|-----|strong pair | | | ------------> |-----|-----|strong pair | | | |-----|-----|weak pair | -------> null key value v |-----|-----| weak pair key value
Whenever a key in a weak hashtable is garbage collected: the corresponding location in the weak pair is set to the BWP object (a special unique object that has this exact purpose, BWP stands for “broken weak pointer”); whenever a bucket is accessed, it is first cleared of weak pairs holding BWP in key position.
NOTE Immediate values (those that fit into a single machine word:
#f, nil, fixnums, characters, etc.) and interned symbols are never garbage collected. If we use them as weak hashtable keys: the associated entries will never be removed from the table unless we explicitly do it with
When the number of collected objects equals the number of buckets (whatever the distribution of elements), the table is enlarged doubling the number of buckets; the table is never restricted by reducing the number of buckets.
At present, weak hashtables are subjected to the following constraints:
The API of weak hashtables is similar to the API of R6RS
hashtables. The following bindings are exported by the library
(vicare containers weak-hashtables).
Build and return a new weak hashtable using hash-function as hash function for keys and equiv-function as comparison function between keys. When dimension is used: it is approximately the initial number of buckets; when not used it defaults to 16.
#t if obj is a weak hashtable, otherwise
Weak hashtables are disjoint values.
Validation clause to be used with the facilities of the library
(vicare arguments validation). Succeed if obj is an
Add an entry to table holding key and value. Return unspecified values.
Search for key in table; if found: return the corresponding value, else return default.
#t if table contains an entry for key, else
If key is in table: remove it, else do nothing. Return unspecified values.
Return the approximate number of entries in table. The returned value can be incorrect if some keys have been garbage collected but the corresponding entries in the table are not yet removed.
Remove all the entries from table. The number of buckets is reset to the its initial value. Return unspecified values.
Return a vector holding the keys in table.
Return two values: a vector holding the keys in table, a vector holding the values in table.
If no entry exists for key in table: create a new entry associating key to the result of applying proc to default.
If an entry exists for key in table: replace its value with the result of applying proc to the old value.