Furquan Shaikh has uploaded this change for review. ( https://review.coreboot.org/26803
Change subject: util/sconfig: Change walk_device_tree to breadth-first walk ......................................................................
util/sconfig: Change walk_device_tree to breadth-first walk
Instead of relying on next_sibling to walk through the entire device tree, this change does breadth-first walk by making use of the generic queue.
BUG=b:80081934 TEST=Verified by grepping and sorting device structure names with and without this CL to ensure that there is no change in static.c for all boards built using abuild.
Change-Id: I485b2c51f091d5186f8bc8f3075f28193148e940 Signed-off-by: Furquan Shaikh furquan@google.com --- M util/sconfig/main.c 1 file changed, 29 insertions(+), 3 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/03/26803/1
diff --git a/util/sconfig/main.c b/util/sconfig/main.c index 3bdd4d2..d60fb03 100644 --- a/util/sconfig/main.c +++ b/util/sconfig/main.c @@ -750,13 +750,39 @@ emit_dev_children(fil, ptr); }
+static void add_siblings_to_queue(struct queue **bfs_queue, struct device *d) +{ + while (d) { + enqueue_tail(bfs_queue, d); + d = d->sibling; + } +} + +static void add_children_to_queue(struct queue **bfs_queue, struct device *d) +{ + if (!device_has_instance(d)) { + add_siblings_to_queue(bfs_queue, d->children); + return; + } + + struct dev_instance *ins = d->dev_instance; + while (ins) { + add_siblings_to_queue(bfs_queue, ins->children); + ins = ins->next; + } +} + static void walk_device_tree(FILE * fil, struct device *ptr, void (*func) (FILE *, struct device *)) { - do { + struct queue *bfs_queue = NULL; + + enqueue_tail(&bfs_queue, ptr); + + while ((ptr = dequeue_head(&bfs_queue))) { + add_children_to_queue(&bfs_queue, ptr); func(fil, ptr); - ptr = ptr->next_sibling; - } while (ptr); + } }
static void emit_chip_headers(FILE *fil, struct chip *chip)