Changeset b76a2217 in mainline for kernel/generic/src/adt/avl.c

Timestamp:

2007-07-29T19:17:25Z (18 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

7fe9c5b

Parents:

83a5cba

Message:

Give the AVL tree walkers the possibility to take an argument.
Each walker is now supposed to return a bool value to support walk termination.

Switch over from the tasks_btree B+tree to tasks_tree AVL tree.
This makes the fix for ticket #48 complete.

File:

• kernel/generic/src/adt/avl.c (modified) (1 diff)

kernel/generic/src/adt/avl.c

@@ -686 +686 @@
 }
 
-static void _avltree_walk(avltree_node_t *node, avltree_walker_t walker)
+/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
+ * visited node.
+ *
+ * @param node          Node representing the root of an AVL subtree to be
+ *                      walked.
+ * @param walker        Walker function that will be appliad on each visited
+ *                      node.
+ * @param arg           Argument for the walker.
+ *
+ * @return              Zero if the walk should stop or non-zero otherwise.
+ */
+static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
+    void *arg)
 {
-        if (node->lft)
-                _avltree_walk(node->lft, walker);
-        walker(node);
-        if (node->rgt)
-                _avltree_walk(node->rgt, walker);
+        if (node->lft) {
+                if (!_avltree_walk(node->lft, walker, arg))
+                        return false;
+        }
+        if (!walker(node, arg))
+                return false;
+        if (node->rgt) {
+                if (!_avltree_walk(node->rgt, walker, arg))
+                        return false;
+        }
+        return true;
 }
 
-/** Walk the AVL tree and apply the walker function on each visited node.
+/** Walk the AVL tree in-order and apply the walker function on each visited
+ * node.
  *
  * @param t             AVL tree to be walked.
  * @param walker        Walker function that will be called on each visited
  *                      node.
- */
-void avltree_walk(avltree_t *t, avltree_walker_t walker)
+ * @param arg           Argument for the walker.
+ */
+void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
 {
-        _avltree_walk(t->root, walker);
+        _avltree_walk(t->root, walker, arg);
 }