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