}
-
-
-
PSplayroot
psplay_init_root (PSplayroot self, psplay_cmp_t cmp, psplay_delete_t delete)
{
return self;
}
+
PSplayroot
psplay_destroy_root (PSplayroot self)
{
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)
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