summaryrefslogtreecommitdiff
path: root/src/common/tree.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/tree.h')
-rw-r--r--src/common/tree.h1159
1 files changed, 629 insertions, 530 deletions
diff --git a/src/common/tree.h b/src/common/tree.h
index 4a295f894..3da49e422 100644
--- a/src/common/tree.h
+++ b/src/common/tree.h
@@ -43,533 +43,632 @@
43 * The maximum height of a red-black tree is 2lg (n+1). 43 * The maximum height of a red-black tree is 2lg (n+1).
44 */ 44 */
45 45
46/* Macros that define a red-black tree */ 46namespace Common {
47#define RB_HEAD(name, type) \ 47template <typename T>
48 struct name { \ 48class RBHead {
49 struct type* rbh_root; /* root of the tree */ \ 49public:
50 } 50 [[nodiscard]] T* Root() {
51 51 return rbh_root;
52#define RB_INITIALIZER(root) \ 52 }
53 { NULL } 53
54 54 [[nodiscard]] const T* Root() const {
55#define RB_INIT(root) \ 55 return rbh_root;
56 do { \ 56 }
57 (root)->rbh_root = NULL; \ 57
58 } while (/*CONSTCOND*/ 0) 58 void SetRoot(T* root) {
59 59 rbh_root = root;
60#define RB_BLACK 0 60 }
61#define RB_RED 1 61
62#define RB_ENTRY(type) \ 62 [[nodiscard]] bool IsEmpty() const {
63 struct { \ 63 return Root() == nullptr;
64 struct type* rbe_left; /* left element */ \ 64 }
65 struct type* rbe_right; /* right element */ \ 65
66 struct type* rbe_parent; /* parent element */ \ 66private:
67 int rbe_color; /* node color */ \ 67 T* rbh_root = nullptr;
68 } 68};
69 69
70#define RB_LEFT(elm, field) (elm)->field.rbe_left 70enum class EntryColor {
71#define RB_RIGHT(elm, field) (elm)->field.rbe_right 71 Black,
72#define RB_PARENT(elm, field) (elm)->field.rbe_parent 72 Red,
73#define RB_COLOR(elm, field) (elm)->field.rbe_color 73};
74#define RB_ROOT(head) (head)->rbh_root 74
75#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 75template <typename T>
76 76class RBEntry {
77#define RB_SET(elm, parent, field) \ 77public:
78 do { \ 78 [[nodiscard]] T* Left() {
79 RB_PARENT(elm, field) = parent; \ 79 return rbe_left;
80 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 80 }
81 RB_COLOR(elm, field) = RB_RED; \ 81
82 } while (/*CONSTCOND*/ 0) 82 [[nodiscard]] const T* Left() const {
83 83 return rbe_left;
84#define RB_SET_BLACKRED(black, red, field) \ 84 }
85 do { \ 85
86 RB_COLOR(black, field) = RB_BLACK; \ 86 void SetLeft(T* left) {
87 RB_COLOR(red, field) = RB_RED; \ 87 rbe_left = left;
88 } while (/*CONSTCOND*/ 0) 88 }
89 89
90#ifndef RB_AUGMENT 90 [[nodiscard]] T* Right() {
91#define RB_AUGMENT(x) \ 91 return rbe_right;
92 do { \ 92 }
93 } while (0) 93
94#endif 94 [[nodiscard]] const T* Right() const {
95 95 return rbe_right;
96#define RB_ROTATE_LEFT(head, elm, tmp, field) \ 96 }
97 do { \ 97
98 (tmp) = RB_RIGHT(elm, field); \ 98 void SetRight(T* right) {
99 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 99 rbe_right = right;
100 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 100 }
101 } \ 101
102 RB_AUGMENT(elm); \ 102 [[nodiscard]] T* Parent() {
103 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 103 return rbe_parent;
104 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 104 }
105 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 105
106 else \ 106 [[nodiscard]] const T* Parent() const {
107 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 107 return rbe_parent;
108 } else \ 108 }
109 (head)->rbh_root = (tmp); \ 109
110 RB_LEFT(tmp, field) = (elm); \ 110 void SetParent(T* parent) {
111 RB_PARENT(elm, field) = (tmp); \ 111 rbe_parent = parent;
112 RB_AUGMENT(tmp); \ 112 }
113 if ((RB_PARENT(tmp, field))) \ 113
114 RB_AUGMENT(RB_PARENT(tmp, field)); \ 114 [[nodiscard]] bool IsBlack() const {
115 } while (/*CONSTCOND*/ 0) 115 return rbe_color == EntryColor::Black;
116 116 }
117#define RB_ROTATE_RIGHT(head, elm, tmp, field) \ 117
118 do { \ 118 [[nodiscard]] bool IsRed() const {
119 (tmp) = RB_LEFT(elm, field); \ 119 return rbe_color == EntryColor::Red;
120 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 120 }
121 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 121
122 } \ 122 [[nodiscard]] EntryColor Color() const {
123 RB_AUGMENT(elm); \ 123 return rbe_color;
124 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 124 }
125 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 125
126 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 126 void SetColor(EntryColor color) {
127 else \ 127 rbe_color = color;
128 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 128 }
129 } else \ 129
130 (head)->rbh_root = (tmp); \ 130private:
131 RB_RIGHT(tmp, field) = (elm); \ 131 T* rbe_left = nullptr;
132 RB_PARENT(elm, field) = (tmp); \ 132 T* rbe_right = nullptr;
133 RB_AUGMENT(tmp); \ 133 T* rbe_parent = nullptr;
134 if ((RB_PARENT(tmp, field))) \ 134 EntryColor rbe_color{};
135 RB_AUGMENT(RB_PARENT(tmp, field)); \ 135};
136 } while (/*CONSTCOND*/ 0) 136
137 137template <typename Node>
138/* Generates prototypes and inline functions */ 138[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) {
139#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, ) 139 return node->GetEntry();
140#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 140}
141 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static) 141
142#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 142template <typename Node>
143 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 143[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) {
144 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 144 return node->GetEntry();
145 RB_PROTOTYPE_INSERT(name, type, attr); \ 145}
146 RB_PROTOTYPE_REMOVE(name, type, attr); \ 146
147 RB_PROTOTYPE_FIND(name, type, attr); \ 147template <typename Node>
148 RB_PROTOTYPE_NFIND(name, type, attr); \ 148[[nodiscard]] Node* RB_PARENT(Node* node) {
149 RB_PROTOTYPE_FIND_LIGHT(name, type, attr); \ 149 return RB_ENTRY(node).Parent();
150 RB_PROTOTYPE_NFIND_LIGHT(name, type, attr); \ 150}
151 RB_PROTOTYPE_NEXT(name, type, attr); \ 151
152 RB_PROTOTYPE_PREV(name, type, attr); \ 152template <typename Node>
153 RB_PROTOTYPE_MINMAX(name, type, attr); 153[[nodiscard]] const Node* RB_PARENT(const Node* node) {
154#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 154 return RB_ENTRY(node).Parent();
155 attr void name##_RB_INSERT_COLOR(struct name*, struct type*) 155}
156#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 156
157 attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*) 157template <typename Node>
158#define RB_PROTOTYPE_REMOVE(name, type, attr) \ 158void RB_SET_PARENT(Node* node, Node* parent) {
159 attr struct type* name##_RB_REMOVE(struct name*, struct type*) 159 return RB_ENTRY(node).SetParent(parent);
160#define RB_PROTOTYPE_INSERT(name, type, attr) \ 160}
161 attr struct type* name##_RB_INSERT(struct name*, struct type*) 161
162#define RB_PROTOTYPE_FIND(name, type, attr) \ 162template <typename Node>
163 attr struct type* name##_RB_FIND(struct name*, struct type*) 163[[nodiscard]] Node* RB_LEFT(Node* node) {
164#define RB_PROTOTYPE_NFIND(name, type, attr) \ 164 return RB_ENTRY(node).Left();
165 attr struct type* name##_RB_NFIND(struct name*, struct type*) 165}
166#define RB_PROTOTYPE_FIND_LIGHT(name, type, attr) \ 166
167 attr struct type* name##_RB_FIND_LIGHT(struct name*, const void*) 167template <typename Node>
168#define RB_PROTOTYPE_NFIND_LIGHT(name, type, attr) \ 168[[nodiscard]] const Node* RB_LEFT(const Node* node) {
169 attr struct type* name##_RB_NFIND_LIGHT(struct name*, const void*) 169 return RB_ENTRY(node).Left();
170#define RB_PROTOTYPE_NEXT(name, type, attr) attr struct type* name##_RB_NEXT(struct type*) 170}
171#define RB_PROTOTYPE_PREV(name, type, attr) attr struct type* name##_RB_PREV(struct type*) 171
172#define RB_PROTOTYPE_MINMAX(name, type, attr) attr struct type* name##_RB_MINMAX(struct name*, int) 172template <typename Node>
173 173void RB_SET_LEFT(Node* node, Node* left) {
174/* Main rb operation. 174 return RB_ENTRY(node).SetLeft(left);
175 * Moves node close to the key of elm to top 175}
176 */ 176
177#define RB_GENERATE_WITHOUT_COMPARE(name, type, field) \ 177template <typename Node>
178 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, ) 178[[nodiscard]] Node* RB_RIGHT(Node* node) {
179#define RB_GENERATE_WITHOUT_COMPARE_STATIC(name, type, field) \ 179 return RB_ENTRY(node).Right();
180 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, static) 180}
181#define RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ 181
182 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 182template <typename Node>
183 RB_GENERATE_REMOVE(name, type, field, attr) \ 183[[nodiscard]] const Node* RB_RIGHT(const Node* node) {
184 RB_GENERATE_NEXT(name, type, field, attr) \ 184 return RB_ENTRY(node).Right();
185 RB_GENERATE_PREV(name, type, field, attr) \ 185}
186 RB_GENERATE_MINMAX(name, type, field, attr) 186
187 187template <typename Node>
188#define RB_GENERATE_WITH_COMPARE(name, type, field, cmp, lcmp) \ 188void RB_SET_RIGHT(Node* node, Node* right) {
189 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, ) 189 return RB_ENTRY(node).SetRight(right);
190#define RB_GENERATE_WITH_COMPARE_STATIC(name, type, field, cmp, lcmp) \ 190}
191 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, static) 191
192#define RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, attr) \ 192template <typename Node>
193 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 193[[nodiscard]] bool RB_IS_BLACK(const Node* node) {
194 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 194 return RB_ENTRY(node).IsBlack();
195 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 195}
196 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 196
197 RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ 197template <typename Node>
198 RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) 198[[nodiscard]] bool RB_IS_RED(const Node* node) {
199 199 return RB_ENTRY(node).IsRed();
200#define RB_GENERATE_ALL(name, type, field, cmp) RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, ) 200}
201#define RB_GENERATE_ALL_STATIC(name, type, field, cmp) \ 201
202 RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, static) 202template <typename Node>
203#define RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, attr) \ 203[[nodiscard]] EntryColor RB_COLOR(const Node* node) {
204 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ 204 return RB_ENTRY(node).Color();
205 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, attr) 205}
206 206
207#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 207template <typename Node>
208 attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { \ 208void RB_SET_COLOR(Node* node, EntryColor color) {
209 struct type *parent, *gparent, *tmp; \ 209 return RB_ENTRY(node).SetColor(color);
210 while ((parent = RB_PARENT(elm, field)) != NULL && RB_COLOR(parent, field) == RB_RED) { \ 210}
211 gparent = RB_PARENT(parent, field); \ 211
212 if (parent == RB_LEFT(gparent, field)) { \ 212template <typename Node>
213 tmp = RB_RIGHT(gparent, field); \ 213void RB_SET(Node* node, Node* parent) {
214 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 214 auto& entry = RB_ENTRY(node);
215 RB_COLOR(tmp, field) = RB_BLACK; \ 215 entry.SetParent(parent);
216 RB_SET_BLACKRED(parent, gparent, field); \ 216 entry.SetLeft(nullptr);
217 elm = gparent; \ 217 entry.SetRight(nullptr);
218 continue; \ 218 entry.SetColor(EntryColor::Red);
219 } \ 219}
220 if (RB_RIGHT(parent, field) == elm) { \ 220
221 RB_ROTATE_LEFT(head, parent, tmp, field); \ 221template <typename Node>
222 tmp = parent; \ 222void RB_SET_BLACKRED(Node* black, Node* red) {
223 parent = elm; \ 223 RB_SET_COLOR(black, EntryColor::Black);
224 elm = tmp; \ 224 RB_SET_COLOR(red, EntryColor::Red);
225 } \ 225}
226 RB_SET_BLACKRED(parent, gparent, field); \ 226
227 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 227template <typename Node>
228 } else { \ 228void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) {
229 tmp = RB_LEFT(gparent, field); \ 229 tmp = RB_RIGHT(elm);
230 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 230 RB_SET_RIGHT(elm, RB_LEFT(tmp));
231 RB_COLOR(tmp, field) = RB_BLACK; \ 231 if (RB_RIGHT(elm) != nullptr) {
232 RB_SET_BLACKRED(parent, gparent, field); \ 232 RB_SET_PARENT(RB_LEFT(tmp), elm);
233 elm = gparent; \ 233 }
234 continue; \ 234
235 } \ 235 RB_SET_PARENT(tmp, RB_PARENT(elm));
236 if (RB_LEFT(parent, field) == elm) { \ 236 if (RB_PARENT(tmp) != nullptr) {
237 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 237 if (elm == RB_LEFT(RB_PARENT(elm))) {
238 tmp = parent; \ 238 RB_SET_LEFT(RB_PARENT(elm), tmp);
239 parent = elm; \ 239 } else {
240 elm = tmp; \ 240 RB_SET_RIGHT(RB_PARENT(elm), tmp);
241 } \ 241 }
242 RB_SET_BLACKRED(parent, gparent, field); \ 242 } else {
243 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 243 head->SetRoot(tmp);
244 } \ 244 }
245 } \ 245
246 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 246 RB_SET_LEFT(tmp, elm);
247 } 247 RB_SET_PARENT(elm, tmp);
248 248}
249#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 249
250 attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { \ 250template <typename Node>
251 struct type* tmp; \ 251void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) {
252 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { \ 252 tmp = RB_LEFT(elm);
253 if (RB_LEFT(parent, field) == elm) { \ 253 RB_SET_LEFT(elm, RB_RIGHT(tmp));
254 tmp = RB_RIGHT(parent, field); \ 254 if (RB_LEFT(elm) != nullptr) {
255 if (RB_COLOR(tmp, field) == RB_RED) { \ 255 RB_SET_PARENT(RB_RIGHT(tmp), elm);
256 RB_SET_BLACKRED(tmp, parent, field); \ 256 }
257 RB_ROTATE_LEFT(head, parent, tmp, field); \ 257
258 tmp = RB_RIGHT(parent, field); \ 258 RB_SET_PARENT(tmp, RB_PARENT(elm));
259 } \ 259 if (RB_PARENT(tmp) != nullptr) {
260 if ((RB_LEFT(tmp, field) == NULL || \ 260 if (elm == RB_LEFT(RB_PARENT(elm))) {
261 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 261 RB_SET_LEFT(RB_PARENT(elm), tmp);
262 (RB_RIGHT(tmp, field) == NULL || \ 262 } else {
263 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 263 RB_SET_RIGHT(RB_PARENT(elm), tmp);
264 RB_COLOR(tmp, field) = RB_RED; \ 264 }
265 elm = parent; \ 265 } else {
266 parent = RB_PARENT(elm, field); \ 266 head->SetRoot(tmp);
267 } else { \ 267 }
268 if (RB_RIGHT(tmp, field) == NULL || \ 268
269 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 269 RB_SET_RIGHT(tmp, elm);
270 struct type* oleft; \ 270 RB_SET_PARENT(elm, tmp);
271 if ((oleft = RB_LEFT(tmp, field)) != NULL) \ 271}
272 RB_COLOR(oleft, field) = RB_BLACK; \ 272
273 RB_COLOR(tmp, field) = RB_RED; \ 273template <typename Node>
274 RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 274void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) {
275 tmp = RB_RIGHT(parent, field); \ 275 Node* parent = nullptr;
276 } \ 276 Node* tmp = nullptr;
277 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 277
278 RB_COLOR(parent, field) = RB_BLACK; \ 278 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
279 if (RB_RIGHT(tmp, field)) \ 279 Node* gparent = RB_PARENT(parent);
280 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 280 if (parent == RB_LEFT(gparent)) {
281 RB_ROTATE_LEFT(head, parent, tmp, field); \ 281 tmp = RB_RIGHT(gparent);
282 elm = RB_ROOT(head); \ 282 if (tmp && RB_IS_RED(tmp)) {
283 break; \ 283 RB_SET_COLOR(tmp, EntryColor::Black);
284 } \ 284 RB_SET_BLACKRED(parent, gparent);
285 } else { \ 285 elm = gparent;
286 tmp = RB_LEFT(parent, field); \ 286 continue;
287 if (RB_COLOR(tmp, field) == RB_RED) { \ 287 }
288 RB_SET_BLACKRED(tmp, parent, field); \ 288
289 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 289 if (RB_RIGHT(parent) == elm) {
290 tmp = RB_LEFT(parent, field); \ 290 RB_ROTATE_LEFT(head, parent, tmp);
291 } \ 291 tmp = parent;
292 if ((RB_LEFT(tmp, field) == NULL || \ 292 parent = elm;
293 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 293 elm = tmp;
294 (RB_RIGHT(tmp, field) == NULL || \ 294 }
295 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 295
296 RB_COLOR(tmp, field) = RB_RED; \ 296 RB_SET_BLACKRED(parent, gparent);
297 elm = parent; \ 297 RB_ROTATE_RIGHT(head, gparent, tmp);
298 parent = RB_PARENT(elm, field); \ 298 } else {
299 } else { \ 299 tmp = RB_LEFT(gparent);
300 if (RB_LEFT(tmp, field) == NULL || \ 300 if (tmp && RB_IS_RED(tmp)) {
301 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 301 RB_SET_COLOR(tmp, EntryColor::Black);
302 struct type* oright; \ 302 RB_SET_BLACKRED(parent, gparent);
303 if ((oright = RB_RIGHT(tmp, field)) != NULL) \ 303 elm = gparent;
304 RB_COLOR(oright, field) = RB_BLACK; \ 304 continue;
305 RB_COLOR(tmp, field) = RB_RED; \ 305 }
306 RB_ROTATE_LEFT(head, tmp, oright, field); \ 306
307 tmp = RB_LEFT(parent, field); \ 307 if (RB_LEFT(parent) == elm) {
308 } \ 308 RB_ROTATE_RIGHT(head, parent, tmp);
309 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 309 tmp = parent;
310 RB_COLOR(parent, field) = RB_BLACK; \ 310 parent = elm;
311 if (RB_LEFT(tmp, field)) \ 311 elm = tmp;
312 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 312 }
313 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 313
314 elm = RB_ROOT(head); \ 314 RB_SET_BLACKRED(parent, gparent);
315 break; \ 315 RB_ROTATE_LEFT(head, gparent, tmp);
316 } \ 316 }
317 } \ 317 }
318 } \ 318
319 if (elm) \ 319 RB_SET_COLOR(head->Root(), EntryColor::Black);
320 RB_COLOR(elm, field) = RB_BLACK; \ 320}
321 } 321
322 322template <typename Node>
323#define RB_GENERATE_REMOVE(name, type, field, attr) \ 323void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
324 attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { \ 324 Node* tmp;
325 struct type *child, *parent, *old = elm; \ 325 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root()) {
326 int color; \ 326 if (RB_LEFT(parent) == elm) {
327 if (RB_LEFT(elm, field) == NULL) \ 327 tmp = RB_RIGHT(parent);
328 child = RB_RIGHT(elm, field); \ 328 if (RB_IS_RED(tmp)) {
329 else if (RB_RIGHT(elm, field) == NULL) \ 329 RB_SET_BLACKRED(tmp, parent);
330 child = RB_LEFT(elm, field); \ 330 RB_ROTATE_LEFT(head, parent, tmp);
331 else { \ 331 tmp = RB_RIGHT(parent);
332 struct type* left; \ 332 }
333 elm = RB_RIGHT(elm, field); \ 333
334 while ((left = RB_LEFT(elm, field)) != NULL) \ 334 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
335 elm = left; \ 335 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
336 child = RB_RIGHT(elm, field); \ 336 RB_SET_COLOR(tmp, EntryColor::Red);
337 parent = RB_PARENT(elm, field); \ 337 elm = parent;
338 color = RB_COLOR(elm, field); \ 338 parent = RB_PARENT(elm);
339 if (child) \ 339 } else {
340 RB_PARENT(child, field) = parent; \ 340 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) {
341 if (parent) { \ 341 Node* oleft;
342 if (RB_LEFT(parent, field) == elm) \ 342 if ((oleft = RB_LEFT(tmp)) != nullptr) {
343 RB_LEFT(parent, field) = child; \ 343 RB_SET_COLOR(oleft, EntryColor::Black);
344 else \ 344 }
345 RB_RIGHT(parent, field) = child; \ 345
346 RB_AUGMENT(parent); \ 346 RB_SET_COLOR(tmp, EntryColor::Red);
347 } else \ 347 RB_ROTATE_RIGHT(head, tmp, oleft);
348 RB_ROOT(head) = child; \ 348 tmp = RB_RIGHT(parent);
349 if (RB_PARENT(elm, field) == old) \ 349 }
350 parent = elm; \ 350
351 (elm)->field = (old)->field; \ 351 RB_SET_COLOR(tmp, RB_COLOR(parent));
352 if (RB_PARENT(old, field)) { \ 352 RB_SET_COLOR(parent, EntryColor::Black);
353 if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 353 if (RB_RIGHT(tmp)) {
354 RB_LEFT(RB_PARENT(old, field), field) = elm; \ 354 RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black);
355 else \ 355 }
356 RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 356
357 RB_AUGMENT(RB_PARENT(old, field)); \ 357 RB_ROTATE_LEFT(head, parent, tmp);
358 } else \ 358 elm = head->Root();
359 RB_ROOT(head) = elm; \ 359 break;
360 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 360 }
361 if (RB_RIGHT(old, field)) \ 361 } else {
362 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 362 tmp = RB_LEFT(parent);
363 if (parent) { \ 363 if (RB_IS_RED(tmp)) {
364 left = parent; \ 364 RB_SET_BLACKRED(tmp, parent);
365 do { \ 365 RB_ROTATE_RIGHT(head, parent, tmp);
366 RB_AUGMENT(left); \ 366 tmp = RB_LEFT(parent);
367 } while ((left = RB_PARENT(left, field)) != NULL); \ 367 }
368 } \ 368
369 goto color; \ 369 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
370 } \ 370 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
371 parent = RB_PARENT(elm, field); \ 371 RB_SET_COLOR(tmp, EntryColor::Red);
372 color = RB_COLOR(elm, field); \ 372 elm = parent;
373 if (child) \ 373 parent = RB_PARENT(elm);
374 RB_PARENT(child, field) = parent; \ 374 } else {
375 if (parent) { \ 375 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) {
376 if (RB_LEFT(parent, field) == elm) \ 376 Node* oright;
377 RB_LEFT(parent, field) = child; \ 377 if ((oright = RB_RIGHT(tmp)) != nullptr) {
378 else \ 378 RB_SET_COLOR(oright, EntryColor::Black);
379 RB_RIGHT(parent, field) = child; \ 379 }
380 RB_AUGMENT(parent); \ 380
381 } else \ 381 RB_SET_COLOR(tmp, EntryColor::Red);
382 RB_ROOT(head) = child; \ 382 RB_ROTATE_LEFT(head, tmp, oright);
383 color: \ 383 tmp = RB_LEFT(parent);
384 if (color == RB_BLACK) \ 384 }
385 name##_RB_REMOVE_COLOR(head, parent, child); \ 385
386 return (old); \ 386 RB_SET_COLOR(tmp, RB_COLOR(parent));
387 } 387 RB_SET_COLOR(parent, EntryColor::Black);
388 388
389#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 389 if (RB_LEFT(tmp)) {
390 /* Inserts a node into the RB tree */ \ 390 RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black);
391 attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { \ 391 }
392 struct type* tmp; \ 392
393 struct type* parent = NULL; \ 393 RB_ROTATE_RIGHT(head, parent, tmp);
394 int comp = 0; \ 394 elm = head->Root();
395 tmp = RB_ROOT(head); \ 395 break;
396 while (tmp) { \ 396 }
397 parent = tmp; \ 397 }
398 comp = (cmp)(elm, parent); \ 398 }
399 if (comp < 0) \ 399
400 tmp = RB_LEFT(tmp, field); \ 400 if (elm) {
401 else if (comp > 0) \ 401 RB_SET_COLOR(elm, EntryColor::Black);
402 tmp = RB_RIGHT(tmp, field); \ 402 }
403 else \ 403}
404 return (tmp); \ 404
405 } \ 405template <typename Node>
406 RB_SET(elm, parent, field); \ 406Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
407 if (parent != NULL) { \ 407 Node* child = nullptr;
408 if (comp < 0) \ 408 Node* parent = nullptr;
409 RB_LEFT(parent, field) = elm; \ 409 Node* old = elm;
410 else \ 410 EntryColor color{};
411 RB_RIGHT(parent, field) = elm; \ 411
412 RB_AUGMENT(parent); \ 412 const auto finalize = [&] {
413 } else \ 413 if (color == EntryColor::Black) {
414 RB_ROOT(head) = elm; \ 414 RB_REMOVE_COLOR(head, parent, child);
415 name##_RB_INSERT_COLOR(head, elm); \ 415 }
416 return (NULL); \ 416
417 } 417 return old;
418 418 };
419#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 419
420 /* Finds the node with the same key as elm */ \ 420 if (RB_LEFT(elm) == nullptr) {
421 attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { \ 421 child = RB_RIGHT(elm);
422 struct type* tmp = RB_ROOT(head); \ 422 } else if (RB_RIGHT(elm) == nullptr) {
423 int comp; \ 423 child = RB_LEFT(elm);
424 while (tmp) { \ 424 } else {
425 comp = cmp(elm, tmp); \ 425 Node* left;
426 if (comp < 0) \ 426 elm = RB_RIGHT(elm);
427 tmp = RB_LEFT(tmp, field); \ 427 while ((left = RB_LEFT(elm)) != nullptr) {
428 else if (comp > 0) \ 428 elm = left;
429 tmp = RB_RIGHT(tmp, field); \ 429 }
430 else \ 430
431 return (tmp); \ 431 child = RB_RIGHT(elm);
432 } \ 432 parent = RB_PARENT(elm);
433 return (NULL); \ 433 color = RB_COLOR(elm);
434 } 434
435 435 if (child) {
436#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 436 RB_SET_PARENT(child, parent);
437 /* Finds the first node greater than or equal to the search key */ \ 437 }
438 attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { \ 438 if (parent) {
439 struct type* tmp = RB_ROOT(head); \ 439 if (RB_LEFT(parent) == elm) {
440 struct type* res = NULL; \ 440 RB_SET_LEFT(parent, child);
441 int comp; \ 441 } else {
442 while (tmp) { \ 442 RB_SET_RIGHT(parent, child);
443 comp = cmp(elm, tmp); \ 443 }
444 if (comp < 0) { \ 444 } else {
445 res = tmp; \ 445 head->SetRoot(child);
446 tmp = RB_LEFT(tmp, field); \ 446 }
447 } else if (comp > 0) \ 447
448 tmp = RB_RIGHT(tmp, field); \ 448 if (RB_PARENT(elm) == old) {
449 else \ 449 parent = elm;
450 return (tmp); \ 450 }
451 } \ 451
452 return (res); \ 452 elm->SetEntry(old->GetEntry());
453 } 453
454 454 if (RB_PARENT(old)) {
455#define RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ 455 if (RB_LEFT(RB_PARENT(old)) == old) {
456 /* Finds the node with the same key as elm */ \ 456 RB_SET_LEFT(RB_PARENT(old), elm);
457 attr struct type* name##_RB_FIND_LIGHT(struct name* head, const void* lelm) { \ 457 } else {
458 struct type* tmp = RB_ROOT(head); \ 458 RB_SET_RIGHT(RB_PARENT(old), elm);
459 int comp; \ 459 }
460 while (tmp) { \ 460 } else {
461 comp = lcmp(lelm, tmp); \ 461 head->SetRoot(elm);
462 if (comp < 0) \ 462 }
463 tmp = RB_LEFT(tmp, field); \ 463 RB_SET_PARENT(RB_LEFT(old), elm);
464 else if (comp > 0) \ 464 if (RB_RIGHT(old)) {
465 tmp = RB_RIGHT(tmp, field); \ 465 RB_SET_PARENT(RB_RIGHT(old), elm);
466 else \ 466 }
467 return (tmp); \ 467 if (parent) {
468 } \ 468 left = parent;
469 return (NULL); \ 469 }
470 } 470
471 471 return finalize();
472#define RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) \ 472 }
473 /* Finds the first node greater than or equal to the search key */ \ 473
474 attr struct type* name##_RB_NFIND_LIGHT(struct name* head, const void* lelm) { \ 474 parent = RB_PARENT(elm);
475 struct type* tmp = RB_ROOT(head); \ 475 color = RB_COLOR(elm);
476 struct type* res = NULL; \ 476
477 int comp; \ 477 if (child) {
478 while (tmp) { \ 478 RB_SET_PARENT(child, parent);
479 comp = lcmp(lelm, tmp); \ 479 }
480 if (comp < 0) { \ 480 if (parent) {
481 res = tmp; \ 481 if (RB_LEFT(parent) == elm) {
482 tmp = RB_LEFT(tmp, field); \ 482 RB_SET_LEFT(parent, child);
483 } else if (comp > 0) \ 483 } else {
484 tmp = RB_RIGHT(tmp, field); \ 484 RB_SET_RIGHT(parent, child);
485 else \ 485 }
486 return (tmp); \ 486 } else {
487 } \ 487 head->SetRoot(child);
488 return (res); \ 488 }
489 } 489
490 490 return finalize();
491#define RB_GENERATE_NEXT(name, type, field, attr) \ 491}
492 /* ARGSUSED */ \ 492
493 attr struct type* name##_RB_NEXT(struct type* elm) { \ 493// Inserts a node into the RB tree
494 if (RB_RIGHT(elm, field)) { \ 494template <typename Node, typename CompareFunction>
495 elm = RB_RIGHT(elm, field); \ 495Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
496 while (RB_LEFT(elm, field)) \ 496 Node* parent = nullptr;
497 elm = RB_LEFT(elm, field); \ 497 Node* tmp = head->Root();
498 } else { \ 498 int comp = 0;
499 if (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 499
500 elm = RB_PARENT(elm, field); \ 500 while (tmp) {
501 else { \ 501 parent = tmp;
502 while (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 502 comp = cmp(elm, parent);
503 elm = RB_PARENT(elm, field); \ 503 if (comp < 0) {
504 elm = RB_PARENT(elm, field); \ 504 tmp = RB_LEFT(tmp);
505 } \ 505 } else if (comp > 0) {
506 } \ 506 tmp = RB_RIGHT(tmp);
507 return (elm); \ 507 } else {
508 } 508 return tmp;
509 509 }
510#define RB_GENERATE_PREV(name, type, field, attr) \ 510 }
511 /* ARGSUSED */ \ 511
512 attr struct type* name##_RB_PREV(struct type* elm) { \ 512 RB_SET(elm, parent);
513 if (RB_LEFT(elm, field)) { \ 513
514 elm = RB_LEFT(elm, field); \ 514 if (parent != nullptr) {
515 while (RB_RIGHT(elm, field)) \ 515 if (comp < 0) {
516 elm = RB_RIGHT(elm, field); \ 516 RB_SET_LEFT(parent, elm);
517 } else { \ 517 } else {
518 if (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 518 RB_SET_RIGHT(parent, elm);
519 elm = RB_PARENT(elm, field); \ 519 }
520 else { \ 520 } else {
521 while (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 521 head->SetRoot(elm);
522 elm = RB_PARENT(elm, field); \ 522 }
523 elm = RB_PARENT(elm, field); \ 523
524 } \ 524 RB_INSERT_COLOR(head, elm);
525 } \ 525 return nullptr;
526 return (elm); \ 526}
527 } 527
528 528// Finds the node with the same key as elm
529#define RB_GENERATE_MINMAX(name, type, field, attr) \ 529template <typename Node, typename CompareFunction>
530 attr struct type* name##_RB_MINMAX(struct name* head, int val) { \ 530Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
531 struct type* tmp = RB_ROOT(head); \ 531 Node* tmp = head->Root();
532 struct type* parent = NULL; \ 532
533 while (tmp) { \ 533 while (tmp) {
534 parent = tmp; \ 534 const int comp = cmp(elm, tmp);
535 if (val < 0) \ 535 if (comp < 0) {
536 tmp = RB_LEFT(tmp, field); \ 536 tmp = RB_LEFT(tmp);
537 else \ 537 } else if (comp > 0) {
538 tmp = RB_RIGHT(tmp, field); \ 538 tmp = RB_RIGHT(tmp);
539 } \ 539 } else {
540 return (parent); \ 540 return tmp;
541 } 541 }
542 542 }
543#define RB_NEGINF -1 543
544#define RB_INF 1 544 return nullptr;
545 545}
546#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 546
547#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 547// Finds the first node greater than or equal to the search key
548#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 548template <typename Node, typename CompareFunction>
549#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 549Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
550#define RB_FIND_LIGHT(name, x, y) name##_RB_FIND_LIGHT(x, y) 550 Node* tmp = head->Root();
551#define RB_NFIND_LIGHT(name, x, y) name##_RB_NFIND_LIGHT(x, y) 551 Node* res = nullptr;
552#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 552
553#define RB_PREV(name, x, y) name##_RB_PREV(y) 553 while (tmp) {
554#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 554 const int comp = cmp(elm, tmp);
555#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 555 if (comp < 0) {
556 556 res = tmp;
557#define RB_FOREACH(x, name, head) \ 557 tmp = RB_LEFT(tmp);
558 for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x)) 558 } else if (comp > 0) {
559 559 tmp = RB_RIGHT(tmp);
560#define RB_FOREACH_FROM(x, name, y) \ 560 } else {
561 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y)) 561 return tmp;
562 562 }
563#define RB_FOREACH_SAFE(x, name, head, y) \ 563 }
564 for ((x) = RB_MIN(name, head); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 564
565 (x) = (y)) 565 return res;
566 566}
567#define RB_FOREACH_REVERSE(x, name, head) \ 567
568 for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x)) 568// Finds the node with the same key as lelm
569 569template <typename Node, typename CompareFunction>
570#define RB_FOREACH_REVERSE_FROM(x, name, y) \ 570Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
571 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y)) 571 Node* tmp = head->Root();
572 572
573#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 573 while (tmp) {
574 for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 574 const int comp = lcmp(lelm, tmp);
575 (x) = (y)) 575 if (comp < 0) {
576 tmp = RB_LEFT(tmp);
577 } else if (comp > 0) {
578 tmp = RB_RIGHT(tmp);
579 } else {
580 return tmp;
581 }
582 }
583
584 return nullptr;
585}
586
587// Finds the first node greater than or equal to the search key
588template <typename Node, typename CompareFunction>
589Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
590 Node* tmp = head->Root();
591 Node* res = nullptr;
592
593 while (tmp) {
594 const int comp = lcmp(lelm, tmp);
595 if (comp < 0) {
596 res = tmp;
597 tmp = RB_LEFT(tmp);
598 } else if (comp > 0) {
599 tmp = RB_RIGHT(tmp);
600 } else {
601 return tmp;
602 }
603 }
604
605 return res;
606}
607
608template <typename Node>
609Node* RB_NEXT(Node* elm) {
610 if (RB_RIGHT(elm)) {
611 elm = RB_RIGHT(elm);
612 while (RB_LEFT(elm)) {
613 elm = RB_LEFT(elm);
614 }
615 } else {
616 if (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
617 elm = RB_PARENT(elm);
618 } else {
619 while (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
620 elm = RB_PARENT(elm);
621 }
622 elm = RB_PARENT(elm);
623 }
624 }
625 return elm;
626}
627
628template <typename Node>
629Node* RB_PREV(Node* elm) {
630 if (RB_LEFT(elm)) {
631 elm = RB_LEFT(elm);
632 while (RB_RIGHT(elm)) {
633 elm = RB_RIGHT(elm);
634 }
635 } else {
636 if (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
637 elm = RB_PARENT(elm);
638 } else {
639 while (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
640 elm = RB_PARENT(elm);
641 }
642 elm = RB_PARENT(elm);
643 }
644 }
645 return elm;
646}
647
648template <typename Node>
649Node* RB_MINMAX(RBHead<Node>* head, bool is_min) {
650 Node* tmp = head->Root();
651 Node* parent = nullptr;
652
653 while (tmp) {
654 parent = tmp;
655 if (is_min) {
656 tmp = RB_LEFT(tmp);
657 } else {
658 tmp = RB_RIGHT(tmp);
659 }
660 }
661
662 return parent;
663}
664
665template <typename Node>
666Node* RB_MIN(RBHead<Node>* head) {
667 return RB_MINMAX(head, true);
668}
669
670template <typename Node>
671Node* RB_MAX(RBHead<Node>* head) {
672 return RB_MINMAX(head, false);
673}
674} // namespace Common
HIC SVNT DRACONES