From 472f9e4bed3b6d62bb063c6d8111cd37688c34ac Mon Sep 17 00:00:00 2001
From: Sebastian Harl <sh@tokkee.org>
Date: Wed, 9 Jul 2014 21:49:30 +0200
Subject: [PATCH] avltree: Added sdb_avltree_lookup().

---
 src/include/utils/avltree.h |  3 +++
 src/utils/avltree.c         | 25 +++++++++++++++++++++++++
 t/unit/utils/avltree_test.c | 35 +++++++++++++++++++++++++++++++++++
 3 files changed, 63 insertions(+)

diff --git a/src/include/utils/avltree.h b/src/include/utils/avltree.h
index 548c695..ca3bf08 100644
--- a/src/include/utils/avltree.h
+++ b/src/include/utils/avltree.h
@@ -57,6 +57,9 @@ sdb_avltree_clear(sdb_avltree_t *tree);
 int
 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj);
 
+sdb_object_t *
+sdb_avltree_lookup(sdb_avltree_t *tree, const sdb_object_t *ref);
+
 sdb_avltree_iter_t *
 sdb_avltree_get_iter(sdb_avltree_t *tree);
 
diff --git a/src/utils/avltree.c b/src/utils/avltree.c
index 353a384..56bc57d 100644
--- a/src/utils/avltree.c
+++ b/src/utils/avltree.c
@@ -362,6 +362,31 @@ sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
 	return 0;
 } /* sdb_avltree_insert */
 
+sdb_object_t *
+sdb_avltree_lookup(sdb_avltree_t *tree, const sdb_object_t *ref)
+{
+	node_t *n;
+
+	if (! tree)
+		return NULL;
+
+	n = tree->root;
+	while (n) {
+		int diff = tree->cmp(n->obj, ref);
+
+		if (! diff) {
+			sdb_object_ref(n->obj);
+			return n->obj;
+		}
+
+		if (diff < 0)
+			n = n->right;
+		else
+			n = n->left;
+	}
+	return NULL;
+} /* sdb_avltree_lookup_by_name */
+
 sdb_avltree_iter_t *
 sdb_avltree_get_iter(sdb_avltree_t *tree)
 {
diff --git a/t/unit/utils/avltree_test.c b/t/unit/utils/avltree_test.c
index 0488693..3526e41 100644
--- a/t/unit/utils/avltree_test.c
+++ b/t/unit/utils/avltree_test.c
@@ -66,6 +66,8 @@ static sdb_object_t test_data[] = {
 	SDB_OBJECT_STATIC("a"),
 };
 
+static char *unused_names[] = { "x", "y", "z" };
+
 static void
 populate(void)
 {
@@ -153,6 +155,38 @@ START_TEST(test_insert)
 }
 END_TEST
 
+START_TEST(test_lookup)
+{
+	size_t i;
+
+	populate();
+
+	for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
+		sdb_object_t ref = SDB_OBJECT_STATIC(test_data[i].name);
+		sdb_object_t *obj;
+
+		obj = sdb_avltree_lookup(tree, &ref);
+		fail_unless(obj != NULL,
+				"sdb_avltree_lookup(<tree>, <%s>) = NULL; "
+				"expected: <obj>", ref.name);
+		fail_unless(obj == &test_data[i],
+				"sdb_avltree_lookup(<tree>, <%s>) = %p (%s); "
+				"expected: %p, (%s)", ref.name, obj, obj->name,
+				&test_data[i], test_data[i].name);
+	}
+
+	for (i = 0; i < SDB_STATIC_ARRAY_LEN(unused_names); ++i) {
+		sdb_object_t ref = SDB_OBJECT_STATIC(unused_names[i]);
+		sdb_object_t *obj;
+
+		obj = sdb_avltree_lookup(tree, &ref);
+		fail_unless(obj == NULL,
+				"sdb_avltree_lookup(<tree>, <%s> = %p (%s); "
+				"expected: NULL", ref.name, obj, obj ? obj->name : "<nil>");
+	}
+}
+END_TEST
+
 START_TEST(test_iter)
 {
 	sdb_avltree_iter_t *iter;
@@ -213,6 +247,7 @@ util_avltree_suite(void)
 	tcase_add_checked_fixture(tc, setup, teardown);
 	tcase_add_test(tc, test_null);
 	tcase_add_test(tc, test_insert);
+	tcase_add_test(tc, test_lookup);
 	tcase_add_test(tc, test_iter);
 	suite_add_tcase(s, tc);
 
-- 
2.30.2