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

a	first key
b	second key

Returns

shall return -1/0/1 when a is less than/equal to/biggier than b.

Definition at line 64 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

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.

Definition at line 74 of file psplay.h.

psplay_key_fn

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

Retrieve the key from a user datastructure.

Parameters

node	pointer 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 82 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

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

Definition at line 265 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

self	pointer to the tree

Returns

number of elements

Definition at line 112 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

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

Returns

self

Definition at line 75 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

self	pointer to the psplay structure

Returns

self

Definition at line 110 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

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

Returns

allcoated splay tree or NULL on error

Definition at line 97 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

self	pointer to the psplay structure

Definition at line 124 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

self	pointer to the node to be initialised

Returns

self

Definition at line 131 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

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

Definition at line 255 of file psplay.c.

psplay_find()

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

Definition at line 309 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

self	pointer to the splay tree
node	node 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 349 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

self	pointer to the splay tree
key	key of the node to be removed

Returns

pointer to the removed node

Definition at line 400 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

self	pointer to the splay tree
node	node to be removed Calls the registered delete handler, frees all resources.

Definition at line 407 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

self	pointer to the splay tree
key	key of the node to be removed Calls the registered delete handler, frees all resources.

Definition at line 415 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

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

Definition at line 451 of file psplay.c.