red–black binary search tree

Collaboration diagram for red–black binary search tree:

Data Structures
struct	a_rbt_node
	instance structure for red–black binary search tree node More...
union	a_rbt
	instance structure for red–black binary search tree root More...

Macros
#define	A_RBT_ROOT   {A_NULL}
#define	a_rbt_entry(ptr, type, member)
	access the struct for this entry
#define	a_rbt_foreach(cur, root)
	iterate over a red–black binary search tree in-order
#define	A_RBT_FOREACH(cur, root)
#define	a_rbt_foreach_reverse(cur, root)
	iterate over a red–black binary search tree in-order reverse
#define	A_RBT_FOREACH_REVERSE(cur, root)
#define	a_rbt_pre_foreach(cur, root)
	iterate over a red–black binary search tree preorder
#define	A_RBT_PRE_FOREACH(cur, root)
#define	a_rbt_pre_foreach_reverse(cur, root)
	iterate over a red–black binary search tree preorder reverse
#define	A_RBT_PRE_FOREACH_REVERSE(cur, root)
#define	a_rbt_post_foreach(cur, root)
	iterate over a red–black binary search tree postorder
#define	A_RBT_POST_FOREACH(cur, root)
#define	a_rbt_post_foreach_reverse(cur, root)
	iterate over a red–black binary search tree postorder reverse
#define	A_RBT_POST_FOREACH_REVERSE(cur, root)
#define	a_rbt_fortear(cur, next, root)
	tear a red–black binary search tree using postorder traversal
#define	A_RBT_FORTEAR(cur, next, root)

Typedefs
typedef struct a_rbt_node	a_rbt_node
	instance structure for red–black binary search tree node
typedef union a_rbt	a_rbt
	instance structure for red–black binary search tree root

Functions
a_rbt_node *	a_rbt_parent (a_rbt_node const *node)
	access parent of red–black binary search tree node
a_rbt_node *	a_rbt_init (a_rbt_node *node, a_rbt_node *parent)
	initialize for red–black binary search tree node
void	a_rbt_root (a_rbt *root)
	initialize for red–black binary search tree root
a_rbt_node *	a_rbt_head (a_rbt const *root)
	access head node of red–black binary search tree in-order
a_rbt_node *	a_rbt_tail (a_rbt const *root)
	access tail node of red–black binary search tree in-order
a_rbt_node *	a_rbt_next (a_rbt_node *node)
	access next node of red–black binary search tree node in-order
a_rbt_node *	a_rbt_prev (a_rbt_node *node)
	access prev node of red–black binary search tree node in-order
a_rbt_node *	a_rbt_pre_next (a_rbt_node *node)
	access next node of red–black binary search tree node preorder
a_rbt_node *	a_rbt_pre_prev (a_rbt_node *node)
	access prev node of red–black binary search tree node preorder
a_rbt_node *	a_rbt_post_head (a_rbt const *root)
	access head node of red–black binary search tree postorder
a_rbt_node *	a_rbt_post_tail (a_rbt const *root)
	access tail node of red–black binary search tree postorder
a_rbt_node *	a_rbt_post_next (a_rbt_node *node)
	access next node of red–black binary search tree node postorder
a_rbt_node *	a_rbt_post_prev (a_rbt_node *node)
	access prev node of red–black binary search tree node postorder
a_rbt_node *	a_rbt_tear (a_rbt *root, a_rbt_node **next)
	tear a node from red–black binary search tree
a_rbt_node *	a_rbt_search (a_rbt const *root, void const *ctx, int(*cmp)(void const *, void const *))
	search specified content from red–black binary search tree
a_rbt_node *	a_rbt_insert (a_rbt *root, a_rbt_node *node, int(*cmp)(void const *, void const *))
	insert specified node into red–black binary search tree
void	a_rbt_insert_adjust (a_rbt *root, a_rbt_node *node)
	rebalance the tree after insertion of the specified node
void	a_rbt_remove (a_rbt *root, a_rbt_node *node)
	remove specified node from red–black binary search tree

Detailed Description

Macro Definition Documentation

a_rbt_entry

#define a_rbt_entry	(		ptr,
			type,
			member )

Value:

a_container_of(ptr, type, member)

access the struct for this entry

Parameters

ptr	the &a_rbt_node pointer
type	the type of the struct this is embedded in
member	the name of the a_rbt_node within the struct

A_RBT_FOREACH

#define A_RBT_FOREACH	(		cur,
			root )

Value:

    for (cur = a_rbt_head(root); cur; cur = a_rbt_next(cur))

a_rbt_foreach

#define a_rbt_foreach	(		cur,
			root )

Value:

    for (a_rbt_node *cur = a_rbt_head(root); cur; cur = a_rbt_next(cur))

iterate over a red–black binary search tree in-order

