Lumiera  0.pre.03
»edit your freedom«
psplay.h File Reference

Go to the source code of this file.

Description

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 Documentation

◆ psplay_cmp_fn

typedef int(* psplay_cmp_fn) (const void *a, const void *b)

Function use to compare keys.

Parameters
afirst key
bsecond key
Returns
shall return -1/0/1 when a is less than/equal to/biggier than b.

Definition at line 55 of file psplay.h.

◆ psplay_delete_fn

typedef void(* psplay_delete_fn) (PSplaynode node)

Destructor for user defined data Called when an element got removed from a splay tree.

Parameters
nodepointer 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.

Definition at line 65 of file psplay.h.

◆ psplay_key_fn

typedef const void*(* psplay_key_fn) (const PSplaynode node)

Retrieve the key from a user datastructure.

Parameters
nodepointer to the intrusive node inside the users datastructure This functiom must return a pointer to the key under which the user stores his data.

Definition at line 73 of file psplay.h.

◆ psplay_action_fn

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
nodepointer to the currently traversed node
whichstate 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.
leveldepth of the node in the tree
datauser 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

Definition at line 256 of file psplay.h.


Class Documentation

◆ psplay_struct

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
+ Collaboration diagram for psplay:

◆ psplaynode_struct

struct psplaynode_struct
Class Members
PSplaynode left
PSplaynode right
+ Collaboration diagram for psplaynode:

Function Documentation

◆ psplay_nelements()

static size_t psplay_nelements ( PSplay  self)
inlinestatic

Number of elements in tree.

Parameters
selfpointer to the tree
Returns
number of elements

Definition at line 103 of file psplay.h.

References psplay_init().

+ Here is the call graph for this function:

◆ psplay_init()

PSplay psplay_init ( PSplay  self,
psplay_cmp_fn  cmp,
psplay_key_fn  key,
psplay_delete_fn  del 
)

Initialize a splay tree.

Parameters
selfpointer to the psplay structure
cmpuser supplied compare function
keyuser supplied function to retrieve a key
deleteuser supplied destructor function or NULL if no destructor is necessary
Returns
self

Definition at line 66 of file psplay.c.

Referenced by lumiera_config_lookup_init(), and psplay_nelements().

+ Here is the caller graph for this function:

◆ psplay_destroy()

PSplay psplay_destroy ( PSplay  self)

Destroy a splay tree Frees all elements and associated resources of a splay tree.

Parameters
selfpointer to the psplay structure
Returns
self

Definition at line 101 of file psplay.c.

References psplay_remove().

Referenced by lumiera_config_lookup_destroy(), and psplay_delete().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ psplay_new()

PSplay psplay_new ( psplay_cmp_fn  cmp,
psplay_key_fn  key,
psplay_delete_fn  del 
)

Allocate a splay tree.

Parameters
cmpuser supplied compare function
keyuser supplied function to retrieve a key
deleteuser supplied destructor function or NULL if no destructor is necessary
Returns
allcoated splay tree or NULL on error

Definition at line 88 of file psplay.c.

◆ psplay_delete()

void psplay_delete ( PSplay  self)

Delete a splay tree Frees all elements and associated resources of a splay tree and then itseld.

Parameters
selfpointer to the psplay structure

Definition at line 115 of file psplay.c.

References psplay_destroy().

+ Here is the call graph for this function:

◆ psplaynode_init()

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.

Parameters
selfpointer to the node to be initialised
Returns
self

Definition at line 122 of file psplay.c.

Referenced by lumiera_plugin_new().

+ Here is the caller graph for this function:

◆ psplay_insert()

PSplaynode psplay_insert ( PSplay  self,
PSplaynode  node,
int  splayfactor 
)

Insert a element into a splay tree.

Parameters
selfpointer to the splay tree
nodepointer to the node to be inserted
splayfactorweight 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

Definition at line 246 of file psplay.c.

◆ psplay_find()

PSplaynode psplay_find ( PSplay  self,
const void *  key,
int  splayfactor 
)

Find a element in a splay tree.

Parameters
selfpointer to the splay tree
keypointer to the key to be searched
splayfactorweight 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

Definition at line 300 of file psplay.c.

Referenced by lumiera_config_lookup_find(), and psplay_remove_key().

+ Here is the caller graph for this function:

◆ psplay_remove()

PSplaynode psplay_remove ( PSplay  self,
PSplaynode  node 
)

Remove a node from a splay tree.

Parameters
selfpointer to the splay tree
nodenode to be removed
Returns
pointer to the removed node removal is optimised for the case where one call it immediately after one did a psplay_find() as last operation on that tree

Definition at line 340 of file psplay.c.

Referenced by psplay_destroy(), and psplay_remove_key().

+ Here is the caller graph for this function:

◆ psplay_remove_key()

PSplaynode psplay_remove_key ( PSplay  self,
void *  key 
)

Remove a node by key from a splay tree.

Parameters
selfpointer to the splay tree
keykey of the node to be removed
Returns
pointer to the removed node

Definition at line 391 of file psplay.c.

References psplay_find(), and psplay_remove().

+ Here is the call graph for this function:

◆ psplay_delete_node()

void psplay_delete_node ( PSplay  self,
PSplaynode  node 
)

Delete a node from a splay tree.

Parameters
selfpointer to the splay tree
nodenode 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().

+ Here is the caller graph for this function:

◆ psplay_delete_key()

void psplay_delete_key ( PSplay  self,
void *  key 
)

Delete a node by key from a splay tree.

Parameters
selfpointer to the splay tree
keykey of the node to be removed Calls the registered delete handler, frees all resources.

Definition at line 406 of file psplay.c.

◆ psplay_walk()

int psplay_walk ( PSplay  self,
PSplaynode  node,
psplay_action_fn  action,
int  level,
void *  data 
)

Start a tree traversal.

Parameters
selfthe tree to be traversed
nodepointer to root node where traversal shall start, use NULL for the whole tree
actionhandler function as defined above
levelinitial value for the level
datauser 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

Definition at line 442 of file psplay.c.