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.h1410
1 files changed, 631 insertions, 779 deletions
diff --git a/src/common/tree.h b/src/common/tree.h
index a6b636646..3da49e422 100644
--- a/src/common/tree.h
+++ b/src/common/tree.h
@@ -27,33 +27,10 @@
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */ 28 */
29 29
30#ifndef _SYS_TREE_H_ 30#pragma once
31#define _SYS_TREE_H_
32
33/* FreeBSD <sys/cdefs.h> has a lot of defines we don't really want. */
34/* tree.h only actually uses __inline and __unused, so we'll just define those. */
35
36/* #include <sys/cdefs.h> */
37
38#ifndef __inline
39#define __inline inline
40#endif
41 31
42/* 32/*
43 * This file defines data structures for different types of trees: 33 * This file defines data structures for red-black trees.
44 * splay trees and red-black trees.
45 *
46 * A splay tree is a self-organizing data structure. Every operation
47 * on the tree causes a splay to happen. The splay moves the requested
48 * node to the root of the tree and partly rebalances it.
49 *
50 * This has the benefit that request locality causes faster lookups as
51 * the requested nodes move to the top of the tree. On the other hand,
52 * every lookup causes memory writes.
53 *
54 * The Balance Theorem bounds the total access time for m operations
55 * and n inserts on an initially empty tree as O((m + n)lg n). The
56 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
57 * 34 *
58 * A red-black tree is a binary search tree with the node color as an 35 * A red-black tree is a binary search tree with the node color as an
59 * extra attribute. It fulfills a set of conditions: 36 * extra attribute. It fulfills a set of conditions:
@@ -66,757 +43,632 @@
66 * 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).
67 */ 44 */
68 45
69#define SPLAY_HEAD(name, type) \ 46namespace Common {
70 struct name { \ 47template <typename T>
71 struct type* sph_root; /* root of the tree */ \ 48class RBHead {
72 } 49public:
73 50 [[nodiscard]] T* Root() {
74#define SPLAY_INITIALIZER(root) \ 51 return rbh_root;
75 { NULL } 52 }
76 53
77#define SPLAY_INIT(root) \ 54 [[nodiscard]] const T* Root() const {
78 do { \ 55 return rbh_root;
79 (root)->sph_root = NULL; \ 56 }
80 } while (/*CONSTCOND*/ 0) 57
81 58 void SetRoot(T* root) {
82#define SPLAY_ENTRY(type) \ 59 rbh_root = root;
83 struct { \ 60 }
84 struct type* spe_left; /* left element */ \ 61
85 struct type* spe_right; /* right element */ \ 62 [[nodiscard]] bool IsEmpty() const {
86 } 63 return Root() == nullptr;
87 64 }
88#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 65
89#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 66private:
90#define SPLAY_ROOT(head) (head)->sph_root 67 T* rbh_root = nullptr;
91#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 68};
92 69
93/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 70enum class EntryColor {
94#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ 71 Black,
95 do { \ 72 Red,
96 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 73};
97 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 74
98 (head)->sph_root = tmp; \ 75template <typename T>
99 } while (/*CONSTCOND*/ 0) 76class RBEntry {
100 77public:
101#define SPLAY_ROTATE_LEFT(head, tmp, field) \ 78 [[nodiscard]] T* Left() {
102 do { \ 79 return rbe_left;
103 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 80 }
104 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 81
105 (head)->sph_root = tmp; \ 82 [[nodiscard]] const T* Left() const {
106 } while (/*CONSTCOND*/ 0) 83 return rbe_left;
107 84 }
108#define SPLAY_LINKLEFT(head, tmp, field) \ 85
109 do { \ 86 void SetLeft(T* left) {
110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 87 rbe_left = left;
111 tmp = (head)->sph_root; \ 88 }
112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 89
113 } while (/*CONSTCOND*/ 0) 90 [[nodiscard]] T* Right() {
114 91 return rbe_right;
115#define SPLAY_LINKRIGHT(head, tmp, field) \ 92 }
116 do { \ 93
117 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 94 [[nodiscard]] const T* Right() const {
118 tmp = (head)->sph_root; \ 95 return rbe_right;
119 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 96 }
120 } while (/*CONSTCOND*/ 0) 97
121 98 void SetRight(T* right) {
122#define SPLAY_ASSEMBLE(head, node, left, right, field) \ 99 rbe_right = right;
123 do { \ 100 }
124 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 101
125 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ 102 [[nodiscard]] T* Parent() {
126 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 103 return rbe_parent;
127 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 104 }
128 } while (/*CONSTCOND*/ 0) 105
129 106 [[nodiscard]] const T* Parent() const {
130/* Generates prototypes and inline functions */ 107 return rbe_parent;
131 108 }
132#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 109
133 void name##_SPLAY(struct name*, struct type*); \ 110 void SetParent(T* parent) {
134 void name##_SPLAY_MINMAX(struct name*, int); \ 111 rbe_parent = parent;
135 struct type* name##_SPLAY_INSERT(struct name*, struct type*); \ 112 }
136 struct type* name##_SPLAY_REMOVE(struct name*, struct type*); \ 113
137 \ 114 [[nodiscard]] bool IsBlack() const {
138 /* Finds the node with the same key as elm */ \ 115 return rbe_color == EntryColor::Black;
139 static __inline struct type* name##_SPLAY_FIND(struct name* head, struct type* elm) { \ 116 }
140 if (SPLAY_EMPTY(head)) \ 117
141 return (NULL); \ 118 [[nodiscard]] bool IsRed() const {
142 name##_SPLAY(head, elm); \ 119 return rbe_color == EntryColor::Red;
143 if ((cmp)(elm, (head)->sph_root) == 0) \ 120 }
144 return (head->sph_root); \ 121
145 return (NULL); \ 122 [[nodiscard]] EntryColor Color() const {
146 } \ 123 return rbe_color;
147 \ 124 }
148 static __inline struct type* name##_SPLAY_NEXT(struct name* head, struct type* elm) { \ 125
149 name##_SPLAY(head, elm); \ 126 void SetColor(EntryColor color) {
150 if (SPLAY_RIGHT(elm, field) != NULL) { \ 127 rbe_color = color;
151 elm = SPLAY_RIGHT(elm, field); \ 128 }
152 while (SPLAY_LEFT(elm, field) != NULL) { \ 129
153 elm = SPLAY_LEFT(elm, field); \ 130private:
154 } \ 131 T* rbe_left = nullptr;
155 } else \ 132 T* rbe_right = nullptr;
156 elm = NULL; \ 133 T* rbe_parent = nullptr;
157 return (elm); \ 134 EntryColor rbe_color{};
158 } \ 135};
159 \ 136
160 static __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { \ 137template <typename Node>
161 name##_SPLAY_MINMAX(head, val); \ 138[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) {
162 return (SPLAY_ROOT(head)); \ 139 return node->GetEntry();
163 } 140}
164 141
165/* Main splay operation. 142template <typename Node>
166 * Moves node close to the key of elm to top 143[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) {
167 */ 144 return node->GetEntry();
168#define SPLAY_GENERATE(name, type, field, cmp) \ 145}
169 struct type* name##_SPLAY_INSERT(struct name* head, struct type* elm) { \ 146
170 if (SPLAY_EMPTY(head)) { \ 147template <typename Node>
171 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 148[[nodiscard]] Node* RB_PARENT(Node* node) {
172 } else { \ 149 return RB_ENTRY(node).Parent();
173 int __comp; \ 150}
174 name##_SPLAY(head, elm); \ 151
175 __comp = (cmp)(elm, (head)->sph_root); \ 152template <typename Node>
176 if (__comp < 0) { \ 153[[nodiscard]] const Node* RB_PARENT(const Node* node) {
177 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ 154 return RB_ENTRY(node).Parent();
178 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 155}
179 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 156
180 } else if (__comp > 0) { \ 157template <typename Node>
181 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ 158void RB_SET_PARENT(Node* node, Node* parent) {
182 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 159 return RB_ENTRY(node).SetParent(parent);
183 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 160}
184 } else \ 161
185 return ((head)->sph_root); \ 162template <typename Node>
186 } \ 163[[nodiscard]] Node* RB_LEFT(Node* node) {
187 (head)->sph_root = (elm); \ 164 return RB_ENTRY(node).Left();
188 return (NULL); \ 165}
189 } \ 166
190 \ 167template <typename Node>
191 struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) { \ 168[[nodiscard]] const Node* RB_LEFT(const Node* node) {
192 struct type* __tmp; \ 169 return RB_ENTRY(node).Left();
193 if (SPLAY_EMPTY(head)) \ 170}
194 return (NULL); \ 171
195 name##_SPLAY(head, elm); \ 172template <typename Node>
196 if ((cmp)(elm, (head)->sph_root) == 0) { \ 173void RB_SET_LEFT(Node* node, Node* left) {
197 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 174 return RB_ENTRY(node).SetLeft(left);
198 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 175}
199 } else { \ 176
200 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 177template <typename Node>
201 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 178[[nodiscard]] Node* RB_RIGHT(Node* node) {
202 name##_SPLAY(head, elm); \ 179 return RB_ENTRY(node).Right();
203 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 180}
204 } \ 181
205 return (elm); \ 182template <typename Node>
206 } \ 183[[nodiscard]] const Node* RB_RIGHT(const Node* node) {
207 return (NULL); \ 184 return RB_ENTRY(node).Right();
208 } \ 185}
209 \ 186
210 void name##_SPLAY(struct name* head, struct type* elm) { \ 187template <typename Node>
211 struct type __node, *__left, *__right, *__tmp; \ 188void RB_SET_RIGHT(Node* node, Node* right) {
212 int __comp; \ 189 return RB_ENTRY(node).SetRight(right);
213 \ 190}
214 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 191
215 __left = __right = &__node; \ 192template <typename Node>
216 \ 193[[nodiscard]] bool RB_IS_BLACK(const Node* node) {
217 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 194 return RB_ENTRY(node).IsBlack();
218 if (__comp < 0) { \ 195}
219 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 196
220 if (__tmp == NULL) \ 197template <typename Node>
221 break; \ 198[[nodiscard]] bool RB_IS_RED(const Node* node) {
222 if ((cmp)(elm, __tmp) < 0) { \ 199 return RB_ENTRY(node).IsRed();
223 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 200}
224 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 201
225 break; \ 202template <typename Node>
226 } \ 203[[nodiscard]] EntryColor RB_COLOR(const Node* node) {
227 SPLAY_LINKLEFT(head, __right, field); \ 204 return RB_ENTRY(node).Color();
228 } else if (__comp > 0) { \ 205}
229 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 206
230 if (__tmp == NULL) \ 207template <typename Node>
231 break; \ 208void RB_SET_COLOR(Node* node, EntryColor color) {
232 if ((cmp)(elm, __tmp) > 0) { \ 209 return RB_ENTRY(node).SetColor(color);
233 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 210}
234 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 211
235 break; \ 212template <typename Node>
236 } \ 213void RB_SET(Node* node, Node* parent) {
237 SPLAY_LINKRIGHT(head, __left, field); \ 214 auto& entry = RB_ENTRY(node);
238 } \ 215 entry.SetParent(parent);
239 } \ 216 entry.SetLeft(nullptr);
240 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 217 entry.SetRight(nullptr);
241 } \ 218 entry.SetColor(EntryColor::Red);
242 \ 219}
243 /* Splay with either the minimum or the maximum element \ 220
244 * Used to find minimum or maximum element in tree. \ 221template <typename Node>
245 */ \ 222void RB_SET_BLACKRED(Node* black, Node* red) {
246 void name##_SPLAY_MINMAX(struct name* head, int __comp) { \ 223 RB_SET_COLOR(black, EntryColor::Black);
247 struct type __node, *__left, *__right, *__tmp; \ 224 RB_SET_COLOR(red, EntryColor::Red);
248 \ 225}
249 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 226
250 __left = __right = &__node; \ 227template <typename Node>
251 \ 228void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) {
252 while (1) { \ 229 tmp = RB_RIGHT(elm);
253 if (__comp < 0) { \ 230 RB_SET_RIGHT(elm, RB_LEFT(tmp));
254 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 231 if (RB_RIGHT(elm) != nullptr) {
255 if (__tmp == NULL) \ 232 RB_SET_PARENT(RB_LEFT(tmp), elm);
256 break; \ 233 }
257 if (__comp < 0) { \ 234
258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 235 RB_SET_PARENT(tmp, RB_PARENT(elm));
259 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 236 if (RB_PARENT(tmp) != nullptr) {
260 break; \ 237 if (elm == RB_LEFT(RB_PARENT(elm))) {
261 } \ 238 RB_SET_LEFT(RB_PARENT(elm), tmp);
262 SPLAY_LINKLEFT(head, __right, field); \ 239 } else {
263 } else if (__comp > 0) { \ 240 RB_SET_RIGHT(RB_PARENT(elm), tmp);
264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 241 }
265 if (__tmp == NULL) \ 242 } else {
266 break; \ 243 head->SetRoot(tmp);
267 if (__comp > 0) { \ 244 }
268 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 245
269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 246 RB_SET_LEFT(tmp, elm);
270 break; \ 247 RB_SET_PARENT(elm, tmp);
271 } \ 248}
272 SPLAY_LINKRIGHT(head, __left, field); \ 249
273 } \ 250template <typename Node>
274 } \ 251void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) {
275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 252 tmp = RB_LEFT(elm);
276 } 253 RB_SET_LEFT(elm, RB_RIGHT(tmp));
277 254 if (RB_LEFT(elm) != nullptr) {
278#define SPLAY_NEGINF -1 255 RB_SET_PARENT(RB_RIGHT(tmp), elm);
279#define SPLAY_INF 1 256 }
280 257
281#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 258 RB_SET_PARENT(tmp, RB_PARENT(elm));
282#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 259 if (RB_PARENT(tmp) != nullptr) {
283#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 260 if (elm == RB_LEFT(RB_PARENT(elm))) {
284#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 261 RB_SET_LEFT(RB_PARENT(elm), tmp);
285#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 262 } else {
286#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 263 RB_SET_RIGHT(RB_PARENT(elm), tmp);
287 264 }
288#define SPLAY_FOREACH(x, name, head) \ 265 } else {
289 for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x)) 266 head->SetRoot(tmp);
290 267 }
291/* Macros that define a red-black tree */ 268
292#define RB_HEAD(name, type) \ 269 RB_SET_RIGHT(tmp, elm);
293 struct name { \ 270 RB_SET_PARENT(elm, tmp);
294 struct type* rbh_root; /* root of the tree */ \ 271}
295 } 272
296 273template <typename Node>
297#define RB_INITIALIZER(root) \ 274void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) {
298 { NULL } 275 Node* parent = nullptr;
299 276 Node* tmp = nullptr;
300#define RB_INIT(root) \ 277
301 do { \ 278 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
302 (root)->rbh_root = NULL; \ 279 Node* gparent = RB_PARENT(parent);
303 } while (/*CONSTCOND*/ 0) 280 if (parent == RB_LEFT(gparent)) {
304 281 tmp = RB_RIGHT(gparent);
305#define RB_BLACK 0 282 if (tmp && RB_IS_RED(tmp)) {
306#define RB_RED 1 283 RB_SET_COLOR(tmp, EntryColor::Black);
307#define RB_ENTRY(type) \ 284 RB_SET_BLACKRED(parent, gparent);
308 struct { \ 285 elm = gparent;
309 struct type* rbe_left; /* left element */ \ 286 continue;
310 struct type* rbe_right; /* right element */ \ 287 }
311 struct type* rbe_parent; /* parent element */ \ 288
312 int rbe_color; /* node color */ \ 289 if (RB_RIGHT(parent) == elm) {
313 } 290 RB_ROTATE_LEFT(head, parent, tmp);
314 291 tmp = parent;
315#define RB_LEFT(elm, field) (elm)->field.rbe_left 292 parent = elm;
316#define RB_RIGHT(elm, field) (elm)->field.rbe_right 293 elm = tmp;
317#define RB_PARENT(elm, field) (elm)->field.rbe_parent 294 }
318#define RB_COLOR(elm, field) (elm)->field.rbe_color 295
319#define RB_ROOT(head) (head)->rbh_root 296 RB_SET_BLACKRED(parent, gparent);
320#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 297 RB_ROTATE_RIGHT(head, gparent, tmp);
321 298 } else {
322#define RB_SET(elm, parent, field) \ 299 tmp = RB_LEFT(gparent);
323 do { \ 300 if (tmp && RB_IS_RED(tmp)) {
324 RB_PARENT(elm, field) = parent; \ 301 RB_SET_COLOR(tmp, EntryColor::Black);
325 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 302 RB_SET_BLACKRED(parent, gparent);
326 RB_COLOR(elm, field) = RB_RED; \ 303 elm = gparent;
327 } while (/*CONSTCOND*/ 0) 304 continue;
328 305 }
329#define RB_SET_BLACKRED(black, red, field) \ 306
330 do { \ 307 if (RB_LEFT(parent) == elm) {
331 RB_COLOR(black, field) = RB_BLACK; \ 308 RB_ROTATE_RIGHT(head, parent, tmp);
332 RB_COLOR(red, field) = RB_RED; \ 309 tmp = parent;
333 } while (/*CONSTCOND*/ 0) 310 parent = elm;
334 311 elm = tmp;
335#ifndef RB_AUGMENT 312 }
336#define RB_AUGMENT(x) \ 313
337 do { \ 314 RB_SET_BLACKRED(parent, gparent);
338 } while (0) 315 RB_ROTATE_LEFT(head, gparent, tmp);
339#endif 316 }
340 317 }
341#define RB_ROTATE_LEFT(head, elm, tmp, field) \ 318
342 do { \ 319 RB_SET_COLOR(head->Root(), EntryColor::Black);
343 (tmp) = RB_RIGHT(elm, field); \ 320}
344 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 321
345 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 322template <typename Node>
346 } \ 323void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
347 RB_AUGMENT(elm); \ 324 Node* tmp;
348 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 325 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root()) {
349 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 326 if (RB_LEFT(parent) == elm) {
350 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 327 tmp = RB_RIGHT(parent);
351 else \ 328 if (RB_IS_RED(tmp)) {
352 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 329 RB_SET_BLACKRED(tmp, parent);
353 } else \ 330 RB_ROTATE_LEFT(head, parent, tmp);
354 (head)->rbh_root = (tmp); \ 331 tmp = RB_RIGHT(parent);
355 RB_LEFT(tmp, field) = (elm); \ 332 }
356 RB_PARENT(elm, field) = (tmp); \ 333
357 RB_AUGMENT(tmp); \ 334 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
358 if ((RB_PARENT(tmp, field))) \ 335 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
359 RB_AUGMENT(RB_PARENT(tmp, field)); \ 336 RB_SET_COLOR(tmp, EntryColor::Red);
360 } while (/*CONSTCOND*/ 0) 337 elm = parent;
361 338 parent = RB_PARENT(elm);
362#define RB_ROTATE_RIGHT(head, elm, tmp, field) \ 339 } else {
363 do { \ 340 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) {
364 (tmp) = RB_LEFT(elm, field); \ 341 Node* oleft;
365 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 342 if ((oleft = RB_LEFT(tmp)) != nullptr) {
366 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 343 RB_SET_COLOR(oleft, EntryColor::Black);
367 } \ 344 }
368 RB_AUGMENT(elm); \ 345
369 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 346 RB_SET_COLOR(tmp, EntryColor::Red);
370 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 347 RB_ROTATE_RIGHT(head, tmp, oleft);
371 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 348 tmp = RB_RIGHT(parent);
372 else \ 349 }
373 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 350
374 } else \ 351 RB_SET_COLOR(tmp, RB_COLOR(parent));
375 (head)->rbh_root = (tmp); \ 352 RB_SET_COLOR(parent, EntryColor::Black);
376 RB_RIGHT(tmp, field) = (elm); \ 353 if (RB_RIGHT(tmp)) {
377 RB_PARENT(elm, field) = (tmp); \ 354 RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black);
378 RB_AUGMENT(tmp); \ 355 }
379 if ((RB_PARENT(tmp, field))) \ 356
380 RB_AUGMENT(RB_PARENT(tmp, field)); \ 357 RB_ROTATE_LEFT(head, parent, tmp);
381 } while (/*CONSTCOND*/ 0) 358 elm = head->Root();
382 359 break;
383/* Generates prototypes and inline functions */ 360 }
384#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, ) 361 } else {
385#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 362 tmp = RB_LEFT(parent);
386 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static) 363 if (RB_IS_RED(tmp)) {
387#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 364 RB_SET_BLACKRED(tmp, parent);
388 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 365 RB_ROTATE_RIGHT(head, parent, tmp);
389 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 366 tmp = RB_LEFT(parent);
390 RB_PROTOTYPE_INSERT(name, type, attr); \ 367 }
391 RB_PROTOTYPE_REMOVE(name, type, attr); \ 368
392 RB_PROTOTYPE_FIND(name, type, attr); \ 369 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
393 RB_PROTOTYPE_NFIND(name, type, attr); \ 370 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
394 RB_PROTOTYPE_FIND_LIGHT(name, type, attr); \ 371 RB_SET_COLOR(tmp, EntryColor::Red);
395 RB_PROTOTYPE_NFIND_LIGHT(name, type, attr); \ 372 elm = parent;
396 RB_PROTOTYPE_NEXT(name, type, attr); \ 373 parent = RB_PARENT(elm);
397 RB_PROTOTYPE_PREV(name, type, attr); \ 374 } else {
398 RB_PROTOTYPE_MINMAX(name, type, attr); 375 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) {
399#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 376 Node* oright;
400 attr void name##_RB_INSERT_COLOR(struct name*, struct type*) 377 if ((oright = RB_RIGHT(tmp)) != nullptr) {
401#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 378 RB_SET_COLOR(oright, EntryColor::Black);
402 attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*) 379 }
403#define RB_PROTOTYPE_REMOVE(name, type, attr) \ 380
404 attr struct type* name##_RB_REMOVE(struct name*, struct type*) 381 RB_SET_COLOR(tmp, EntryColor::Red);
405#define RB_PROTOTYPE_INSERT(name, type, attr) \ 382 RB_ROTATE_LEFT(head, tmp, oright);
406 attr struct type* name##_RB_INSERT(struct name*, struct type*) 383 tmp = RB_LEFT(parent);
407#define RB_PROTOTYPE_FIND(name, type, attr) \ 384 }
408 attr struct type* name##_RB_FIND(struct name*, struct type*) 385
409#define RB_PROTOTYPE_NFIND(name, type, attr) \ 386 RB_SET_COLOR(tmp, RB_COLOR(parent));
410 attr struct type* name##_RB_NFIND(struct name*, struct type*) 387 RB_SET_COLOR(parent, EntryColor::Black);
411#define RB_PROTOTYPE_FIND_LIGHT(name, type, attr) \ 388
412 attr struct type* name##_RB_FIND_LIGHT(struct name*, const void*) 389 if (RB_LEFT(tmp)) {
413#define RB_PROTOTYPE_NFIND_LIGHT(name, type, attr) \ 390 RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black);
414 attr struct type* name##_RB_NFIND_LIGHT(struct name*, const void*) 391 }
415#define RB_PROTOTYPE_NEXT(name, type, attr) attr struct type* name##_RB_NEXT(struct type*) 392
416#define RB_PROTOTYPE_PREV(name, type, attr) attr struct type* name##_RB_PREV(struct type*) 393 RB_ROTATE_RIGHT(head, parent, tmp);
417#define RB_PROTOTYPE_MINMAX(name, type, attr) attr struct type* name##_RB_MINMAX(struct name*, int) 394 elm = head->Root();
418 395 break;
419/* Main rb operation. 396 }
420 * Moves node close to the key of elm to top 397 }
421 */ 398 }
422#define RB_GENERATE_WITHOUT_COMPARE(name, type, field) \ 399
423 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, ) 400 if (elm) {
424#define RB_GENERATE_WITHOUT_COMPARE_STATIC(name, type, field) \ 401 RB_SET_COLOR(elm, EntryColor::Black);
425 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, static) 402 }
426#define RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ 403}
427 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 404
428 RB_GENERATE_REMOVE(name, type, field, attr) \ 405template <typename Node>
429 RB_GENERATE_NEXT(name, type, field, attr) \ 406Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
430 RB_GENERATE_PREV(name, type, field, attr) \ 407 Node* child = nullptr;
431 RB_GENERATE_MINMAX(name, type, field, attr) 408 Node* parent = nullptr;
432 409 Node* old = elm;
433#define RB_GENERATE_WITH_COMPARE(name, type, field, cmp, lcmp) \ 410 EntryColor color{};
434 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, ) 411
435#define RB_GENERATE_WITH_COMPARE_STATIC(name, type, field, cmp, lcmp) \ 412 const auto finalize = [&] {
436 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, static) 413 if (color == EntryColor::Black) {
437#define RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, attr) \ 414 RB_REMOVE_COLOR(head, parent, child);
438 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 415 }
439 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 416
440 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 417 return old;
441 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 418 };
442 RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ 419
443 RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) 420 if (RB_LEFT(elm) == nullptr) {
444 421 child = RB_RIGHT(elm);
445#define RB_GENERATE_ALL(name, type, field, cmp) RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, ) 422 } else if (RB_RIGHT(elm) == nullptr) {
446#define RB_GENERATE_ALL_STATIC(name, type, field, cmp) \ 423 child = RB_LEFT(elm);
447 RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, static) 424 } else {
448#define RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, attr) \ 425 Node* left;
449 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ 426 elm = RB_RIGHT(elm);
450 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, attr) 427 while ((left = RB_LEFT(elm)) != nullptr) {
451 428 elm = left;
452#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 429 }
453 attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { \ 430
454 struct type *parent, *gparent, *tmp; \ 431 child = RB_RIGHT(elm);
455 while ((parent = RB_PARENT(elm, field)) != NULL && RB_COLOR(parent, field) == RB_RED) { \ 432 parent = RB_PARENT(elm);
456 gparent = RB_PARENT(parent, field); \ 433 color = RB_COLOR(elm);
457 if (parent == RB_LEFT(gparent, field)) { \ 434
458 tmp = RB_RIGHT(gparent, field); \ 435 if (child) {
459 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 436 RB_SET_PARENT(child, parent);
460 RB_COLOR(tmp, field) = RB_BLACK; \ 437 }
461 RB_SET_BLACKRED(parent, gparent, field); \ 438 if (parent) {
462 elm = gparent; \ 439 if (RB_LEFT(parent) == elm) {
463 continue; \ 440 RB_SET_LEFT(parent, child);
464 } \ 441 } else {
465 if (RB_RIGHT(parent, field) == elm) { \ 442 RB_SET_RIGHT(parent, child);
466 RB_ROTATE_LEFT(head, parent, tmp, field); \ 443 }
467 tmp = parent; \ 444 } else {
468 parent = elm; \ 445 head->SetRoot(child);
469 elm = tmp; \ 446 }
470 } \ 447
471 RB_SET_BLACKRED(parent, gparent, field); \ 448 if (RB_PARENT(elm) == old) {
472 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 449 parent = elm;
473 } else { \ 450 }
474 tmp = RB_LEFT(gparent, field); \ 451
475 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 452 elm->SetEntry(old->GetEntry());
476 RB_COLOR(tmp, field) = RB_BLACK; \ 453
477 RB_SET_BLACKRED(parent, gparent, field); \ 454 if (RB_PARENT(old)) {
478 elm = gparent; \ 455 if (RB_LEFT(RB_PARENT(old)) == old) {
479 continue; \ 456 RB_SET_LEFT(RB_PARENT(old), elm);
480 } \ 457 } else {
481 if (RB_LEFT(parent, field) == elm) { \ 458 RB_SET_RIGHT(RB_PARENT(old), elm);
482 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 459 }
483 tmp = parent; \ 460 } else {
484 parent = elm; \ 461 head->SetRoot(elm);
485 elm = tmp; \ 462 }
486 } \ 463 RB_SET_PARENT(RB_LEFT(old), elm);
487 RB_SET_BLACKRED(parent, gparent, field); \ 464 if (RB_RIGHT(old)) {
488 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 465 RB_SET_PARENT(RB_RIGHT(old), elm);
489 } \ 466 }
490 } \ 467 if (parent) {
491 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 468 left = parent;
492 } 469 }
493 470
494#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 471 return finalize();
495 attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { \ 472 }
496 struct type* tmp; \ 473
497 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { \ 474 parent = RB_PARENT(elm);
498 if (RB_LEFT(parent, field) == elm) { \ 475 color = RB_COLOR(elm);
499 tmp = RB_RIGHT(parent, field); \ 476
500 if (RB_COLOR(tmp, field) == RB_RED) { \ 477 if (child) {
501 RB_SET_BLACKRED(tmp, parent, field); \ 478 RB_SET_PARENT(child, parent);
502 RB_ROTATE_LEFT(head, parent, tmp, field); \ 479 }
503 tmp = RB_RIGHT(parent, field); \ 480 if (parent) {
504 } \ 481 if (RB_LEFT(parent) == elm) {
505 if ((RB_LEFT(tmp, field) == NULL || \ 482 RB_SET_LEFT(parent, child);
506 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 483 } else {
507 (RB_RIGHT(tmp, field) == NULL || \ 484 RB_SET_RIGHT(parent, child);
508 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 485 }
509 RB_COLOR(tmp, field) = RB_RED; \ 486 } else {
510 elm = parent; \ 487 head->SetRoot(child);
511 parent = RB_PARENT(elm, field); \ 488 }
512 } else { \ 489
513 if (RB_RIGHT(tmp, field) == NULL || \ 490 return finalize();
514 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 491}
515 struct type* oleft; \ 492
516 if ((oleft = RB_LEFT(tmp, field)) != NULL) \ 493// Inserts a node into the RB tree
517 RB_COLOR(oleft, field) = RB_BLACK; \ 494template <typename Node, typename CompareFunction>
518 RB_COLOR(tmp, field) = RB_RED; \ 495Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
519 RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 496 Node* parent = nullptr;
520 tmp = RB_RIGHT(parent, field); \ 497 Node* tmp = head->Root();
521 } \ 498 int comp = 0;
522 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 499
523 RB_COLOR(parent, field) = RB_BLACK; \ 500 while (tmp) {
524 if (RB_RIGHT(tmp, field)) \ 501 parent = tmp;
525 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 502 comp = cmp(elm, parent);
526 RB_ROTATE_LEFT(head, parent, tmp, field); \ 503 if (comp < 0) {
527 elm = RB_ROOT(head); \ 504 tmp = RB_LEFT(tmp);
528 break; \ 505 } else if (comp > 0) {
529 } \ 506 tmp = RB_RIGHT(tmp);
530 } else { \ 507 } else {
531 tmp = RB_LEFT(parent, field); \ 508 return tmp;
532 if (RB_COLOR(tmp, field) == RB_RED) { \ 509 }
533 RB_SET_BLACKRED(tmp, parent, field); \ 510 }
534 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 511
535 tmp = RB_LEFT(parent, field); \ 512 RB_SET(elm, parent);
536 } \ 513
537 if ((RB_LEFT(tmp, field) == NULL || \ 514 if (parent != nullptr) {
538 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 515 if (comp < 0) {
539 (RB_RIGHT(tmp, field) == NULL || \ 516 RB_SET_LEFT(parent, elm);
540 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 517 } else {
541 RB_COLOR(tmp, field) = RB_RED; \ 518 RB_SET_RIGHT(parent, elm);
542 elm = parent; \ 519 }
543 parent = RB_PARENT(elm, field); \ 520 } else {
544 } else { \ 521 head->SetRoot(elm);
545 if (RB_LEFT(tmp, field) == NULL || \ 522 }
546 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 523
547 struct type* oright; \ 524 RB_INSERT_COLOR(head, elm);
548 if ((oright = RB_RIGHT(tmp, field)) != NULL) \ 525 return nullptr;
549 RB_COLOR(oright, field) = RB_BLACK; \ 526}
550 RB_COLOR(tmp, field) = RB_RED; \ 527
551 RB_ROTATE_LEFT(head, tmp, oright, field); \ 528// Finds the node with the same key as elm
552 tmp = RB_LEFT(parent, field); \ 529template <typename Node, typename CompareFunction>
553 } \ 530Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
554 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 531 Node* tmp = head->Root();
555 RB_COLOR(parent, field) = RB_BLACK; \ 532
556 if (RB_LEFT(tmp, field)) \ 533 while (tmp) {
557 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 534 const int comp = cmp(elm, tmp);
558 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 535 if (comp < 0) {
559 elm = RB_ROOT(head); \ 536 tmp = RB_LEFT(tmp);
560 break; \ 537 } else if (comp > 0) {
561 } \ 538 tmp = RB_RIGHT(tmp);
562 } \ 539 } else {
563 } \ 540 return tmp;
564 if (elm) \ 541 }
565 RB_COLOR(elm, field) = RB_BLACK; \ 542 }
566 } 543
567 544 return nullptr;
568#define RB_GENERATE_REMOVE(name, type, field, attr) \ 545}
569 attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { \ 546
570 struct type *child, *parent, *old = elm; \ 547// Finds the first node greater than or equal to the search key
571 int color; \ 548template <typename Node, typename CompareFunction>
572 if (RB_LEFT(elm, field) == NULL) \ 549Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
573 child = RB_RIGHT(elm, field); \ 550 Node* tmp = head->Root();
574 else if (RB_RIGHT(elm, field) == NULL) \ 551 Node* res = nullptr;
575 child = RB_LEFT(elm, field); \ 552
576 else { \ 553 while (tmp) {
577 struct type* left; \ 554 const int comp = cmp(elm, tmp);
578 elm = RB_RIGHT(elm, field); \ 555 if (comp < 0) {
579 while ((left = RB_LEFT(elm, field)) != NULL) \ 556 res = tmp;
580 elm = left; \ 557 tmp = RB_LEFT(tmp);
581 child = RB_RIGHT(elm, field); \ 558 } else if (comp > 0) {
582 parent = RB_PARENT(elm, field); \ 559 tmp = RB_RIGHT(tmp);
583 color = RB_COLOR(elm, field); \ 560 } else {
584 if (child) \ 561 return tmp;
585 RB_PARENT(child, field) = parent; \ 562 }
586 if (parent) { \ 563 }
587 if (RB_LEFT(parent, field) == elm) \ 564
588 RB_LEFT(parent, field) = child; \ 565 return res;
589 else \ 566}
590 RB_RIGHT(parent, field) = child; \ 567
591 RB_AUGMENT(parent); \ 568// Finds the node with the same key as lelm
592 } else \ 569template <typename Node, typename CompareFunction>
593 RB_ROOT(head) = child; \ 570Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
594 if (RB_PARENT(elm, field) == old) \ 571 Node* tmp = head->Root();
595 parent = elm; \ 572
596 (elm)->field = (old)->field; \ 573 while (tmp) {
597 if (RB_PARENT(old, field)) { \ 574 const int comp = lcmp(lelm, tmp);
598 if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 575 if (comp < 0) {
599 RB_LEFT(RB_PARENT(old, field), field) = elm; \ 576 tmp = RB_LEFT(tmp);
600 else \ 577 } else if (comp > 0) {
601 RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 578 tmp = RB_RIGHT(tmp);
602 RB_AUGMENT(RB_PARENT(old, field)); \ 579 } else {
603 } else \ 580 return tmp;
604 RB_ROOT(head) = elm; \ 581 }
605 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 582 }
606 if (RB_RIGHT(old, field)) \ 583
607 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 584 return nullptr;
608 if (parent) { \ 585}
609 left = parent; \ 586
610 do { \ 587// Finds the first node greater than or equal to the search key
611 RB_AUGMENT(left); \ 588template <typename Node, typename CompareFunction>
612 } while ((left = RB_PARENT(left, field)) != NULL); \ 589Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
613 } \ 590 Node* tmp = head->Root();
614 goto color; \ 591 Node* res = nullptr;
615 } \ 592
616 parent = RB_PARENT(elm, field); \ 593 while (tmp) {
617 color = RB_COLOR(elm, field); \ 594 const int comp = lcmp(lelm, tmp);
618 if (child) \ 595 if (comp < 0) {
619 RB_PARENT(child, field) = parent; \ 596 res = tmp;
620 if (parent) { \ 597 tmp = RB_LEFT(tmp);
621 if (RB_LEFT(parent, field) == elm) \ 598 } else if (comp > 0) {
622 RB_LEFT(parent, field) = child; \ 599 tmp = RB_RIGHT(tmp);
623 else \ 600 } else {
624 RB_RIGHT(parent, field) = child; \ 601 return tmp;
625 RB_AUGMENT(parent); \ 602 }
626 } else \ 603 }
627 RB_ROOT(head) = child; \ 604
628 color: \ 605 return res;
629 if (color == RB_BLACK) \ 606}
630 name##_RB_REMOVE_COLOR(head, parent, child); \ 607
631 return (old); \ 608template <typename Node>
632 } 609Node* RB_NEXT(Node* elm) {
633 610 if (RB_RIGHT(elm)) {
634#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 611 elm = RB_RIGHT(elm);
635 /* Inserts a node into the RB tree */ \ 612 while (RB_LEFT(elm)) {
636 attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { \ 613 elm = RB_LEFT(elm);
637 struct type* tmp; \ 614 }
638 struct type* parent = NULL; \ 615 } else {
639 int comp = 0; \ 616 if (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
640 tmp = RB_ROOT(head); \ 617 elm = RB_PARENT(elm);
641 while (tmp) { \ 618 } else {
642 parent = tmp; \ 619 while (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
643 comp = (cmp)(elm, parent); \ 620 elm = RB_PARENT(elm);
644 if (comp < 0) \ 621 }
645 tmp = RB_LEFT(tmp, field); \ 622 elm = RB_PARENT(elm);
646 else if (comp > 0) \ 623 }
647 tmp = RB_RIGHT(tmp, field); \ 624 }
648 else \ 625 return elm;
649 return (tmp); \ 626}
650 } \ 627
651 RB_SET(elm, parent, field); \ 628template <typename Node>
652 if (parent != NULL) { \ 629Node* RB_PREV(Node* elm) {
653 if (comp < 0) \ 630 if (RB_LEFT(elm)) {
654 RB_LEFT(parent, field) = elm; \ 631 elm = RB_LEFT(elm);
655 else \ 632 while (RB_RIGHT(elm)) {
656 RB_RIGHT(parent, field) = elm; \ 633 elm = RB_RIGHT(elm);
657 RB_AUGMENT(parent); \ 634 }
658 } else \ 635 } else {
659 RB_ROOT(head) = elm; \ 636 if (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
660 name##_RB_INSERT_COLOR(head, elm); \ 637 elm = RB_PARENT(elm);
661 return (NULL); \ 638 } else {
662 } 639 while (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
663 640 elm = RB_PARENT(elm);
664#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 641 }
665 /* Finds the node with the same key as elm */ \ 642 elm = RB_PARENT(elm);
666 attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { \ 643 }
667 struct type* tmp = RB_ROOT(head); \ 644 }
668 int comp; \ 645 return elm;
669 while (tmp) { \ 646}
670 comp = cmp(elm, tmp); \ 647
671 if (comp < 0) \ 648template <typename Node>
672 tmp = RB_LEFT(tmp, field); \ 649Node* RB_MINMAX(RBHead<Node>* head, bool is_min) {
673 else if (comp > 0) \ 650 Node* tmp = head->Root();
674 tmp = RB_RIGHT(tmp, field); \ 651 Node* parent = nullptr;
675 else \ 652
676 return (tmp); \ 653 while (tmp) {
677 } \ 654 parent = tmp;
678 return (NULL); \ 655 if (is_min) {
679 } 656 tmp = RB_LEFT(tmp);
680 657 } else {
681#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 658 tmp = RB_RIGHT(tmp);
682 /* Finds the first node greater than or equal to the search key */ \ 659 }
683 attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { \ 660 }
684 struct type* tmp = RB_ROOT(head); \ 661
685 struct type* res = NULL; \ 662 return parent;
686 int comp; \ 663}
687 while (tmp) { \ 664
688 comp = cmp(elm, tmp); \ 665template <typename Node>
689 if (comp < 0) { \ 666Node* RB_MIN(RBHead<Node>* head) {
690 res = tmp; \ 667 return RB_MINMAX(head, true);
691 tmp = RB_LEFT(tmp, field); \ 668}
692 } else if (comp > 0) \ 669
693 tmp = RB_RIGHT(tmp, field); \ 670template <typename Node>
694 else \ 671Node* RB_MAX(RBHead<Node>* head) {
695 return (tmp); \ 672 return RB_MINMAX(head, false);
696 } \ 673}
697 return (res); \ 674} // namespace Common
698 }
699
700#define RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \
701 /* Finds the node with the same key as elm */ \
702 attr struct type* name##_RB_FIND_LIGHT(struct name* head, const void* lelm) { \
703 struct type* tmp = RB_ROOT(head); \
704 int comp; \
705 while (tmp) { \
706 comp = lcmp(lelm, tmp); \
707 if (comp < 0) \
708 tmp = RB_LEFT(tmp, field); \
709 else if (comp > 0) \
710 tmp = RB_RIGHT(tmp, field); \
711 else \
712 return (tmp); \
713 } \
714 return (NULL); \
715 }
716
717#define RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) \
718 /* Finds the first node greater than or equal to the search key */ \
719 attr struct type* name##_RB_NFIND_LIGHT(struct name* head, const void* lelm) { \
720 struct type* tmp = RB_ROOT(head); \
721 struct type* res = NULL; \
722 int comp; \
723 while (tmp) { \
724 comp = lcmp(lelm, tmp); \
725 if (comp < 0) { \
726 res = tmp; \
727 tmp = RB_LEFT(tmp, field); \
728 } else if (comp > 0) \
729 tmp = RB_RIGHT(tmp, field); \
730 else \
731 return (tmp); \
732 } \
733 return (res); \
734 }
735
736#define RB_GENERATE_NEXT(name, type, field, attr) \
737 /* ARGSUSED */ \
738 attr struct type* name##_RB_NEXT(struct type* elm) { \
739 if (RB_RIGHT(elm, field)) { \
740 elm = RB_RIGHT(elm, field); \
741 while (RB_LEFT(elm, field)) \
742 elm = RB_LEFT(elm, field); \
743 } else { \
744 if (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
745 elm = RB_PARENT(elm, field); \
746 else { \
747 while (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
748 elm = RB_PARENT(elm, field); \
749 elm = RB_PARENT(elm, field); \
750 } \
751 } \
752 return (elm); \
753 }
754
755#define RB_GENERATE_PREV(name, type, field, attr) \
756 /* ARGSUSED */ \
757 attr struct type* name##_RB_PREV(struct type* elm) { \
758 if (RB_LEFT(elm, field)) { \
759 elm = RB_LEFT(elm, field); \
760 while (RB_RIGHT(elm, field)) \
761 elm = RB_RIGHT(elm, field); \
762 } else { \
763 if (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
764 elm = RB_PARENT(elm, field); \
765 else { \
766 while (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
767 elm = RB_PARENT(elm, field); \
768 elm = RB_PARENT(elm, field); \
769 } \
770 } \
771 return (elm); \
772 }
773
774#define RB_GENERATE_MINMAX(name, type, field, attr) \
775 attr struct type* name##_RB_MINMAX(struct name* head, int val) { \
776 struct type* tmp = RB_ROOT(head); \
777 struct type* parent = NULL; \
778 while (tmp) { \
779 parent = tmp; \
780 if (val < 0) \
781 tmp = RB_LEFT(tmp, field); \
782 else \
783 tmp = RB_RIGHT(tmp, field); \
784 } \
785 return (parent); \
786 }
787
788#define RB_NEGINF -1
789#define RB_INF 1
790
791#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
792#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
793#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
794#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
795#define RB_FIND_LIGHT(name, x, y) name##_RB_FIND_LIGHT(x, y)
796#define RB_NFIND_LIGHT(name, x, y) name##_RB_NFIND_LIGHT(x, y)
797#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
798#define RB_PREV(name, x, y) name##_RB_PREV(y)
799#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
800#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
801
802#define RB_FOREACH(x, name, head) \
803 for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x))
804
805#define RB_FOREACH_FROM(x, name, y) \
806 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y))
807
808#define RB_FOREACH_SAFE(x, name, head, y) \
809 for ((x) = RB_MIN(name, head); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
810 (x) = (y))
811
812#define RB_FOREACH_REVERSE(x, name, head) \
813 for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x))
814
815#define RB_FOREACH_REVERSE_FROM(x, name, y) \
816 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y))
817
818#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
819 for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
820 (x) = (y))
821
822#endif /* _SYS_TREE_H_ */
HIC SVNT DRACONES