Zephyr API Documentation  3.6.99
A Scalable Open Source RTOS
Loading...
Searching...
No Matches
Balanced Red/Black Tree

Balanced Red/Black Tree implementation. More...

Data Structures

struct  rbnode
 Balanced red/black tree node structure. More...
 
struct  rbtree
 Balanced red/black tree structure. More...
 

Macros

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

Typedefs

typedef bool(* rb_lessthan_t) (struct rbnode *a, struct rbnode *b)
 Red/black tree comparison predicate.
 
typedef void(* rb_visit_t) (struct rbnode *node, void *cookie)
 Prototype for node visitor callback.
 

Functions

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

Detailed Description

Balanced Red/Black Tree implementation.

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 rbnode handle is intended to be placed in a separate struct, in the same way as with other such structures (e.g. Zephyr's Doubly-linked 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

◆ RB_FOR_EACH

#define RB_FOR_EACH (   tree,
  node 
)

#include <zephyr/sys/rb.h>

Value:
for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node); \
(node = z_rb_foreach_next(tree, &__f)); \
)

Walk a tree in-order without recursing.

While rb_walk() is very simple, recursing on the C stack can be clumsy for some purposes and on some architectures wastes significant memory in stack frames. This macro implements a non-recursive "foreach" loop that can iterate directly on the tree, at a moderate cost in code size.

Note that the resulting loop is not safe against modifications to the tree. Changes to the tree structure during the loop will produce incorrect results, as nodes may be skipped or duplicated. Unlike linked lists, no _SAFE variant exists.

Note also that the macro expands its arguments multiple times, so they should not be expressions with side effects.

Parameters
treeA pointer to a struct rbtree to walk
nodeThe symbol name of a local struct rbnode* variable to use as the iterator

◆ RB_FOR_EACH_CONTAINER

#define RB_FOR_EACH_CONTAINER (   tree,
  node,
  field 
)

#include <zephyr/sys/rb.h>

Value:
for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node); \
({struct rbnode *n = z_rb_foreach_next(tree, &__f); \
node = n ? CONTAINER_OF(n, __typeof__(*(node)), \
field) : NULL; (node); }) != NULL; \
)
#define CONTAINER_OF(ptr, type, field)
Get a pointer to a structure containing the element.
Definition: util.h:268
Balanced red/black tree node structure.
Definition: rb.h:58

Loop over rbtree with implicit container field logic.

As for RB_FOR_EACH(), but "node" can have an arbitrary type containing a struct rbnode.

Parameters
treeA pointer to a struct rbtree to walk
nodeThe symbol name of a local iterator
fieldThe field name of a struct rbnode inside node

Typedef Documentation

◆ rb_lessthan_t

rb_lessthan_t

#include <zephyr/sys/rb.h>

Red/black tree comparison predicate.

Compares the two nodes and returns true if node A is strictly less than B according to the tree's sorting criteria, false otherwise.

Note that during insert, the new node being inserted will always be "A", where "B" is the existing node within the tree against which it is being compared. This trait can be used (with care!) to implement "most/least recently added" semantics between nodes which would otherwise compare as equal.

◆ rb_visit_t

typedef void(* rb_visit_t) (struct rbnode *node, void *cookie)

#include <zephyr/sys/rb.h>

Prototype for node visitor callback.

Parameters
nodeNode being visited
cookieUser-specified data

Function Documentation

◆ rb_contains()

bool rb_contains ( struct rbtree tree,
struct rbnode node 
)

#include <zephyr/sys/rb.h>

Returns true if the given node is part of the tree.

Note that this does not internally dereference the node pointer (though the tree's lessthan callback might!), it just tests it for equality with items in the tree. So it's feasible to use this to implement a "set" construct by simply testing the pointer value itself.

◆ rb_get_max()

static struct rbnode * rb_get_max ( struct rbtree tree)
inlinestatic

#include <zephyr/sys/rb.h>

Returns the highest-sorted member of the tree.

◆ rb_get_min()

static struct rbnode * rb_get_min ( struct rbtree tree)
inlinestatic

#include <zephyr/sys/rb.h>

Returns the lowest-sorted member of the tree.

◆ rb_insert()

void rb_insert ( struct rbtree tree,
struct rbnode node 
)

#include <zephyr/sys/rb.h>

Insert node into tree.

◆ rb_remove()

void rb_remove ( struct rbtree tree,
struct rbnode node 
)

#include <zephyr/sys/rb.h>

Remove node from tree.

◆ rb_walk()

static void rb_walk ( struct rbtree tree,
rb_visit_t  visit_fn,
void *  cookie 
)
inlinestatic

#include <zephyr/sys/rb.h>

Walk/enumerate a rbtree.

Very simple recursive enumeration. Low code size, but requiring a separate function can be clumsy for the user and there is no way to break out of the loop early. See RB_FOR_EACH for an iterative implementation.