]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use core::borrow::Borrow; |
9cc50fc6 SL |
2 | use core::cmp::Ordering; |
3 | ||
60c5eb7d | 4 | use super::node::{marker, ForceResult::*, Handle, NodeRef}; |
9cc50fc6 | 5 | |
9fa01778 | 6 | use SearchResult::*; |
9cc50fc6 SL |
7 | |
8 | pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> { | |
9 | Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>), | |
60c5eb7d | 10 | GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>), |
9cc50fc6 SL |
11 | } |
12 | ||
13 | pub fn search_tree<BorrowType, K, V, Q: ?Sized>( | |
14 | mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, | |
60c5eb7d | 15 | key: &Q, |
9cc50fc6 | 16 | ) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf> |
60c5eb7d XL |
17 | where |
18 | Q: Ord, | |
19 | K: Borrow<Q>, | |
20 | { | |
9cc50fc6 SL |
21 | loop { |
22 | match search_node(node, key) { | |
23 | Found(handle) => return Found(handle), | |
24 | GoDown(handle) => match handle.force() { | |
25 | Leaf(leaf) => return GoDown(leaf), | |
26 | Internal(internal) => { | |
27 | node = internal.descend(); | |
28 | continue; | |
29 | } | |
60c5eb7d | 30 | }, |
9cc50fc6 SL |
31 | } |
32 | } | |
33 | } | |
34 | ||
35 | pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>( | |
36 | node: NodeRef<BorrowType, K, V, Type>, | |
60c5eb7d | 37 | key: &Q, |
9cc50fc6 | 38 | ) -> SearchResult<BorrowType, K, V, Type, Type> |
60c5eb7d XL |
39 | where |
40 | Q: Ord, | |
41 | K: Borrow<Q>, | |
42 | { | |
9cc50fc6 | 43 | match search_linear(&node, key) { |
60c5eb7d XL |
44 | (idx, true) => Found(Handle::new_kv(node, idx)), |
45 | (idx, false) => SearchResult::GoDown(Handle::new_edge(node, idx)), | |
9cc50fc6 SL |
46 | } |
47 | } | |
48 | ||
8bb4bdeb | 49 | pub fn search_linear<BorrowType, K, V, Type, Q: ?Sized>( |
9cc50fc6 | 50 | node: &NodeRef<BorrowType, K, V, Type>, |
60c5eb7d | 51 | key: &Q, |
9cc50fc6 | 52 | ) -> (usize, bool) |
60c5eb7d XL |
53 | where |
54 | Q: Ord, | |
55 | K: Borrow<Q>, | |
56 | { | |
9cc50fc6 SL |
57 | for (i, k) in node.keys().iter().enumerate() { |
58 | match key.cmp(k.borrow()) { | |
60c5eb7d | 59 | Ordering::Greater => {} |
9cc50fc6 | 60 | Ordering::Equal => return (i, true), |
60c5eb7d | 61 | Ordering::Less => return (i, false), |
9cc50fc6 SL |
62 | } |
63 | } | |
64 | (node.keys().len(), false) | |
65 | } |