bintree: Add bintree_find

This allows finding a node from the tree without adding it in it
first.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/bintree.c b/bintree.c
index aaad3d6fb146ee11210530ebb01e73872135225b..416d1050aad63ae65c80a5052b81048563553943 100644 (file)
--- a/bintree.c
+++ b/bintree.c
@@ -36,6 +36,38 @@ struct bintree *bintree_add(struct bintree *tree, struct bintree *new,
        return tree;
 }
 
+/*
+ * bintree_find - Find a node from a tree.
+ *
+ * If node is found, pointer to the node is returned. If no node is
+ * found, null is returned.
+ */
+struct bintree *bintree_find(struct bintree *tree, struct bintree *new,
+                       struct bintree_ops *ops)
+{
+       int ret;
+
+       if (tree == NULL)
+               return NULL;
+
+       ret = ops->compare(tree, new);
+       if (ret < 0) {
+               if (tree->left)
+                       return bintree_find(tree->left, new, ops);
+
+               return NULL;
+       }
+
+       if (ret > 0) {
+               if (tree->right)
+                       return bintree_find(tree->right, new, ops);
+
+               return NULL;
+       }
+
+       return tree;
+}
+
 /*
  * bintree_walk - walk through a binary tree from left to right
  *