diff options
Diffstat (limited to 'core')
-rw-r--r-- | core/device.c | 56 | ||||
-rw-r--r-- | core/test/run-device.c | 71 |
2 files changed, 123 insertions, 4 deletions
diff --git a/core/device.c b/core/device.c index c5f8634..4818d40 100644 --- a/core/device.c +++ b/core/device.c @@ -65,21 +65,69 @@ struct dt_node *dt_new_root(const char *name) return new_node(name); } +static const char *get_unitname(const struct dt_node *node) +{ + const char *c = strchr(node->name, '@'); + + if (!c) + return NULL; + + return c + 1; +} + +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); + + ptrdiff_t basenamelen = a_unit - a->name; + + /* sort hex unit addresses by number */ + if (a_unit && b_unit && !strncmp(a->name, b->name, basenamelen)) { + unsigned long long a_num, b_num; + char *a_end, *b_end; + + a_num = strtoul(a_unit, &a_end, 16); + b_num = strtoul(b_unit, &b_end, 16); + + /* only compare if the unit addr parsed correctly */ + if (*a_end == 0 && *b_end == 0) + return (a_num > b_num) - (a_num < b_num); + } + + return strcmp(a->name, b->name); +} + bool dt_attach_root(struct dt_node *parent, struct dt_node *root) { struct dt_node *node; - /* Look for duplicates */ - assert(!root->parent); + + if (list_empty(&parent->children)) { + list_add(&parent->children, &root->list); + root->parent = parent; + + return true; + } + dt_for_each_child(parent, node) { - if (!strcmp(node->name, root->name)) { + int cmp = dt_cmp_subnodes(node, root); + + /* Look for duplicates */ + if (cmp == 0) { prerror("DT: %s failed, duplicate %s\n", __func__, root->name); return false; } + + /* insert before the first node that's larger + * the the node we're inserting */ + if (cmp > 0) + break; } - list_add_tail(&parent->children, &root->list); + + list_add_before(&parent->children, &root->list, &node->list); root->parent = parent; return true; 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; } + |