rbtree.h File Reference

Generic red-black tree. More...

#include <stdbool.h>
#include <stdint.h>
#include "datatypes.h"
#include "pool.h"

Go to the source code of this file.

Data Structures
struct	RBNode
	Structure holding node data. More...
struct	RBTree
	Red-black tree. More...
struct	RBTree::_RBTreePair
	Found key-value pair. More...
struct	RBTreeIterStackItem
	Structure holding a node and the iteration state. More...
struct	RBTreeIter
	Structure to iterate over the elements of a RBTree. More...

Macros
#define	rbtree_pair_key(p)   p->node->key
#define	rbtree_pair_value(p)   p->node->value
#define	rbtree_iter_key(iter)   iter.sp->node->key
#define	rbtree_iter_value(iter)   iter.sp->node->value

Typedefs
typedef struct _RBTreePair	RBTreePair

Enumerations
enum	RBTreeInsertResult { RBTREE_INSERT_RESULT_NEW , RBTREE_INSERT_RESULT_REPLACED , RBTREE_INSERT_RESULT_FAILED }
	result of rbtree_set() method. More...

Functions
RBTree *	rbtree_new (CompareFunc compare_keys, FreeFunc free_key, FreeFunc free_value, Pool *pool)
void	rbtree_init (RBTree *tree, CompareFunc compare_keys, FreeFunc free_key, FreeFunc free_value, Pool *pool)
void	rbtree_free (RBTree *tree)
void	rbtree_destroy (RBTree *tree)
void	rbtree_clear (RBTree *tree)
RBTreeInsertResult	rbtree_set (RBTree *tree, void *key, void *value, bool replace_key)
size_t	rbtree_count (const RBTree *tree)
RBTreePair *	rbtree_lookup (RBTree *tree, const void *key)
void *	rbtree_pair_get_key (const RBTreePair *pair)
void *	rbtree_pair_get_value (const RBTreePair *pair)
void	rbtree_pair_set_value (RBTreePair *pair, void *value)
bool	rbtree_key_exists (const RBTree *tree, const void *key)
bool	rbtree_remove (RBTree *tree, const void *key)
void	rbtree_iter_init (const RBTree *tree, RBTreeIter *iter)
void	rbtree_iter_free (RBTreeIter *iter)
void	rbtree_iter_reuse (const RBTree *tree, RBTreeIter *iter)
bool	rbtree_iter_next (RBTreeIter *iter)
void *	rbtree_iter_get_key (const RBTreeIter *iter)
void *	rbtree_iter_get_value (const RBTreeIter *iter)

Detailed Description

Generic red-black tree.

Author

Sebastian Fedrau sebas.nosp@m.tian.nosp@m..fedr.nosp@m.au@g.nosp@m.mail..nosp@m.com

Definition in file rbtree.h.

---

Data Structure Documentation

RBNode

struct RBNode

Structure holding node data.

Definition at line 35 of file rbtree.h.

Data Fields
bool	black	true if color is black.
void *	key	Key of the node.
struct _rbnode *	left	Left node or NULL.
struct _rbnode *	right	Right node or NULL.
void *	value	Value of the node.

RBTree

struct RBTree

Red-black tree.

Definition at line 53 of file rbtree.h.

Data Fields
CompareFunc	compare_keys	Function to compare two keys.
size_t	count	Number of stored items.
FreeFunc	free_key	Function to free a key.
FreeFunc	free_value	Function to free a value.
struct _RBTreePair	pair	Last found key-value pair.
Pool *	pool	An optional pool to create nodes.
RBNode *	root	The root node.
RBNode **	sp	The stack pointer.
RBNode **	stack	Stack used when traversing tree.
size_t	stack_size	Size of the stack.

RBTree::_RBTreePair

struct RBTree::_RBTreePair

Found key-value pair.

Definition at line 80 of file rbtree.h.

Data Fields
FreeFunc	free_value	A function to free the associated value.
RBNode *	node	Found node.

RBTreeIterStackItem

struct RBTreeIterStackItem

Structure holding a node and the iteration state.

Definition at line 110 of file rbtree.h.

Data Fields
RBNode *	node	A node.
int	state	Iteration state.

RBTreeIter

struct RBTreeIter

Structure to iterate over the elements of a RBTree.

Definition at line 122 of file rbtree.h.

Data Fields
bool	finished	true if iteration is finished.
RBTreeIterStackItem *	sp	The stack pointer.
RBTreeIterStackItem *	stack	A stack holding nodes and iteration state.
size_t	stack_size	Size of the stack.
const RBTree *	tree	Pointer to related tree.

Macro Definition Documentation

rbtree_iter_key

#define rbtree_iter_key

(

iter

)

iter.sp->node->key

Accesses the key of the current element directly.

Definition at line 297 of file rbtree.h.

rbtree_iter_value

#define rbtree_iter_value

(

iter

)

iter.sp->node->value

Accesses the value of the current element directly.

Definition at line 308 of file rbtree.h.

rbtree_pair_key

#define rbtree_pair_key

(

p

)

p->node->key

Accesses the key of a key-value pair directly.

Definition at line 217 of file rbtree.h.

rbtree_pair_value

#define rbtree_pair_value

(

p

)

p->node->value

Accesses the value of a key-value pair directly.

Definition at line 228 of file rbtree.h.

Typedef Documentation

RBTreePair

typedef struct _RBTreePair RBTreePair

A found key-value pair.

Definition at line 90 of file rbtree.h.

Enumeration Type Documentation

RBTreeInsertResult

enum RBTreeInsertResult

result of rbtree_set() method.

