Skip to content
charmOS docs

Red black tree

include/structures/rbt.h View source View on GitHub

Structs

Section titled “Structs”

rbt_parent

Section titled “rbt_parent”
struct rbt_parent (1 field) source
§ uintptr_t word

Lowest bit is color

rbt_node

Section titled “rbt_node”
struct rbt_node (3 fields) source
§ struct rbt_node *left
§ struct rbt_node *right
§ struct rbt_parent parent_data

rbt

Section titled “rbt”
struct rbt (3 fields) source
TODO

stop using get_data. for now it works but in the future we may want to allow for rb-trees that are “backwards” or sorted by some other rule beyond integer field comparison

§ rbt_get_data get_data
§ rbt_compare compare
§ struct rbt_node *root

Enums

Section titled “Enums”

rbt_node_color

Section titled “rbt_node_color”
enum rbt_node_color (2 variants) source
§ TREE_NODE_RED = 0
§ TREE_NODE_BLACK = 1

Type Aliases

Section titled “Type Aliases”

rbt_compare

Section titled “rbt_compare”
typedef int32_t (*rbt_compare)(
    const struct rbt_node * a,
    const struct rbt_node * b
)
source

rbt_get_data

Section titled “rbt_get_data”
typedef size_t (*rbt_get_data)(struct rbt_node * *)
source

Functions

Section titled “Functions”

rbt_parent

Section titled “rbt_parent”
struct rbt_node * rbt_parent(const struct rbt_node *node)
source

rbt_color

Section titled “rbt_color”
enum rbt_node_color rbt_color(const struct rbt_node *node)
source

rbt_set_color

Section titled “rbt_set_color”
void rbt_set_color(struct rbt_node *node, enum rbt_node_color c)
source

rbt_set_parent

Section titled “rbt_set_parent”
void rbt_set_parent(struct rbt_node *node, struct rbt_node *parent)
source

rbt_last

Section titled “rbt_last”
struct rbt_node * rbt_last(const struct rbt *root)
source

rbt_prev

Section titled “rbt_prev”
struct rbt_node * rbt_prev(struct rbt_node *node)
source

rbt_init_node

Section titled “rbt_init_node”
void rbt_init_node(struct rbt_node *n)
source

rbt_first

Section titled “rbt_first”
struct rbt_node * rbt_first(const struct rbt *root)
source
Section titled “rbt_link_node”
void rbt_link_node(
    struct rbt_node *node,
    struct rbt_node *parent,
    struct rbt_node **link
)
source

rbt_insert_color

Section titled “rbt_insert_color”
void rbt_insert_color(struct rbt *tree, struct rbt_node *node)
source

rbt_init

Section titled “rbt_init”
struct rbt * rbt_init(
    struct rbt *t,
    rbt_get_data get_data,
    rbt_compare compare
)
source

rbt_create

Section titled “rbt_create”
struct rbt * rbt_create(rbt_get_data get, rbt_compare compare)
source

rbt_find_min

Section titled “rbt_find_min”
struct rbt_node * rbt_find_min(struct rbt_node *node)
source

rbt_find_max

Section titled “rbt_find_max”
struct rbt_node * rbt_find_max(struct rbt_node *node)
source

rbt_delete

Section titled “rbt_delete”
void rbt_delete(struct rbt *tree, struct rbt_node *z)
source

z must be linked into tree

Section titled “rbt_search”
struct rbt_node * rbt_search(struct rbt *tree, uint64_t data)
source

rbt_remove

Section titled “rbt_remove”
void rbt_remove(struct rbt *tree, uint64_t data)
source

rbt_insert

Section titled “rbt_insert”
void rbt_insert(struct rbt *tree, struct rbt_node *new_node)
source

rbt_min

Section titled “rbt_min”
struct rbt_node * rbt_min(struct rbt *tree)
source

rbt_max

Section titled “rbt_max”
struct rbt_node * rbt_max(struct rbt *tree)
source

rbt_next

Section titled “rbt_next”
struct rbt_node * rbt_next(struct rbt_node *node)
source

rbt_find_predecessor

Section titled “rbt_find_predecessor”
struct rbt_node * rbt_find_predecessor(
    struct rbt *tree,
    uint64_t data
)
source

rbt_find_successor

Section titled “rbt_find_successor”
struct rbt_node * rbt_find_successor(struct rbt *tree, uint64_t data)
source

rbt_empty

