Module patch 

Adaptive radix tree (PATCH) used as the backing store for trible indexes. Persistent Adaptive Trie with Cuckoo-compression and Hash-maintenance (PATCH).

See the PATCH chapter of the Tribles Book for the full design description and hashing scheme.

Values stored in leaves are not part of hashing or equality comparisons. Two PATCHes are considered equal if they contain the same set of keys, even if the associated values differ. This allows using the structure as an idempotent blobstore where a value’s hash determines its key.

Re-exports

pub use bytetable::*;

Modules

bytetable

Byte-indexed lookup tables used by PATCH branch nodes.

Structs

Entry

Re-export of Entry. Reference-counted handle to a leaf node in a PATCH trie.

IdentitySchema

A KeySchema that does not reorder the keys. This is useful for keys that are already ordered in the desired way. This is the default ordering.

PATCH

A PATCH is a persistent data structure that stores a set of keys. Each key can be reordered and segmented, based on the provided key ordering and segmentation.

PATCHIntoIterator

Iterator that owns a PATCH and yields keys in key-order. The iterator consumes the PATCH and stores it on the heap (Box) so it can safely hold raw pointers into the patch memory while the iterator is moved.

PATCHIntoOrderedIterator

Iterator that owns a PATCH and yields keys in key order.

PATCHIterator

An iterator over all keys in a PATCH. The keys are returned in key ordering but in random order.

PATCHOrderedIterator

An iterator over every key in a PATCH, returned in key order.

PATCHPrefixIterator

An iterator over all keys in a PATCH that have a given prefix. The keys are returned in tree ordering and in tree order.

SingleSegmentation

A KeySegmentation that does not segment the keys. This is useful for keys that do not have a segment structure. This is the default segmentation.

Traits

KeySchema

A trait is used to provide a re-ordered view of the keys stored in the PATCH. This allows for different PATCH instances share the same leaf nodes, independent of the key ordering used in the tree.

KeySegmentation

This trait is used to segment keys stored in the PATCH. The segmentation is used to determine sub-fields of the key, allowing for segment based operations, like counting the number of elements in a segment with a given prefix without traversing the tree.

Functions

build_key_to_tree

Builds a table translating indices from key order to tree order.

build_segmentation

Builds a per-byte segment map from the segment lengths.

identity_map

Builds an identity permutation table of length N.

invert

Inverts a permutation table.