Electroneum
rbtree.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  rbnode_type
 
struct  rbtree_type
 

Macros

#define RBTREE_NULL   &rbtree_null_node
 
#define RBTREE_FOR(node, type, rbtree)
 

Typedefs

typedef struct rbnode_type rbnode_type
 
typedef struct rbtree_type rbtree_type
 

Functions

rbtree_typerbtree_create (int(*cmpf)(const void *, const void *))
 
void rbtree_init (rbtree_type *rbtree, int(*cmpf)(const void *, const void *))
 
rbnode_typerbtree_insert (rbtree_type *rbtree, rbnode_type *data)
 
rbnode_typerbtree_delete (rbtree_type *rbtree, const void *key)
 
rbnode_typerbtree_search (rbtree_type *rbtree, const void *key)
 
int rbtree_find_less_equal (rbtree_type *rbtree, const void *key, rbnode_type **result)
 
rbnode_typerbtree_first (rbtree_type *rbtree)
 
rbnode_typerbtree_last (rbtree_type *rbtree)
 
rbnode_typerbtree_next (rbnode_type *rbtree)
 
rbnode_typerbtree_previous (rbnode_type *rbtree)
 
void traverse_postorder (rbtree_type *tree, void(*func)(rbnode_type *, void *), void *arg)
 

Variables

rbnode_type rbtree_null_node
 

Detailed Description

Red black tree. Implementation taken from NSD 3.0.5, adjusted for use in unbound (memory allocation, logging and so on).

Definition in file rbtree.h.

Macro Definition Documentation

◆ RBTREE_FOR

#define RBTREE_FOR (   node,
  type,
  rbtree 
)
Value:
for(node=(type)rbtree_first(rbtree); \
(rbnode_type*)node != RBTREE_NULL; \
node = (type)rbtree_next((rbnode_type*)node))
rbnode_type * rbtree_next(rbnode_type *rbtree)
rbnode_type * rbtree_first(rbtree_type *rbtree)
#define RBTREE_NULL
Definition: rbtree.h:69

Call with node=variable of struct* with rbnode_type as first element. with type is the type of a pointer to that struct.

Definition at line 173 of file rbtree.h.

◆ RBTREE_NULL

#define RBTREE_NULL   &rbtree_null_node

The nullpointer, points to empty node

Definition at line 69 of file rbtree.h.

Typedef Documentation

◆ rbnode_type

typedef struct rbnode_type rbnode_type

This structure must be the first member of the data structure in the rbtree. This allows easy casting between an rbnode_type and the user data (poor man's inheritance).

Definition at line 51 of file rbtree.h.

◆ rbtree_type

typedef struct rbtree_type rbtree_type

An entire red black tree

Definition at line 74 of file rbtree.h.

Function Documentation

◆ rbtree_create()

rbtree_type* rbtree_create ( int(*)(const void *, const void *)  cmpf)

Create new tree (malloced) with given key compare function.

Parameters
cmpfcompare function (like strcmp) takes pointers to two keys.
Returns
: new tree, empty.

◆ rbtree_delete()

rbnode_type* rbtree_delete ( rbtree_type rbtree,
const void *  key 
)

Delete element from tree.

Parameters
rbtreetree to delete from.
keykey of item to delete.
Returns
: node that is now unlinked from the tree. User to delete it. returns 0 if node not present

◆ rbtree_find_less_equal()

int rbtree_find_less_equal ( rbtree_type rbtree,
const void *  key,
rbnode_type **  result 
)

Find, but match does not have to be exact.

Parameters
rbtreetree to find in.
keykey to find position of.
resultset to the exact node if present, otherwise to element that precedes the position of key in the tree. NULL if no smaller element.
Returns
: true if exact match in result. Else result points to <= element, or NULL if key is smaller than the smallest key.

◆ rbtree_first()

rbnode_type* rbtree_first ( rbtree_type rbtree)

Returns first (smallest) node in the tree

Parameters
rbtreetree
Returns
: smallest element or NULL if tree empty.

◆ rbtree_init()

void rbtree_init ( rbtree_type rbtree,
int(*)(const void *, const void *)  cmpf 
)

Init a new tree (malloced by caller) with given key compare function.

Parameters
rbtreeuninitialised memory for new tree, returned empty.
cmpfcompare function (like strcmp) takes pointers to two keys.

◆ rbtree_insert()

rbnode_type* rbtree_insert ( rbtree_type rbtree,
rbnode_type data 
)

Insert data into the tree.

Parameters
rbtreetree to insert to.
dataelement to insert.
Returns
: data ptr or NULL if key already present.

◆ rbtree_last()

rbnode_type* rbtree_last ( rbtree_type rbtree)

Returns last (largest) node in the tree

Parameters
rbtreetree
Returns
: largest element or NULL if tree empty.

◆ rbtree_next()

rbnode_type* rbtree_next ( rbnode_type rbtree)

Returns next larger node in the tree

Parameters
rbtreetree
Returns
: next larger element or NULL if no larger in tree.

◆ rbtree_previous()

rbnode_type* rbtree_previous ( rbnode_type rbtree)

Returns previous smaller node in the tree

Parameters
rbtreetree
Returns
: previous smaller element or NULL if no previous in tree.

◆ rbtree_search()

rbnode_type* rbtree_search ( rbtree_type rbtree,
const void *  key 
)

Find key in tree. Returns NULL if not found.

Parameters
rbtreetree to find in.
keykey that must match.
Returns
: node that fits or NULL.

◆ traverse_postorder()

void traverse_postorder ( rbtree_type tree,
void(*)(rbnode_type *, void *)  func,
void *  arg 
)

Call function for all elements in the redblack tree, such that leaf elements are called before parent elements. So that all elements can be safely free()d. Note that your function must not remove the nodes from the tree. Since that may trigger rebalances of the rbtree.

Parameters
treethe tree
funcfunction called with element and user arg. The function must not alter the rbtree.
arguser argument.

Variable Documentation

◆ rbtree_null_node

rbnode_type rbtree_null_node

the global empty node