Red-Black Interval Tree

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

Structs

interval

struct interval (2 fields) source

§ size_t low

§ size_t high

rbit_node

struct rbit_node (6 fields) source

§ 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 (2 fields) source

§ struct rbit_node *root

§ rbit_augment_fn augment

NULL => default interval-max

Enums

rbit_color

enum rbit_color (2 variants) source

§ RBIT_RED

§ RBIT_BLACK

Type Aliases

rbit_augment_fn

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

source

Augmentation hook: recompute node’s augmented data purely from its own interval and its children, and return whether anything changed

Functions

rbit_node_max

size_t rbit_node_max(const struct rbit_node *n)

source

rbit_init_node

void rbit_init_node(struct rbit_node *n)

source

rbit_first

struct rbit_node * rbit_first(const struct rbit *tree)

source

rbit_last

struct rbit_node * rbit_last(const struct rbit *tree)

source

rbit_prev

struct rbit_node * rbit_prev(struct rbit_node *node)

source

rbit_empty

bool rbit_empty(const struct rbit *tree)

source

rbit_init

struct rbit * rbit_init(struct rbit *rbit)

source

rbit_tree_create

struct rbit * rbit_tree_create(void)

source

rbit_find_min

struct rbit_node * rbit_find_min(struct rbit_node *node)

source

rbit_find_max

struct rbit_node * rbit_find_max(struct rbit_node *node)

source

rbit_min

struct rbit_node * rbit_min(struct rbit *tree)

source

rbit_max

struct rbit_node * rbit_max(struct rbit *tree)

source

rbit_next

struct rbit_node * rbit_next(struct rbit_node *node)

source

rbit_find_predecessor

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

source

rbit_find_successor

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

source

rbit_has_node

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

source

rbit_delete

void rbit_delete(struct rbit *tree, struct rbit_node *cc_nonnull_ptr)

source

rbit_search

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

source

rbit_overlap_search

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

source

rbit_remove

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

source

rbit_insert

void rbit_insert(struct rbit *tree, struct rbit_node *cc_nonnull_ptr)

source

Macros

rbit_for_each_safe

#define rbit_for_each_safe(pos, tmp, tree)

source

Expansion

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

source

Expansion

#define rbit_for_each_entry_safe(pos, tmp, tree, member) \
    for (typeof(rbit_first(tree)) __n = rbit_first(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = rbit_entry(__n, typeof(*(pos)), member)), \
          (__nx = rbit_next(__n)), \
          ((tmp) = __nx ? rbit_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)

rbit_for_each_safe_reverse

#define rbit_for_each_safe_reverse(pos, tmp, tree)

source

Expansion

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

source

Expansion

#define rbit_for_each_entry_safe_reverse(pos, tmp, tree, member) \
    for (typeof(rbit_last(tree)) __n = rbit_last(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = rbit_entry(__n, typeof(*(pos)), member)), \
          (__nx = rbit_prev(__n)), \
          ((tmp) = __nx ? rbit_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)

rbit_for_each

#define rbit_for_each(pos, tree)

source

Expansion

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

source

Expansion

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

rbit_for_each_reverse

#define rbit_for_each_reverse(pos, tree)

source

Expansion

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

source

Expansion

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

rbit_entry

#define rbit_entry(ptr, type, member)

source

Expansion

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

rbit_parent

#define rbit_parent(n)

source

Expansion

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

RBIT_NODE_INIT

#define RBIT_NODE_INIT

source

Expansion

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