fast_btree/btree_base/
btree_traits.rs

1use std::fmt::Debug;
2use std::{marker::PhantomData, mem::size_of};
3
4// Traits bound
5pub trait KeyOfValue<K, V>: Clone + Debug {
6    fn get(value: &V) -> &K;
7}
8pub trait KeyComparator<T>: Clone + Debug {
9    fn new() -> Self;
10    fn less(&self, lhs: &T, rhs: &T) -> bool;
11}
12
13#[derive(Clone, Debug)]
14pub struct InnerValueType<T: BTreeParams>(pub T::KeyType, pub T::ValueType);
15
16impl<T: BTreeParams> InnerValueType<T> {
17    pub fn key(&self) -> &T::KeyType {
18        &self.0
19    }
20
21    pub fn value(&self) -> &T::ValueType {
22        &self.1
23    }
24}
25
26impl<T: BTreeParams> KeyOfValue<T::KeyType, InnerValueType<T>> for InnerValueType<T> {
27    fn get(value: &InnerValueType<T>) -> &T::KeyType {
28        value.key()
29    }
30}
31
32#[derive(Clone, Debug)]
33pub struct ValueCompare<'a, T: BTreeParams> {
34    key_comp: &'a T::KeyCompareType,
35}
36
37impl<'a, T: BTreeParams> ValueCompare<'a, T> {
38    pub fn new(key_comp: &'a T::KeyCompareType) -> Self {
39        Self { key_comp }
40    }
41
42    pub fn less(&self, x: &InnerValueType<T>, y: &InnerValueType<T>) -> bool {
43        self.key_comp.less(&x.0, &y.0)
44    }
45}
46
47pub trait BTreeTraits: Clone + Debug {
48    const LEAF_SLOTS: usize;
49    const INNER_SLOTS: usize;
50    const BINSEARCH_THRESHOLD: usize;
51}
52
53#[derive(Clone, Debug)]
54pub struct DefaultBTreeTraits<K: Clone + Debug, V: Clone + Debug> {
55    _k: PhantomData<K>,
56    _v: PhantomData<V>,
57}
58
59const fn _max(a: usize, b: usize) -> usize {
60    [a, b][(a < b) as usize]
61}
62
63impl<K: Clone + Debug, V: Clone + Debug> BTreeTraits for DefaultBTreeTraits<K, V> {
64    const LEAF_SLOTS: usize = _max(8, 256 / size_of::<V>());
65    const INNER_SLOTS: usize = _max(8, 256 / (size_of::<K>() + size_of::<*const ()>()));
66    const BINSEARCH_THRESHOLD: usize = 256;
67}
68
69pub trait BTreeParams: Clone + Debug {
70    type KeyType: Clone + Debug + Default;
71    type ValueType: Clone + Debug;
72    type KeyCompareType: KeyComparator<Self::KeyType>;
73    type KeyOfValueType: KeyOfValue<Self::KeyType, InnerValueType<Self>>;
74    type Traits: BTreeTraits;
75    const LEAF_SLOTMAX: usize;
76    const INNER_SLOTMAX: usize;
77    const LEAF_SLOTMIN: usize;
78    const INNER_SLOTMIN: usize;
79    const ALLOW_DUPLICATE: bool;
80    const SELF_VERIFY: bool;
81}
82
83#[derive(Clone, Debug)]
84pub struct _BTree<
85    TKey: Clone + Debug + Default,
86    TValue: Clone + Debug,
87    TCompare,
88    Traits: BTreeTraits,
89> where
90    [(); Traits::LEAF_SLOTS]: Sized,
91    [(); Traits::INNER_SLOTS + 1]: Sized,
92{
93    _phantom_key: PhantomData<TKey>,
94    _phantom_value: PhantomData<TValue>,
95    _phantom_compare: PhantomData<TCompare>,
96    _phantom_traits: PhantomData<Traits>,
97}
98
99impl<
100        TKey: Clone + Debug + Default,
101        TValue: Clone + Debug,
102        TCompare: KeyComparator<TKey>,
103        TTraits: BTreeTraits,
104    > BTreeParams for _BTree<TKey, TValue, TCompare, TTraits>
105where
106    [(); TTraits::LEAF_SLOTS]: Sized,
107    [(); TTraits::INNER_SLOTS + 1]: Sized,
108{
109    type KeyType = TKey;
110    type ValueType = TValue;
111    type KeyCompareType = TCompare;
112    type KeyOfValueType = InnerValueType<Self>;
113    type Traits = TTraits;
114    const LEAF_SLOTMAX: usize = TTraits::LEAF_SLOTS;
115    const INNER_SLOTMAX: usize = TTraits::INNER_SLOTS;
116    const LEAF_SLOTMIN: usize = Self::LEAF_SLOTMAX / 2;
117    const INNER_SLOTMIN: usize = Self::INNER_SLOTMAX / 2;
118    const ALLOW_DUPLICATE: bool = false;
119    const SELF_VERIFY: bool = false;
120}
121
122#[cfg(test)]
123#[test]
124fn test_btree_traits() {
125    assert_eq!(DefaultBTreeTraits::<u64, u64>::LEAF_SLOTS, 32);
126    assert_eq!(DefaultBTreeTraits::<u64, u64>::INNER_SLOTS, 16);
127    assert_eq!(DefaultBTreeTraits::<u64, u64>::BINSEARCH_THRESHOLD, 256);
128}
fast_btree/btree_base/btree_traits.rs

fast_btree/btree_base/
btree_traits.rs