Enumerator
RBTREE_INSERT_RESULT_NEW	Node has been inserted.
RBTREE_INSERT_RESULT_REPLACED	Node has been replaced.
RBTREE_INSERT_RESULT_FAILED	Node insertion failed.

Definition at line 96 of file rbtree.h.

Function Documentation

rbtree_clear()

void rbtree_clear

(

RBTree *

tree

)

Parameters

tree

a RBTree

Removes all nodes.

Definition at line 137 of file rbtree.c.

rbtree_count()

size_t rbtree_count

(

const RBTree *

tree

)

Parameters

tree

a RBTree

Returns

number of stored nodes

Gets the number of stored nodes.

Definition at line 152 of file rbtree.c.

rbtree_destroy()

void rbtree_destroy

(

RBTree *

tree

)

Parameters

tree

a RBTree

Frees resources and the tree pointer.

Definition at line 115 of file rbtree.c.

rbtree_free()

void rbtree_free

(

RBTree *

tree

)

Parameters

tree

a RBTree

Frees resources without freeing the tree pointer.

Definition at line 124 of file rbtree.c.

rbtree_init()

void rbtree_init	(	RBTree *	tree,
		CompareFunc	compare_keys,
		FreeFunc	free_key,
		FreeFunc	free_value,
		Pool *	pool
	)

Parameters

tree	an uninitialized RBTree
compare_keys	function to compare two keys
free_key	function to free a key
free_value	function to free a value
pool	an optional memory pool for creating/destroying RBNodes or NULL

Initializes a RBTree.

Definition at line 54 of file rbtree.c.

rbtree_iter_free()

void rbtree_iter_free

(

RBTreeIter *

iter

)

Parameters

iter	a RBTreeIter

Frees the iterator.

Definition at line 897 of file rbtree.c.

rbtree_iter_get_key()

void * rbtree_iter_get_key

(

const RBTreeIter *

iter

)

Parameters

iter	a RBTreeIter

Returns

key of current element

Retrieves the key of the current element.

Definition at line 1002 of file rbtree.c.

rbtree_iter_get_value()

void * rbtree_iter_get_value

(

const RBTreeIter *

iter

)

Parameters

iter	a RBTreeIter

Returns

value of current element

Retrieves the value of the current element.

Definition at line 1015 of file rbtree.c.

rbtree_iter_init()

void rbtree_iter_init	(	const RBTree *	tree,
		RBTreeIter *	iter
	)

Parameters

tree	a RBTree
iter	an uninitialized RBTreeIter

Initializes a key/value pair iterator and associates it with the tree. Modifying the tree while using the iterator might lead to undefined behaviour.

Definition at line 870 of file rbtree.c.

rbtree_iter_next()

bool rbtree_iter_next

(

RBTreeIter *

iter

)

Parameters

iter	a RBTreeIter

Returns

false if end of the RBTree has been reached

Goes to next element of the RBTree.

Definition at line 936 of file rbtree.c.

rbtree_iter_reuse()

void rbtree_iter_reuse	(	const RBTree *	tree,
		RBTreeIter *	iter
	)

Parameters

tree	a RBTree
iter	an already initialized RBTreeIter

Reuses (reinitializes) an iterator.

Definition at line 905 of file rbtree.c.

rbtree_key_exists()

bool rbtree_key_exists	(	const RBTree *	tree,
		const void *	key
	)

Parameters

tree	a RBTree
key	a key

Returns

true if given key does exist

Checks if a key does exist.

Definition at line 622 of file rbtree.c.

rbtree_lookup()

RBTreePair * rbtree_lookup	(	RBTree *	tree,
		const void *	key
	)

Parameters

tree	a RBTree
key	key to find

Returns

the found key-value pair or NULL

Looks up a key-value pair in the RBTree.

Definition at line 564 of file rbtree.c.

rbtree_new()

RBTree * rbtree_new	(	CompareFunc	compare_keys,
		FreeFunc	free_key,
		FreeFunc	free_value,
		Pool *	pool
	)

Parameters

compare_keys	function to compare two keys
free_key	function to free a key
free_value	function to free a value
pool	an optional memory pool for creating/destroying RBNodes or NULL

Returns

a new RBTree

Creates a new RBTree.

Definition at line 36 of file rbtree.c.

rbtree_pair_get_key()

void * rbtree_pair_get_key

(

const RBTreePair *

pair

)

Parameters

pair	a key-value pair

Returns

key of the pair

Retrieves the key of a key-value pair.

Definition at line 582 of file rbtree.c.

rbtree_pair_get_value()

void * rbtree_pair_get_value

(

const RBTreePair *

pair

)

Parameters

pair	a key-value pair

Returns

value of the pair

Retrieves the value of a key-value pair.

Definition at line 595 of file rbtree.c.

rbtree_pair_set_value()

void rbtree_pair_set_value	(	RBTreePair *	pair,
		void *	value
	)

Parameters

pair	a RBTreePair
value	new value to set

Overwrites the value of a key-value pair.

Definition at line 608 of file rbtree.c.

rbtree_remove()

bool rbtree_remove	(	RBTree *	tree,
		const void *	key
	)

Parameters

tree	a RBTree
key	key of the element to remove

Returns

true if node has been removed

Removes an element from the RBTree.

Definition at line 793 of file rbtree.c.

rbtree_set()

RBTreeInsertResult rbtree_set	(	RBTree *	tree,
		void *	key,
		void *	value,
		bool	replace_key
	)

Parameters

tree	a RBTree
key	key of the item
value	value of the item
replace_key	true to overwrite exisiting key

Returns

type of the performed insert operation

Inserts a new key and value in the RBTree. If replace_key is set an existing key is freed using the specified free_key function before it gets replaced.

Definition at line 506 of file rbtree.c.