1/* @title: Red-Black Interval Tree */
2#pragma once
3#include <container_of.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdint.h>
7
8#define rbit_for_each_safe(pos, tmp, tree) \
9 for (pos = rbit_first(tree), tmp = rbit_next(pos); pos != NULL; \
10 pos = tmp, tmp = rbit_next(pos))
11
12#define rbit_for_each_entry_safe(pos, tmp, tree, member) \
13 for (typeof(rbit_first(tree)) __n = rbit_first(tree), __nx = NULL; \
14 __n != NULL && \
15 (((pos) = rbit_entry(__n, typeof(*(pos)), member)), \
16 (__nx = rbit_next(__n)), \
17 ((tmp) = __nx ? rbit_entry(__nx, typeof(*(tmp)), member) : NULL), \
18 true); \
19 __n = __nx)
20
21#define rbit_for_each_safe_reverse(pos, tmp, tree) \
22 for (pos = rbit_last(tree), tmp = rbit_prev(pos); pos != NULL; \
23 pos = tmp, tmp = rbit_prev(pos))
24
25#define rbit_for_each_entry_safe_reverse(pos, tmp, tree, member) \
26 for (typeof(rbit_last(tree)) __n = rbit_last(tree), __nx = NULL; \
27 __n != NULL && \
28 (((pos) = rbit_entry(__n, typeof(*(pos)), member)), \
29 (__nx = rbit_prev(__n)), \
30 ((tmp) = __nx ? rbit_entry(__nx, typeof(*(tmp)), member) : NULL), \
31 true); \
32 __n = __nx)
33
34#define rbit_for_each(pos, tree) \
35 for (pos = rbit_first(tree); pos != NULL; pos = rbit_next(pos))
36
37#define rbit_for_each_entry(pos, tree, member) \
38 for (typeof(rbit_first(tree)) __n = rbit_first(tree); \
39 __n != NULL && \
40 (((pos) = rbit_entry(__n, typeof(*(pos)), member)), true); \
41 __n = rbit_next(__n))
42
43#define rbit_for_each_reverse(pos, tree) \
44 for (pos = rbit_last(tree); pos != NULL; pos = rbit_prev(pos))
45
46#define rbit_for_each_entry_reverse(pos, tree, member) \
47 for (typeof(rbit_last(tree)) __n = rbit_last(tree); \
48 __n != NULL && \
49 (((pos) = rbit_entry(__n, typeof(*(pos)), member)), true); \
50 __n = rbit_prev(__n))
51
52#define rbit_entry(ptr, type, member) container_of(ptr, type, member)
53#define rbit_parent(n) ((n)->parent)
54
55enum rbit_color { RBIT_RED, RBIT_BLACK };
56
57struct interval {
58 size_t low;
59 size_t high;
60};
61
62struct rbit_node {
63 struct interval interval;
64 enum rbit_color color;
65 size_t max;
66 struct rbit_node *left;
67 struct rbit_node *right;
68 struct rbit_node *parent;
69};
70
71/* Augmentation hook: recompute `node`'s augmented data purely from its own
72 * interval and its children, and return whether anything changed */
73typedef bool (*rbit_augment_fn)(struct rbit_node *node);
74
75struct rbit {
76 struct rbit_node *root;
77 rbit_augment_fn augment; /* NULL => default interval-max */
78};
79
80static inline size_t rbit_node_max(const struct rbit_node *n) {
81 return n ? n->max : 0;
82}
83
84#define RBIT_NODE_INIT \
85 (struct rbit_node) { \
86 .interval = {0, 0}, .color = RBIT_BLACK, .max = 0, .left = NULL, \
87 .right = NULL, .parent = NULL \
88 }
89
90static inline void rbit_init_node(struct rbit_node *n) {
91 n->interval.low = 0;
92 n->interval.high = 0;
93 n->color = RBIT_BLACK;
94 n->max = 0;
95 n->left = n->right = n->parent = NULL;
96}
97
98static inline struct rbit_node *rbit_first(const struct rbit *tree) {
99 struct rbit_node *node = tree->root;
100 if (!node)
101 return NULL;
102 while (node->left)
103 node = node->left;
104 return node;
105}
106
107static inline struct rbit_node *rbit_last(const struct rbit *tree) {
108 struct rbit_node *node = tree->root;
109 if (!node)
110 return NULL;
111 while (node->right)
112 node = node->right;
113 return node;
114}
115
116static inline struct rbit_node *rbit_prev(struct rbit_node *node) {
117 if (!node)
118 return NULL;
119 if (node->left) {
120 /* predecessor is rightmost node of left subtree */
121 node = node->left;
122 while (node->right)
123 node = node->right;
124 return node;
125 }
126
127 /* climb up until we come from the right */
128 struct rbit_node *parent = node->parent;
129 while (parent && node == parent->left) {
130 node = parent;
131 parent = parent->parent;
132 }
133 return parent;
134}
135
136static inline bool rbit_empty(const struct rbit *tree) {
137 return !tree->root;
138}
139
140struct rbit *rbit_init(struct rbit *rbit);
141struct rbit *rbit_tree_create(void);
142struct rbit_node *rbit_find_min(struct rbit_node *node);
143struct rbit_node *rbit_find_max(struct rbit_node *node);
144struct rbit_node *rbit_min(struct rbit *tree);
145struct rbit_node *rbit_max(struct rbit *tree);
146struct rbit_node *rbit_next(struct rbit_node *node);
147struct rbit_node *rbit_find_predecessor(struct rbit *tree, size_t low);
148struct rbit_node *rbit_find_successor(struct rbit *tree, size_t low);
149bool rbit_has_node(struct rbit *tree, struct rbit_node *node);
150void rbit_delete(struct rbit *tree, struct rbit_node *cc_nonnull_ptr z);
151struct rbit_node *rbit_search(struct rbit_node *root, struct interval iv);
152struct rbit_node *rbit_overlap_search(struct rbit_node *root,
153 struct interval iv);
154void rbit_remove(struct rbit *tree, struct interval iv);
155void rbit_insert(struct rbit *tree, struct rbit_node *cc_nonnull_ptr new_node);
156