psplay.c File Reference

Go to the source code of this file.

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>

Classes
struct	psplaytrail

Macros
#define	PSPLAY_FORMULA   (self->log2*100/(depth + (psplay_fast_prng () & 63)) + trail->dir) * splayfactor
#define	PSPLAY_PROB_ZIGZAG   2500
#define	PSPLAY_PROB_ZIGZIG   5000
#define	PSPLAY_TRAIL_DEPTH   128

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)
static uint32_t	psplay_fast_prng ()
PSplaynode	psplay_find (PSplay self, const void *key, int splayfactor)
	Find a element in a splay tree. More...
static int	psplay_handle (PSplay self, PSplaynode node, psplay_delete_fn res)
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...
PSplay	psplay_new (psplay_cmp_fn cmp, psplay_key_fn key, psplay_delete_fn del)
	Allocate a splay tree. More...
static psplay_delete_fn	psplay_print_node (PSplaynode node, const enum psplay_order_enum which, int level, void *data)
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...
static void	psplay_splay (PSplay self, struct psplaytrail *trail, unsigned splayfactor)
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...
static unsigned	trailidx (unsigned n)

Variables
const psplay_delete_fn	PSPLAY_CONT = (psplay_delete_fn)0x0
const psplay_delete_fn	PSPLAY_REMOVE = (psplay_delete_fn)0x2
const psplay_delete_fn	PSPLAY_STOP = (psplay_delete_fn)0x1

---

Class Documentation

psplaytrail

struct psplaytrail

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

Collaboration diagram for psplaytrail:

Function Documentation

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