Skip to content
charmOS docs

Red black tree

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

Structs

Section titled “Structs”

rbt_node

Section titled “rbt_node”
struct rbt_node {
    enum rbt_node_color  color;
    struct rbt_node      *left;
    struct rbt_node      *right;
    struct rbt_node      *parent;
};

rbt

Section titled “rbt”
struct rbt {
    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 {
    TREE_NODE_RED,
    TREE_NODE_BLACK,
};

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

rbt_get_data

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

Functions

Section titled “Functions”

rbt_last

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

rbt_prev

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

rbt_init_node

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

rbt_first

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

rbt_insert_color

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

rbt_init

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

rbt_create

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

rbt_find_min

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

rbt_find_max

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

rbt_delete

Section titled “rbt_delete”
void rbt_delete(struct rbt *tree, struct rbt_node *z);
Section titled “rbt_search”
struct rbt_node * rbt_search(struct rbt *tree, uint64_t data);

rbt_remove

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

rbt_insert

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

rbt_min

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

rbt_max

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

rbt_next

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

rbt_find_predecessor

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

rbt_find_successor

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

rbt_empty

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

rbt_has_node

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

Macros

Section titled “Macros”

rbt_for_each_safe

Section titled “rbt_for_each_safe”
#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, type, member, root) \
    for (pos = rbt_entry(rbt_first(root), type, member), \
        tmp = rbt_entry(rbt_next(&pos->member), type, member); \
         &pos->member != NULL; \
         pos = tmp, tmp = rbt_entry(rbt_next(&tmp->member), type, member))

rbt_for_each_safe_reverse

Section titled “rbt_for_each_safe_reverse”
#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, type, member, root) \
    for (pos = rbt_entry(rbt_last(root), type, member), \
        tmp = rbt_entry(rbt_prev(&pos->member), type, member); \
         &pos->member != NULL; \
         pos = tmp, tmp = rbt_entry(rbt_prev(&tmp->member), type, member))

rbt_for_each

Section titled “rbt_for_each”
#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, type, member, root) \
    for (pos = rbt_entry(rbt_first(root), type, member); &pos->member != NULL; \
         pos = rbt_entry(rbt_next(&pos->member), type, member))

rbt_for_each_reverse

Section titled “rbt_for_each_reverse”
#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, type, member, root) \
    for (pos = rbt_entry(rbt_last(root), type, member); &pos->member != NULL; \
         pos = rbt_entry(rbt_prev(&pos->member), type, member))

rbt_entry

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

rbt_parent

Section titled “rbt_parent”
#define rbt_parent(n) ((n)->parent)

RBT_NODE_INIT

Section titled “RBT_NODE_INIT”
#define RBT_NODE_INIT \
    (struct rbt_node) { \
        .color = TREE_NODE_BLACK, .left = NULL, .right = NULL, .parent = NULL \
    }