Crate blart

Adaptive radix trie implementation

References

• Leis, V., Kemper, A., & Neumann, T. (2013, April). The adaptive radix tree: ARTful indexing for main-memory databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE) (pp. 38-49). IEEE. Link to PDF

Modules

map

Module containing implementations of the TreeMap and associated iterators/etc.

visitor

Utilities for inspecting the trie structure.

Structs

AttemptOptimisticPrefixMatch

This struct represents a successful match against a prefix using the InnerNode::attempt_pessimistic_match_prefix function.

ConcatTuple

This type implements a BytesMapping for tuples of types, concatenating their byte representations together.

ExplicitMismatch

Represents a prefix mismatch when looking at the entire prefix, including in cases where it is read from a child leaf node.

Identity

This type implements a BytesMapping that preserves the original type without converting it to bytes.

InnerNode48

Node that references between 17 and 49 children

InnerNode256

Node that references between 49 and 256 children

InnerNodeCompressed

Node type that has a compact representation for key bytes and children pointers.

LeafNode

Node that contains a single leaf value.

Mapped

A container for the bytestring that is produced from BytesMapping conversion

Node48Iter

This struct is an iterator over the children of a InnerNode48.

Node256Iter

This struct is an iterator over the children of a InnerNode256.

NodePtr

A pointer to a Node.

OpaqueNodePtr

An opaque pointer to a Node.

OptimisticMismatch

Represents a prefix mismatch when looking only at the prefix content present in an InnerNode header.

PessimisticMismatch

Represents a prefix mismatch when looking only at the prefix content present in an InnerNode header.

PrefixMatch

This struct represents a successful match against a prefix using either the InnerNode::optimistic_match_prefix or InnerNode::match_full_prefix functions.

RestrictedNodeIndex

A restricted index only valid from 0 to LIMIT - 1.

ToIBE

This struct represents a conversion of signed integers to a format that allows the natural ordering of the numbers to match the lexicographic ordering of the bytes.

ToOctets

This struct represents a conversion of IP addresses (V4 and V6) into their component bytes.

ToUBE

This struct represents a conversion of unsigned integers to the big endian format, so that the natural ordering of the numbers matches the lexicographic ordering of the bytes.

TreeMap

An ordered map based on an adaptive radix tree.

TryFromByteError

The error type returned when attempting to construct an index outside the accepted range of a PartialNodeIndex.

Enums

ConcreteInnerNodePtr

An enum that encapsulates pointers to every type of InnerNode

ConcreteNodePtr

An enum that encapsulates pointers to every type of Node

NodeType

The representation of inner nodes

Traits

AsBytes

Any type implementing AsBytes can be decomposed into bytes.

BytesMapping

Trait representing a reversible conversion from a type to some sort of byte string.

InnerNode

Common methods implemented by all inner node.

NoPrefixesBytes

This trait is used to mark types which have a byte representation which is guaranteed to not be a prefix of any other value of the same type.

Node

All nodes which contain a runtime tag that validates their type.

OrderedBytes

This trait is used to mark types where the lexicographic ordering of their byte representation (as output by AsBytes::as_bytes) matches their normal ordering (as determined by Ord).

Type Aliases

InnerNode4

Node that references between 2 and 4 children

InnerNode16

Node that references between 5 and 16 children

InnerNodeCompressedIter

Iterator type for an InnerNodeCompressed