Simple, Deterministic Dictionaries

This package defines immutable and mutable deterministic dictionaries (or ddicts, for short). A ddict is a dictionary (i.e. it implements the generic interface gen:dict) whose API mimics that of a hash table but which also guarantees LIFO ordering when iterating over the elements of the dictionary.

Caveats concerning concurrent modification: A mutable ddict can be manipulated with ddict-set!, ddict-remove!, ddict-ref!, and ddict-update! concurrently by multiple threads; updates to internal state are performed with a check-and-set operation which protects from invalid internal states. However, the following caveats apply:

• Keys which are removed concurrently during the following operations may or may not be visited during the traversal: ddict-map, ddict-for-each, in-ddict in-ddict-keys, and in-ddict-values.

• The ddict-update! and ddict-ref! functions perform a separate ddict-ref and ddict-set! when required as part of their functionality, which means that the update as a whole is not “atomic.”

Caveat concerning mutable keys: If a key in an equal?-based ddict is mutated, then the ddict’s behavior for insertion and lookup operations becomes unpredictable.

1 Constructors

The key to val mappings are added to the table in the order they appear in the argument list, so later mappings can hide earlier ones if the keys are equal.

2 Basic Predicates

ddict-eqv? returns #t if the given ddict’s keys are compared with eqv?, #f otherwise.

ddict-eq? returns #t if the given ddict’s keys are compared with eq?, #f otherwise.

3 Basic Operations

See also the caveat concerning mutable keys above.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

• If failure-result is a procedure, it is called with no arguments to produce the result.

• Otherwise, failure-result is returned as the result.

See also the caveat concerning mutable keys above.

See also the caveat concerning mutable keys above.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

4 Additional Operations

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

See also the caveat concerning mutable keys above.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

5 Traversal and Iteration Functions

in-ddict-keys returns a sequence containing the keys of dd in LIFO order w.r.t. the order they were inserted into dd.

in-ddict-values returns a sequence containing the values of dd in LIFO order w.r.t. the order their keys were inserted into dd.

These forms provide for fast, direct iteration when used in conjunction with Racket’s various for loops.

6 Performance and Memory Usage

Performance. Immutable and mutable ddicts internally use Racket’s immutable hash data structure along with a list of keys in order to provide hash-like performance and a deterministic iteration order. ddict operations obviously have overhead which the native hash operations do not, but as a dictionary increases in size the overhead should become less noticeable (i.e. the overhead is constant for the atomic ddict operations so the asymptotic complexity is unaffected). To determine if this overhead is acceptable you should of course perform your own application-specific benchmarks.

Memory Usage. In order to keep ddict operations such as ddict-remove efficient (i.e. non-linear), we do not immediately remove elements from the internal key list. Instead, a certain amount of “fragmentation” in the key list is tolerated, but once it passes a predetermined threshold (when the number of removed key slots exceeds the number of active keys), the list is then “defragmented”. To prevent this fragmentation from causing unexpected memory leaks, each key in the key list is stored in a weak-box so its presence in the key list after removal does not prevent garbage collection that would otherwise occur.

The hope is that these implementation details are mostly unobservable to ddict users since their costs will be amortized.

If a user is concerned and wants more fine grained control over the presence of internal fragmentation (e.g. if removals are performed early on in computation then never again) the following functions report on the presence of fragmentation and allow a user to remove any: