Module key 

Abstraction over various key types.

Unlike comparison-based maps like BTreeMap, which accept keys implementing PartialOrd, or hash-based maps like HashMap, which accept keys implementing Hash and Eq, the maps and sets in this crate are backed by a radix tree, which accepts keys represented by a sequence of bytes.

We abstract over such keys with the Key trait. Our implementation additionally requires keys to satisfy the prefix property: no key is a prefix of another key¹. Fixed-size key types like integers (u8-u128) and arrays ([u8; N]) naturally satisfy the prefix property, but dynamically-sized key types require additional infrastructure.

We establish type safety by providing wrappers for Box<[u8]> (BoxedSlice) and [u8] (Slice) that are parameterized by an Invariant: currently, this can be either NonNull or Terminated, which is sufficient to guarantee the prefix property.

---

1. Internally, this prevents one key prefix from mapping to both a node and a value. ↩

Structs

BoxedSlice

An owned, dynamically sized key that satisfies an Invariant.

NonNull

Invariant ZST indicating this key does not contain any null bytes.

Slice

A borrowed, dynamically sized key that satisfies an Invariant.

Terminated

Invariant ZST indicating this key contains exactly one TERMINATOR byte at the end of the key.

Traits

Invariant

An invariant of [u8] that is sufficient to guarantee the prefix property (no key is a prefix of another key).

Key

Byte sequence that can be stored in an adaptive radix tree.

Split

Key types that can split off their last byte, which enables an efficient set implementation.

Type Aliases

BoxedStr

Convenience type alias for a BoxedSlice that is backed by a str.

Str

Convenience type alias for a Slice that is backed by a str.