Skip to content
charmOS docs

Red black tree

include/structures/rbt.h

Section titled “include/structures/rbt.h”

struct rbt_node

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

struct rbt_node referenced types:

struct rbt

Section titled “struct rbt”
struct rbt {
    rbt_get_data     get_data;
    rbt_compare      compare;
    struct rbt_node  *root;
};

struct rbt referenced types:

enum rbt_node_color

Section titled “enum rbt_node_color”
enum rbt_node_color {
    TREE_NODE_RED,
    TREE_NODE_BLACK,
};

type alias rbt_compare

Section titled “type alias rbt_compare”
typedef int32_t (*rbt_compare)(struct rbt_node * a, struct rbt_node * b);

type alias rbt_compare referenced types:

type alias rbt_get_data

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

type alias rbt_get_data referenced types:

rbt_last

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

rbt_last referenced types:

rbt_prev

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

rbt_prev referenced types:

rbt_init_node

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

rbt_init_node referenced types:

rbt_first

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

rbt_first referenced types:

rbt_init

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

rbt_init referenced types:

rbt_create

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

rbt_create referenced types:

rbt_find_min

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

rbt_find_min referenced types:

rbt_find_max

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

rbt_find_max referenced types:

rbt_delete

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

rbt_delete referenced types:

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

rbt_search referenced types:

rbt_remove

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

rbt_remove referenced types:

rbt_insert

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

rbt_insert referenced types:

rbt_min

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

rbt_min referenced types:

rbt_max

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

rbt_max referenced types:

rbt_next

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

rbt_next referenced types:

rbt_find_predecessor

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

rbt_find_predecessor referenced types:

rbt_find_successor

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

rbt_find_successor referenced types:

rbt_empty

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

rbt_empty referenced types:

rbt_has_node

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

rbt_has_node referenced types:

Defines

Section titled “Defines”

rbt_for_each_safe(pos, tmp, root)

Section titled “rbt_for_each_safe(pos, tmp, root)”
#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(pos, root)

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

rbt_for_each_reverse(pos, root)

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

rbt_entry(ptr, type, member)

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

rbt_parent(n)

Section titled “rbt_parent(n)”
#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  \ }