psplay.h File Reference

Probabilistic splay tree. More...

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>

Macros
#define	PSPLAYNODE_INITIALIZER   {NULL, NULL}

Typedefs
typedef psplaynode *	PSplaynode
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 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.

Enumerations
enum	psplay_order_enum {   PSPLAY_PREORDER ,   PSPLAY_INORDER ,   PSPLAY_POSTORDER }

Classes
struct	psplaynode
	Type and handle for a psplay tree node This node have to be placed inside users data. More...
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...

Functions
static size_t	psplay_nelements (PSplay self)
	Number of elements in tree.
PSplay	psplay_init (PSplay self, psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del)
	Initialize a splay tree.
PSplay	psplay_destroy (PSplay self)
	Destroy a splay tree Frees all elements and associated resources of a splay tree.
PSplay	psplay_new (psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del)
	Allocate a splay tree.
void	psplay_delete (PSplay self)
	Delete a splay tree Frees all elements and associated resources of a splay tree and then itseld.
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.
PSplaynode	psplay_insert (PSplay self, PSplaynode node, int splayfactor)
	Insert a element into a splay tree.
PSplaynode	psplay_find (PSplay self, const void *key, int splayfactor)
	Find a element in 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.
void	psplay_delete_node (PSplay self, PSplaynode node)
	Delete a node from a splay tree.
void	psplay_delete_key (PSplay self, void *key)
	Delete 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.
void	psplay_dump (PSplay self, FILE *dest)

Variables
const psplay_delete_fn	PSPLAY_CONT
const psplay_delete_fn	PSPLAY_STOP
const psplay_delete_fn	PSPLAY_REMOVE

Typedef Documentation

PSplaynode

typedef psplaynode* PSplaynode

Definition at line 40 of file psplay.h.

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 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

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 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

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 73 of file psplay.h.

PSplay

typedef psplay* PSplay

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 256 of file psplay.h.

Enumeration Type Documentation

psplay_order_enum

enum psplay_order_enum

Enumerator
PSPLAY_PREORDER
PSPLAY_INORDER
PSPLAY_POSTORDER

Definition at line 228 of file psplay.h.

Macro Definition Documentation

PSPLAYNODE_INITIALIZER

#define PSPLAYNODE_INITIALIZER   {NULL, NULL}

Definition at line 47 of file psplay.h.

---

Class Documentation

psplaynode_struct

struct psplaynode_struct

Class Members
PSplaynode	left
PSplaynode	right

Collaboration diagram for psplaynode:

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:

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 103 of file psplay.h.

Referenced by lumiera_interfaceregistry_destroy().

Here is the caller 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 66 of file psplay.c.

References cmp, and NULL.

Referenced by lumiera_config_lookup_init(), psplay_new(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

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 101 of file psplay.c.

References psplay_remove().

Referenced by lumiera_config_lookup_destroy(), lumiera_interfaceregistry_destroy(), psplay_delete(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

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 88 of file psplay.c.

References cmp, and psplay_init().

Referenced by lumiera_interfaceregistry_init().

Here is the call graph for this function:

Here is the caller graph for this function:

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 115 of file psplay.c.

References psplay_destroy().

Referenced by lumiera_interfaceregistry_destroy(), and TEST().

Here is the call graph for this function:

Here is the caller 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 122 of file psplay.c.

References NULL.

Referenced by lumiera_config_lookupentry_init(), lumiera_interfacenode_new(), lumiera_plugin_new(), and testitem_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 246 of file psplay.c.

References psplaytrail::dir, NULL, psplay_splay(), psplaytrail::trail, and trailidx().

Referenced by lumiera_config_lookup_insert(), lumiera_config_lookup_insert_default(), lumiera_interfaceregistry_bulkregister_interfaces(), lumiera_interfaceregistry_register_interface(), lumiera_plugin_register(), TEST(), TEST(), TEST(), TEST(), and TEST().

Here is the call graph for this function:

Here is the caller graph for this function:

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 300 of file psplay.c.

References psplaytrail::dir, psplay_splay(), psplaytrail::trail, and trailidx().

Referenced by lumiera_config_lookup_find(), lumiera_config_lookup_insert(), lumiera_config_lookup_insert_default(), lumiera_interface_close(), lumiera_interfaceregistry_bulkremove_interfaces(), lumiera_interfaceregistry_interfacenode_find(), lumiera_interfaceregistry_remove_interface(), lumiera_plugin_discover(), lumiera_plugin_lookup(), psplay_delete_key(), psplay_remove(), psplay_remove_key(), TEST(), and TEST().

Here is the call graph for this function:

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 340 of file psplay.c.

References NULL, psplay_fast_prng(), and psplay_find().

Referenced by lumiera_interfaceregistry_bulkremove_interfaces(), lumiera_interfaceregistry_remove_interface(), lumiera_plugin_unload(), psplay_delete_node(), psplay_destroy(), psplay_handle(), psplay_remove_key(), and TEST().

Here is the call graph for this function:

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 391 of file psplay.c.

References psplay_find(), and psplay_remove().

Referenced by TEST().

Here is the call graph for this function:

Here is the caller 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 398 of file psplay.c.

References psplay_remove().

Referenced by lumiera_config_lookup_remove(), and psplay_delete_key().

Here is the call graph for this function:

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 406 of file psplay.c.

References psplay_delete_node(), and psplay_find().

Here is the call graph for this function:

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 442 of file psplay.c.

References psplay_handle(), PSPLAY_INORDER, PSPLAY_POSTORDER, PSPLAY_PREORDER, and psplay_walk().

Referenced by psplay_dump(), psplay_walk(), testitem_dump(), and testitem_graphvizdump().

Here is the call graph for this function:

Here is the caller graph for this function:

psplay_dump()

void psplay_dump	(	PSplay	self,
		FILE *	dest
	)

Definition at line 507 of file psplay.c.

References NULL, psplay_print_node(), and psplay_walk().

Referenced by TEST(), TEST(), TEST(), and TEST().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

PSPLAY_CONT

const psplay_delete_fn PSPLAY_CONT

extern

Definition at line 414 of file psplay.c.

Referenced by psplay_handle(), psplay_print_node(), testitem_graphvizprint_node(), and testitem_print_node().

PSPLAY_STOP

const psplay_delete_fn PSPLAY_STOP

extern

Definition at line 415 of file psplay.c.

Referenced by psplay_handle().

PSPLAY_REMOVE

const psplay_delete_fn PSPLAY_REMOVE

extern

Definition at line 416 of file psplay.c.

Referenced by psplay_handle().