osom_lib_btree/btree/
the_tree.rs

1use core::ops::DerefMut;
2use core::{marker::PhantomData, mem::ManuallyDrop};
3
4use osom_lib_primitives::length::Length;
5use osom_lib_reprc::traits::ReprC;
6
7use super::BTreeConfig;
8use super::node_ptr::BTreeNodePtr;
9
10/// The main data structure for the B-tree algorithm.
11#[repr(C)]
12#[must_use]
13#[derive(Debug)]
14pub struct BTree<TKey, TValue, TConfig>
15where
16    TKey: Ord,
17    TConfig: BTreeConfig,
18{
19    pub(super) data: BTreeNodePtr<TKey, TValue, TConfig>,
20    pub(super) total_len: Length,
21    pub(super) config: ManuallyDrop<TConfig>,
22    _phantom: PhantomData<[(TKey, TValue)]>,
23}
24
25impl<TKey, TValue, TConfig> BTree<TKey, TValue, TConfig>
26where
27    TKey: Ord,
28    TConfig: BTreeConfig,
29{
30    /// Creates a new [`BTree`] with the default configuration.
31    ///
32    /// Note: this method doesn't allocate anything.
33    #[inline]
34    pub fn new() -> Self
35    where
36        TConfig: Default,
37    {
38        Self::with_config(TConfig::default())
39    }
40
41    /// Creates a new [`BTree`] with the specified configuration.
42    ///
43    /// Note: this method doesn't allocate anything.
44    #[inline]
45    pub fn with_config(config: TConfig) -> Self {
46        Self::new_unchecked(BTreeNodePtr::NULL, Length::ZERO, config)
47    }
48
49    /// Returns the number of key-value pairs in the [`BTree`].
50    #[inline(always)]
51    pub const fn len(&self) -> Length {
52        self.total_len
53    }
54
55    #[inline(always)]
56    const fn new_unchecked(data: BTreeNodePtr<TKey, TValue, TConfig>, total_len: Length, config: TConfig) -> Self {
57        const {
58            assert!(
59                TConfig::CHILDREN_COUNT >= 4,
60                "BTreeConfig::CHILDREN_COUNT must be greater or equal to 4"
61            );
62            assert!(
63                TConfig::CHILDREN_COUNT < 65536,
64                "BTreeConfig::CHILDREN_COUNT must be less than 65536"
65            );
66            assert!(
67                TConfig::CHILDREN_COUNT.is_multiple_of(2),
68                "BTreeConfig::CHILDREN_COUNT must be a multiple of 2"
69            );
70        }
71
72        Self {
73            data,
74            total_len,
75            config: ManuallyDrop::new(config),
76            _phantom: PhantomData,
77        }
78    }
79}
80
81unsafe impl<TKey, TValue, TConfig> Send for BTree<TKey, TValue, TConfig>
82where
83    TKey: Ord + Send,
84    TValue: Send,
85    TConfig: BTreeConfig + Send,
86{
87}
88
89unsafe impl<TKey, TValue, TConfig> Sync for BTree<TKey, TValue, TConfig>
90where
91    TKey: Ord + Sync,
92    TValue: Sync,
93    TConfig: BTreeConfig + Sync,
94{
95}
96
97unsafe impl<TKey, TValue, TConfig> ReprC for BTree<TKey, TValue, TConfig>
98where
99    TKey: Ord + ReprC,
100    TValue: ReprC,
101    TConfig: BTreeConfig,
102{
103    const CHECK: () = const {
104        osom_lib_reprc::hidden::is_reprc::<TKey>();
105        osom_lib_reprc::hidden::is_reprc::<TValue>();
106        osom_lib_reprc::hidden::is_reprc::<TConfig>();
107    };
108}
109
110impl<TKey, TValue, TConfig> Default for BTree<TKey, TValue, TConfig>
111where
112    TKey: Ord,
113    TConfig: BTreeConfig + Default,
114{
115    fn default() -> Self {
116        Self::new()
117    }
118}
119
120impl<TKey, TValue, TConfig> Drop for BTree<TKey, TValue, TConfig>
121where
122    TKey: Ord,
123    TConfig: BTreeConfig,
124{
125    fn drop(&mut self) {
126        unsafe {
127            if !self.data.is_null() {
128                self.data.drop_recursively(self.config.deref_mut());
129            }
130            ManuallyDrop::drop(&mut self.config);
131        }
132    }
133}
osom_lib_btree/btree/the_tree.rs

osom_lib_btree/btree/
the_tree.rs
