RBT_INIT(9) | Kernel Developer's Manual | RBT_INIT(9)

# NAME

`RBT_HEAD`, `RBT_ENTRY`, `RBT_PROTOTYPE`, `RBT_GENERATE`, `RBT_INITIALIZER`, `RBT_INIT`, `RBT_INSERT`, `RBT_REMOVE`, `RBT_FIND`, `RBT_NFIND`, `RBT_EMPTY`, `RBT_ROOT`, `RBT_MIN`, `RBT_MAX`, `RBT_NEXT`, `RBT_PREV`, `RBT_LEFT`, `RBT_RIGHT`, `RBT_PARENT`, `RBT_SET_LEFT`, `RBT_SET_RIGHT`, `RBT_SET_PARENT`, `RBT_FOREACH`, `RBT_FOREACH_SAFE`, `RBT_FOREACH_REVERSE`, `RBT_FOREACH_REVERSE_SAFE`, `RBT_POISON`, `RBT_CHECK` — Kernel red-black trees

# SYNOPSIS

`#include <sys/tree.h>`

`RBT_HEAD`(NAME, TYPE);

`RBT_ENTRY`(TYPE);

`RBT_PROTOTYPE`(NAME, TYPE, ENTRY, int (*compare)(const struct TYPE *, const struct TYPE *));

`RBT_GENERATE`(NAME, TYPE, ENTRY, int (*compare)(const struct TYPE *, const struct TYPE *));

struct NAME
`RBT_INITIALIZER`(struct NAME *self);

void
`RBT_INIT`(NAME, struct NAME *rbt);

struct TYPE *
`RBT_INSERT`(NAME, struct NAME *rbt, struct TYPE *elm);

struct TYPE *
`RBT_REMOVE`(NAME, struct NAME *rbt, struct TYPE *elm);

struct TYPE *
`RBT_FIND`(NAME, struct NAME *rbt, const struct TYPE *key);

struct TYPE *
`RBT_NFIND`(NAME, struct NAME *rbt, const struct TYPE *key);

int
`RBT_EMPTY`(NAME, struct NAME *rbt);

struct TYPE *
`RBT_ROOT`(NAME, struct NAME *rbt);

struct TYPE *
`RBT_MIN`(NAME, struct NAME *rbt);

struct TYPE *
`RBT_MAX`(NAME, struct NAME *rbt);

struct TYPE *
`RBT_NEXT`(NAME, struct TYPE *elm);

struct TYPE *
`RBT_PREV`(NAME, struct TYPE *elm);

struct TYPE *
`RBT_LEFT`(NAME, struct TYPE *elm);

struct TYPE *
`RBT_RIGHT`(NAME, struct TYPE *elm);

struct TYPE *
`RBT_PARENT`(NAME, struct TYPE *elm);

void
`RBT_SET_LEFT`(NAME, struct TYPE *elm, struct TYPE *left);

void
`RBT_SET_RIGHT`(NAME, struct TYPE *elm, struct TYPE *right);

void
`RBT_SET_PARENT`(NAME, struct TYPE *elm, struct TYPE *parent);

`RBT_FOREACH`(VARNAME, NAME, struct NAME *rbt);

`RBT_FOREACH_REVERSE`(VARNAME, NAME, struct NAME *rbt);

`RBT_FOREACH_SAFE`(VARNAME, NAME, struct NAME *rbt, NEXTVARNAME);

`RBT_FOREACH_REVERSE_SAFE`(VARNAME, NAME, struct NAME *rbt, NEXTVARNAME);

void
`RBT_POISON`(NAME, struct TYPE *elm, unsigned long poison);

int
`RBT_CHECK`(NAME, struct TYPE *elm, unsigned long poison);

# DESCRIPTION

The red-black tree API provides data structures and operations for storing structures in red-black trees.

A red-black tree is a binary search tree with the node color as an extra attribute. It fulfills a set of conditions:

1. every search path from the root to a leaf consists of the same number of black nodes,
2. each red node (except for the root) has a black parent,
3. each leaf node is black.

Every operation on a red-black tree is bounded as O(lg n). The maximum height of a red-black tree is 2lg (n+1).

This API is implemented as a set of functions that operate on generic pointers, but users of the API generate wrappers and macros that provide type safety when calling the functions.

In the macro definitions, TYPE is the name of a structure that will be stored in a red-black tree. The TYPE structure must contain an `RBT_ENTRY`() field that allows the element to be connected to a tree. The argument NAME is the name of a red-black tree type that can store a particular TYPE element.

## Creating a Red-Black Tree Type

The `RBT_HEAD`() macro creates a red-black tree type to store TYPE structures as elements in the tree. The argument NAME must uniquely identify every type of tree that is defined.

`RBT_PROTOTYPE`() produces the wrappers for a red-black tree type identified by NAME to operate on elements of type TYPE. ENTRY specifies which field in the TYPE structure is used to connect elements to NAME red-black trees. Elements in the red-black tree are ordered according to the result of comparing them with the compare function. If the first argument to compare is to be ordered lower than the second, the function returns a value smaller than zero. If the first argument is to be ordered higher than the second, the function returns a value greater than zero. If they are equal, the function returns zero.

`RBT_GENERATE`() produces the internal data structures used by the red-black tree type identified by NAME to operate on elements of type TYPE. The ENTRY and compare arguments are the same as the `RBT_PROTOTYPE`() arguments of the same names.

## Initialising a Red-Black Tree

`RBT_INIT`() initialises the red-black tree rbt of type NAME to an empty state.

`RBT_INITIALIZER`() can be used to initialise a declaration of the red-black tree self of type NAME to an empty state.

## Red-Black Tree Operations

