Fixes T120: mdb: Add mdb tree traversal functions.

Signed-off-by: Moritz Hoffmann <moritz.hoffmann@inf.ethz.ch>

diff --git a/include/mdb/mdb_tree.h b/include/mdb/mdb_tree.h
index 8269982..e65dfed 100644 (file)
--- a/include/mdb/mdb_tree.h
+++ b/include/mdb/mdb_tree.h
@@ -136,6 +136,37 @@ errval_t mdb_find_cap_for_address(genpaddr_t address, struct cte **ret_node);
 
 bool mdb_reachable(struct cte *cte);
 
+/**
+ * Call-back function for tree traversals.
+ * @param cte The current tree entry.
+ * @param data User provided data pointer.
+ */
+typedef errval_t (*mdb_tree_traversal_fn)(struct cte *cte, void *data);
+
+typedef enum {
+    MDB_TRAVERSAL_ORDER_ASCENDING, ///< Traverse the tree in ascending order
+    MDB_TRAVERSAL_ORDER_DESCENDING ///< Traverse the tree in descending order
+} mdb_tree_traversal_order;
+
+/**
+ * Traverse the mdb tree using some order with a call-back function and
+ * user-provided data. This function starts at the root of the tree.
+ * @param order The order to traverse the tree in.
+ * @param cb The call-back to execute for every node in the tree.
+ * @parm data User-provided data pointer.
+ */
+errval_t mdb_traverse(mdb_tree_traversal_order order, mdb_tree_traversal_fn cb, void *data);
+
+/**
+ * Traverse an mdb sub tree using some order with a call-back function and
+ * user-provided data.
+ * @param cte The subtree to traverse. The call-back will be executed on this node.
+ * @param order The order to traverse the tree in.
+ * @param cb The call-back to execute for every node in the tree.
+ * @parm data User-provided data pointer.
+ */
+errval_t mdb_traverse_subtree(struct cte *cte, mdb_tree_traversal_order order, mdb_tree_traversal_fn cb, void *data);
+
 __END_DECLS
 
 #endif // LIBMDB_MDB_TREE_H

diff --git a/lib/mdb/mdb_tree.c b/lib/mdb/mdb_tree.c
index aefc62f..daa4361 100644 (file)
--- a/lib/mdb/mdb_tree.c
+++ b/lib/mdb/mdb_tree.c
@@ -1291,3 +1291,49 @@ bool mdb_reachable(struct cte *cte)
 {
     return mdb_is_reachable(mdb_root, cte);
 }
+
+errval_t
+mdb_traverse(mdb_tree_traversal_order order, mdb_tree_traversal_fn cb, void *data)
+{
+    return mdb_traverse_subtree(mdb_root, order, cb, data);
+}
+
+errval_t
+mdb_traverse_subtree(struct cte *cte, mdb_tree_traversal_order order,
+        mdb_tree_traversal_fn cb, void *data)
+{
+    struct mdbnode *node = N(cte);
+    assert(node);
+
+    struct cte *first, *second;
+    if (order == MDB_TRAVERSAL_ORDER_ASCENDING) {
+        first = node->left;
+        second = node->right;
+    } else {
+        first = node->right;
+        second = node->left;
+    }
+
+    errval_t err;
+
+    if (first) {
+        err = mdb_traverse_subtree(first, order, cb, data);
+        if (err_is_fail(err)) {
+            return err;
+        }
+    }
+
+    err = cb(cte, data);
+
+    if (err_is_fail(err)) {
+        return err;
+    }
+
+    if (second) {
+        err = mdb_traverse_subtree(second, order, cb, data);
+        if (err_is_fail(err)) {
+            return err;
+        }
+    }
+    return SYS_ERR_OK;
+}