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.h625
1 files changed, 341 insertions, 284 deletions
diff --git a/src/common/tree.h b/src/common/tree.h
index 18faa4a48..28370e343 100644
--- a/src/common/tree.h
+++ b/src/common/tree.h
@@ -43,294 +43,265 @@
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#include "common/assert.h" 46namespace Common::freebsd {
47 47
48namespace Common { 48enum class RBColor {
49 RB_BLACK = 0,
50 RB_RED = 1,
51};
52
53#pragma pack(push, 4)
49template <typename T> 54template <typename T>
50class RBHead { 55class RBEntry {
51public: 56public:
52 [[nodiscard]] T* Root() { 57 constexpr RBEntry() = default;
53 return rbh_root;
54 }
55 58
56 [[nodiscard]] const T* Root() const { 59 [[nodiscard]] constexpr T* Left() {
57 return rbh_root; 60 return m_rbe_left;
58 } 61 }
59 62 [[nodiscard]] constexpr const T* Left() const {
60 void SetRoot(T* root) { 63 return m_rbe_left;
61 rbh_root = root;
62 } 64 }
63 65
64 [[nodiscard]] bool IsEmpty() const { 66 constexpr void SetLeft(T* e) {
65 return Root() == nullptr; 67 m_rbe_left = e;
66 } 68 }
67 69
68private: 70 [[nodiscard]] constexpr T* Right() {
69 T* rbh_root = nullptr; 71 return m_rbe_right;
70};
71
72enum class EntryColor {
73 Black,
74 Red,
75};
76
77template <typename T>
78class RBEntry {
79public:
80 [[nodiscard]] T* Left() {
81 return rbe_left;
82 } 72 }
83 73 [[nodiscard]] constexpr const T* Right() const {
84 [[nodiscard]] const T* Left() const { 74 return m_rbe_right;
85 return rbe_left;
86 } 75 }
87 76
88 void SetLeft(T* left) { 77 constexpr void SetRight(T* e) {
89 rbe_left = left; 78 m_rbe_right = e;
90 } 79 }
91 80
92 [[nodiscard]] T* Right() { 81 [[nodiscard]] constexpr T* Parent() {
93 return rbe_right; 82 return m_rbe_parent;
94 } 83 }
95 84 [[nodiscard]] constexpr const T* Parent() const {
96 [[nodiscard]] const T* Right() const { 85 return m_rbe_parent;
97 return rbe_right;
98 } 86 }
99 87
100 void SetRight(T* right) { 88 constexpr void SetParent(T* e) {
101 rbe_right = right; 89 m_rbe_parent = e;
102 } 90 }
103 91
104 [[nodiscard]] T* Parent() { 92 [[nodiscard]] constexpr bool IsBlack() const {
105 return rbe_parent; 93 return m_rbe_color == RBColor::RB_BLACK;
106 } 94 }
107 95 [[nodiscard]] constexpr bool IsRed() const {
108 [[nodiscard]] const T* Parent() const { 96 return m_rbe_color == RBColor::RB_RED;
109 return rbe_parent;
110 } 97 }
111 98 [[nodiscard]] constexpr RBColor Color() const {
112 void SetParent(T* parent) { 99 return m_rbe_color;
113 rbe_parent = parent;
114 } 100 }
115 101
116 [[nodiscard]] bool IsBlack() const { 102 constexpr void SetColor(RBColor c) {
117 return rbe_color == EntryColor::Black; 103 m_rbe_color = c;
118 } 104 }
119 105
120 [[nodiscard]] bool IsRed() const { 106private:
121 return rbe_color == EntryColor::Red; 107 T* m_rbe_left{};
122 } 108 T* m_rbe_right{};
109 T* m_rbe_parent{};
110 RBColor m_rbe_color{RBColor::RB_BLACK};
111};
112#pragma pack(pop)
123 113
124 [[nodiscard]] EntryColor Color() const { 114template <typename T>
125 return rbe_color; 115struct CheckRBEntry {
126 } 116 static constexpr bool value = false;
117};
118template <typename T>
119struct CheckRBEntry<RBEntry<T>> {
120 static constexpr bool value = true;
121};
127 122
128 void SetColor(EntryColor color) { 123template <typename T>
129 rbe_color = color; 124concept IsRBEntry = CheckRBEntry<T>::value;
130 }
131 125
126template <typename T>
127concept HasRBEntry = requires(T& t, const T& ct) {
128 { t.GetRBEntry() } -> std::same_as<RBEntry<T>&>;
129 { ct.GetRBEntry() } -> std::same_as<const RBEntry<T>&>;
130};
131
132template <typename T>
133requires HasRBEntry<T>
134class RBHead {
132private: 135private:
133 T* rbe_left = nullptr; 136 T* m_rbh_root = nullptr;
134 T* rbe_right = nullptr; 137
135 T* rbe_parent = nullptr; 138public:
136 EntryColor rbe_color{}; 139 [[nodiscard]] constexpr T* Root() {
140 return m_rbh_root;
141 }
142 [[nodiscard]] constexpr const T* Root() const {
143 return m_rbh_root;
144 }
145 constexpr void SetRoot(T* root) {
146 m_rbh_root = root;
147 }
148
149 [[nodiscard]] constexpr bool IsEmpty() const {
150 return this->Root() == nullptr;
151 }
137}; 152};
138 153
139template <typename Node> 154template <typename T>
140[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) { 155requires HasRBEntry<T>
141 return node->GetEntry(); 156[[nodiscard]] constexpr RBEntry<T>& RB_ENTRY(T* t) {
157 return t->GetRBEntry();
142} 158}
143 159template <typename T>
144template <typename Node> 160requires HasRBEntry<T>
145[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) { 161[[nodiscard]] constexpr const RBEntry<T>& RB_ENTRY(const T* t) {
146 return node->GetEntry(); 162 return t->GetRBEntry();
147} 163}
148 164
149template <typename Node> 165template <typename T>
150[[nodiscard]] Node* RB_PARENT(Node* node) { 166requires HasRBEntry<T>
151 return RB_ENTRY(node).Parent(); 167[[nodiscard]] constexpr T* RB_LEFT(T* t) {
168 return RB_ENTRY(t).Left();
152} 169}
153 170template <typename T>
154template <typename Node> 171requires HasRBEntry<T>
155[[nodiscard]] const Node* RB_PARENT(const Node* node) { 172[[nodiscard]] constexpr const T* RB_LEFT(const T* t) {
156 return RB_ENTRY(node).Parent(); 173 return RB_ENTRY(t).Left();
157} 174}
158 175
159template <typename Node> 176template <typename T>
160void RB_SET_PARENT(Node* node, Node* parent) { 177requires HasRBEntry<T>
161 return RB_ENTRY(node).SetParent(parent); 178[[nodiscard]] constexpr T* RB_RIGHT(T* t) {
179 return RB_ENTRY(t).Right();
162} 180}
163 181template <typename T>
164template <typename Node> 182requires HasRBEntry<T>
165[[nodiscard]] Node* RB_LEFT(Node* node) { 183[[nodiscard]] constexpr const T* RB_RIGHT(const T* t) {
166 return RB_ENTRY(node).Left(); 184 return RB_ENTRY(t).Right();
167} 185}
168 186
169template <typename Node> 187template <typename T>
170[[nodiscard]] const Node* RB_LEFT(const Node* node) { 188requires HasRBEntry<T>
171 return RB_ENTRY(node).Left(); 189[[nodiscard]] constexpr T* RB_PARENT(T* t) {
190 return RB_ENTRY(t).Parent();
172} 191}
173 192template <typename T>
174template <typename Node> 193requires HasRBEntry<T>
175void RB_SET_LEFT(Node* node, Node* left) { 194[[nodiscard]] constexpr const T* RB_PARENT(const T* t) {
176 return RB_ENTRY(node).SetLeft(left); 195 return RB_ENTRY(t).Parent();
177} 196}
178 197
179template <typename Node> 198template <typename T>
180[[nodiscard]] Node* RB_RIGHT(Node* node) { 199requires HasRBEntry<T>
181 return RB_ENTRY(node).Right(); 200constexpr void RB_SET_LEFT(T* t, T* e) {
201 RB_ENTRY(t).SetLeft(e);
182} 202}
183 203template <typename T>
184template <typename Node> 204requires HasRBEntry<T>
185[[nodiscard]] const Node* RB_RIGHT(const Node* node) { 205constexpr void RB_SET_RIGHT(T* t, T* e) {
186 return RB_ENTRY(node).Right(); 206 RB_ENTRY(t).SetRight(e);
187} 207}
188 208template <typename T>
189template <typename Node> 209requires HasRBEntry<T>
190void RB_SET_RIGHT(Node* node, Node* right) { 210constexpr void RB_SET_PARENT(T* t, T* e) {
191 return RB_ENTRY(node).SetRight(right); 211 RB_ENTRY(t).SetParent(e);
192} 212}
193 213
194template <typename Node> 214template <typename T>
195[[nodiscard]] bool RB_IS_BLACK(const Node* node) { 215requires HasRBEntry<T>
196 return RB_ENTRY(node).IsBlack(); 216[[nodiscard]] constexpr bool RB_IS_BLACK(const T* t) {
217 return RB_ENTRY(t).IsBlack();
197} 218}
198 219template <typename T>
199template <typename Node> 220requires HasRBEntry<T>
200[[nodiscard]] bool RB_IS_RED(const Node* node) { 221[[nodiscard]] constexpr bool RB_IS_RED(const T* t) {
201 return RB_ENTRY(node).IsRed(); 222 return RB_ENTRY(t).IsRed();
202} 223}
203 224
204template <typename Node> 225template <typename T>
205[[nodiscard]] EntryColor RB_COLOR(const Node* node) { 226requires HasRBEntry<T>
206 return RB_ENTRY(node).Color(); 227[[nodiscard]] constexpr RBColor RB_COLOR(const T* t) {
228 return RB_ENTRY(t).Color();
207} 229}
208 230
209template <typename Node> 231template <typename T>
210void RB_SET_COLOR(Node* node, EntryColor color) { 232requires HasRBEntry<T>
211 return RB_ENTRY(node).SetColor(color); 233constexpr void RB_SET_COLOR(T* t, RBColor c) {
234 RB_ENTRY(t).SetColor(c);
212} 235}
213 236
214template <typename Node> 237template <typename T>
215void RB_SET(Node* node, Node* parent) { 238requires HasRBEntry<T>
216 auto& entry = RB_ENTRY(node); 239constexpr void RB_SET(T* elm, T* parent) {
217 entry.SetParent(parent); 240 auto& rb_entry = RB_ENTRY(elm);
218 entry.SetLeft(nullptr); 241 rb_entry.SetParent(parent);
219 entry.SetRight(nullptr); 242 rb_entry.SetLeft(nullptr);
220 entry.SetColor(EntryColor::Red); 243 rb_entry.SetRight(nullptr);
244 rb_entry.SetColor(RBColor::RB_RED);
221} 245}
222 246
223template <typename Node> 247template <typename T>
224void RB_SET_BLACKRED(Node* black, Node* red) { 248requires HasRBEntry<T>
225 RB_SET_COLOR(black, EntryColor::Black); 249constexpr void RB_SET_BLACKRED(T* black, T* red) {
226 RB_SET_COLOR(red, EntryColor::Red); 250 RB_SET_COLOR(black, RBColor::RB_BLACK);
251 RB_SET_COLOR(red, RBColor::RB_RED);
227} 252}
228 253
229template <typename Node> 254template <typename T>
230void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) { 255requires HasRBEntry<T>
256constexpr void RB_ROTATE_LEFT(RBHead<T>& head, T* elm, T*& tmp) {
231 tmp = RB_RIGHT(elm); 257 tmp = RB_RIGHT(elm);
232 RB_SET_RIGHT(elm, RB_LEFT(tmp)); 258 if (RB_SET_RIGHT(elm, RB_LEFT(tmp)); RB_RIGHT(elm) != nullptr) {
233 if (RB_RIGHT(elm) != nullptr) {
234 RB_SET_PARENT(RB_LEFT(tmp), elm); 259 RB_SET_PARENT(RB_LEFT(tmp), elm);
235 } 260 }
236 261
237 RB_SET_PARENT(tmp, RB_PARENT(elm)); 262 if (RB_SET_PARENT(tmp, RB_PARENT(elm)); RB_PARENT(tmp) != nullptr) {
238 if (RB_PARENT(tmp) != nullptr) {
239 if (elm == RB_LEFT(RB_PARENT(elm))) { 263 if (elm == RB_LEFT(RB_PARENT(elm))) {
240 RB_SET_LEFT(RB_PARENT(elm), tmp); 264 RB_SET_LEFT(RB_PARENT(elm), tmp);
241 } else { 265 } else {
242 RB_SET_RIGHT(RB_PARENT(elm), tmp); 266 RB_SET_RIGHT(RB_PARENT(elm), tmp);
243 } 267 }
244 } else { 268 } else {
245 head->SetRoot(tmp); 269 head.SetRoot(tmp);
246 } 270 }
247 271
248 RB_SET_LEFT(tmp, elm); 272 RB_SET_LEFT(tmp, elm);
249 RB_SET_PARENT(elm, tmp); 273 RB_SET_PARENT(elm, tmp);
250} 274}
251 275
252template <typename Node> 276template <typename T>
253void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) { 277requires HasRBEntry<T>
278constexpr void RB_ROTATE_RIGHT(RBHead<T>& head, T* elm, T*& tmp) {
254 tmp = RB_LEFT(elm); 279 tmp = RB_LEFT(elm);
255 RB_SET_LEFT(elm, RB_RIGHT(tmp)); 280 if (RB_SET_LEFT(elm, RB_RIGHT(tmp)); RB_LEFT(elm) != nullptr) {
256 if (RB_LEFT(elm) != nullptr) {
257 RB_SET_PARENT(RB_RIGHT(tmp), elm); 281 RB_SET_PARENT(RB_RIGHT(tmp), elm);
258 } 282 }
259 283
260 RB_SET_PARENT(tmp, RB_PARENT(elm)); 284 if (RB_SET_PARENT(tmp, RB_PARENT(elm)); RB_PARENT(tmp) != nullptr) {
261 if (RB_PARENT(tmp) != nullptr) {
262 if (elm == RB_LEFT(RB_PARENT(elm))) { 285 if (elm == RB_LEFT(RB_PARENT(elm))) {
263 RB_SET_LEFT(RB_PARENT(elm), tmp); 286 RB_SET_LEFT(RB_PARENT(elm), tmp);
264 } else { 287 } else {
265 RB_SET_RIGHT(RB_PARENT(elm), tmp); 288 RB_SET_RIGHT(RB_PARENT(elm), tmp);
266 } 289 }
267 } else { 290 } else {
268 head->SetRoot(tmp); 291 head.SetRoot(tmp);
269 } 292 }
270 293
271 RB_SET_RIGHT(tmp, elm); 294 RB_SET_RIGHT(tmp, elm);
272 RB_SET_PARENT(elm, tmp); 295 RB_SET_PARENT(elm, tmp);
273} 296}
274 297
275template <typename Node> 298template <typename T>
276void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) { 299requires HasRBEntry<T>
277 Node* parent = nullptr; 300constexpr void RB_REMOVE_COLOR(RBHead<T>& head, T* parent, T* elm) {
278 Node* tmp = nullptr; 301 T* tmp;
279 302 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head.Root()) {
280 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
281 Node* gparent = RB_PARENT(parent);
282 if (parent == RB_LEFT(gparent)) {
283 tmp = RB_RIGHT(gparent);
284 if (tmp && RB_IS_RED(tmp)) {
285 RB_SET_COLOR(tmp, EntryColor::Black);
286 RB_SET_BLACKRED(parent, gparent);
287 elm = gparent;
288 continue;
289 }
290
291 if (RB_RIGHT(parent) == elm) {
292 RB_ROTATE_LEFT(head, parent, tmp);
293 tmp = parent;
294 parent = elm;
295 elm = tmp;
296 }
297
298 RB_SET_BLACKRED(parent, gparent);
299 RB_ROTATE_RIGHT(head, gparent, tmp);
300 } else {
301 tmp = RB_LEFT(gparent);
302 if (tmp && RB_IS_RED(tmp)) {
303 RB_SET_COLOR(tmp, EntryColor::Black);
304 RB_SET_BLACKRED(parent, gparent);
305 elm = gparent;
306 continue;
307 }
308
309 if (RB_LEFT(parent) == elm) {
310 RB_ROTATE_RIGHT(head, parent, tmp);
311 tmp = parent;
312 parent = elm;
313 elm = tmp;
314 }
315
316 RB_SET_BLACKRED(parent, gparent);
317 RB_ROTATE_LEFT(head, gparent, tmp);
318 }
319 }
320
321 RB_SET_COLOR(head->Root(), EntryColor::Black);
322}
323
324template <typename Node>
325void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
326 Node* tmp;
327 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root() && parent != nullptr) {
328 if (RB_LEFT(parent) == elm) { 303 if (RB_LEFT(parent) == elm) {
329 tmp = RB_RIGHT(parent); 304 tmp = RB_RIGHT(parent);
330 if (!tmp) {
331 ASSERT_MSG(false, "tmp is invalid!");
332 break;
333 }
334 if (RB_IS_RED(tmp)) { 305 if (RB_IS_RED(tmp)) {
335 RB_SET_BLACKRED(tmp, parent); 306 RB_SET_BLACKRED(tmp, parent);
336 RB_ROTATE_LEFT(head, parent, tmp); 307 RB_ROTATE_LEFT(head, parent, tmp);
@@ -339,29 +310,29 @@ void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
339 310
340 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && 311 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
341 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { 312 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
342 RB_SET_COLOR(tmp, EntryColor::Red); 313 RB_SET_COLOR(tmp, RBColor::RB_RED);
343 elm = parent; 314 elm = parent;
344 parent = RB_PARENT(elm); 315 parent = RB_PARENT(elm);
345 } else { 316 } else {
346 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) { 317 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) {
347 Node* oleft; 318 T* oleft;
348 if ((oleft = RB_LEFT(tmp)) != nullptr) { 319 if ((oleft = RB_LEFT(tmp)) != nullptr) {
349 RB_SET_COLOR(oleft, EntryColor::Black); 320 RB_SET_COLOR(oleft, RBColor::RB_BLACK);
350 } 321 }
351 322
352 RB_SET_COLOR(tmp, EntryColor::Red); 323 RB_SET_COLOR(tmp, RBColor::RB_RED);
353 RB_ROTATE_RIGHT(head, tmp, oleft); 324 RB_ROTATE_RIGHT(head, tmp, oleft);
354 tmp = RB_RIGHT(parent); 325 tmp = RB_RIGHT(parent);
355 } 326 }
356 327
357 RB_SET_COLOR(tmp, RB_COLOR(parent)); 328 RB_SET_COLOR(tmp, RB_COLOR(parent));
358 RB_SET_COLOR(parent, EntryColor::Black); 329 RB_SET_COLOR(parent, RBColor::RB_BLACK);
359 if (RB_RIGHT(tmp)) { 330 if (RB_RIGHT(tmp)) {
360 RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black); 331 RB_SET_COLOR(RB_RIGHT(tmp), RBColor::RB_BLACK);
361 } 332 }
362 333
363 RB_ROTATE_LEFT(head, parent, tmp); 334 RB_ROTATE_LEFT(head, parent, tmp);
364 elm = head->Root(); 335 elm = head.Root();
365 break; 336 break;
366 } 337 }
367 } else { 338 } else {
@@ -372,68 +343,56 @@ void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
372 tmp = RB_LEFT(parent); 343 tmp = RB_LEFT(parent);
373 } 344 }
374 345
375 if (!tmp) {
376 ASSERT_MSG(false, "tmp is invalid!");
377 break;
378 }
379
380 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && 346 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
381 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { 347 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
382 RB_SET_COLOR(tmp, EntryColor::Red); 348 RB_SET_COLOR(tmp, RBColor::RB_RED);
383 elm = parent; 349 elm = parent;
384 parent = RB_PARENT(elm); 350 parent = RB_PARENT(elm);
385 } else { 351 } else {
386 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) { 352 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) {
387 Node* oright; 353 T* oright;
388 if ((oright = RB_RIGHT(tmp)) != nullptr) { 354 if ((oright = RB_RIGHT(tmp)) != nullptr) {
389 RB_SET_COLOR(oright, EntryColor::Black); 355 RB_SET_COLOR(oright, RBColor::RB_BLACK);
390 } 356 }
391 357
392 RB_SET_COLOR(tmp, EntryColor::Red); 358 RB_SET_COLOR(tmp, RBColor::RB_RED);
393 RB_ROTATE_LEFT(head, tmp, oright); 359 RB_ROTATE_LEFT(head, tmp, oright);
394 tmp = RB_LEFT(parent); 360 tmp = RB_LEFT(parent);
395 } 361 }
396 362
397 RB_SET_COLOR(tmp, RB_COLOR(parent)); 363 RB_SET_COLOR(tmp, RB_COLOR(parent));
398 RB_SET_COLOR(parent, EntryColor::Black); 364 RB_SET_COLOR(parent, RBColor::RB_BLACK);
399 365
400 if (RB_LEFT(tmp)) { 366 if (RB_LEFT(tmp)) {
401 RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black); 367 RB_SET_COLOR(RB_LEFT(tmp), RBColor::RB_BLACK);
402 } 368 }
403 369
404 RB_ROTATE_RIGHT(head, parent, tmp); 370 RB_ROTATE_RIGHT(head, parent, tmp);
405 elm = head->Root(); 371 elm = head.Root();
406 break; 372 break;
407 } 373 }
408 } 374 }
409 } 375 }
410 376
411 if (elm) { 377 if (elm) {
412 RB_SET_COLOR(elm, EntryColor::Black); 378 RB_SET_COLOR(elm, RBColor::RB_BLACK);
413 } 379 }
414} 380}
415 381
416template <typename Node> 382template <typename T>
417Node* RB_REMOVE(RBHead<Node>* head, Node* elm) { 383requires HasRBEntry<T>
418 Node* child = nullptr; 384constexpr T* RB_REMOVE(RBHead<T>& head, T* elm) {
419 Node* parent = nullptr; 385 T* child = nullptr;
420 Node* old = elm; 386 T* parent = nullptr;
421 EntryColor color{}; 387 T* old = elm;
422 388 RBColor color = RBColor::RB_BLACK;
423 const auto finalize = [&] {
424 if (color == EntryColor::Black) {
425 RB_REMOVE_COLOR(head, parent, child);
426 }
427
428 return old;
429 };
430 389
431 if (RB_LEFT(elm) == nullptr) { 390 if (RB_LEFT(elm) == nullptr) {
432 child = RB_RIGHT(elm); 391 child = RB_RIGHT(elm);
433 } else if (RB_RIGHT(elm) == nullptr) { 392 } else if (RB_RIGHT(elm) == nullptr) {
434 child = RB_LEFT(elm); 393 child = RB_LEFT(elm);
435 } else { 394 } else {
436 Node* left; 395 T* left;
437 elm = RB_RIGHT(elm); 396 elm = RB_RIGHT(elm);
438 while ((left = RB_LEFT(elm)) != nullptr) { 397 while ((left = RB_LEFT(elm)) != nullptr) {
439 elm = left; 398 elm = left;
@@ -446,6 +405,7 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
446 if (child) { 405 if (child) {
447 RB_SET_PARENT(child, parent); 406 RB_SET_PARENT(child, parent);
448 } 407 }
408
449 if (parent) { 409 if (parent) {
450 if (RB_LEFT(parent) == elm) { 410 if (RB_LEFT(parent) == elm) {
451 RB_SET_LEFT(parent, child); 411 RB_SET_LEFT(parent, child);
@@ -453,14 +413,14 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
453 RB_SET_RIGHT(parent, child); 413 RB_SET_RIGHT(parent, child);
454 } 414 }
455 } else { 415 } else {
456 head->SetRoot(child); 416 head.SetRoot(child);
457 } 417 }
458 418
459 if (RB_PARENT(elm) == old) { 419 if (RB_PARENT(elm) == old) {
460 parent = elm; 420 parent = elm;
461 } 421 }
462 422
463 elm->SetEntry(old->GetEntry()); 423 elm->SetRBEntry(old->GetRBEntry());
464 424
465 if (RB_PARENT(old)) { 425 if (RB_PARENT(old)) {
466 if (RB_LEFT(RB_PARENT(old)) == old) { 426 if (RB_LEFT(RB_PARENT(old)) == old) {
@@ -469,17 +429,24 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
469 RB_SET_RIGHT(RB_PARENT(old), elm); 429 RB_SET_RIGHT(RB_PARENT(old), elm);
470 } 430 }
471 } else { 431 } else {
472 head->SetRoot(elm); 432 head.SetRoot(elm);
473 } 433 }
434
474 RB_SET_PARENT(RB_LEFT(old), elm); 435 RB_SET_PARENT(RB_LEFT(old), elm);
436
475 if (RB_RIGHT(old)) { 437 if (RB_RIGHT(old)) {
476 RB_SET_PARENT(RB_RIGHT(old), elm); 438 RB_SET_PARENT(RB_RIGHT(old), elm);
477 } 439 }
440
478 if (parent) { 441 if (parent) {
479 left = parent; 442 left = parent;
480 } 443 }
481 444
482 return finalize(); 445 if (color == RBColor::RB_BLACK) {
446 RB_REMOVE_COLOR(head, parent, child);
447 }
448
449 return old;
483 } 450 }
484 451
485 parent = RB_PARENT(elm); 452 parent = RB_PARENT(elm);
@@ -495,17 +462,69 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
495 RB_SET_RIGHT(parent, child); 462 RB_SET_RIGHT(parent, child);
496 } 463 }
497 } else { 464 } else {
498 head->SetRoot(child); 465 head.SetRoot(child);
466 }
467
468 if (color == RBColor::RB_BLACK) {
469 RB_REMOVE_COLOR(head, parent, child);
470 }
471
472 return old;
473}
474
475template <typename T>
476requires HasRBEntry<T>
477constexpr void RB_INSERT_COLOR(RBHead<T>& head, T* elm) {
478 T *parent = nullptr, *tmp = nullptr;
479 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
480 T* gparent = RB_PARENT(parent);
481 if (parent == RB_LEFT(gparent)) {
482 tmp = RB_RIGHT(gparent);
483 if (tmp && RB_IS_RED(tmp)) {
484 RB_SET_COLOR(tmp, RBColor::RB_BLACK);
485 RB_SET_BLACKRED(parent, gparent);
486 elm = gparent;
487 continue;
488 }
489
490 if (RB_RIGHT(parent) == elm) {
491 RB_ROTATE_LEFT(head, parent, tmp);
492 tmp = parent;
493 parent = elm;
494 elm = tmp;
495 }
496
497 RB_SET_BLACKRED(parent, gparent);
498 RB_ROTATE_RIGHT(head, gparent, tmp);
499 } else {
500 tmp = RB_LEFT(gparent);
501 if (tmp && RB_IS_RED(tmp)) {
502 RB_SET_COLOR(tmp, RBColor::RB_BLACK);
503 RB_SET_BLACKRED(parent, gparent);
504 elm = gparent;
505 continue;
506 }
507
508 if (RB_LEFT(parent) == elm) {
509 RB_ROTATE_RIGHT(head, parent, tmp);
510 tmp = parent;
511 parent = elm;
512 elm = tmp;
513 }
514
515 RB_SET_BLACKRED(parent, gparent);
516 RB_ROTATE_LEFT(head, gparent, tmp);
517 }
499 } 518 }
500 519
501 return finalize(); 520 RB_SET_COLOR(head.Root(), RBColor::RB_BLACK);
502} 521}
503 522
504// Inserts a node into the RB tree 523template <typename T, typename Compare>
505template <typename Node, typename CompareFunction> 524requires HasRBEntry<T>
506Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) { 525constexpr T* RB_INSERT(RBHead<T>& head, T* elm, Compare cmp) {
507 Node* parent = nullptr; 526 T* parent = nullptr;
508 Node* tmp = head->Root(); 527 T* tmp = head.Root();
509 int comp = 0; 528 int comp = 0;
510 529
511 while (tmp) { 530 while (tmp) {
@@ -529,17 +548,17 @@ Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
529 RB_SET_RIGHT(parent, elm); 548 RB_SET_RIGHT(parent, elm);
530 } 549 }
531 } else { 550 } else {
532 head->SetRoot(elm); 551 head.SetRoot(elm);
533 } 552 }
534 553
535 RB_INSERT_COLOR(head, elm); 554 RB_INSERT_COLOR(head, elm);
536 return nullptr; 555 return nullptr;
537} 556}
538 557
539// Finds the node with the same key as elm 558template <typename T, typename Compare>
540template <typename Node, typename CompareFunction> 559requires HasRBEntry<T>
541Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) { 560constexpr T* RB_FIND(RBHead<T>& head, T* elm, Compare cmp) {
542 Node* tmp = head->Root(); 561 T* tmp = head.Root();
543 562
544 while (tmp) { 563 while (tmp) {
545 const int comp = cmp(elm, tmp); 564 const int comp = cmp(elm, tmp);
@@ -555,11 +574,11 @@ Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
555 return nullptr; 574 return nullptr;
556} 575}
557 576
558// Finds the first node greater than or equal to the search key 577template <typename T, typename Compare>
559template <typename Node, typename CompareFunction> 578requires HasRBEntry<T>
560Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) { 579constexpr T* RB_NFIND(RBHead<T>& head, T* elm, Compare cmp) {
561 Node* tmp = head->Root(); 580 T* tmp = head.Root();
562 Node* res = nullptr; 581 T* res = nullptr;
563 582
564 while (tmp) { 583 while (tmp) {
565 const int comp = cmp(elm, tmp); 584 const int comp = cmp(elm, tmp);
@@ -576,13 +595,13 @@ Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
576 return res; 595 return res;
577} 596}
578 597
579// Finds the node with the same key as lelm 598template <typename T, typename U, typename Compare>
580template <typename Node, typename CompareFunction> 599requires HasRBEntry<T>
581Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) { 600constexpr T* RB_FIND_KEY(RBHead<T>& head, const U& key, Compare cmp) {
582 Node* tmp = head->Root(); 601 T* tmp = head.Root();
583 602
584 while (tmp) { 603 while (tmp) {
585 const int comp = lcmp(lelm, tmp); 604 const int comp = cmp(key, tmp);
586 if (comp < 0) { 605 if (comp < 0) {
587 tmp = RB_LEFT(tmp); 606 tmp = RB_LEFT(tmp);
588 } else if (comp > 0) { 607 } else if (comp > 0) {
@@ -595,14 +614,14 @@ Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp)
595 return nullptr; 614 return nullptr;
596} 615}
597 616
598// Finds the first node greater than or equal to the search key 617template <typename T, typename U, typename Compare>
599template <typename Node, typename CompareFunction> 618requires HasRBEntry<T>
600Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) { 619constexpr T* RB_NFIND_KEY(RBHead<T>& head, const U& key, Compare cmp) {
601 Node* tmp = head->Root(); 620 T* tmp = head.Root();
602 Node* res = nullptr; 621 T* res = nullptr;
603 622
604 while (tmp) { 623 while (tmp) {
605 const int comp = lcmp(lelm, tmp); 624 const int comp = cmp(key, tmp);
606 if (comp < 0) { 625 if (comp < 0) {
607 res = tmp; 626 res = tmp;
608 tmp = RB_LEFT(tmp); 627 tmp = RB_LEFT(tmp);
@@ -616,8 +635,43 @@ Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp)
616 return res; 635 return res;
617} 636}
618 637
619template <typename Node> 638template <typename T, typename Compare>
620Node* RB_NEXT(Node* elm) { 639requires HasRBEntry<T>
640constexpr T* RB_FIND_EXISTING(RBHead<T>& head, T* elm, Compare cmp) {
641 T* tmp = head.Root();
642
643 while (true) {
644 const int comp = cmp(elm, tmp);
645 if (comp < 0) {
646 tmp = RB_LEFT(tmp);
647 } else if (comp > 0) {
648 tmp = RB_RIGHT(tmp);
649 } else {
650 return tmp;
651 }
652 }
653}
654
655template <typename T, typename U, typename Compare>
656requires HasRBEntry<T>
657constexpr T* RB_FIND_EXISTING_KEY(RBHead<T>& head, const U& key, Compare cmp) {
658 T* tmp = head.Root();
659
660 while (true) {
661 const int comp = cmp(key, tmp);
662 if (comp < 0) {
663 tmp = RB_LEFT(tmp);
664 } else if (comp > 0) {
665 tmp = RB_RIGHT(tmp);
666 } else {
667 return tmp;
668 }
669 }
670}
671
672template <typename T>
673requires HasRBEntry<T>
674constexpr T* RB_NEXT(T* elm) {
621 if (RB_RIGHT(elm)) { 675 if (RB_RIGHT(elm)) {
622 elm = RB_RIGHT(elm); 676 elm = RB_RIGHT(elm);
623 while (RB_LEFT(elm)) { 677 while (RB_LEFT(elm)) {
@@ -636,8 +690,9 @@ Node* RB_NEXT(Node* elm) {
636 return elm; 690 return elm;
637} 691}
638 692
639template <typename Node> 693template <typename T>
640Node* RB_PREV(Node* elm) { 694requires HasRBEntry<T>
695constexpr T* RB_PREV(T* elm) {
641 if (RB_LEFT(elm)) { 696 if (RB_LEFT(elm)) {
642 elm = RB_LEFT(elm); 697 elm = RB_LEFT(elm);
643 while (RB_RIGHT(elm)) { 698 while (RB_RIGHT(elm)) {
@@ -656,30 +711,32 @@ Node* RB_PREV(Node* elm) {
656 return elm; 711 return elm;
657} 712}
658 713
659template <typename Node> 714template <typename T>
660Node* RB_MINMAX(RBHead<Node>* head, bool is_min) { 715requires HasRBEntry<T>
661 Node* tmp = head->Root(); 716constexpr T* RB_MIN(RBHead<T>& head) {
662 Node* parent = nullptr; 717 T* tmp = head.Root();
718 T* parent = nullptr;
663 719
664 while (tmp) { 720 while (tmp) {
665 parent = tmp; 721 parent = tmp;
666 if (is_min) { 722 tmp = RB_LEFT(tmp);
667 tmp = RB_LEFT(tmp);
668 } else {
669 tmp = RB_RIGHT(tmp);
670 }
671 } 723 }
672 724
673 return parent; 725 return parent;
674} 726}
675 727
676template <typename Node> 728template <typename T>
677Node* RB_MIN(RBHead<Node>* head) { 729requires HasRBEntry<T>
678 return RB_MINMAX(head, true); 730constexpr T* RB_MAX(RBHead<T>& head) {
679} 731 T* tmp = head.Root();
732 T* parent = nullptr;
680 733
681template <typename Node> 734 while (tmp) {
682Node* RB_MAX(RBHead<Node>* head) { 735 parent = tmp;
683 return RB_MINMAX(head, false); 736 tmp = RB_RIGHT(tmp);
737 }
738
739 return parent;
684} 740}
685} // namespace Common 741
742} // namespace Common::freebsd
HIC SVNT DRACONES