arctic/raw/
key.rs

1//! Abstraction over various key types.
2//!
3//! Unlike comparison-based maps like [`BTreeMap`][std::collections::BTreeMap],
4//! which accept keys implementing [`PartialOrd`], or hash-based maps
5//! like [`HashMap`][std::collections::HashMap], which accept keys implementing
6//! [`Hash`][core::hash::Hash] and [`Eq`], the maps and sets in this crate are
7//! backed by a radix tree, which accepts keys represented by a sequence of bytes.
8//!
9//! We abstract over such keys with the [`Key`] trait. Our implementation additionally
10//! requires keys to satisfy the **prefix property**: no key is a prefix of another
11//! key[^1]. Fixed-size key types like integers (`u8`-`u128`) and arrays (`[u8; N]`)
12//! naturally satisfy the prefix property, but dynamically-sized key types require
13//! additional infrastructure.
14//!
15//! We establish type safety by providing wrappers for `Box<[u8]>` ([`BoxedSlice`])
16//! and `[u8]` ([`Slice`]) that are parameterized by an [`Invariant`]: currently,
17//! this can be either [`NonNull`] or [`Terminated`], which is sufficient to
18//! guarantee the prefix property.
19//!
20//! [^1]: Internally, this prevents one key prefix from mapping to both a node and a value.
21
22mod discard;
23mod len;
24mod sized;
25mod r#unsized;
26
27pub(crate) use discard::Discard;
28pub(crate) use len::Bit;
29pub(crate) use len::Byte;
30pub(crate) use len::Len;
31#[cfg_attr(not(feature = "smr-hazard"), expect(unused))]
32pub(crate) use sized::unsigned;
33pub(crate) use r#unsized::Terminate;
34pub(crate) use r#unsized::boxed_slice;
35#[cfg_attr(not(feature = "smr-hazard"), expect(unused))]
36pub(crate) use r#unsized::slice;
37
38pub use r#unsized::Invariant;
39pub use r#unsized::NonNull;
40pub use r#unsized::Terminated;
41pub use r#unsized::boxed_slice::BoxedSlice;
42pub use r#unsized::slice::Slice;
43
44/// Convenience type alias for a [`Slice`] that is backed by a [`str`].
45pub type Str<I> = Slice<I, str>;
46/// Convenience type alias for a [`BoxedSlice`] that is backed by a [`str`].
47pub type BoxedStr<I> = BoxedSlice<I, str>;
48
49use core::borrow::Borrow;
50use core::fmt;
51
52use crate::raw::edge;
53use crate::raw::edge::Meta as _;
54
55/// Byte sequence that can be stored in an adaptive radix tree.
56///
57/// Must satisfy the prefix property: no key is a prefix of any
58/// other key. Fixed-size keys (e.g., [`u64`], `[u8; N]`) trivially
59/// satisfy this property, but dynamically sized keys (slices, boxed slices)
60/// require some additional [`Invariant`][unsized::Invariant]s.
61///
62/// The following table depicts the most relevant key properties
63/// for users of this crate. Methods that can insert into the tree
64/// take `Insert<'_>`; other methods take `&'_ Borrowed`.
65/// Using the [`Iterator`] API may be expensive for dynamically
66/// allocated key types, as they need to be constructed and cloned
67/// during traversal; see [`crate::sequential::Map`] for workarounds.
68///
69/// | Key Family  | Example                                   | Insert<'_>                          | Borrowed                        | Clone in iterator? |
70/// |-------------|-------------------------------------------|-------------------------------------|---------------------------------|--------------------|
71/// | Integer     | u64                                       | u64                                 | u64                             | N                  |
72/// | Array       | [u8; 5]                                   | `&'_ [u8; 5]`                       | [u8; 5]                         | Y                  |
73/// | Slice       | [`&'a Slice<NonNull>`][Slice]             | [`&'a Slice<NonNull>`][Slice]       | [`Slice<NonNull>`][Slice]       | N                  |
74/// | Boxed Slice | [`BoxedStr<Terminated<b'\n'>>`][BoxedStr] | [`&'_ Str<Terminated<b'\n'>>`][Str] | [`Str<Terminated<b'\n'>>`][Str] | Y                  |
75pub trait Key: Borrow<Self::Borrowed> {
76    /// A non-allocated byte sequence that a key can be cheaply borrowed as.
77    type Borrowed: 'static + ?Sized;
78
79    /// Keys can either have edges that store inline bytes (e.g., u64, [`BoxedSlice`]),
80    /// or pointers (i.e., [`Slice`]).
81    ///
82    /// The former can take borrowed bytes with any lifetime when inserting,
83    /// but the latter can only take borrowed bytes that outlive the key type.
84    type Insert<'k>: Copy + Borrow<Self::Borrowed>
85    where
86        Self: 'k;
87
88    /// Tracks key length and allows extracting edges and slicing key bytes.
89    #[expect(private_bounds)]
90    type Read<'k>: Read<Edge = Self::Edge, Len = Self::Len> + From<&'k Self::Borrowed>;
91
92    /// Constructs a key from an initial reader prefix and sequence of bytes and edges.
93    #[expect(private_bounds)]
94    type Write: for<'k> Write<Self::Read<'k>>;
95
96    /// Edge metadata.
97    #[expect(private_bounds)]
98    type Edge: ribbit::Pack<Packed: edge::Meta> + Send + Sync;
99
100    /// Key length.
101    #[expect(private_bounds)]
102    type Len: Len + From<<ribbit::Packed<Self::Edge> as edge::Meta>::Len>;
103
104    /// Convert the key type to the insert type.
105    fn as_insert(&self) -> Self::Insert<'_>;
106
107    /// Convert the insert type to a reader with appropriate lifetime.
108    fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>
109    where
110        Self: 'k;
111
112    /// Convert the insert type to the key type.
113    fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self
114    where
115        Self: 'k;
116
117    /// Convert a reference to a writer into the insert type.
118    ///
119    /// # Safety
120    ///
121    /// Caller must guarantee that `writer` contains a valid key.
122    unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>
123    where
124        Self: 'k;
125}
126
127/// Key types that can split off their last byte,
128/// which enables an efficient set implementation.
129pub trait Split: Key {
130    /// Split a key into a reader and the last byte.
131    fn split_last<'k>(key: &'k Self::Borrowed) -> (Self::Read<'k>, u8);
132}
133
134pub(crate) trait Read: Copy + fmt::Debug + Default + Eq {
135    // Hint for fixed-size keys
136    const LEN: Option<Self::Len>;
137
138    type Edge: ribbit::Pack<Packed: edge::Meta>;
139    type Len: Len
140        + From<<ribbit::Packed<Self::Edge> as edge::Meta>::Len>
141        + Into<<ribbit::Packed<Self::Edge> as edge::Meta>::Len>;
142
143    fn len(&self) -> Self::Len;
144
145    fn get_edge(
146        &self,
147        len: <ribbit::Packed<Self::Edge> as edge::Meta>::Len,
148    ) -> ribbit::Packed<Self::Edge>;
149
150    fn get_byte(&self, index: <ribbit::Packed<Self::Edge> as edge::Meta>::Len) -> Option<u8>;
151
152    #[inline]
153    unsafe fn get_byte_unchecked(
154        &self,
155        index: <ribbit::Packed<Self::Edge> as edge::Meta>::Len,
156    ) -> u8 {
157        match self.get_byte(index) {
158            Some(byte) => byte,
159            None => if_validate!(unreachable!(), unsafe {
160                core::hint::unreachable_unchecked()
161            }),
162        }
163    }
164
165    #[inline]
166    fn match_exact(
167        &self,
168        meta: <Self::Edge as ribbit::Pack>::Packed,
169    ) -> Option<<ribbit::Packed<Self::Edge> as edge::Meta>::Len> {
170        let len = self.match_prefix(meta);
171        (len >= meta.len().into()).then_some(meta.len())
172    }
173
174    fn match_prefix(&self, meta: <Self::Edge as ribbit::Pack>::Packed) -> Self::Len;
175
176    fn prefix(self, end: Self::Len) -> Self;
177    fn suffix(self, start: Self::Len) -> Self;
178    fn common_prefix(self, other: Self) -> Self;
179}
180
181pub(crate) trait Write<R: Read>: fmt::Debug + Default {
182    type Len: Copy + fmt::Debug;
183
184    fn new(prefix: R, key: ribbit::Packed<R::Edge>) -> (Self, Self::Len);
185
186    /// Replace bytes starting at `start` with bytes from `node` and `edge`
187    fn replace(&mut self, start: Self::Len, node: u8, edge: ribbit::Packed<R::Edge>) -> Self::Len;
188}
arctic/raw/key.rs

arctic/raw/
key.rs
