Red black tree

include/structures/rbt.h

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:

• enum rbt_node_color
• struct rbt_node

struct rbt

struct rbt {
    rbt_get_data     get_data;
    rbt_compare      compare;
    struct rbt_node  *root;
};

struct rbt referenced types:

• rbt_get_data
• rbt_compare
• struct rbt_node

enum rbt_node_color

enum rbt_node_color {
    TREE_NODE_RED,
    TREE_NODE_BLACK,
};

type alias rbt_compare

typedef int32_t (*rbt_compare)(struct rbt_node * a, struct rbt_node * b);

type alias rbt_compare referenced types:

• struct rbt_node

type alias rbt_get_data

typedef size_t (*rbt_get_data)(struct rbt_node *);

type alias rbt_get_data referenced types:

• struct rbt_node

rbt_last

struct rbt_node rbt_last(struct rbt *root);

rbt_last referenced types:

• struct rbt_node
• struct rbt

rbt_prev

struct rbt_node rbt_prev(struct rbt_node *node);

rbt_prev referenced types:

• struct rbt_node

rbt_init_node

void rbt_init_node(struct rbt_node *n);

rbt_init_node referenced types:

• struct rbt_node

rbt_first

struct rbt_node rbt_first(struct rbt *root);

rbt_first referenced types:

• struct rbt_node
• struct rbt

rbt_empty

bool rbt_empty(struct rbt *tree);

rbt_empty referenced types:

• struct rbt

Defines

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)

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

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)

#define rbt_entry(ptr, type, member) container_of(ptr, type, member)

rbt_parent(n)

#define rbt_parent(n) ((n)->parent)

---