`RBT_INSERT`() inserts the element elm into the red-black tree rbt of type NAME. Upon success, `NULL` is returned. If a matching element already exists in the tree, the insertion is aborted and a pointer to the existing element is returned.

`RBT_REMOVE`() removes the element elm from the red-black tree rbt of type NAME. elm must exist in the tree rbt before it is removed.

`RBT_FIND`() performs a binary search for an exact match of key in the red-black tree rbt of type NAME.

`RBT_NFIND`() performs a binary search for the first node that is greater than or equal to key in the red-black tree rbt of type NAME.

`RBT_EMPTY`() returns if the red-black tree rbt of type NAME is empty.

`RBT_ROOT`() returns the root element in the red-black tree rbt of type NAME.

`RBT_MIN`() returns the lowest ordered element in the red-black tree rbt of type NAME.

`RBT_MAX`() returns the highest ordered element in the red-black tree rbt of type NAME.

## Red-Black Tree Element Operations

`RBT_NEXT`() returns a pointer to the next ordered element after elm in a red-black tree of type NAME.

`RBT_PREV`() returns a pointer to the previous ordered element before elm in a red-black tree of type NAME.

`RBT_LEFT`() returns a pointer to the left child element of elm in a red-black tree of type NAME.

`RBT_RIGHT`() returns a pointer to the right child element of elm in a red-black tree of type NAME.

`RBT_PARENT`() returns a pointer to the parent element of elm in a red-black tree of type NAME.

`RBT_SET_LEFT`() sets the left child pointer of element elm to left in a red-black tree of type NAME.

`RBT_SET_RIGHT`() sets the right child pointer of element elm to right in a red-black tree of type NAME.

`RBT_SET_PARENT`() sets the parent pointer of element elm to parent in a red-black tree of type NAME.

## Red-Black Tree Iterators

The `RBT_FOREACH`() macro iterates over the red-black tree rbt of type NAME from the lowest ordered element to the highest ordered element, setting VARNAME to each element in turn.

The `RBT_FOREACH_REVERSE`() macro iterates over the red-black tree rbt of type NAME from the highest ordered element to the lowest ordered element, setting VARNAME to each element in turn.

The `RBT_FOREACH_SAFE`() macro iterates over the red-black tree rbt of type NAME from the lowest ordered element to the highest ordered element, setting VARNAME to each element in turn. VARNAME may be removed from the tree during iteration because a reference to the next element is held in NEXTVARNAME.

The `RBT_FOREACH_REVERSE_SAFE`() macro iterates over the red-black tree rbt of type NAME from the highest ordered element to the lowest ordered element, setting VARNAME to each element in turn. VARNAME may be removed from the tree during iteration because a reference to the next element is held in NEXTVARNAME.

## Red-Black Tree Element Poisoning

`RBT_POISON`() is used to poison the pointers in the RBT_ENTRY structure inside elm which has been removed from a red-black tree of type NAME with the poison value.

`RBT_CHECK`() is used to verify that the pointers in the RBT_ENTRY structure inside elm are set to the poison value.

# CONTEXT

`RBT_INIT`(), `RBT_INSERT`(), `RBT_REMOVE`(), `RBT_FIND`(), `RBT_NFIND`(), `RBT_EMPTY`(), `RBT_ROOT`(), `RBT_MIN`(), `RBT_MAX`(), `RBT_NEXT`(), `RBT_PREV`(), `RBT_LEFT`(), `RBT_RIGHT`(), `RBT_PARENT`(), `RBT_SET_LEFT`(), `RBT_SET_RIGHT`(), `RBT_SET_PARENT`(), `RBT_FOREACH`(), `RBT_FOREACH_REVERSE`(), `RBT_FOREACH_SAFE`(), `RBT_FOREACH_SAFE_REVERSE`(), `RBT_POISON`(), and `RBT_CHECK`() can be called during autoconf, from process context, or from interrupt context.

It is up to the caller to provide appropriate locking around calls to these functions to prevent concurrent access to the relevant data structures.

# RETURN VALUES

`RBT_INSERT`() will return `NULL` on successful insertion of elm into the tree, otherwise it will return a reference to an existing element with the same key.

`RBT_FIND`() will return a reference to an element that compares as equal to key, or `NULL` if no such element could be found.

`RBT_NFIND`() will return a reference to the nearest element that compares as equal or greater to key, or `NULL` if no such element could be found.

`RBT_EMPTY`() returns non-zero if the red-black tree rbt is empty, otherwise 0.

`RBT_ROOT`() returns a reference to the root node in the red-black tree rbt, or `NULL` if it is empty.

`RBT_MIN`() returns a reference to the lowest ordered element in the red-black tree rbt, or `NULL` if it is empty.

`RBT_MAX`() returns a reference to the lowest ordered element in the red-black tree rbt, or `NULL` if it is empty.

`RBT_NEXT`() returns a reference to the next ordered element in the red-black tree after elm, or `NULL` if it is the greatest element in the tree.

`RBT_PREV`() returns a reference to the previous ordered element in the red-black tree before elm, or `NULL` if it is the lowest element in the tree.

`RBT_LEFT`() returns a reference to the left child element of elm, or `NULL` if it is a leaf in the tree.

`RBT_RIGHT`() returns a reference to the right child element of elm, or `NULL` if it is a leaf in the tree.

`RBT_PARENT`() returns a reference to the parent element of elm, or `NULL` if it is the root of the tree.

`RBT_CHECK`() returns non-zero if the RBT_ENTRY in the red-black tree element contains the poison value, otherwise 0.

# SEE ALSO

RB_INIT(3)

# HISTORY

The red-black tree kernel API first appeared in OpenBSD 6.1.

June 8, 2017 | Debian