Next: , Previous: , Up: Top   [Index]

31 Weak hashtables

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: #t, #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 weak-hashtable-delete! or weak-hashtable-clear!.

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).

Function: make-weak-hashtable hash-function equiv-function
Function: make-weak-hashtable hash-function equiv-function dimension

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.

Function: weak-hashtable? obj

Return #t if obj is a weak hashtable, otherwise #f. Weak hashtables are disjoint values.

Validation Clause: weak-hashtable obj

Validation clause to be used with the facilities of the library (vicare arguments validation). Succeed if obj is an instance of weak-hashtable.

Function: weak-hashtable-set! table key value

Add an entry to table holding key and value. Return unspecified values.

Function: weak-hashtable-ref table key default

Search for key in table; if found: return the corresponding value, else return default.

Function: weak-hashtable-contains? table key

Return #t if table contains an entry for key, else return #f.

Function: weak-hashtable-delete! table key

If key is in table: remove it, else do nothing. Return unspecified values.

Function: weak-hashtable-size table

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.

Function: weak-hashtable-clear! table

Remove all the entries from table. The number of buckets is reset to the its initial value. Return unspecified values.

Function: weak-hashtable-keys table

Return a vector holding the keys in table.

Function: weak-hashtable-entries table

Return two values: a vector holding the keys in table, a vector holding the values in table.

Function: weak-hashtable-update! table key proc default

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.

Next: , Previous: , Up: Top   [Index]