typedef struct
{
    a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_foreach(cur, &root)
{
    T *it = a_rbt_entry(cur, T, node);
}

Parameters

cur	the &a_rbt_node to use as a loop counter
root	red–black binary search tree root

A_RBT_FOREACH_REVERSE

#define A_RBT_FOREACH_REVERSE	(		cur,
			root )

Value:

    for (cur = a_rbt_tail(root); cur; cur = a_rbt_prev(cur))

a_rbt_foreach_reverse

#define a_rbt_foreach_reverse	(		cur,
			root )

Value:

    for (a_rbt_node *cur = a_rbt_tail(root); cur; cur = a_rbt_prev(cur))

iterate over a red–black binary search tree in-order reverse

typedef struct
{
    a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_foreach_reverse(cur, &root)
{
    T *it = a_rbt_entry(cur, T, node);
}

Parameters

cur	the &a_rbt_node to use as a loop counter
root	red–black binary search tree root

A_RBT_FORTEAR

#define A_RBT_FORTEAR	(		cur,
			next,
			root )

Value:

    for ((void)(next = A_NULL), cur = a_rbt_tear(root, &next); cur; cur = a_rbt_tear(root, &next))

a_rbt_fortear

#define a_rbt_fortear	(		cur,
			next,
			root )

Value:

    for (a_rbt_node *next = A_NULL, *cur = a_rbt_tear(root, &next); cur; cur = a_rbt_tear(root, &next))

tear a red–black binary search tree using postorder traversal

typedef struct
{
    a_rbt_node node;
} T;
a_rbt root = A_AVL_ROOT;
a_rbt_fortear(cur, next, &root)
{
    T *it = a_rbt_entry(cur, T, node);
}

Parameters

cur	the &a_rbt_node to use as a loop counter
next	the &a_rbt_node to use as next node
root	red–black binary search tree root

A_RBT_POST_FOREACH

#define A_RBT_POST_FOREACH	(		cur,
			root )

Value:

    for (cur = a_rbt_post_head(root); cur; cur = a_rbt_post_next(cur))

a_rbt_post_foreach

#define a_rbt_post_foreach	(		cur,
			root )

Value:

    for (a_rbt_node *cur = a_rbt_post_head(root); cur; cur = a_rbt_post_next(cur))

iterate over a red–black binary search tree postorder

typedef struct
{
    a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_post_foreach(cur, &root)
{
    T *it = a_rbt_entry(cur, T, node);
}

Parameters

cur	the &a_rbt_node to use as a loop counter
root	red–black binary search tree root

A_RBT_POST_FOREACH_REVERSE

#define A_RBT_POST_FOREACH_REVERSE	(		cur,
			root )

Value:

    for (cur = a_rbt_post_tail(root); cur; cur = a_rbt_post_prev(cur))

a_rbt_post_foreach_reverse

#define a_rbt_post_foreach_reverse	(		cur,
			root )

Value:

    for (a_rbt_node *cur = a_rbt_post_tail(root); cur; cur = a_rbt_post_prev(cur))

iterate over a red–black binary search tree postorder reverse

typedef struct
{
    a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_post_foreach_reverse(cur, &root)
{
    T *it = a_rbt_entry(cur, T, node);
}

Parameters

cur	the &a_rbt_node to use as a loop counter
root	red–black binary search tree root

A_RBT_PRE_FOREACH

#define A_RBT_PRE_FOREACH	(		cur,
			root )

Value:

    for (cur = (root)->node; cur; cur = a_rbt_pre_next(cur))

a_rbt_pre_foreach

#define a_rbt_pre_foreach	(		cur,
			root )

Value:

    for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_next(cur))

iterate over a red–black binary search tree preorder

typedef struct
{
    a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_pre_foreach(cur, &root)
{
    T *it = a_rbt_entry(cur, T, node);
}

Parameters

cur	the &a_rbt_node to use as a loop counter
root	red–black binary search tree root

A_RBT_PRE_FOREACH_REVERSE

#define A_RBT_PRE_FOREACH_REVERSE	(		cur,
			root )

Value:

    for (cur = (root)->node; cur; cur = a_rbt_pre_prev(cur))

a_rbt_pre_foreach_reverse

#define a_rbt_pre_foreach_reverse	(		cur,
			root )

Value:

    for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_prev(cur))

iterate over a red–black binary search tree preorder reverse

typedef struct
{
    a_rbt_node node;
} T;
a_rbt root = A_RBT_ROOT;
a_rbt_pre_foreach_reverse(cur, &root)
{
    T *it = a_rbt_entry(cur, T, node);
}

Parameters

cur	the &a_rbt_node to use as a loop counter
root	red–black binary search tree root

Function Documentation

a_rbt_head()

a_rbt_node * a_rbt_head

(

a_rbt const *

root

)

access head node of red–black binary search tree in-order

Parameters

