Trait Key 

pub trait Key: Borrow<Self::Borrowed> {
    type Borrowed: 'static + ?Sized;
    type Insert<'k>: Copy + Borrow<Self::Borrowed>
       where Self: 'k;
    type Read<'k>: Read<Edge = Self::Edge, Len = Self::Len> + From<&'k Self::Borrowed>;
    type Write: for<'k> Write<Self::Read<'k>>;
    type Edge: Pack<Packed: Meta> + Send + Sync;
    type Len: Len + From<<Packed<Self::Edge> as Meta>::Len>;

    // Required methods
    fn as_insert(&self) -> Self::Insert<'_>;
    fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>
       where Self: 'k;
    fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self
       where Self: 'k;
    unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>
       where Self: 'k;
}

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

Must satisfy the prefix property: no key is a prefix of any other key. Fixed-size keys (e.g., u64, [u8; N]) trivially satisfy this property, but dynamically sized keys (slices, boxed slices) require some additional Invariants.

The following table depicts the most relevant key properties for users of this crate. Methods that can insert into the tree take Insert<'_>; other methods take &'_ Borrowed. Using the Iterator API may be expensive for dynamically allocated key types, as they need to be constructed and cloned during traversal; see crate::sequential::Map for workarounds.

Key Family	Example	Insert<’_>	Borrowed	Clone in iterator?
Integer	u64	u64	u64	N
Array	[u8; 5]	&'_ [u8; 5]	[u8; 5]	Y
Slice	&'a Slice<NonNull>	&'a Slice<NonNull>	Slice<NonNull>	N
Boxed Slice	BoxedStr<Terminated<b'\n'>>	&'_ Str<Terminated<b'\n'>>	Str<Terminated<b'\n'>>	Y

Required Associated Types

type Borrowed: 'static + ?Sized

A non-allocated byte sequence that a key can be cheaply borrowed as.

type Insert<'k>: Copy + Borrow<Self::Borrowed> where Self: 'k

Keys can either have edges that store inline bytes (e.g., u64, BoxedSlice), or pointers (i.e., Slice).

The former can take borrowed bytes with any lifetime when inserting, but the latter can only take borrowed bytes that outlive the key type.

type Read<'k>: Read<Edge = Self::Edge, Len = Self::Len> + From<&'k Self::Borrowed>

Tracks key length and allows extracting edges and slicing key bytes.

type Write: for<'k> Write<Self::Read<'k>>

Constructs a key from an initial reader prefix and sequence of bytes and edges.

type Edge: Pack<Packed: Meta> + Send + Sync

Edge metadata.

type Len: Len + From<<Packed<Self::Edge> as Meta>::Len>

Key length.

Required Methods

fn as_insert(&self) -> Self::Insert<'_>

Convert the key type to the insert type.

fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>

where Self: 'k,

Convert the insert type to a reader with appropriate lifetime.

fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self

where Self: 'k,

Convert the insert type to the key type.

unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>

where Self: 'k,

Convert a reference to a writer into the insert type.

Safety

Caller must guarantee that writer contains a valid key.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementations on Foreign Types

impl Key for u16

type Read<'k> = Reader<u16>

type Write = Writer<u16>

type Borrowed = u16

type Insert<'k> = u16

type Edge = Be

type Len = Bit

fn as_insert(&self) -> Self::Insert<'_>

fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>

where Self: 'k,

fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self

where Self: 'k,

unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>

where Self: 'k,

impl Key for u32

type Read<'k> = Reader<u32>

type Write = Writer<u32>

type Borrowed = u32

type Insert<'k> = u32

type Edge = Be

type Len = Bit

fn as_insert(&self) -> Self::Insert<'_>

fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>

where Self: 'k,

fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self

where Self: 'k,

unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>

where Self: 'k,

impl Key for u64

type Read<'k> = Reader<u64>

type Write = Writer<u64>

type Borrowed = u64

type Insert<'k> = u64

type Edge = Be

type Len = Bit

fn as_insert(&self) -> Self::Insert<'_>

fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>

where Self: 'k,

fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self

where Self: 'k,

unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>

where Self: 'k,

impl Key for u128

type Read<'k> = Reader<u128>

type Write = Writer<u128>

type Borrowed = u128

type Insert<'k> = u128

type Edge = Be

type Len = Bit

fn as_insert(&self) -> Self::Insert<'_>

fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>

where Self: 'k,

fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self

where Self: 'k,

unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>

where Self: 'k,

impl<const N: usize> Key for [u8; N]

type Read<'k> = Reader<'k, N>

type Write = Writer<N>

type Borrowed = [u8; N]

type Insert<'k> = &'k [u8; N]

type Edge = Le

type Len = Byte

fn as_insert(&self) -> Self::Insert<'_>

fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>

where Self: 'k,

fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self

where Self: 'k,

unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> &'k Self::Borrowed

where Self: 'k,

Implementors

impl<'a, I, R> Key for &'a Slice<I, R>

where I: Invariant, R: ?Sized + Raw,

type Borrowed = Slice<I, R>

type Insert<'k> = &'a Slice<I, R> where Self: 'k

type Read<'k> = Reader<'k, <I as Invariant>::Terminate>

type Write = Writer<I>

type Edge = Slice<<I as Invariant>::Terminate>

type Len = Byte

impl<I, R> Key for BoxedSlice<I, R>

where I: Invariant, R: ?Sized + Raw,

type Read<'k> = Reader<'k, <I as Invariant>::Terminate>

type Write = Writer

type Borrowed = Slice<I, R>

type Insert<'k> = &'k Slice<I, R>

type Edge = Le

type Len = Byte