cuprate_database/key.rs
1//! Database key abstraction; `trait Key`.
2
3//---------------------------------------------------------------------------------------------------- Import
4use std::{cmp::Ordering, fmt::Debug};
5
6use crate::{storable::Storable, StorableBytes, StorableStr, StorableVec};
7
8//---------------------------------------------------------------------------------------------------- Table
9/// Database [`Table`](crate::table::Table) key metadata.
10///
11/// Purely compile time information for database table keys.
12///
13/// ## Comparison
14/// There are 2 differences between [`Key`] and [`Storable`]:
15/// 1. [`Key`] must be [`Sized`]
16/// 2. [`Key`] represents a [`Storable`] type that defines a comparison function
17///
18/// The database backends will use [`Key::KEY_COMPARE`]
19/// to sort the keys within database tables.
20///
21/// [`Key::KEY_COMPARE`] is pre-implemented as a straight byte comparison.
22///
23/// This default is overridden for numbers, which use a number comparison.
24/// For example, [`u64`] keys are sorted as `{0, 1, 2 ... 999_998, 999_999, 1_000_000}`.
25///
26/// If you would like to re-define this for number types, consider;
27/// 1. Creating a wrapper type around primitives like a `struct SortU8(pub u8)`
28/// 2. Implement [`Key`] on that wrapper
29/// 3. Define a custom [`Key::KEY_COMPARE`]
30pub trait Key: Storable + Sized + Ord {
31 /// Compare 2 [`Key`]'s against each other.
32 ///
33 /// # Defaults for types
34 /// For arrays and vectors that contain a `T: Storable`,
35 /// this does a straight _byte_ comparison, not a comparison of the key's value.
36 ///
37 /// For [`StorableStr`], this will use [`str::cmp`], i.e. it is the same as the default behavior; it is a
38 /// [lexicographical comparison](https://doc.rust-lang.org/std/cmp/trait.Ord.html#lexicographical-comparison)
39 ///
40 /// For all primitive number types ([`u8`], [`i128`], etc), this will
41 /// convert the bytes to the number using [`Storable::from_bytes`],
42 /// then do a number comparison.
43 ///
44 /// # Example
45 /// ```rust
46 /// # use cuprate_database::*;
47 /// // Normal byte comparison.
48 /// let vec1 = StorableVec(vec![0, 1]);
49 /// let vec2 = StorableVec(vec![255, 0]);
50 /// assert_eq!(
51 /// <StorableVec<u8> as Key>::KEY_COMPARE
52 /// .as_compare_fn::<StorableVec<u8>>()(&vec1, &vec2),
53 /// std::cmp::Ordering::Less,
54 /// );
55 ///
56 /// // Integer comparison.
57 /// let byte1 = [0, 1]; // 256
58 /// let byte2 = [255, 0]; // 255
59 /// let num1 = u16::from_le_bytes(byte1);
60 /// let num2 = u16::from_le_bytes(byte2);
61 /// assert_eq!(num1, 256);
62 /// assert_eq!(num2, 255);
63 /// assert_eq!(
64 /// // 256 > 255
65 /// <u16 as Key>::KEY_COMPARE.as_compare_fn::<u16>()(&byte1, &byte2),
66 /// std::cmp::Ordering::Greater,
67 /// );
68 /// ```
69 const KEY_COMPARE: KeyCompare = KeyCompare::Default;
70}
71
72//---------------------------------------------------------------------------------------------------- Impl
73/// [`Ord`] comparison for arrays/vectors.
74impl<const N: usize, T> Key for [T; N] where T: Key + Storable + Sized + bytemuck::Pod {}
75impl<T: bytemuck::Pod + Debug + Ord> Key for StorableVec<T> {}
76
77/// [`Ord`] comparison for misc types.
78///
79/// This is not a blanket implementation because
80/// it allows outer crates to define their own
81/// comparison functions for their `T: Storable` types.
82impl Key for () {}
83impl Key for StorableBytes {}
84impl Key for StorableStr {}
85
86/// Number comparison.
87///
88/// # Invariant
89/// This must _only_ be implemented for [`u32`], [`u64`] (and maybe [`usize`]).
90///
91/// This is because:
92/// 1. We use LMDB's `INTEGER_KEY` flag when this enum variant is used
93/// 2. LMDB only supports these types when using that flag
94///
95/// See: <https://docs.rs/heed/0.20.0-alpha.9/heed/struct.DatabaseFlags.html#associatedconstant.INTEGER_KEY>
96///
97/// Other numbers will still have the same behavior, but they use
98/// [`impl_custom_numbers_key`] and essentially pass LMDB a "custom"
99/// number compare function.
100macro_rules! impl_number_key {
101 ($($t:ident),* $(,)?) => {
102 $(
103 impl Key for $t {
104 const KEY_COMPARE: KeyCompare = KeyCompare::Number;
105 }
106 )*
107 };
108}
109
110impl_number_key!(u32, u64, usize);
111#[cfg(not(any(target_pointer_width = "32", target_pointer_width = "64")))]
112compile_error!("`cuprate_database`: `usize` must be equal to `u32` or `u64` for LMDB's `usize` key sorting to function correctly");
113
114/// Custom number comparison for other numbers.
115macro_rules! impl_custom_numbers_key {
116 ($($t:ident),* $(,)?) => {
117 $(
118 impl Key for $t {
119 // Just forward the the number comparison function.
120 const KEY_COMPARE: KeyCompare = KeyCompare::Custom(|left, right| {
121 KeyCompare::Number.as_compare_fn::<$t>()(left, right)
122 });
123 }
124 )*
125 };
126}
127
128impl_custom_numbers_key!(u8, u16, u128, i8, i16, i32, i64, i128, isize);
129
130//---------------------------------------------------------------------------------------------------- KeyCompare
131/// Comparison behavior for [`Key`]s.
132///
133/// This determines how the database sorts [`Key`]s inside a database [`Table`](crate::Table).
134///
135/// See [`Key`] for more info.
136#[derive(Default, Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
137pub enum KeyCompare {
138 /// Use the default comparison behavior of the backend.
139 ///
140 /// Currently, both `heed` and `redb` use
141 /// [lexicographical comparison](https://doc.rust-lang.org/1.79.0/std/cmp/trait.Ord.html#lexicographical-comparison)
142 /// by default, i.e. a straight byte comparison.
143 #[default]
144 Default,
145
146 /// A by-value number comparison, i.e. `255 < 256`.
147 ///
148 /// This _behavior_ is implemented as the default for all number primitives,
149 /// although some implementations on numbers use [`KeyCompare::Custom`] due
150 /// to internal implementation details of LMDB.
151 Number,
152
153 /// A custom sorting function.
154 ///
155 /// The input of the function is 2 [`Key`]s in byte form.
156 Custom(fn(&[u8], &[u8]) -> Ordering),
157}
158
159impl KeyCompare {
160 /// Return [`Self`] as a pure comparison function.
161 ///
162 /// The returned function expects 2 [`Key`]s in byte form as input.
163 #[inline]
164 pub const fn as_compare_fn<K: Key>(self) -> fn(&[u8], &[u8]) -> Ordering {
165 match self {
166 Self::Default => Ord::cmp,
167 Self::Number => |left, right| {
168 let left = <K as Storable>::from_bytes(left);
169 let right = <K as Storable>::from_bytes(right);
170 Ord::cmp(&left, &right)
171 },
172 Self::Custom(f) => f,
173 }
174 }
175}
176
177//---------------------------------------------------------------------------------------------------- Tests
178#[cfg(test)]
179mod test {
180 // use super::*;
181}