Section titled “rbt_empty”
bool rbt_empty(struct rbt *tree)
source

rbt_has_node

Section titled “rbt_has_node”
bool rbt_has_node(struct rbt *tree, struct rbt_node *node)
source

rbt_reinsert

Section titled “rbt_reinsert”
bool rbt_reinsert(struct rbt *tree, struct rbt_node *node)
source

Re-position nodes whose sort key changes, with checks to first verify it needs to move at all, returning true if moved

rbt_position_valid

Section titled “rbt_position_valid”
bool rbt_position_valid(struct rbt *tree, struct rbt_node *node)
source

True when ordering is correct

rbt_move

Section titled “rbt_move”
void rbt_move(struct rbt *from, struct rbt *to, struct rbt_node *node)
source

Macros

Section titled “Macros”

RBT_NODE_INIT

Section titled “RBT_NODE_INIT”
#define RBT_NODE_INIT
source
Expansion
#define RBT_NODE_INIT \
    (struct rbt_node) { \
        .parent_data.word = TREE_NODE_BLACK, .left = NULL, .right = NULL \
    }

rbt_for_each_safe

Section titled “rbt_for_each_safe”
#define rbt_for_each_safe(pos, tmp, root)
source
Expansion
#define rbt_for_each_safe(pos, tmp, root) \
    for (pos = rbt_first(root), tmp = rbt_next(pos); pos != NULL; \
         pos = tmp, tmp = rbt_next(pos))

rbt_for_each_entry_safe

Section titled “rbt_for_each_entry_safe”
#define rbt_for_each_entry_safe(pos, tmp, tree, member)
source
Expansion
#define rbt_for_each_entry_safe(pos, tmp, tree, member) \
    for (typeof(rbt_first(tree)) __n = rbt_first(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = rbt_entry(__n, typeof(*(pos)), member)), \
          (__nx = rbt_next(__n)), \
          ((tmp) = __nx ? rbt_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)

rbt_for_each_safe_reverse

Section titled “rbt_for_each_safe_reverse”
#define rbt_for_each_safe_reverse(pos, tmp, root)
source
Expansion
#define rbt_for_each_safe_reverse(pos, tmp, root) \
    for (pos = rbt_last(root), tmp = rbt_prev(pos); pos != NULL; \
         pos = tmp, tmp = rbt_prev(pos))

rbt_for_each_entry_safe_reverse

Section titled “rbt_for_each_entry_safe_reverse”
#define rbt_for_each_entry_safe_reverse(pos, tmp, tree, member)
source
Expansion
#define rbt_for_each_entry_safe_reverse(pos, tmp, tree, member) \
    for (typeof(rbt_last(tree)) __n = rbt_last(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = rbt_entry(__n, typeof(*(pos)), member)), \
          (__nx = rbt_prev(__n)), \
          ((tmp) = __nx ? rbt_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)

rbt_for_each

Section titled “rbt_for_each”
#define rbt_for_each(pos, root)
source
Expansion
#define rbt_for_each(pos, root) \
    for (pos = rbt_first(root); pos != NULL; pos = rbt_next(pos))

rbt_for_each_entry

Section titled “rbt_for_each_entry”
#define rbt_for_each_entry(pos, tree, member)
source
Expansion
#define rbt_for_each_entry(pos, tree, member) \
    for (typeof(rbt_first(tree)) __n = rbt_first(tree); \
         __n != NULL && \
         (((pos) = rbt_entry(__n, typeof(*(pos)), member)), true); \
         __n = rbt_next(__n))

rbt_for_each_reverse

Section titled “rbt_for_each_reverse”
#define rbt_for_each_reverse(pos, root)
source
Expansion
#define rbt_for_each_reverse(pos, root) \
    for (pos = rbt_last(root); pos != NULL; pos = rbt_prev(pos))

rbt_for_each_entry_reverse

Section titled “rbt_for_each_entry_reverse”
#define rbt_for_each_entry_reverse(pos, tree, member)
source
Expansion
#define rbt_for_each_entry_reverse(pos, tree, member) \
    for (typeof(rbt_last(tree)) __n = rbt_last(tree); \
         __n != NULL && \
         (((pos) = rbt_entry(__n, typeof(*(pos)), member)), true); \
         __n = rbt_prev(__n))

rbt_entry

Section titled “rbt_entry”
#define rbt_entry(ptr, type, member)
source
Expansion
#define rbt_entry(ptr, type, member) container_of(ptr, type, member)