Changeset 2f8f480 in mainline for kernel/genarch/src/ofw/ofw_tree.c

Timestamp:

2006-11-07T18:41:42Z (18 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

3869e9c5

Parents:

b63a7cc

Message:

Rewrite OFW device tree traversal algorithms to iterate over the list of peers rather than recurse on each
peer node. This saves us from big troubles with stack overflows.

File:

• kernel/genarch/src/ofw/ofw_tree.c (modified) (4 diffs)

kernel/genarch/src/ofw/ofw_tree.c

@@ -151 +151 @@
 /** Lookup node with matching node_handle.
  *
+ * Child nodes are looked up recursively contrary to peer nodes that
+ * are looked up iteratively to avoid stack overflow.
+ *
  * @param root Root of the searched subtree.
  * @param handle OpenFirmware handle.
@@ -158 +161 @@
 ofw_tree_node_t *ofw_tree_find_node_by_handle(ofw_tree_node_t *root, uint32_t handle)
 {
-        ofw_tree_node_t *node;
-
-        if (root->node_handle == handle)
-                return root;
-
-        if (root->peer) {
-                node = ofw_tree_find_node_by_handle(root->peer, handle);
-                if (node)
-                        return node;
-        }
-                
-        if (root->child) {
-                node = ofw_tree_find_node_by_handle(root->child, handle);
-                if (node)
-                        return node;
+        ofw_tree_node_t *cur;
+
+        for (cur = root; cur; cur = cur->peer) {                
+                if (cur->node_handle == handle)
+                        return cur;
+
+                if (cur->child) {
+                        ofw_tree_node_t *node;
+                        
+                        node = ofw_tree_find_node_by_handle(cur->child, handle);
+                        if (node)
+                                return node;
+                }
         }
         
@@ -231 +232 @@
 }
 
-/** Recursively print subtree rooted in a node.
+/** Print OpenFirmware device subtree rooted in a node.
+ *
+ * Child nodes are processed recursively and peer nodes are processed
+ * iteratively in order to avoid stack overflow.
  *
  * @param node Root of the subtree.
@@ -239 +243 @@
 {
         char *p;
+        const ofw_tree_node_t *cur;
 
         p = (char *) malloc(PATH_MAX_LEN, 0);
 
-        if (node->parent) {
-                snprintf(p, PATH_MAX_LEN, "%s/%s", path, node->da_name);
-                printf("%s\n", p);
-        } else {
-                snprintf(p, PATH_MAX_LEN, "%s", node->da_name);
-                printf("/\n");
-        }
-
-        if (node->child)
-                ofw_tree_node_print(node->child, p);
-
-        if (node->peer)
-                ofw_tree_node_print(node->peer, path);
+        for (cur = node; cur; cur = cur->peer) {
+                if (cur->parent) {
+                        snprintf(p, PATH_MAX_LEN, "%s/%s", path, cur->da_name);
+                        printf("%s\n", p);
+                } else {
+                        snprintf(p, PATH_MAX_LEN, "%s", cur->da_name);
+                        printf("/\n");
+                }
+
+                if (cur->child)
+                        ofw_tree_node_print(cur->child, p);
+        }
 
         free(p);