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

• bytes 🔒
• collections 🔒
• map
  Module containing implementations of the TreeMap and associated iterators/etc.
• nightly_rust_apis 🔒
  Module containing copies of Rust standard library unstable functions for use outside of the nightly distribution.
• nodes 🔒
  Trie node representation and manipulation
• tagged_pointer
  A tagged pointer is a pointer (concretely a memory address) with additional data associated with it, such as an indirection bit or reference count. This additional data is often “folded” into the pointer, meaning stored inline in the data representing the address, taking advantage of certain properties of memory addressing.
• visitor
  Utilities for inspecting the trie structure.

Structs

• DeleteResult
  The results of a successful delete operation
• Header
  The common header for all inner nodes
• InnerNode48
  Node that references between 17 and 49 children
• InnerNode48Iter
  An iterator over all the children of a InnerNode48.
• InnerNode256
  Node that references between 49 and 256 children
• InnerNode256Iter
  An iterator over all the children of a InnerNode256.
• InnerNodeCompressed
  Node type that has a compact representation for key bytes and children pointers.
• InnerNodeCompressedIter
  An iterator all the children of an InnerNodeCompressed.
• InnerNodeTreeIterator
  An iterator over all the LeafNodes in a non-singleton tree.
• InsertPrefixError
  Attempted to insert a key which was a prefix of an existing key in the tree.
• InsertResult
  The results of a successful tree insert
• InsertSearchResult
  This struct contains the results from searching for an insert point for a new node in the tree.
• LeafNode
  Node that contains a single leaf value.
• Mapped
  A container for the bytestring that is produced from BytesMapping conversion
• NodePtr
  A pointer to a Node.
• OpaqueNodePtr
  An opaque pointer to a Node.
• RestrictedNodeIndex
  A restricted index only valid from 0 to LIMIT - 1.
• ToBE
  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.
• ToOctets
  This struct represents a conversion of IP addresses (V4 and V6) into their component bytes. The ordering of IP addresses is already the lexicographic ordering of the component bytes, so it will be preserved.
• ToUIntBE
  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.
• 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

• ConcreteNodePtr
  An enum that encapsulates pointers to every type of Node
• InnerNodeIter
  A generic iterator that uses specific iterators for each NodeType (excluding leaves) inside.
• InsertSearchResultType
  The type of insert
• NodeType
  The representation of inner nodes
• TreeIterator
  An iterator over all the leaves in a tree.

Constants

• NUM_PREFIX_BYTES
  The number of bytes stored for path compression in the node header.

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, while preserving the ordering of the original type.
• 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).

Functions

• deallocate_tree^⚠
  Deallocate the given node and all children of the given node.
• delete_maximum_unchecked^⚠
  Find and delete the maximum leaf in the tree, returning the maximum LeafNode.
• delete_minimum_unchecked^⚠
  Find and delete the minimum leaf in the tree, returning the minimum LeafNode.
• delete_unchecked^⚠
  Removes a key from the tree, returning the LeafNode corresponding to the key if the key was previously in the tree.
• insert_unchecked^⚠
  Insert the given key-value pair into the tree.
• maximum_unchecked^⚠
  Search for the leaf with the maximum key, by lexicographic ordering.
• minimum_unchecked^⚠
  Search for the leaf with the minimum key, by lexicographic ordering.
• search_for_insert_point^⚠
  Perform an iterative search for the insert point for the given key, starting at the given root node.
• search_unchecked^⚠
  Search in the given tree for the value stored with the given key.

Type Definitions

• InnerNode4
  Node that references between 2 and 4 children
• InnerNode16
  Node that references between 5 and 16 children