Lumiera  0.pre.03
»edit your freedom«
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
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 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
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 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
selfpointer 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
selfpointer 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
selfpointer 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
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 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
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 309 of file psplay.c.

Referenced by lumiera_config_lookup_find(), psplay_delete_key(), 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 349 of file psplay.c.

Referenced by psplay_delete_node(), 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 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
selfpointer to the splay tree
nodenode to be removed Calls the registered delete handler, frees all resources.

Definition at line 407 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
selfpointer to the splay tree
keykey of the node to be removed Calls the registered delete handler, frees all resources.

Definition at line 415 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
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 451 of file psplay.c.