The Linux kernel rbtree: a red-black tree with embedded nodes and no stored comparator
Linux's red-black tree never stores a comparator. Embedded nodes, your own search loop, helpers taking per-call compare functions, colour bits, cached and augmented trees, lockless lookup in v6.17.
The Linux kernel’s red-black tree has no rb_insert(tree, key, value). Nor does the tree have anywhere to register and keep a comparison function. With the basic API you write the loop that walks down the tree and picks left or right, and the library only takes over at the end to recolour and rotate. The v6.17 header also has inline helpers that run that loop for you, but they don’t store a comparison function either; they take one as an argument on every call.
This post looks at why the API is shaped this way when the data structure is the textbook one, and what that shape lets you choose. Everything is based on Linux v6.17: Documentation/core-api/rbtree.rst, include/linux/rbtree.h, include/linux/rbtree_augmented.h and lib/rbtree.c.
Why the callback was dropped and the loop handed over
The kernel documentation says the implementation is optimised for speed. Instead of keeping nodes and data apart and linking them with pointers, it embeds struct rb_node inside the data structure, which gives one less layer of indirection and better cache locality. Having users write their own search and insert functions, instead of the tree holding a comparison callback pointer and calling it, comes from the same goal. The header comment in rbtree.h, under Andrea Arcangeli’s 1999 copyright line, says callbacks would drop performance dramatically and that this is the way to get both performance and genericity in C. Locking is also left to the user.
The documentation compares the tree with other kernel structures as well. Hash tables are not kept sorted, so they are not easy to traverse in order, and they have to be tuned for a specific size and hash function. Rbtrees, it says, scale gracefully while storing arbitrary keys. What happens to a hash table in its worst case is covered in When is a hash table not O(1)?
The node lives inside your data
A structure that goes into the tree has a struct rb_node member.
struct mytype {
struct rb_node node;
char *keystring;
};
struct rb_root mytree = RB_ROOT;Tree functions only take and return struct rb_node *. To get back to the enclosing structure you use container_of() or the equivalent rb_entry(node, type, member) macro. The tree has no idea where the key is or what type it has.
Search is an ordinary binary search tree walk: start at the root and follow rb_left or rb_right depending on the comparison. The documentation’s example is a single while loop that picks a direction from the result of strcmp.
Insertion comes in two steps
Insertion splits into finding the slot for the new node and rebalancing after it is attached. Here is what the documentation’s example does, as pseudocode:
link = address of the root link (type struct rb_node **)
parent = none
while link points to a node cur:
parent = cur
new key < cur's key -> link = address of cur's left link
new key > cur's key -> link = address of cur's right link
equal -> return failure (key already present)
step 1: rb_link_node(new node, parent, link) attach in the empty slot
step 2: rb_insert_color(new node, root) fix colours and rotateThe documentation’s C example gets cur’s enclosing structure with container_of() and compares keys with strcmp. Unlike search, this loop follows the address of the link (struct rb_node **) rather than the node. When it ends, link is the empty slot to write the new node into. rb_link_node() records the parent, sets both children to NULL and writes the node into that slot. rb_insert_color() then fixes colours and rotates if needed.
The loop also decides what happens on an equal key. The example returns failure; if you want duplicates, write it to keep going down one side.
Helpers in the v6.17 header
So that you don’t have to write that loop every time, rbtree.h in v6.17 includes helpers that take a comparison function as an argument on each call. The tree doesn’t store it, so you have to pass a consistent one every time you use the same tree. In the table below, rb_for_each() is a preprocessor macro that expands to a for loop; the rest are static __always_inline functions.
| Name | Kind | Comparison | What it does |
|---|---|---|---|
rb_add() |
inline function | less(a, b) |
Inserts the node. No return value |
rb_find_add() |
inline function | cmp(a, b) |
Returns the node for which cmp is 0 if there is one; otherwise inserts and returns NULL |
rb_find() |
inline function | cmp(key, node) |
The node matching the key, or NULL |
rb_find_first() |
inline function | cmp(key, node) |
The leftmost matching node |
rb_for_each() |
macro | cmp(key, node) |
Iterates over the matching nodes (uses rb_find_first() and rb_next_match()) |
A header comment defines how the two operators relate, for example that cmp(a->key, b) < 0 means the same as less(a, b). If the operators only define a partial order, it says, there is no guarantee which of the matching elements rb_find() returns. The reason for this key-only search form is to avoid building a dummy object on the stack just to compare against, which might not be feasible when objects are large.
In rb_add()’s loop, the walk goes left only when less(node, parent) is true; on equal it goes right. One property follows from that (it’s derived from the code, not a guarantee stated in the comments). If the whole tree was built by rb_add() with a consistent less, a new node lands after every existing node with the same key in sort order. Rotations don’t change sort order, so that stays true. It’s also why rb_find_first(), not rb_find(), is the one to use when you want the first element with a given key.
Colour hides in the low bits of the parent pointer
There is no visible colour field. The macros in rbtree.h and rbtree_augmented.h show the parent pointer and colour sharing one unsigned long called __rb_parent_color.
__rb_parent_color (one unsigned long)
[ parent node address ...... | b1 | b0 ] b1, b0 = the low 2 bits
rb_parent(r) = value & ~3 clear the low 2 bits to get the parent address
rb_color(r) = value & 1 bit 0 is the colour (RB_RED = 0, RB_BLACK = 1)This only works if the low two bits of a node’s address are always zero. The struct rb_node definition that would guarantee that alignment is in rbtree_types.h, which was not among the files checked for this post.
The same field also marks a node that is not in any tree. RB_CLEAR_NODE(node) sets it to the node’s own address and RB_EMPTY_NODE(node) checks for that. rb_next() and rb_prev() return NULL when given such a node.
Balance and the number of rotations
The header comment of lib/rbtree.c lists the five red-black properties and explains that two of them, “both children of every red node are black” and “every simple path from root to leaves contains the same number of black nodes”, give the O(log n) guarantee. Two red nodes can’t be consecutive, so if every path has B black nodes, the longest possible path is 2B.
The kernel documentation says that, compared with AVL trees, red-black trees give faster real-time bounded worst-case performance for insertion and deletion: at most two rotations to rebalance after an insert and three after a delete. Lookup is slightly slower in exchange, but still O(log n).
The structure of __rb_insert() shows where those numbers come from.
| Insert case | Condition | Action | Rotations | Then |
|---|---|---|---|---|
| Case 1 | Uncle is red | Parent and uncle black, grandparent red | 0 | Repeat at the grandparent |
| Case 2 | Uncle black, node is the inner child | Rotate at the parent into Case 3’s shape | 1 | Falls through to Case 3 |
| Case 3 | Uncle black, node is the outer child | Rotate at the grandparent | 1 | Done |
Any path that rotates ends in Case 3, so there are at most two rotations. Case 1, though, only recolours and loops again two levels up, so recolouring can climb towards the root several times. “At most two rotations” doesn’t mean the fix-up after an insert is constant time. ____rb_erase_color() on the delete side has the same structure: even going through every rotating case (1, 3 and 4), it stops at Case 4, while Case 2, which only recolours, can move up to the parent.
Iteration: parent pointers instead of a stack
Four functions walk the tree in sorted order: rb_first(), rb_last(), rb_next() and rb_prev().
struct rb_node *node;
for (node = rb_first(&mytree); node; node = rb_next(node))
printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);If the node has a right child, rb_next() goes down into it and then as far left as it can. Otherwise it follows parent pointers up and returns the first parent it reaches from a left child. No separate stack is needed because every node carries a parent pointer.
To free a whole tree there is postorder iteration. rbtree_postorder_for_each_entry_safe(pos, n, root, field) visits children before parents and fetches the next node in advance, so the loop body may free pos. The comment adds a caveat: it can’t handle other modifications that re-order the tree, and that includes calling rb_erase() on pos, because erasing may rebalance the tree and cause nodes to be missed.
Cached trees: keeping the leftmost node at hand
rb_first() walks from the root to the far left, so it costs the height of the tree. For uses that ask for the smallest element often there is struct rb_root_cached. The documentation describes it as a regular rb_root plus one pointer to the leftmost node, with negligible maintenance overhead but a larger memory footprint. In the header, rb_first_cached() just reads that pointer, and its comment says “Same as rb_first(), but O(1)”.
Keeping the cache right is partly your job. rb_insert_color_cached(node, root, leftmost) takes whether the new node is leftmost as its third argument. If your hand-written insert loop went right even once, you must pass false. rb_add_cached() works this out for you and returns the node if it became the new leftmost, NULL otherwise. On removal, rb_erase_cached() moves the cache to rb_next() when the node being erased is the leftmost.
Repeatedly taking the smallest element is also what a priority queue does. What a heap maintains instead of full sorted order is covered in A heap is not a sorted list. An rbtree keeps everything in sorted order, so the iteration functions above can step to the neighbours of any node.
Augmented trees: keeping a subtree summary
An augmented rbtree stores extra data in each node, and that data must be a function of the whole subtree rooted at the node. The documentation’s example is an interval tree. Each node stores an interval [start, last] and keeps the largest last in its subtree as __subtree_last. If the left child’s value is smaller than the start of the query, nothing in the left subtree can overlap, so there’s no need to go down there. The documentation says this finds the match with the lowest start address in O(log n).
When rotations or deletions change the shape of a subtree, the summary has to be fixed too. So you pass three callbacks in struct rb_augment_callbacks:
- propagate: recompute the value from a given node up to a stop point (or the root).
- copy: copy a subtree’s value to the node that has just become that subtree’s root.
- rotate: do the same copy, then recompute the value for the former subtree root.
On insert, you update the values along the path yourself on the way down, then call rb_link_node() and rb_insert_augmented() in place of rb_insert_color(). On delete you use rb_erase_augmented(). The propagate callback in the documentation’s sample and in the RB_DECLARE_CALLBACKS_MAX macro stops as soon as the recomputed value equals the stored one, since the ancestors above have no reason to change.
The documentation asks for two more things. The compiled code for rb_erase_augmented() may inline the propagate and copy callbacks and become large, so each augmented rbtree user should have a single call site for it. And because <linux/rbtree_augmented.h> exposes implementation details, include it only from C files, never from headers. The header’s own comment says only struct rb_augment_callbacks and the prototypes for rb_insert_augmented() and rb_erase_augmented() are meant to be public; the rest are implementation details not to depend on.
What lockless lookup promises, and what it doesn’t
Locking is left to the user, but lib/rbtree.c has notes for lookups done without a lock. Every store to the tree structure (rb_left, rb_right) uses WRITE_ONCE(), and the code must not create even temporary loops in program order. Those two rules guarantee:
- A lockless traversal sees only valid elements and finishes instead of getting stuck in a loop.
- If a lookup returns an element, it is the correct one.
The notes also spell out what is not guaranteed. Rotations are not atomic, so a lookup can miss entire subtrees. Not returning an element does not mean it isn’t there. The comment on rb_find_rcu() warns likewise that descending while rotations run concurrently is unsound and can give false negatives. So a “not found” from a lockless lookup can’t be taken as the answer; if it matters, it needs a separate check.
For insertion there is rb_link_node_rcu() and rb_find_add_rcu(), which uses it. The difference from the normal version is that the new node is written into its slot with rcu_assign_pointer(); the comment describes this as adding a store-release.
Replacing a node does not re-sort
rb_replace_node(old, new, root) swaps one node for another without the erase-and-reinsert dance. The implementation copies old’s pointers and colour into new and points the children and parent at new. It never compares anything. That’s why the documentation warns that if the new node doesn’t have the same key as the old one, the tree will probably become corrupted. To change a key, erase and insert again.
Documentation and source
- Red-black Trees (rbtree) in Linux, Linux kernel documentation v6.17 (the page itself is dated January 18, 2007, by Rob Landley)
include/linux/rbtree.h, Linux v6.17include/linux/rbtree_augmented.h, Linux v6.17lib/rbtree.c, Linux v6.17
Checked on October 15, 2026. Other kernel versions may have a different set of helpers or different signatures.