From f4befd15d0e141c543243f93424cab3864f9460f Mon Sep 17 00:00:00 2001
From: Sebastian Harl <sh@tokkee.org>
Date: Wed, 9 Jul 2014 21:07:58 +0200
Subject: [PATCH] avltree: Added helper function sdb_avltree_valid().

The function walks the entire tree and checks each node for problems (e.g.
unbalanced nodes, wrong height, missing child/parent links).

Use the function in the unit tests (which is the primary use for the function
anyway ;-)).
---
 src/include/utils/avltree.h |  3 +++
 src/utils/avltree.c         | 53 +++++++++++++++++++++++++++++++++++++
 t/unit/utils/avltree_test.c |  4 +++
 3 files changed, 60 insertions(+)

diff --git a/src/include/utils/avltree.h b/src/include/utils/avltree.h
index b3eec42..4e4d00c 100644
--- a/src/include/utils/avltree.h
+++ b/src/include/utils/avltree.h
@@ -73,6 +73,9 @@ sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter);
 size_t
 sdb_avltree_size(sdb_avltree_t *tree);
 
+_Bool
+sdb_avltree_valid(sdb_avltree_t *tree);
+
 #ifdef __cplusplus
 } /* extern "C" */
 #endif
diff --git a/src/utils/avltree.c b/src/utils/avltree.c
index d8151c8..353a384 100644
--- a/src/utils/avltree.c
+++ b/src/utils/avltree.c
@@ -31,6 +31,7 @@
 
 #include "sysdb.h"
 #include "utils/avltree.h"
+#include "utils/error.h"
 
 #include <assert.h>
 
@@ -54,6 +55,7 @@ struct node {
 	size_t height;
 };
 
+#define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "<nil>")
 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
 			NODE_HEIGHT((n)->left)) + 1)
@@ -420,5 +422,56 @@ sdb_avltree_size(sdb_avltree_t *tree)
 	return tree ? tree->size : 0;
 } /* sdb_avltree_size */
 
+_Bool
+sdb_avltree_valid(sdb_avltree_t *tree)
+{
+	node_t *n;
+
+	_Bool status = 1;
+	size_t size = 0;
+
+	if (! tree)
+		return 1;
+
+	for (n = node_smallest(tree); n; n = node_next(n)) {
+		int bf = BALANCE(n);
+
+		if ((bf < -1) || (1 < bf)) {
+			sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)",
+					NODE_NAME(n), bf);
+			status = 0;
+		}
+
+		if (NODE_HEIGHT(n) != n->height) {
+			sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': "
+					"%zu; expected: %zu", NODE_NAME(n), n->height,
+					NODE_HEIGHT(n));
+			status = 0;
+		}
+
+		if (n->parent && (n->parent->left != n) && (n->parent->right != n)) {
+			sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of "
+					"node '%s': {left: %s, right: %s}; expected: %s",
+					NODE_NAME(n), NODE_NAME(n->parent->left),
+					NODE_NAME(n->parent->right), NODE_NAME(n));
+			status = 0;
+		}
+		if ((! n->parent) && (n != tree->root)) {
+			sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not "
+					"have a parent", NODE_NAME(n));
+			status = 0;
+		}
+
+		++size;
+	}
+
+	if (size != tree->size) {
+		sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu",
+				tree->size, size);
+		status = 0;
+	}
+	return status;
+} /* sdb_avltree_valid */
+
 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 
diff --git a/t/unit/utils/avltree_test.c b/t/unit/utils/avltree_test.c
index 9b48fdc..f1ea1fc 100644
--- a/t/unit/utils/avltree_test.c
+++ b/t/unit/utils/avltree_test.c
@@ -130,6 +130,10 @@ START_TEST(test_insert)
 		fail_unless(check == (int)i + 1,
 				"sdb_avltree_size(<tree>) = %d; expected: %zu",
 				check, i + 1);
+
+		fail_unless(sdb_avltree_valid(tree),
+				"sdb_avltree_insert(<tree>, <%s>) left behind invalid tree",
+				test_data[i].name);
 	}
 
 	/* and again ... now reporting errors because of duplicates */
-- 
2.30.2