APPEND/PREPEND commands
[rxpd] / psplay.c
index d4fdd9d..9b26fa1 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)
 {
@@ -101,7 +99,7 @@ psplay_splay (PSplay* root, PSplay node)
               if (node == p->left)
                 {
                   // zigzig
-                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZIG)
+                  if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZIG)
                     return;
 
                   g->left = p->right;
@@ -118,7 +116,7 @@ psplay_splay (PSplay* root, PSplay node)
               else
                 {
                   // zigzag
-                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZAG)
+                  if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZAG)
                     return;
 
                   p->right = node->left;
@@ -139,7 +137,7 @@ psplay_splay (PSplay* root, PSplay node)
               if (node == p->left)
                 {
                   // zagzig
-                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZAG)
+                  if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZAG)
                     return;
 
                   p->left = node->right;
@@ -156,7 +154,7 @@ psplay_splay (PSplay* root, PSplay node)
               else
                 {
                   // zagzag
-                  if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZIG)
+                  if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZIG)
                     return;
 
                   g->right = p->left;
@@ -189,7 +187,7 @@ psplay_splay (PSplay* root, PSplay node)
         {
           if (p)
             {
-              if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIG)
+              if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIG)
                 return;
 
               if (node == p->left)
@@ -230,6 +228,7 @@ psplay_init (PSplay self, const void* key)
       self->key = key;
       self->up = self->left = self->right = NULL;
     }
+  return self;
 }
 
 void
@@ -384,19 +383,117 @@ 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)
+{
+  FILE* fh = 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)
+    {
+      if (which == PSPLAY_PREORDER)
+        fprintf (fh, "%s ...\n", sp+40-level);
+      return PSPLAY_CONT;
+    }
+
+  switch (which)
+    {
+    case PSPLAY_PREORDER:
+      fprintf (fh, "%s%p\n", sp+40-level, node);
+      fprintf (fh, "%skey %p (%.4s)\n", sp+40-level, (char*)node->key, node->key?(char*)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 +516,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);
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  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);
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  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);
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  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);
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  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