[coreboot-gerrit] Change in coreboot[master]: util/sconfig: Change walk_device_tree to breadth-first walk

[Furquan Shaikh (Code Review)]

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 at 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)

-- 
To view, visit https://review.coreboot.org/26803
To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings

Gerrit-Project: coreboot
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I485b2c51f091d5186f8bc8f3075f28193148e940
Gerrit-Change-Number: 26803
Gerrit-PatchSet: 1
Gerrit-Owner: Furquan Shaikh <furquan at google.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.coreboot.org/pipermail/coreboot-gerrit/attachments/20180604/20255b8f/attachment-0001.html>