lib/psplay.h File Reference
Detailed Description
Probabilistic splay trees A splay trees is self-optimizing (in contrast to self-balancing) datastructure.We introduce here a probabilistic bottom up approach which reduces the splay costs. Without affecting the performance. The randomization gives also some insurance that worst case situations are extremely unlikely. Tree nodes are very small (just 2 pointers) and are intrusively placed into the users datastructure.
Definition in file psplay.h.
#include <stdint.h>
#include <stdio.h>
Include dependency graph for psplay.h:
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
Classes | |
| struct | psplay_struct |
| struct | psplaynode_struct |
Defines | |
| #define | PSPLAYNODE_INITIALIZER {NULL, NULL} |
Typedefs | |
| typedef psplay * | PSplay |
| typedef struct psplay_struct | psplay |
| Type and handle for a psplay root structure This structure shall be treated opaque, its only defined in the header to allow one to integrate it directly instead referencing it. | |
| typedef psplay_delete_fn(* | psplay_action_fn )(PSplaynode node, const enum psplay_order_enum which, int level, void *data) |
| Traverse a splay tree Traversing a tree calls a user supplied action three times 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. | |
| typedef int(* | psplay_cmp_fn )(const void *a, const void *b) |
| Function use to compare keys. | |
| typedef void(* | psplay_delete_fn )(PSplaynode node) |
| Destructor for user defined data Called when an element got removed from a splay tree. | |
| typedef const void *(* | psplay_key_fn )(const PSplaynode node) |
| Retrieve the key from a user datastructure. | |
| typedef psplaynode * | PSplaynode |
| typedef struct psplaynode_struct | psplaynode |
| Type and handle for a psplay tree node This node have to be placed inside users data. | |
Enumerations | |
| enum | psplay_order_enum { PSPLAY_PREORDER, PSPLAY_INORDER, PSPLAY_POSTORDER } |
Functions | |
| void | psplay_delete (PSplay self) |
| Delete a splay tree Frees all elements and associated resources of a splay tree and then itseld. | |
| void | psplay_delete_key (PSplay self, void *key) |
| Delete a node by key from a splay tree. | |
| void | psplay_delete_node (PSplay self, PSplaynode node) |
| Delete a node from a splay tree. | |
| PSplay | psplay_destroy (PSplay self) |
| Destroy a splay tree Frees all elements and associated resources of a splay tree. | |
| void | psplay_dump (PSplay self, FILE *dest) |
| PSplaynode | psplay_find (PSplay self, const void *key, int splayfactor) |
| Find a element in a splay tree. | |
| PSplay | psplay_init (PSplay self, psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del) |
| Initialize a splay tree. | |
| PSplaynode | psplay_insert (PSplay self, PSplaynode node, int splayfactor) |
| Insert a element into a splay tree. | |
| static size_t | psplay_nelements (PSplay self) |
| Number of elements in tree. | |
| PSplay | psplay_new (psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del) |
| Allocate a splay tree. | |
| PSplaynode | psplay_remove (PSplay self, PSplaynode node) |
| Remove a node from a splay tree. | |
| PSplaynode | psplay_remove_key (PSplay self, void *key) |
| Remove a node by key from a splay tree. | |
| int | psplay_walk (PSplay self, PSplaynode node, psplay_action_fn action, int level, void *data) |
| Start a tree traversal. | |
| PSplaynode | psplaynode_init (PSplaynode self) |
| Initialize a splay tree node The user has to place this nodes within his datastructure and must initialize them before using them. | |
Variables | |
| const psplay_delete_fn | PSPLAY_CONT |
| const psplay_delete_fn | PSPLAY_REMOVE |
| const psplay_delete_fn | PSPLAY_STOP |
Typedef Documentation
| typedef struct psplaynode_struct psplaynode |
| typedef int(* psplay_cmp_fn)(const void *a, const void *b) |
| typedef void(* psplay_delete_fn)(PSplaynode node) |
Destructor for user defined data Called when an element got removed from a splay tree.
- Parameters:
-
node pointer to the intrusive node inside the users datastructure The user is responsible for casting 'node' back to his real datastructure (maybe with OFFSET_OF()), free all resources associated with it and finally free the datastructure itself.
| typedef const void*(* psplay_key_fn)(const PSplaynode node) |
| typedef struct psplay_struct psplay |
| typedef psplay_delete_fn(* psplay_action_fn)(PSplaynode node, const enum psplay_order_enum which, int level, void *data) |
Traverse a splay tree Traversing a tree calls a user supplied action three times 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.
- Parameters:
-
node pointer to the currently traversed node which state of the traversal: 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 shall return PSPLAY_CONT when the traversal of the tree shall continue. level depth of the node in the tree data user supplied data which is transparently passed around
- Returns:
- a pointer to a function which indicates how to proceed, there are three special return values predefined: PSPLAY_CONT - continue with the traversal PSPLAY_STOP - stop the traversal PSPLAY_REMOVE - stops the traversal and removes the current node, calling the delete handler any other psplay_delete_fn - stops the traversal and removes the current node, calling the returned delete handler with it
Function Documentation
| static size_t psplay_nelements | ( | PSplay | self | ) | [inline, static] |
Number of elements in tree.
- Parameters:
-
self pointer to the tree
- Returns:
- number of elements
Definition at line 110 of file psplay.h.
Referenced by lumiera_filedescriptor_registry_destroy().
Here is the caller graph for this function:
| PSplay psplay_init | ( | PSplay | self, | |
| psplay_cmp_fn | cmp, | |||
| psplay_key_fn | key, | |||
| psplay_delete_fn | del | |||
| ) |
| PSplay psplay_destroy | ( | PSplay | self | ) |
| PSplay psplay_new | ( | psplay_cmp_fn | cmp, | |
| psplay_key_fn | key, | |||
| psplay_delete_fn | del | |||
| ) |
| void psplay_delete | ( | PSplay | self | ) |
| PSplaynode psplaynode_init | ( | PSplaynode | self | ) |
| PSplaynode psplay_insert | ( | PSplay | self, | |
| PSplaynode | node, | |||
| int | splayfactor | |||
| ) |
Insert a element into a splay tree.
- Parameters:
-
self pointer to the splay tree node pointer to the node to be inserted splayfactor weight for the probabilistic splaying, 0 disables the splaying, 100 is the expected normal value use 100 when in doubt
- Returns:
- self or NULL when a node with same key already in the tree
| PSplaynode psplay_find | ( | PSplay | self, | |
| const void * | key, | |||
| int | splayfactor | |||
| ) |
Find a element in a splay tree.
- Parameters:
-
self pointer to the splay tree key pointer to the key to be searched splayfactor weight for the probabilistic splaying, 0 disables the splaying, 100 is the expected normal value
- Returns:
- found node or NULL if the key was not found in the tree
| PSplaynode psplay_remove | ( | PSplay | self, | |
| PSplaynode | node | |||
| ) |
Remove a node from a splay tree.
- Parameters:
-
self pointer to the splay tree node node to be removed
- Returns:
- pointer to the removed node removal is optimized for the case where one call it immediately after one did a psplay_find() as last operation on that tree
| PSplaynode psplay_remove_key | ( | PSplay | self, | |
| void * | key | |||
| ) |
| void psplay_delete_node | ( | PSplay | self, | |
| PSplaynode | node | |||
| ) |
| void psplay_delete_key | ( | PSplay | self, | |
| void * | key | |||
| ) |
| int psplay_walk | ( | PSplay | self, | |
| PSplaynode | node, | |||
| psplay_action_fn | action, | |||
| int | level, | |||
| void * | data | |||
| ) |
Start a tree traversal.
- Parameters:
-
self the tree to be traversed node pointer to root node where traversal shall start, use NULL for the whole tree action handler function as defined above level initial value for the level data user supplied data which is transparently passed to the action
- Returns:
- 0 when the tree traversal got aborted (by anything but PSPLAY_CONT as action handler return) 1 when the whole tree was traversed successfully
