DT sorting test

Moved the dt_dump() into test/dt_common.c so that it can be shared
between hdata/test/hdata_to_dt.c and core/test/run-device.c

run-device.c contains two tests, one basic sorting test and a
generate-and-sort test.

Signed-off-by: Oliver O'Halloran <oohall@gmail.com>
[stewart@linux.vnet.ibm.com: remove trailing whitespace]
Signed-off-by: Stewart Smith <stewart@linux.vnet.ibm.com>

5 files changed, 148 insertions, 46 deletions

diff --git a/core/device.c b/core/device.c
index 2b44edb..ba983c7 100644
--- a/core/device.c
+++ b/core/device.c
@@ -75,7 +75,7 @@ static const char *get_unitname(const struct dt_node *node)
 	return c + 1;
 }
 
-static int dt_cmp_subnodes(const struct dt_node *a, const struct dt_node *b)
+int dt_cmp_subnodes(const struct dt_node *a, const struct dt_node *b)
 {
 	const char *a_unit = get_unitname(a);
 	const char *b_unit = get_unitname(b);
diff --git a/core/test/run-device.c b/core/test/run-device.c
index cd6ec8d..61ecf84 100644
--- a/core/test/run-device.c
+++ b/core/test/run-device.c
@@ -15,6 +15,7 @@
  */
 
 #include <skiboot.h>
+#include <stdlib.h>
 
 /* Override this for testing. */
 #define is_rodata(p) fake_is_rodata(p)
@@ -32,6 +33,7 @@ static inline bool fake_is_rodata(const void *p)
 #include "../device.c"
 #include "../../ccan/list/list.c" /* For list_check */
 #include <assert.h>
+#include "../../test/dt_common.c"
 
 static void check_path(const struct dt_node *node, const char * expected_path)
 {
@@ -44,6 +46,49 @@ static void check_path(const struct dt_node *node, const char * expected_path)
 	free(path);
 }
 
+/* constructs a random nodes only device tree */
+static void build_tree(int max_depth, int min_depth, struct dt_node *parent)
+{
+	char name[64];
+	int i;
+
+	for (i = 0; i < max_depth; i++) {
+		struct dt_node *new;
+
+		snprintf(name, sizeof name, "prefix@%.8x", rand());
+
+		new = dt_new(parent, name);
+
+		if(max_depth > min_depth)
+			build_tree(max_depth - 1, min_depth, new);
+	}
+}
+
+static bool is_sorted(const struct dt_node *root)
+{
+	struct dt_node *end = list_tail(&root->children, struct dt_node, list);
+	struct dt_node *node;
+
+	dt_for_each_child(root, node) {
+		struct dt_node *next =
+			list_entry(node->list.next, struct dt_node, list);
+
+		/* current node must be "less than" the next node */
+		if (node != end && dt_cmp_subnodes(node, next) != -1) {
+			printf("nodes '%s' and '%s' out of order\n",
+				node->name, next->name);
+
+			return false;
+		}
+
+		if (!is_sorted(node))
+			return false;
+	}
+
+	return true;
+}
+
+
 int main(void)
 {
 	struct dt_node *root, *c1, *c2, *gc1, *gc2, *gc3, *ggc1;
@@ -297,5 +342,31 @@ int main(void)
 	assert(dt_find_by_phandle(root, 0xf0f) == NULL);
 
 	dt_free(root);
+
+	/* basic sorting */
+	root = dt_new_root("rewt");
+	dt_new(root, "a@1");
+	dt_new(root, "a@2");
+	dt_new(root, "a@3");
+	dt_new(root, "a@4");
+	dt_new(root, "b@4");
+	dt_new(root, "c@4");
+
+	assert(is_sorted(root));
+
+	dt_free(root);
+
+	/* Test child node sorting */
+	root = dt_new_root("test root");
+	build_tree(5, 3, root);
+
+	if (!is_sorted(root)) {
+		dump_dt(root, 1, false);
+	}
+	assert(is_sorted(root));
+
+	dt_free(root);
+
 	return 0;
 }
+
diff --git a/hdata/test/hdata_to_dt.c b/hdata/test/hdata_to_dt.c
index 1b20f34..38bf825 100644
--- a/hdata/test/hdata_to_dt.c
+++ b/hdata/test/hdata_to_dt.c
@@ -99,6 +99,7 @@ struct dt_node *add_ics_node(void)
 #include "../../core/vpd.c"
 #include "../../core/device.c"
 #include "../../core/chip.c"
+#include "../../test/dt_common.c"
 
 #include <err.h>
 
@@ -116,57 +117,12 @@ static void *ntuple_addr(const struct spira_ntuple *n)
 	return spira_heap + ((unsigned long)addr - base_addr);
 }
 
