APPEND/PREPEND commands
[rxpd] / psplay.c
index b9c7fe1..9b26fa1 100644 (file)
--- a/psplay.c
+++ b/psplay.c
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
-
-/* simple prng with 2^31-1 cycle */
-static inline uint32_t psplay_fast_prng ()
-{
-  static uint32_t rnd=0xbabeface;
-  return rnd = rnd<<1 ^ ((rnd >> 30) & 1) ^ ((rnd>>2) & 1);
-}
-
-
 /*
   probabilistic distribution as n/255 chance of splaying
 */
@@ -50,8 +41,50 @@ static inline uint32_t psplay_fast_prng ()
 #define PSPLAY_PROB_ZIGZAG 224
 #endif
 
+
+
+/* simple prng with 2^31-1 cycle */
+static inline uint32_t psplay_fast_prng ()
+{
+  static uint32_t rnd=0xbabeface;
+  return rnd = rnd<<1 ^ ((rnd >> 30) & 1) ^ ((rnd>>2) & 1);
+}
+
+
+PSplayroot
+psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete)
+{
+  if (self)
+    {
+      self->tree = NULL;
+      self->cmp = cmp;
+      self->delete = delete;
+      self->elem_cnt = 0;
+    }
+  return self;
+}
+
+
+PSplayroot
+psplay_destroy_root (PSplayroot self)
+{
+  if (self) while (self->tree)
+    {
+      PSplay n = psplay_remove (self, self->tree);
+      if (self->delete)
+        self->delete (n);
+    }
+  return self;
+}
+
+
+
+
+
+
+//
 inline void
-psplay_splay (PSplay_ref root, PSplay node)
+psplay_splay (PSplay* root, PSplay node)
 {
   while (node->up)
     {
@@ -66,7 +99,7 @@ psplay_splay (PSplay_ref 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;
@@ -83,7 +116,7 @@ psplay_splay (PSplay_ref 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;
@@ -104,7 +137,7 @@ psplay_splay (PSplay_ref 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;
@@ -121,7 +154,7 @@ psplay_splay (PSplay_ref 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;
@@ -154,7 +187,7 @@ psplay_splay (PSplay_ref 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)
@@ -188,13 +221,14 @@ psplay_new (void * key)
 
 
 PSplay
-psplay_init (PSplay self, void* key)
+psplay_init (PSplay self, const void* key)
 {
   if (self)
     {
       self->key = key;
       self->up = self->left = self->right = NULL;
     }
+  return self;
 }
 
 void
@@ -205,18 +239,18 @@ psplay_delete (PSplay node)
 
 
 PSplay
-psplay_insert (PSplay_ref root, PSplay node, psplay_cmp_t cmp)
+psplay_insert (PSplayroot root, PSplay node)
 {
-  PSplay n = *root;
+  PSplay n = root->tree;
 
   if (!n)
-    *root = node;
+    root->tree = node;
   else
     {
       while (n != node)
         {
           int c;
-          c = cmp (node->key, n->key);
+          c = root->cmp (node->key, n->key);
 
           if (c < 0)
             {
@@ -239,21 +273,22 @@ psplay_insert (PSplay_ref root, PSplay node, psplay_cmp_t cmp)
           else
             return NULL;
         }
-      psplay_splay (root, node);
+      psplay_splay (&root->tree, node);
     }
+  ++root->elem_cnt;
   return node;
 }
 
 
 PSplay
-psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp)
+psplay_find (PSplayroot root, void* key)
 {
-  PSplay node = *root;
+  PSplay node = root->tree;
 
   while (node)
     {
       int c;
-      c = cmp (key, node->key);
+      c = root->cmp (key, node->key);
 
       if (c < 0)
           node = node->left;
@@ -261,7 +296,7 @@ psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp)
           node = node->right;
       else
         {
-          psplay_splay (root, node);
+          psplay_splay (&root->tree, node);
           break;
         }
     }
@@ -270,12 +305,12 @@ psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp)
 
 
 PSplay
-psplay_remove (PSplay_ref root, PSplay node)
+psplay_remove (PSplayroot root, PSplay node)
 {
   if (!node) return NULL;
 
   PSplay p = node->up;
-  PSplay_ref r;
+  PSplay* r;
 
   if (p)
     {
@@ -285,7 +320,7 @@ psplay_remove (PSplay_ref root, PSplay node)
         r = &p->right;
     }
   else
-    r = root;
+    r = &root->tree;
 
   if (!node->left)
     {
@@ -343,81 +378,184 @@ psplay_remove (PSplay_ref root, PSplay node)
       i->up = node->up;
       *r = i;
     }
+  node->up = node->left = node->right = NULL;
+  --root->elem_cnt;
   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)
 {
   return strcmp (a, b);
 }
 
+
+#ifdef PSPLAY_TESTMAIN
 int
 main ()
 {
-  PSplay tree = NULL;
+  psplayroot root = PSPLAYROOT_INITIALIZER(my_cmp, NULL);
+  psplay_init_root (&root, my_cmp, psplay_delete);
+
+  psplay_insert (&root, psplay_new("foo"));
+  psplay_insert (&root, psplay_new("bar"));
+  psplay_insert (&root, psplay_new("baz"));
+  psplay_insert (&root, psplay_new("test"));
+  psplay_insert (&root, psplay_new("pap"));
+  psplay_insert (&root, psplay_new("qux"));
 
-  psplay_insert (&tree, psplay_new("foo"), my_cmp);
-  psplay_insert (&tree, psplay_new("bar"), my_cmp);
-  psplay_insert (&tree, psplay_new("baz"), my_cmp);
-  psplay_insert (&tree, psplay_new("test"), my_cmp);
-  psplay_insert (&tree, psplay_new("pap"), my_cmp);
-  psplay_insert (&tree, psplay_new("qux"), my_cmp);
+  psplay_dump (&root, stdout);
 
-  psplay_dump (tree, stdout, 0);
+  PSplay f = psplay_find (&root, "baz");
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  psplay_dump (&root, stdout);
 
-  PSplay f = psplay_find (&tree, "baz", my_cmp);
-  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
+  f = psplay_find (&root, "test");
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  psplay_dump (&root, stdout);
 
-  f = psplay_find (&tree, "test", my_cmp);
-  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
+  f = psplay_find (&root, "test");
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  psplay_dump (&root, stdout);
 
-  f = psplay_find (&tree, "test", my_cmp);
-  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
+  f = psplay_find (&root, "foo");
+  printf ("found %p (%.4s)\n", f, f->key?(char*)f->key:"NULL");
+  psplay_dump (&root, stdout);
 
-  f = psplay_find (&tree, "foo", my_cmp);
-  printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
 
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (&root, stdout);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (&root, stdout);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (&root, stdout);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  printf ("destroying\n");
+  psplay_destroy_root (&root);
+  psplay_dump (&root, stdout);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (&root, stdout);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (&root, stdout);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (&root, stdout);
   return 0;
 }
-*/
+#endif