RBT_INIT(9) - OpenBSD manual pages

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:

every search path from the root to a leaf consists of the same number of black nodes,
each red node (except for the root) has a black parent,
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.

HISTORY

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

OpenBSD manual page server