summaryrefslogtreecommitdiff
path: root/src/common/tree.h
diff options
context:
space:
mode:
authorGravatar Lioncash2021-01-12 02:47:36 -0500
committerGravatar Lioncash2021-01-12 16:46:36 -0500
commitb15e1a35011629c3b31edd10c1d10b8d7fafcb2c (patch)
tree6bb48e8e2f65ed47436c4279f0732e45c2041007 /src/common/tree.h
parentcommon/tree: Remove unused splay tree defines (diff)
downloadyuzu-b15e1a35011629c3b31edd10c1d10b8d7fafcb2c.tar.gz
yuzu-b15e1a35011629c3b31edd10c1d10b8d7fafcb2c.tar.xz
yuzu-b15e1a35011629c3b31edd10c1d10b8d7fafcb2c.zip
common/tree: Convert defines over to templates
Reworks the tree header to operate off of templates as opposed to a series of defines. This allows all tree facilities to obey namespacing rules, and also allows this code to be used within modules once compiler support is in place. This also gets rid to use a macro to define functions and structs for necessary data types. With templates, these will be generated when they're actually used, eliminating the need for the separate declaration.
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