Probabilistic splay tree implementation. More...

Description

Probabilistic splay tree implementation.

Definition in file psplay.c.

#include "include/logging.h"
#include "lib/psplay.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <nobug.h>

Macros
#define	PSPLAY_TRAIL_DEPTH 128

#define	PSPLAY_FORMULA (self->log2100/(depth + (psplay_fast_prng () & 63)) + trail->dir) splayfactor

#define	PSPLAY_PROB_ZIGZIG 5000

#define	PSPLAY_PROB_ZIGZAG 2500

Classes
struct	psplaytrail

Functions
static uint32_t	psplay_fast_prng ()

PSplay	psplay_init (PSplay self, psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del)
	Initialize a splay tree.

PSplay	psplay_new (psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del)
	Allocate a splay tree.

PSplay	psplay_destroy (PSplay self)
	Destroy a splay tree Frees all elements and associated resources of 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.

static unsigned	trailidx (unsigned n)

static void	psplay_splay (PSplay self, struct psplaytrail *trail, unsigned splayfactor)

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.

static int	psplay_handle (PSplay self, PSplaynode node, psplay_delete_fn res)

int	psplay_walk (PSplay self, PSplaynode node, psplay_action_fn action, int level, void *data)
	Start a tree traversal.

static psplay_delete_fn	psplay_print_node (PSplaynode node, const enum psplay_order_enum which, int level, void *data)

void	psplay_dump (PSplay self, FILE *dest)

Variables
const psplay_delete_fn	PSPLAY_CONT = (psplay_delete_fn)0x0

const psplay_delete_fn	PSPLAY_STOP = (psplay_delete_fn)0x1

const psplay_delete_fn	PSPLAY_REMOVE = (psplay_delete_fn)0x2

Macro Definition Documentation

◆ PSPLAY_TRAIL_DEPTH

#define PSPLAY_TRAIL_DEPTH 128

Definition at line 31 of file psplay.c.

◆ PSPLAY_FORMULA

#define PSPLAY_FORMULA (self->log2*100/(depth + (psplay_fast_prng () & 63)) + trail->dir) * splayfactor

Definition at line 46 of file psplay.c.

◆ PSPLAY_PROB_ZIGZIG

#define PSPLAY_PROB_ZIGZIG 5000

Definition at line 49 of file psplay.c.

◆ PSPLAY_PROB_ZIGZAG

#define PSPLAY_PROB_ZIGZAG 2500

Definition at line 52 of file psplay.c.

Class Documentation

◆ psplaytrail

struct psplaytrail

Class Members
int	dir
unsigned	depth
PSplaynode *	trail[PSPLAY_TRAIL_DEPTH]

Collaboration diagram for psplaytrail:

Function Documentation

◆ psplay_fast_prng()

static uint32_t psplay_fast_prng ( )

inlinestatic

Definition at line 58 of file psplay.c.

Referenced by psplay_remove().

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

◆ trailidx()

static unsigned trailidx ( unsigned n )

inlinestatic

Definition at line 150 of file psplay.c.

References PSPLAY_TRAIL_DEPTH.

Referenced by psplay_find(), psplay_insert(), and psplay_splay().

Here is the caller graph for this function:

◆ psplay_splay()

static void psplay_splay	(	PSplay	self,
		struct psplaytrail *	trail,
		unsigned	splayfactor
	)

inlinestatic

Definition at line 157 of file psplay.c.

References psplaytrail::depth, psplaytrail::dir, PSPLAY_FORMULA, PSPLAY_PROB_ZIGZAG, PSPLAY_PROB_ZIGZIG, PSPLAY_TRAIL_DEPTH, psplaytrail::trail, and trailidx().

Referenced by psplay_find(), and psplay_insert().

Here is the call graph for this function:

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_handle()

static int psplay_handle	(	PSplay	self,
		PSplaynode	node,
		psplay_delete_fn	res
	)

static

Definition at line 419 of file psplay.c.

References PSPLAY_CONT, psplay_remove(), PSPLAY_REMOVE, and PSPLAY_STOP.

Referenced by psplay_walk().

Here is the call graph for this function:

Here is the caller 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_print_node()

static psplay_delete_fn psplay_print_node	(	PSplaynode	node,
		const enum psplay_order_enum	which,
		int	level,
		void *	data
	)

static

Definition at line 477 of file psplay.c.

References PSPLAY_CONT, PSPLAY_INORDER, PSPLAY_POSTORDER, and PSPLAY_PREORDER.

Referenced by psplay_dump().

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 = (psplay_delete_fn)0x0

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 = (psplay_delete_fn)0x1

Definition at line 415 of file psplay.c.

Referenced by psplay_handle().

◆ PSPLAY_REMOVE

const psplay_delete_fn PSPLAY_REMOVE = (psplay_delete_fn)0x2

Definition at line 416 of file psplay.c.

Referenced by psplay_handle().

Description

Macros

Classes

Functions

Variables

Macro Definition Documentation

◆ PSPLAY_TRAIL_DEPTH

◆ PSPLAY_FORMULA

◆ PSPLAY_PROB_ZIGZIG

◆ PSPLAY_PROB_ZIGZAG

Class Documentation

◆ psplaytrail

Function Documentation

◆ psplay_fast_prng()

◆ psplay_init()

◆ psplay_new()

◆ psplay_destroy()

◆ psplay_delete()

◆ psplaynode_init()

◆ trailidx()

◆ psplay_splay()

◆ psplay_insert()

◆ psplay_find()

◆ psplay_remove()

◆ psplay_remove_key()

◆ psplay_delete_node()

◆ psplay_delete_key()

◆ psplay_handle()

◆ psplay_walk()

◆ psplay_print_node()

◆ psplay_dump()

Variable Documentation

◆ PSPLAY_CONT

◆ PSPLAY_STOP

◆ PSPLAY_REMOVE