#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
*/
#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)
{
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;
else
{
// zigzag
- if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZAG)
+ if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZAG)
return;
p->right = node->left;
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;
else
{
// zagzag
- if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIGZIG)
+ if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIGZIG)
return;
g->right = p->left;
{
if (p)
{
- if (psplay_fast_prng()&0xFF >= PSPLAY_PROB_ZIG)
+ if ((psplay_fast_prng()&0xFF) >= PSPLAY_PROB_ZIG)
return;
if (node == p->left)
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
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)
{
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;
node = node->right;
else
{
- psplay_splay (root, node);
+ psplay_splay (&root->tree, node);
break;
}
}
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)
{
r = &p->right;
}
else
- r = root;
+ r = &root->tree;
if (!node->left)
{
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
projects / rxpd / blobdiff