1 files changed, 66 insertions, 0 deletions
diff --git a/third_party/rust/fallible_collections/src/btree/search.rs b/third_party/rust/fallible_collections/src/btree/search.rs
new file mode 100644
index 0000000000..0031fdc29c
--- /dev/null
+++ b/third_party/rust/fallible_collections/src/btree/search.rs
@@ -0,0 +1,66 @@
+use core::borrow::Borrow;
+
+use core::cmp::Ordering;
+
+use super::node::{marker, ForceResult::*, Handle, NodeRef};
+
+use SearchResult::*;
+
+pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> {
+    Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>),
+    GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>),
+}
+
+pub fn search_tree<BorrowType, K, V, Q: ?Sized>(
+    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
+    key: &Q,
+) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf>
+where
+    Q: Ord,
+    K: Borrow<Q>,
+{
+    loop {
+        match search_node(node, key) {
+            Found(handle) => return Found(handle),
+            GoDown(handle) => match handle.force() {
+                Leaf(leaf) => return GoDown(leaf),
+                Internal(internal) => {
+                    node = internal.descend();
+                    continue;
+                }
+            },
+        }
+    }
+}
+
+pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>(
+    node: NodeRef<BorrowType, K, V, Type>,
+    key: &Q,
+) -> SearchResult<BorrowType, K, V, Type, Type>
+where
+    Q: Ord,
+    K: Borrow<Q>,
+{
+    match search_linear(&node, key) {
+        (idx, true) => Found(Handle::new_kv(node, idx)),
+        (idx, false) => SearchResult::GoDown(Handle::new_edge(node, idx)),
+    }
+}
+
+pub fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
+    node: &NodeRef<BorrowType, K, V, Type>,
+    key: &Q,
+) -> (usize, bool)
+where
+    Q: Ord,
+    K: Borrow<Q>,
+{
+    for (i, k) in node.keys().iter().enumerate() {
+        match key.cmp(k.borrow()) {
+            Ordering::Greater => {}
+            Ordering::Equal => return (i, true),
+            Ordering::Less => return (i, false),
+        }
+    }
+    (node.keys().len(), false)
+}