[in]

root

red–black binary search tree root

Returns

head node or null

a_rbt_init()

a_rbt_node * a_rbt_init	(	a_rbt_node *	node,
		a_rbt_node *	parent )

initialize for red–black binary search tree node

Parameters

[in]	node	node to be initialized
[in]	parent	node parent

Returns

initialized node

a_rbt_insert()

a_rbt_node * a_rbt_insert	(	a_rbt *	root,
		a_rbt_node *	node,
		int(*	cmp )(void const *, void const *) )

insert specified node into red–black binary search tree

Parameters

[in]	root	red–black binary search tree root
[in]	node	specified tree node
[in]	cmp	a function that compares two nodes cmp(lhs,rhs)==0 *lhs is equivalent to *rhs cmp(lhs,rhs)<0 *lhs goes before *rhs cmp(lhs,rhs)>0 *lhs goes after *rhs

Returns

null or duplicate node

a_rbt_insert_adjust()

void a_rbt_insert_adjust	(	a_rbt *	root,
		a_rbt_node *	node )

rebalance the tree after insertion of the specified node

Parameters

[in]	root	red–black binary search tree root
[in]	node	insert tree node

a_rbt_next()

a_rbt_node * a_rbt_next

(

a_rbt_node *

node

)

access next node of red–black binary search tree node in-order

Parameters

[in]

node

red–black binary search tree node

Returns

next node or null

a_rbt_parent()

a_rbt_node * a_rbt_parent

(

a_rbt_node const *

node

)

access parent of red–black binary search tree node

Parameters

[in]

node

points to red–black binary search tree node

Returns

a pointer to the parent of the specified red–black tree node, or null if it is already the root of the tree.

a_rbt_post_head()

a_rbt_node * a_rbt_post_head

(

a_rbt const *

root

)

access head node of red–black binary search tree postorder

Parameters

[in]

root

red–black binary search tree root

Returns

head node or null

a_rbt_post_next()

a_rbt_node * a_rbt_post_next

(

a_rbt_node *

node

)

access next node of red–black binary search tree node postorder

Parameters

[in]

node

red–black binary search tree node

Returns

next node or null

a_rbt_post_prev()

a_rbt_node * a_rbt_post_prev

(

a_rbt_node *

node

)

access prev node of red–black binary search tree node postorder

Parameters

[in]

node

red–black binary search tree node

Returns

prev node or null

a_rbt_post_tail()

a_rbt_node * a_rbt_post_tail

(

a_rbt const *

root

)

access tail node of red–black binary search tree postorder

Parameters

[in]

root

red–black binary search tree root

Returns

tail node or null

a_rbt_pre_next()

a_rbt_node * a_rbt_pre_next

(

a_rbt_node *

node

)

access next node of red–black binary search tree node preorder

Parameters

[in]

node

red–black binary search tree node

Returns

next node or null

a_rbt_pre_prev()

a_rbt_node * a_rbt_pre_prev

(

a_rbt_node *

node

)

access prev node of red–black binary search tree node preorder

Parameters

[in]

node

red–black binary search tree node

Returns

prev node or null

a_rbt_prev()

a_rbt_node * a_rbt_prev

(

a_rbt_node *

node

)

access prev node of red–black binary search tree node in-order

Parameters

[in]

node

red–black binary search tree node

Returns

prev node or null

a_rbt_remove()

void a_rbt_remove	(	a_rbt *	root,
		a_rbt_node *	node )

remove specified node from red–black binary search tree

Parameters

[in]	root	red–black binary search tree root
[in]	node	specified tree node

a_rbt_root()

void a_rbt_root

(

a_rbt *

root

)

initialize for red–black binary search tree root

Parameters

[in,out]

root

red–black binary search tree root

a_rbt_search()

a_rbt_node * a_rbt_search	(	a_rbt const *	root,
		void const *	ctx,
		int(*	cmp )(void const *, void const *) )

search specified content from red–black binary search tree

Parameters

[in]	root	red–black binary search tree root
[in]	ctx	specified content
[in]	cmp	a function that compares two nodes cmp(lhs,rhs)==0 *lhs is equivalent to *rhs cmp(lhs,rhs)<0 *lhs goes before *rhs cmp(lhs,rhs)>0 *lhs goes after *rhs

Returns

specified node or null

a_rbt_tail()

a_rbt_node * a_rbt_tail

(

a_rbt const *

root

)

access tail node of red–black binary search tree in-order

Parameters

[in]

root

red–black binary search tree root

Returns

tail node or null

a_rbt_tear()

a_rbt_node * a_rbt_tear	(	a_rbt *	root,
		a_rbt_node **	next )

tear a node from red–black binary search tree

Parameters

[in]	root	red–black binary search tree root
[in,out]	next	input starting node or, if null, root node. output next node or null.

Returns

teared node or null