Generic red-black tree. More...

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#include "rbtree.h"

Macros
#define	_GNU_SOURCE

#define	RBTREE_INITIAL_BLOCK_SIZE 4

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_destroy (RBTree *tree)

void	rbtree_free (RBTree *tree)

void	rbtree_clear (RBTree *tree)

size_t	rbtree_count (const RBTree *tree)

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

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

Macro Definition Documentation

◆ _GNU_SOURCE

#define _GNU_SOURCE

Definition at line 22 of file rbtree.c.

◆ RBTREE_INITIAL_BLOCK_SIZE

#define RBTREE_INITIAL_BLOCK_SIZE 4

Initial stack size.

Definition at line 33 of file rbtree.c.

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.

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ _GNU_SOURCE

◆ RBTREE_INITIAL_BLOCK_SIZE

Function Documentation

◆ rbtree_clear()

◆ rbtree_count()

◆ rbtree_destroy()

◆ rbtree_free()

◆ rbtree_init()

◆ rbtree_iter_free()

◆ rbtree_iter_get_key()

◆ rbtree_iter_get_value()

◆ rbtree_iter_init()

◆ rbtree_iter_next()

◆ rbtree_iter_reuse()

◆ rbtree_key_exists()

◆ rbtree_lookup()

◆ rbtree_new()

◆ rbtree_pair_get_key()

◆ rbtree_pair_get_value()

◆ rbtree_pair_set_value()

◆ rbtree_remove()

◆ rbtree_set()