implemented a tree-walking api for psplay

diff --git a/psplay.c b/psplay.c
index d4fdd9d..bd5ab69 100644 (file)
--- a/psplay.c
+++ b/psplay.c
@@ -51,9 +51,6 @@ static inline uint32_t psplay_fast_prng ()
 }
 
 
-
-
-
 PSplayroot
 psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete)
 {
@@ -67,6 +64,7 @@ psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete)
   return self;
 }
 
+
 PSplayroot
 psplay_destroy_root (PSplayroot self)
 {
@@ -384,19 +382,112 @@ psplay_remove (PSplayroot root, PSplay node)
   return node;
 }
 
-void
-psplay_dump (PSplay root, FILE* dest, unsigned level)
+/*
+  Walking a tree calls a 'action' three times PSPLAY_PREORDER before visiting the left subtree,
+  PSPLAY_INORDER after visiting the left subtree and before the right subtree, PSPLAY_POSTORDER
+  finally after visiting the right subtree. Example: For to traverse the tree in order action
+  would only handle PSPLAY_INORDER.
+  This action returns PSLPLAY_CONT when the traversal of the tree shall continue.
+  An 'action' must not alter the tree itself but it can indicate aborting the tree traversal and
+  how the current node is handled by its return value:
+   PSPLAY_STOP:
+     just stops the traversal
+   PSPLAY_REMOVE:
+     stops the traversal and removes the current node, calling the delete handler registered in root
+   any other psplay_delete_t:
+     stops the traversal and removes the current node, calling the returned delete handler with it
+*/
+const psplay_delete_t PSPLAY_CONT = (psplay_delete_t)0x0;
+const psplay_delete_t PSPLAY_STOP = (psplay_delete_t)0x1;
+const psplay_delete_t PSPLAY_REMOVE = (psplay_delete_t)0x2;
+
+static int
+psplay_handle (PSplayroot root, PSplay node, psplay_delete_t res)
+{
+  if (res == PSPLAY_CONT)
+    return 1;
+
+  if (res == PSPLAY_STOP)
+    ;
+  else if (res == PSPLAY_REMOVE)
+    {
+      psplay_remove (root, node);
+      if (root->delete)
+        root->delete (node);
+    }
+  else
+    {
+      psplay_remove (root, node);
+      res (node);
+    }
+  return 0;
+}
+
+
+int
+psplay_walk (PSplayroot root, PSplay node, psplay_action_t action, int level, void* data)
+{
+  if (!root->tree)
+    return 1;
+
+  if (!node)
+    node = root->tree;
+
+  psplay_delete_t res;
+
+  res = action (node, PSPLAY_PREORDER, level, data);
+  if (!psplay_handle (root, node, res))
+    return 0;
+
+  if (node->left)
+    if (!psplay_walk (root, node->left, action, level+1, data))
+      return 0;
+
+  res = action (node, PSPLAY_INORDER, level, data);
+  if (!psplay_handle (root, node, res))
+    return 0;
+
+  if (node->right)
+    if (!psplay_walk (root, node->right, action, level+1, data))
+      return 0;
+
+  res = action (node, PSPLAY_POSTORDER, level, data);
+  if (!psplay_handle (root, node, res))
+    return 0;
+
+  return 1;
+}
+
+psplay_delete_t psplay_print_node (PSplay node, const enum psplay_order_e which, int level, void* data)
 {
   static char* sp = "                                        ";
-  fprintf (dest, "%s%p\n", sp+40-level, root);
-  if (level>40 || !root) return;
-  fprintf (dest, "%skey %p (%.4s)\n", sp+40-level, root->key, root->key?root->key:"NULL");
-  fprintf (dest, "%sup %p\n", sp+40-level, root->up);
-  fprintf (dest, "%sleft %p\n", sp+40-level, root->left);
-  psplay_dump (root->left, dest, level+3);
-  fprintf (dest, "%sright %p\n", sp+40-level, root->right);
-  psplay_dump (root->right, dest, level+3);
-  if (level == 0) fprintf (dest, "\n");
+  if (level>40) return;
+
+  FILE* fh = data;
+
+  switch (which)
+    {
+    case PSPLAY_PREORDER:
+      fprintf (fh, "%s%p\n", sp+40-level, node);
+      fprintf (fh, "%skey %p (%.4s)\n", sp+40-level, node->key, node->key?node->key:"NULL");
+      fprintf (fh, "%sup %p\n", sp+40-level, node->up);
+      fprintf (fh, "%sleft %p\n", sp+40-level, node->left);
+      break;
+    case PSPLAY_INORDER:
+      fprintf (fh, "%sright %p\n", sp+40-level, node->right);
+      break;
+    case PSPLAY_POSTORDER:
+      break;
+    }
+
+  return PSPLAY_CONT;
+}
+
+void
+psplay_dump (PSplayroot root, FILE* dest)
+{
+  psplay_walk (root, NULL, psplay_print_node, 0, dest);
+  fprintf (dest, "\n");
 }
 
 int my_cmp (const void* a, const void* b)
@@ -419,46 +510,46 @@ main ()
   psplay_insert (&root, psplay_new("pap"));
   psplay_insert (&root, psplay_new("qux"));
 
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   PSplay f = psplay_find (&root, "baz");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   f = psplay_find (&root, "test");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   f = psplay_find (&root, "test");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   f = psplay_find (&root, "foo");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
 
   psplay_delete (psplay_remove (&root, root.tree));
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   psplay_delete (psplay_remove (&root, root.tree));
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   psplay_delete (psplay_remove (&root, root.tree));
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   printf ("destroying\n");
   psplay_destroy_root (&root);
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   psplay_delete (psplay_remove (&root, root.tree));
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   psplay_delete (psplay_remove (&root, root.tree));
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
 
   psplay_delete (psplay_remove (&root, root.tree));
-  psplay_dump (root.tree, stdout, 0);
+  psplay_dump (&root, stdout);
   return 0;
 }
 #endif

diff --git a/psplay.h b/psplay.h
index b337dba..e2c38b8 100644 (file)
--- a/psplay.h
+++ b/psplay.h
@@ -27,6 +27,13 @@
 #include <stdint.h>
 #include <stdio.h>
 
+enum psplay_order_e
+  {
+    PSPLAY_PREORDER,
+    PSPLAY_INORDER,
+    PSPLAY_POSTORDER
+  };
+
 typedef struct psplayroot_struct psplayroot;
 typedef psplayroot* PSplayroot;
 
@@ -35,6 +42,7 @@ typedef psplay* PSplay;
 
 typedef int (*psplay_cmp_t)(const void*, const void*);
 typedef void (*psplay_delete_t)(PSplay);
+typedef psplay_delete_t (*psplay_action_t)(PSplay node, const enum psplay_order_e which, int level, void* data);
 
 //
 struct psplayroot_struct
@@ -83,7 +91,16 @@ psplay_find (PSplayroot root, void* key);
 PSplay
 psplay_remove (PSplayroot root, PSplay node);
 
+extern const psplay_delete_t PSPLAY_CONT;
+extern const psplay_delete_t PSPLAY_STOP;
+extern const psplay_delete_t PSPLAY_REMOVE;
+
+int
+psplay_walk (PSplayroot root, PSplay node, psplay_action_t action, int level, void* data);
+
+
 void
-psplay_dump (PSplay root, FILE* dest, unsigned level);
+psplay_dump (PSplayroot root, FILE* dest);
+
 
 #endif