rb.h File Reference

Red/Black balanced tree data structure. More...

#include <alloca.h>
#include <stdbool.h>
#include <stdint.h>

Go to the source code of this file.

Data Structures
struct	rbnode
struct	rbtree

Macros
#define	ZEPHYR_INCLUDE_SYS_RB_H_
#define	RB_FOR_EACH(tree, node)
	Walk a tree in-order without recursing. More...
#define	RB_FOR_EACH_CONTAINER(tree, node, field)
	Loop over rbtree with implicit container field logic. More...

Typedefs
typedef bool(*	rb_lessthan_t) (struct rbnode *a, struct rbnode *b)
	Red/black tree comparison predicate. More...
typedef void(*	rb_visit_t) (struct rbnode *node, void *cookie)

Functions
void	rb_insert (struct rbtree *tree, struct rbnode *node)
	Insert node into tree. More...
void	rb_remove (struct rbtree *tree, struct rbnode *node)
	Remove node from tree. More...
static struct rbnode *	rb_get_min (struct rbtree *tree)
	Returns the lowest-sorted member of the tree. More...
static struct rbnode *	rb_get_max (struct rbtree *tree)
	Returns the highest-sorted member of the tree. More...
bool	rb_contains (struct rbtree *tree, struct rbnode *node)
	Returns true if the given node is part of the tree. More...
static void	rb_walk (struct rbtree *tree, rb_visit_t visit_fn, void *cookie)
	Walk/enumerate a rbtree. More...

Detailed Description

Red/Black balanced tree data structure.

This implements an intrusive balanced tree that guarantees O(log2(N)) runtime for all operations and amortized O(1) behavior for creation and destruction of whole trees. The algorithms and naming are conventional per existing academic and didactic implementations, c.f.:

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

The implementation is size-optimized to prioritize runtime memory usage. The data structure is intrusive, which is to say the struct rbnode handle is intended to be placed in a separate struct the same way other such structures (e.g. Zephyr's dlist list) and requires no data pointer to be stored in the node. The color bit is unioned with a pointer (fairly common for such libraries). Most notably, there is no "parent" pointer stored in the node, the upper structure of the tree being generated dynamically via a stack as the tree is recursed. So the overall memory overhead of a node is just two pointers, identical with a doubly-linked list.

Macro Definition Documentation

ZEPHYR_INCLUDE_SYS_RB_H_

#define ZEPHYR_INCLUDE_SYS_RB_H_