TreeTrie

An implementation of a trie map that can hold (patterns over) ordered trees in its keys.

Uses djb's "critbit" structure for each branch node.

There are two types to represent:

Trie = Ok
     | Tl Trie
	 | Br Trie Branch

The first Trie argument to Br is the wildcard case.

Branch = Mt
       | Lf Trie Atom
	   | Nd Int Branch Branch

The Branch type is the "critbit" type, extended with a value slot to make it into a map. We put the Atom last in a Lf, because we might want to use 32-bit pointers internal to our structures, but the hosted atoms might need 64-bit pointers.

The empty Trie, which we'll write empty is a cyclic structure (!):

empty = Br empty Mt

It's the only such structure, so we might want to actually represent it as a distinct constant instead.

Because Ok and Mt are nullary constants, we can represent them with special bit-patterns. Let's choose NULL for this. They don't need to be distinct, since they inhabit different types.

This leaves us with four cases to represent, two in each type. While we could represent these using a single bit, we will instead use two bits, for debuggability.

 33222222222211111111110000000000
 10987654321098765432109876543210
|--------------------------------|

|--------------------------------|
|         Trie pointer         00|   Br case
|--------------------------------|
|        Branch pointer        00|
|--------------------------------|

|--------------------------------|
|         Trie pointer         01|   Tl case
|--------------------------------|

|--------------------------------|
|         Trie pointer         10|   Lf case
|--------------------------------|
|         Atom pointer           |
|     (may be 64 bits long)      |
|--------------------------------|

|--------------------------------|
|              Int             11|   Nd case
|--------------------------------|
|        Branch pointer        00|
|--------------------------------|
|        Branch pointer        00|
|--------------------------------|

We use a weak hash table to index all our objects, because we need to hash-cons them.

Perhaps it could be a Robin-Hood hashtable with backward shift deletion, http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/.

Hmm. For critbit to work, we need to be able to examine the bitpatterns of atoms. However, if those bitpatterns represent pointers to Racket-level objects, and Racket uses a moving collector, then not only will our atom pointers become out of date after a GC, even if we could update them we'd have to reindex each critbit tree.

So we probably want Atom to instead be some index into a different table. (Another level of indirection!) While any (referenced) Trie holds an indirect reference to a given Atom, the underlying Racket object should be preserved across collections. We will need to find the Atom for a given Racket object (based on equal? rather than eq?), and the Racket object for a given Atom (an easy table lookup). We'll want to not hold an Atom's Racket object longer than necessary.

It might be better to have the tag bits in each pointer to an object, rather than in the object header: the tag bits would then identify which of four separate heaps (each with its own object size) is being referred to.

Our data structures are never cyclic.

Supporting direct atoms is probably a sensible thing to do, so that e.g. fixnums map to Atom without having to take up space in the table. In fact, the host language should probably allocate and manage the Atom-to-host-object table itself! That way, our code can be completely ignorant of that kind of detail.