Red-Black Interval Tree

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

Structs

interval

struct interval {
    size_t  low;
    size_t  high;
};

rbit_node

struct rbit_node {
    struct interval   interval;
    enum rbit_color   color;
    size_t            max;
    struct rbit_node  *left;
    struct rbit_node  *right;
    struct rbit_node  *parent;
};

rbit

struct rbit {
    struct rbit_node  *root;
    rbit_augment_fn   augment;
};

Enums

rbit_color

enum rbit_color {
    RBIT_RED,
    RBIT_BLACK,
};

Type Aliases

rbit_augment_fn

typedef bool (*rbit_augment_fn)(struct rbit_node * node);

Functions

rbit_node_max

size_t rbit_node_max(const struct rbit_node *n);

rbit_init_node

void rbit_init_node(struct rbit_node *n);

rbit_first

struct rbit_node rbit_first(const struct rbit *tree);

rbit_last

struct rbit_node rbit_last(const struct rbit *tree);

rbit_prev

struct rbit_node rbit_prev(struct rbit_node *node);

rbit_empty

bool rbit_empty(const struct rbit *tree);

rbit_init

struct rbit * rbit_init(struct rbit *rbit);

rbit_tree_create

struct rbit * rbit_tree_create(void);

rbit_find_min

struct rbit_node * rbit_find_min(struct rbit_node *node);

rbit_find_max

struct rbit_node * rbit_find_max(struct rbit_node *node);

rbit_min

struct rbit_node * rbit_min(struct rbit *tree);

rbit_max

struct rbit_node * rbit_max(struct rbit *tree);

rbit_next

struct rbit_node * rbit_next(struct rbit_node *node);

rbit_find_predecessor

struct rbit_node * rbit_find_predecessor(struct rbit *tree, size_t low);

rbit_find_successor

struct rbit_node * rbit_find_successor(struct rbit *tree, size_t low);

rbit_has_node

bool rbit_has_node(struct rbit *tree, struct rbit_node *node);

rbit_delete

void rbit_delete(struct rbit *tree, struct rbit_node *z);

rbit_search

struct rbit_node * rbit_search(struct rbit_node *root, struct interval iv);

rbit_overlap_search

struct rbit_node * rbit_overlap_search(struct rbit_node *root, struct interval iv);

rbit_remove

void rbit_remove(struct rbit *tree, struct interval iv);

rbit_insert

void rbit_insert(struct rbit *tree, struct rbit_node *new_node);

Macros

rbit_for_each_safe

#define rbit_for_each_safe(pos, tmp, tree) \
    for (pos = rbit_first(tree), tmp = rbit_next(pos); pos != NULL; \
         pos = tmp, tmp = rbit_next(pos))

rbit_for_each_entry_safe

#define rbit_for_each_entry_safe(pos, tmp, tree, member) \
    for (pos = rbit_entry(rbit_first(tree), typeof(*pos), member), \
        tmp = rbit_entry(rbit_next(&pos->member), typeof(*pos), member); \
         pos != NULL; pos = tmp, \
        tmp = rbit_entry(rbit_next(&tmp->member), typeof(*tmp), member))

rbit_for_each_safe_reverse

#define rbit_for_each_safe_reverse(pos, tmp, tree) \
    for (pos = rbit_last(tree), tmp = rbit_prev(pos); pos != NULL; \
         pos = tmp, tmp = rbit_prev(pos))

rbit_for_each_entry_safe_reverse

#define rbit_for_each_entry_safe_reverse(pos, tmp, tree, member) \
    for (pos = rbit_entry(rbit_last(tree), typeof(*pos), member), \
        tmp = rbit_entry(rbit_prev(&pos->member), typeof(*pos), member); \
         pos != NULL; pos = tmp, \
        tmp = rbit_entry(rbit_prev(&tmp->member), typeof(*tmp), member))

rbit_for_each

#define rbit_for_each(pos, tree) \
    for (pos = rbit_first(tree); pos != NULL; pos = rbit_next(pos))

rbit_for_each_entry

#define rbit_for_each_entry(pos, tree, member) \
    for (pos = rbit_entry(rbit_first(tree), typeof(*pos), member); \
         pos != NULL; \
         pos = rbit_entry(rbit_next(&pos->member), typeof(*pos), member))

rbit_for_each_reverse

#define rbit_for_each_reverse(pos, tree) \
    for (pos = rbit_last(tree); pos != NULL; pos = rbit_prev(pos))

rbit_for_each_entry_reverse

#define rbit_for_each_entry_reverse(pos, tree, member) \
    for (pos = rbit_entry(rbit_last(tree), typeof(*pos), member); pos != NULL; \
         pos = rbit_entry(rbit_prev(&pos->member), typeof(*pos), member))

rbit_entry

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

rbit_parent

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

RBIT_NODE_INIT

#define RBIT_NODE_INIT \
    (struct rbit_node) { \
        .interval = {0, 0}, .color = RBIT_BLACK, .max = 0, .left = NULL, \
        .right = NULL, .parent = NULL \
    }

---