Reset path by searching for `key` starting from `root`. If `key` is in the tree, returns the corresponding value and leaved the path pointing at the entry. Otherwise returns `None` and: - A key smaller than all stored keys returns a path to the first entry of the first leaf. - A key larger than all stored keys returns a path to one beyond the last element of the last leaf. - A key between the st
(
&mut self,
key: F::Key,
root: Node,
pool: &NodePool<F>,
comp: &dyn Comparator<F::Key>,
)
| 46 | /// last entry of the first of the leaf nodes. |
| 47 | /// |
| 48 | pub fn find( |
| 49 | &mut self, |
| 50 | key: F::Key, |
| 51 | root: Node, |
| 52 | pool: &NodePool<F>, |
| 53 | comp: &dyn Comparator<F::Key>, |
| 54 | ) -> Option<F::Value> { |
| 55 | let mut node = root; |
| 56 | for level in 0.. { |
| 57 | self.size = level + 1; |
| 58 | self.node[level] = node; |
| 59 | match pool[node] { |
| 60 | NodeData::Inner { size, keys, tree } => { |
| 61 | // Invariant: `tree[i]` contains keys smaller than |
| 62 | // `keys[i]`, greater or equal to `keys[i-1]`. |
| 63 | let i = match comp.search(key, &keys[0..size.into()]) { |
| 64 | // We hit an existing key, so follow the >= branch. |
| 65 | Ok(i) => i + 1, |
| 66 | // Key is less than `keys[i]`, so follow the < branch. |
| 67 | Err(i) => i, |
| 68 | }; |
| 69 | self.entry[level] = i as u8; |
| 70 | node = tree[i]; |
| 71 | } |
| 72 | NodeData::Leaf { size, keys, vals } => { |
| 73 | // For a leaf we want either the found key or an insert position. |
| 74 | return match comp.search(key, &keys.borrow()[0..size.into()]) { |
| 75 | Ok(i) => { |
| 76 | self.entry[level] = i as u8; |
| 77 | Some(vals.borrow()[i]) |
| 78 | } |
| 79 | Err(i) => { |
| 80 | self.entry[level] = i as u8; |
| 81 | None |
| 82 | } |
| 83 | }; |
| 84 | } |
| 85 | NodeData::Free { .. } => panic!("Free {node} reached from {root}"), |
| 86 | } |
| 87 | } |
| 88 | unreachable!(); |
| 89 | } |
| 90 | |
| 91 | /// Move path to the first entry of the tree starting at `root` and return it. |
| 92 | pub fn first(&mut self, root: Node, pool: &NodePool<F>) -> (F::Key, F::Value) { |