made a psplayroot struct

psplayroot carries some metadata and makes the api more clean

diff --git a/psplay.c b/psplay.c
index b9c7fe1..47cb13c 100644 (file)
--- a/psplay.c
+++ b/psplay.c
@@ -25,15 +25,6 @@
 #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,52 @@ 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)
     {
@@ -205,18 +240,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 +274,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 +297,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 +306,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 +321,7 @@ psplay_remove (PSplay_ref root, PSplay node)
         r = &p->right;
     }
   else
-    r = root;
+    r = &root->tree;
 
   if (!node->left)
     {
@@ -343,10 +379,11 @@ 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)
 {
@@ -361,63 +398,67 @@ psplay_dump (PSplay root, FILE* dest, unsigned level)
   psplay_dump (root->right, dest, level+3);
   if (level == 0) 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 (&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_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_dump (tree, stdout, 0);
+  psplay_dump (root.tree, stdout, 0);
 
-  PSplay f = psplay_find (&tree, "baz", my_cmp);
+  PSplay f = psplay_find (&root, "baz");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
+  psplay_dump (root.tree, stdout, 0);
 
-  f = psplay_find (&tree, "test", my_cmp);
+  f = psplay_find (&root, "test");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
+  psplay_dump (root.tree, stdout, 0);
 
-  f = psplay_find (&tree, "test", my_cmp);
+  f = psplay_find (&root, "test");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
+  psplay_dump (root.tree, stdout, 0);
 
-  f = psplay_find (&tree, "foo", my_cmp);
+  f = psplay_find (&root, "foo");
   printf ("found %p (%.4s)\n", f, f->key?f->key:"NULL");
-  psplay_dump (tree, stdout, 0);
+  psplay_dump (root.tree, stdout, 0);
+
 
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (root.tree, stdout, 0);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (root.tree, stdout, 0);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (root.tree, stdout, 0);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  printf ("destroying\n");
+  psplay_destroy_root (&root);
+  psplay_dump (root.tree, stdout, 0);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (root.tree, stdout, 0);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (root.tree, stdout, 0);
 
-  psplay_delete (psplay_remove (&tree, tree));
-  psplay_dump (tree, stdout, 0);
+  psplay_delete (psplay_remove (&root, root.tree));
+  psplay_dump (root.tree, stdout, 0);
   return 0;
 }
-*/
+#endif

diff --git a/psplay.h b/psplay.h
index d9645f7..a42cff5 100644 (file)
--- a/psplay.h
+++ b/psplay.h
@@ -27,10 +27,35 @@
 #include <stdint.h>
 #include <stdio.h>
 
+typedef struct psplayroot_struct psplayroot;
+typedef psplayroot* PSplayroot;
+
 typedef struct psplay_struct psplay;
 typedef psplay* PSplay;
-typedef PSplay* PSplay_ref;
 
+typedef int (*psplay_cmp_t)(const void*, const void*);
+typedef void (*psplay_delete_t)(PSplay);
+
+//
+struct psplayroot_struct
+{
+  PSplay tree;
+  psplay_cmp_t cmp;
+  psplay_delete_t delete;
+  /* amount of elements will some day adjust the probability fucntions, further research necessary */
+  size_t elem_cnt;
+  /* PSplay history[64]; ringbuffer storing the path of a search, optimize 'up' pointer out */
+};
+
+PSplayroot
+psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete);
+
+PSplayroot
+psplay_destroy_root (PSplayroot self);
+
+#define PSPLAYROOT_INITIALIZER(cmp, delete) {NULL, cmp, delete, 0}
+
+//
 struct psplay_struct
 {
   void* key;
@@ -39,7 +64,6 @@ struct psplay_struct
   PSplay right;
 };
 
-typedef int (*psplay_cmp_t)(const void*, const void*);
 
 PSplay
 psplay_new (void * key);
@@ -51,17 +75,15 @@ void
 psplay_delete (PSplay node);
 
 PSplay
-psplay_insert (PSplay_ref root, PSplay node, psplay_cmp_t cmp);
+psplay_insert (PSplayroot root, PSplay node);
 
 PSplay
-psplay_find (PSplay_ref root, void* key, psplay_cmp_t cmp);
+psplay_find (PSplayroot root, void* key);
 
 PSplay
-psplay_remove (PSplay_ref root, PSplay node);
+psplay_remove (PSplayroot root, PSplay node);
 
-/*
 void
 psplay_dump (PSplay root, FILE* dest, unsigned level);
-*/
 
 #endif