rbtree.h File Reference

Red-black trees. More...

#include <stdint.h>
#include <stddef.h>

Go to the source code of this file.

Data Structures
struct	rbtree_node_t
	An rbtree node. More...
struct	rbtree_t
	An rbtree. More...

Macros
#define	rbtree_item(ptr, type, member)    ((type*)(((char*)ptr) - offsetof(type, member)))
	Retrieves an rbtree item.

Typedefs
typedef void(*	rbtree_node_destructor_t) (rbtree_node_t *Node)
	rbtree node destructor.
typedef int(*	rbtree_node_comparator_t) (const rbtree_node_t *lhs, const rbtree_node_t *rhs)
	rbtree node comparator.

Functions
void	rbtree_init (rbtree_t *tree, rbtree_node_comparator_t comparator)
	Initializes an rbtree. More...
int	rbtree_empty (const rbtree_t *tree)
	Gets whether an rbtree is empty. More...
size_t	rbtree_size (const rbtree_t *tree)
	Gets the size of an rbtree. More...
	__attribute__ ((warn_unused_result)) rbtree_node_t *rbtree_insert(rbtree_t *tree
	Inserts a node into an rbtree. More...
void	rbtree_insert_multi (rbtree_t *tree, rbtree_node_t *node)
	Inserts multiple nodes into an rbtree. More...
rbtree_node_t *	rbtree_find (const rbtree_t *tree, const rbtree_node_t *node)
	Finds a node within an rbtree. More...
rbtree_node_t *	rbtree_min (const rbtree_t *tree)
	Gets the minimum node of an rbtree. More...
rbtree_node_t *	rbtree_max (const rbtree_t *tree)
	Gets the maximum node of an rbtree. More...
rbtree_node_t *	rbtree_node_next (const rbtree_node_t *node)
	Gets the next node from an rbtree node. More...
rbtree_node_t *	rbtree_node_prev (const rbtree_node_t *node)
	Gets the previous node from an rbtree node. More...
rbtree_node_t *	rbtree_remove (rbtree_t *tree, rbtree_node_t *node, rbtree_node_destructor_t destructor)
	Removes a node from an rbtree. More...
void	rbtree_clear (rbtree_t *tree, rbtree_node_destructor_t destructor)
	Clears an rbtree. More...

Variables
rbtree_node_t *	node

Detailed Description

Red-black trees.

Function Documentation

__attribute__()

__attribute__

(

(warn_unused_result)

)

Inserts a node into an rbtree.

Parameters

tree	Pointer to the tree.
node	Pointer to the node.

Returns

The inserted node.

Examples

network/sockets/source/sockets.c.

rbtree_clear()

void rbtree_clear	(	rbtree_t *	tree,
		rbtree_node_destructor_t	destructor
	)

Clears an rbtree.

Parameters

tree	Pointer to the tree.
destructor	Destructor to use when clearing the tree's nodes.

rbtree_empty()

int rbtree_empty

(

const rbtree_t *

tree

)

Gets whether an rbtree is empty.

Parameters

tree	Pointer to the tree.

Returns

A non-zero value if the tree is not empty.

rbtree_find()

rbtree_node_t* rbtree_find	(	const rbtree_t *	tree,
		const rbtree_node_t *	node
	)

Finds a node within an rbtree.

Parameters

tree	Pointer to the tree.
node	Pointer to the node.

Returns

The located node.

rbtree_init()

void rbtree_init	(	rbtree_t *	tree,
		rbtree_node_comparator_t	comparator
	)

Initializes an rbtree.

Parameters

tree	Pointer to the tree.
comparator	Comparator to use.

rbtree_insert_multi()

void rbtree_insert_multi	(	rbtree_t *	tree,
		rbtree_node_t *	node
	)

Inserts multiple nodes into an rbtree.

Parameters

tree	Pointer to the tree.
node	Pointer to the nodes.

rbtree_max()

rbtree_node_t* rbtree_max

(

const rbtree_t *

tree

)

Gets the maximum node of an rbtree.

Parameters

tree	Pointer to the tree.

Returns

The maximum node.

rbtree_min()

rbtree_node_t* rbtree_min

(

const rbtree_t *

tree

)

Gets the minimum node of an rbtree.

Parameters

tree	Pointer to the tree.

Returns

The minimum node.

rbtree_node_next()

rbtree_node_t* rbtree_node_next

(

const rbtree_node_t *

node

)

Gets the next node from an rbtree node.

Parameters

node	Pointer to the node.

Returns

The next node.

rbtree_node_prev()

rbtree_node_t* rbtree_node_prev

(

const rbtree_node_t *

node

)

Gets the previous node from an rbtree node.

Parameters

node	Pointer to the node.

Returns

The previous node.

rbtree_remove()

rbtree_node_t* rbtree_remove	(	rbtree_t *	tree,
		rbtree_node_t *	node,
		rbtree_node_destructor_t	destructor
	)

Removes a node from an rbtree.

Parameters

tree	Pointer to the tree.
node	Pointer to the node.
destructor	Destructor to use when removing the node.

Returns

The removed node.

rbtree_size()

size_t rbtree_size

(

const rbtree_t *

tree

)

Gets the size of an rbtree.

Parameters

tree	Pointer to the tree.