-static void indent_num(unsigned indent)
-{
-	unsigned int i;
-
-	for (i = 0; i < indent; i++)
-		putc(' ', stdout);
-}
-
-static void dump_val(unsigned indent, const void *prop, size_t size)
-{
-	size_t i;
-	int width = 78 - indent;
-
-	for (i = 0; i < size; i++) {
-		printf("%02x", ((unsigned char *)prop)[i]);
-		width-=2;
-		if(width < 2) {
-			printf("\n");
-			indent_num(indent);
-			width = 80 - indent;
-		}
-	}
-}
-
 /* Make sure valgrind knows these are undefined bytes. */
 static void undefined_bytes(void *p, size_t len)
 {
 	VALGRIND_MAKE_MEM_UNDEFINED(p, len);
 }
 
-static void dump_dt(const struct dt_node *root, unsigned indent, bool props)
-{
-	const struct dt_node *i;
-	const struct dt_property *p;
-	
-	indent_num(indent);
-	printf("node: %s\n", root->name);
-
-	if (props) {
-		list_for_each(&root->properties, p, list) {
-			indent_num(indent + 1);
-			printf("prop: %s size: %zu val: ", p->name, p->len);
-			dump_val(indent + 1, p->prop, p->len);
-			printf("\n");
-		}
-	}
-
-	list_for_each(&root->children, i, list)
-		dump_dt(i, indent + 2, props);
-}
-
 int main(int argc, char *argv[])
 {
 	int fd, r;
diff --git a/include/device.h b/include/device.h
index a0fc280..28dbd5d 100644
--- a/include/device.h
+++ b/include/device.h
@@ -237,4 +237,9 @@ unsigned int dt_count_addresses(const struct dt_node *node);
 u64 dt_translate_address(const struct dt_node *node, unsigned int index,
 			 u64 *out_size);
 
+/* compare function used to sort child nodes by name when added to the
+ * tree. This is mainly here for testing.
+ */
+int dt_cmp_subnodes(const struct dt_node *a,  const struct dt_node *b);
+
 #endif /* __DEVICE_H */
diff --git a/test/dt_common.c b/test/dt_common.c
new file mode 100644
index 0000000..7622081
--- /dev/null
+++ b/test/dt_common.c
@@ -0,0 +1,70 @@
+/* Copyright 2015 IBM Corp.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * 	http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ * implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <skiboot.h>
+#include <stdlib.h>
+
+#include "../include/device.h"
+
+/* dump_dt() is used in hdata/test/hdata_to_dt.c and core/test/run-device.c
+ * this file is directly #included in both
+ */
+
+static void indent_num(unsigned indent)
+{
+	unsigned int i;
+
+	for (i = 0; i < indent; i++)
+		putc(' ', stdout);
+}
+
+static void dump_val(unsigned indent, const void *prop, size_t size)
+{
+	size_t i;
+	int width = 78 - indent;
+
+	for (i = 0; i < size; i++) {
+		printf("%02x", ((unsigned char *)prop)[i]);
+		width -= 2;
+		if(width < 2) {
+			printf("\n");
+			indent_num(indent);
+			width = 80 - indent;
+		}
+	}
+}
+
+static void dump_dt(const struct dt_node *root, unsigned indent, bool show_props)
+{
+	const struct dt_node *i;
+	const struct dt_property *p;
+
+	indent_num(indent);
+	printf("node: %s\n", root->name);
+
+	if (show_props) {
+		list_for_each(&root->properties, p, list) {
+			indent_num(indent);
+			printf("prop: %s size: %zu val: ", p->name, p->len);
+			dump_val(indent, p->prop, p->len);
+			printf("\n");
+		}
+	}
+
+	list_for_each(&root->children, i, list)
+		dump_dt(i, indent + 2, show_props);
+}
+