RBT_INIT(9)

👑 RBT_INIT(9) — Kernel Developer's Manual 💅

okay bestie, so this is the page for the red-black tree kernel API, section 9 of the Kernel Developer's Manual, and it's lowkey iconic. sit down, grab a strawberry drink 🍓, and let's get into it.

---

✨ 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 🌸

like, that's the whole cast. main characters only.

---

🎀 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);

copy those exactly, bestie. character for character. no improvising 💅

---

🦋 DESCRIPTION 🦋

so the red-black tree API gives you data structures and operations for storing structures in red-black trees.

a red-black tree is a binary search tree, except every node also carries a color as an extra attribute. it's giving extra. and it fulfills a whole 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 single operation on a red-black tree is bounded as O(lg n). the maximum height of a red-black tree is 2lg (n+1). gorgeous. efficient. no notes. ✨

this API is implemented as a set of functions that operate on generic pointers — yes, the void-pointer life — but users of the API generate wrappers and macros that provide type safety when calling the functions. so it's generic under the hood but type-safe at the surface. the way that works? obsessed.

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 lets the element be connected to a tree. no entry field, no tree. periodt.
• 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. so like… don't reuse names, bestie, that's not the vibe 🙈

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, and the rules are:

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

that's the whole contract, iykyk 💖

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. same names, same energy. 🫶

---

🧚 Initialising a Red-Black Tree 🧚

• RBT_INIT() initialises the red-black tree rbt of type NAME to an empty state. fresh start, clean slate, brand new era ✨
• 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. so it's not an error, it's a "we already have one at home" moment 💀
• 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. key detail, don't skip it 🙏
• 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. main character energy 👑
• 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. going up ⬆️

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. going down ⬇️

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. and here's the slay part: VARNAME may be removed from the tree during iteration because a reference to the next element is held in NEXTVARNAME. safe deletion while looping, we love to see it 🫶

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. same safety, opposite direction, equally iconic 💅

---

🍓 Red-Black Tree Element Poisoning 🍓

• RBT_POISON() — 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() — used to verify that the pointers in the RBT_ENTRY structure inside elm are set to the poison value.

so you yeet an element, you poison its pointers, and later you check they're still poisoned. it's giving toxic ex energy and honestly? valid 💀

---

⭐ CONTEXT ⭐

these can be called during autoconf, from process context, or from interrupt 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().

(yes, the list here says RBT_FOREACH_SAFE_REVERSE() — we're just reporting what the page says, bestie, we don't make the rules 🙈)

⚠️ the locking is on YOU. it is up to the caller to provide appropriate locking around calls to these functions to prevent concurrent access to the relevant data structures. nobody's gonna do it for you. this is not a drill, fr fr.

---

🌸 RETURN VALUES 🌸

• RBT_INSERT() — returns NULL on successful insertion of elm into the tree; otherwise it returns a reference to an existing element with the same key.
• RBT_FIND() — returns a reference to an element that compares as equal to key, or NULL if no such element could be found.
• RBT_NFIND() — returns 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. (okay yes, the page literally says lowest for RBT_MAX. we are simply the messenger. don't shoot 🫶)
• 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)

the cousin. the lore. go read it too 💖

---

🎀 HISTORY 🎀

the red-black tree kernel API first appeared in OpenBSD 6.1. a cultural reset. ✨

---

and that's the page, bestie!! 🦋 this one shipped on the Debian build of the manual, dated June 8, 2017 — so if you're citing it, that's the source and date to reference 💫 go forth and balance your trees, you gorgeous nerd 👑💅