Lumiera
0.pre.03
»edit your freedom«
|
Go to the source code of this file.
Probabilistic splay tree.
A splay trees is self-optimising (in contrast to self-balancing) datastructure. We introduce here a probabilistic bottom up approach which reduces the splay costs. Without affecting the performance. The randomisation 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>
Classes | |
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. More... | |
struct | psplaynode |
Type and handle for a psplay tree node This node have to be placed inside users data. More... | |
Typedefs | |
typedef psplay * | 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. More... | |
typedef int(* | psplay_cmp_fn) (const void *a, const void *b) |
Function use to compare keys. More... | |
typedef void(* | psplay_delete_fn) (PSplaynode node) |
Destructor for user defined data Called when an element got removed from a splay tree. More... | |
typedef const void *(* | psplay_key_fn) (const PSplaynode node) |
Retrieve the key from a user datastructure. More... | |
typedef psplaynode * | PSplaynode |
Enumerations | |
enum | psplay_order_enum { PSPLAY_PREORDER, PSPLAY_INORDER, PSPLAY_POSTORDER } |
Macros | |
#define | PSPLAYNODE_INITIALIZER {NULL, NULL} |
Functions | |
void | psplay_delete (PSplay self) |
Delete a splay tree Frees all elements and associated resources of a splay tree and then itseld. More... | |
void | psplay_delete_key (PSplay self, void *key) |
Delete a node by key from a splay tree. More... | |
void | psplay_delete_node (PSplay self, PSplaynode node) |
Delete a node from a splay tree. More... | |
PSplay | psplay_destroy (PSplay self) |
Destroy a splay tree Frees all elements and associated resources of a splay tree. More... | |
void | psplay_dump (PSplay self, FILE *dest) |
PSplaynode | psplay_find (PSplay self, const void *key, int splayfactor) |
Find a element in a splay tree. More... | |
PSplay | psplay_init (PSplay self, psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del) |
Initialize a splay tree. More... | |
PSplaynode | psplay_insert (PSplay self, PSplaynode node, int splayfactor) |
Insert a element into a splay tree. More... | |
static size_t | psplay_nelements (PSplay self) |
Number of elements in tree. More... | |
PSplay | psplay_new (psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del) |
Allocate a splay tree. More... | |
PSplaynode | psplay_remove (PSplay self, PSplaynode node) |
Remove a node from a splay tree. More... | |
PSplaynode | psplay_remove_key (PSplay self, void *key) |
Remove a node by key from a splay tree. More... | |
int | psplay_walk (PSplay self, PSplaynode node, psplay_action_fn action, int level, void *data) |
Start a tree traversal. More... | |
PSplaynode | psplaynode_init (PSplaynode self) |
Initialise a splay tree node The user has to place this nodes within his datastructure and must Initialise them before using them. More... | |
Variables | |
const psplay_delete_fn | PSPLAY_CONT |
const psplay_delete_fn | PSPLAY_REMOVE |
const psplay_delete_fn | PSPLAY_STOP |
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.
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 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.
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 |
struct psplay_struct |
Class Members | ||
---|---|---|
PSplaynode | tree | |
PSplaynode * | found_parent | |
psplay_cmp_fn | cmp | |
psplay_key_fn | key | |
psplay_delete_fn | del | |
size_t | elem_cnt | |
unsigned | log2 |
struct psplaynode_struct |
|
inlinestatic |
Number of elements in tree.
self | pointer to the tree |
Definition at line 103 of file psplay.h.
References psplay_init().
PSplay psplay_init | ( | PSplay | self, |
psplay_cmp_fn | cmp, | ||
psplay_key_fn | key, | ||
psplay_delete_fn | del | ||
) |
Initialize a splay tree.
self | pointer to the psplay structure |
cmp | user supplied compare function |
key | user supplied function to retrieve a key |
delete | user supplied destructor function or NULL if no destructor is necessary |
Definition at line 66 of file psplay.c.
Referenced by lumiera_config_lookup_init(), and psplay_nelements().
PSplay psplay_destroy | ( | PSplay | self | ) |
Destroy a splay tree Frees all elements and associated resources of a splay tree.
self | pointer to the psplay structure |
Definition at line 101 of file psplay.c.
References psplay_remove().
Referenced by lumiera_config_lookup_destroy(), and psplay_delete().
PSplay psplay_new | ( | psplay_cmp_fn | cmp, |
psplay_key_fn | key, | ||
psplay_delete_fn | del | ||
) |
void psplay_delete | ( | PSplay | self | ) |
Delete a splay tree Frees all elements and associated resources of a splay tree and then itseld.
self | pointer to the psplay structure |
Definition at line 115 of file psplay.c.
References psplay_destroy().
PSplaynode psplaynode_init | ( | PSplaynode | self | ) |
Initialise a splay tree node The user has to place this nodes within his datastructure and must Initialise them before using them.
self | pointer to the node to be initialised |
Definition at line 122 of file psplay.c.
Referenced by lumiera_plugin_new().
PSplaynode psplay_insert | ( | PSplay | self, |
PSplaynode | node, | ||
int | splayfactor | ||
) |
Insert a element into a splay tree.
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 |
PSplaynode psplay_find | ( | PSplay | self, |
const void * | key, | ||
int | splayfactor | ||
) |
Find a element in a splay tree.
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 |
Definition at line 300 of file psplay.c.
Referenced by lumiera_config_lookup_find(), and psplay_remove_key().
PSplaynode psplay_remove | ( | PSplay | self, |
PSplaynode | node | ||
) |
Remove a node from a splay tree.
self | pointer to the splay tree |
node | node to be removed |
Definition at line 340 of file psplay.c.
Referenced by psplay_destroy(), and psplay_remove_key().
PSplaynode psplay_remove_key | ( | PSplay | self, |
void * | key | ||
) |
Remove a node by key from a splay tree.
self | pointer to the splay tree |
key | key of the node to be removed |
Definition at line 391 of file psplay.c.
References psplay_find(), and psplay_remove().
void psplay_delete_node | ( | PSplay | self, |
PSplaynode | node | ||
) |
Delete a node from a splay tree.
self | pointer to the splay tree |
node | node to be removed Calls the registered delete handler, frees all resources. |
Definition at line 398 of file psplay.c.
Referenced by lumiera_config_lookup_remove().
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.
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 |