osom_lib_btree/btree/operations/
search.rs

1use core::borrow::Borrow;
2
3use osom_lib_primitives::kvp::KVP;
4
5use crate::btree::{BTree, BTreeConfig, node_ptr::BTreeNodePtr};
6
7use super::helpers;
8
9impl<TKey, TValue, TConfig> BTree<TKey, TValue, TConfig>
10where
11    TKey: Ord,
12    TConfig: BTreeConfig,
13{
14    /// Returns the key-value pair with key matching the given `key`.
15    /// Return `None` if the key is not present in the [`BTree`].
16    pub fn get<Q>(&self, key: &Q) -> Option<KVP<&TKey, &TValue>>
17    where
18        TKey: Borrow<Q>,
19        Q: Ord + ?Sized,
20    {
21        self.search_node(self.data, key)
22    }
23
24    #[allow(clippy::unused_self)]
25    fn search_node<Q>(&self, mut node: BTreeNodePtr<TKey, TValue, TConfig>, key: &Q) -> Option<KVP<&TKey, &TValue>>
26    where
27        TKey: Borrow<Q>,
28        Q: Ord + ?Sized,
29    {
30        unsafe {
31            loop {
32                if node.is_null() {
33                    return None;
34                }
35
36                let index = match helpers::search_key(node, key) {
37                    helpers::SearchKeyResult::ExactMatch { index } => {
38                        let key = node.keys_ptr().add(index).as_ref_unchecked();
39                        let value = node.values_ptr().add(index).as_ref_unchecked();
40                        return Some(KVP { key, value });
41                    }
42                    helpers::SearchKeyResult::InsertionIndex { index } => index,
43                };
44
45                if node.is_leaf() {
46                    return None;
47                }
48
49                let child = node.children_ptr().add(index).read();
50                node = child;
51            }
52        }
53    }
54}
osom_lib_btree/btree/operations/search.rs

osom_lib_btree/btree/operations/
search.rs
