Changeset d1e9321 in mainline

Timestamp:

2007-07-29T13:46:34Z (18 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

5dcee525

Parents:

0d65d76

Message:

Add explicit type for an AVL tree key.
Add function to walk an AVL tree using a supplied walker.

Location:

kernel/generic

Files:

• include/adt/avl.h (modified) (6 diffs)
• src/adt/avl.c (modified) (4 diffs)

kernel/generic/include/adt/avl.h

@@ -33 +33 @@
  */
 
-
 #ifndef KERN_AVLTREE_H_
 #define KERN_AVLTREE_H_ 
@@ -47 +46 @@
  * @param member Name of avltree attribute in the outer structure.
  */
-#define avltree_get_instance(link, type, member) \
-    ((type *)(((uint8_t *)(link)) - ((uint8_t *) &(((type *) NULL)->member))))
-
+#define avltree_get_instance(node, type, member) \
+    ((type *)(((uint8_t *)(node)) - ((uint8_t *) &(((type *) NULL)->member))))
 
 typedef struct avltree_node avltree_node_t;
 typedef struct avltree avltree_t;
 
+typedef uint64_t avltree_key_t;
+
+typedef void (* avltree_walker_t)(avltree_node_t *);
 
 /** AVL tree node structure. */
@@ -78 +79 @@
         
         /** Node's key. */
-        uint64_t key; 
+        avltree_key_t key; 
         
         /**
@@ -101 +102 @@
          * with avltree_delete_min().
          */
-        uint64_t base; 
+        avltree_key_t base; 
 };
 
@@ -109 +110 @@
  * @param t AVL tree.
  */
-static inline void avltree_create (avltree_t *t)
+static inline void avltree_create(avltree_t *t)
 {
         t->root = NULL;
@@ -129 +130 @@
 
 extern avltree_node_t *avltree_find_min(avltree_t *t);
-extern avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
+extern avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key);
 extern void avltree_insert(avltree_t *t, avltree_node_t *newnode);
 extern void avltree_delete(avltree_t *t, avltree_node_t *node);
 extern bool avltree_delete_min(avltree_t *t);
+extern void avltree_walk(avltree_t *t, avltree_walker_t walker);
 
 #endif

kernel/generic/src/adt/avl.c

@@ -53 +53 @@
 #include <debug.h>
 
-
 #define LEFT    0
 #define RIGHT   1
 
-
 /** Search for the first occurence of the given key in an AVL tree.
  *
@@ -65 +63 @@
  * @return Pointer to a node or NULL if there is no such key.
  */
-avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
+avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key)
 {
         avltree_node_t *p;
@@ -121 +119 @@
         avltree_node_t *top;
         avltree_node_t **dpc;
-        uint64_t key;
+        avltree_key_t key;
 
         ASSERT(t);
@@ -708 +706 @@
 }
 
+static void _avltree_walk(avltree_node_t *node, avltree_walker_t walker)
+{
+        if (node->lft)
+                _avltree_walk(node->lft, walker);
+        walker(node);
+        if (node->rgt)
+                _avltree_walk(node->rgt, walker);
+}
+
+/** Walk the AVL tree 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)
+{
+        _avltree_walk(t->root, walker);
+}
+
 /** @}
  */