source: mainline/uspace/lib/cpp/include/__bits/adt/rbtree_node.hpp@ 34b2f54d

Last change on this file since 34b2f54d was b57ba05, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 3 years ago

Update headers in C++ files
  • Property mode set to 100644
File size: 17.6 KB
Line 
1/*
2 * SPDX-FileCopyrightText: 2018 Jaroslav Jindrak
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7#ifndef LIBCPP_BITS_ADT_RBTREE_NODE
8#define LIBCPP_BITS_ADT_RBTREE_NODE
9
10#include <cassert>
11#include <utility>
12
13namespace std::aux
14{
15 enum class rbcolor
16 {
17 red, black
18 };
19
20 template<class Node>
21 struct rbtree_utils
22 {
23 static Node* grandparent(Node* node)
24 {
25 if (node && node->parent())
26 return node->parent()->parent();
27 else
28 return nullptr;
29 }
30
31 static Node* brother(Node* node)
32 {
33 if (node && node->parent())
34 {
35 if (node == node->parent()->left())
36 return node->parent()->right();
37 else
38 return node->parent()->left();
39 }
40 else
41 return nullptr;
42 }
43
44 static Node* uncle(Node* node)
45 {
46 auto gp = grandparent(node);
47 if (gp)
48 {
49 if (node->parent() == gp->left())
50 return gp->right();
51 else
52 return gp->left();
53 }
54 else
55 return nullptr;
56 }
57
58 static bool is_left_child(const Node* node)
59 {
60 if (!node)
61 return false;
62
63 if (node->parent())
64 return node->parent()->left() == node;
65 else
66 return false;
67 }
68
69 static bool is_right_child(const Node* node)
70 {
71 if (!node)
72 return false;
73
74 if (node->parent())
75 return node->parent()->right() == node;
76 else
77 return false;
78 }
79
80 static void rotate_left(Node* node)
81 {
82 // TODO: implement
83 }
84
85 static void rotate_right(Node* node)
86 {
87 // TODO: implement
88 }
89
90 static Node* find_smallest(Node* node)
91 {
92 return const_cast<Node*>(find_smallest(const_cast<const Node*>(node)));
93 }
94
95 static const Node* find_smallest(const Node* node)
96 {
97 if (!node)
98 return nullptr;
99
100 while (node->left())
101 node = node->left();
102
103 return node;
104 }
105
106 static Node* find_largest(Node* node)
107 {
108 return const_cast<Node*>(find_largest(const_cast<const Node*>(node)));
109 }
110
111 static const Node* find_largest(const Node* node)
112 {
113 if (!node)
114 return nullptr;
115
116 while (node->right())
117 node = node->right();
118
119 return node;
120 }
121
122 static Node* successor(Node* node)
123 {
124 return const_cast<Node*>(successor(const_cast<const Node*>(node)));
125 }
126
127 static const Node* successor(const Node* node)
128 {
129 if (!node)
130 return nullptr;
131
132 if (node->right())
133 return find_smallest(node->right());
134 else
135 {
136 while (node && !is_left_child(node))
137 node = node->parent();
138
139 if (node)
140 return node->parent();
141 else
142 return node;
143 }
144 }
145
146 static Node* predecessor(Node* node)
147 {
148 return const_cast<Node*>(predecessor(const_cast<const Node*>(node)));
149 }
150
151 static const Node* predecessor(const Node* node)
152 {
153 if (!node)
154 return nullptr;
155
156 if (node->left())
157 return find_largest(node->left());
158 else
159 {
160 while (node && is_left_child(node))
161 node = node->parent();
162
163 if (node)
164 return node->parent();
165 else
166 return node;
167 }
168 }
169
170 static void add_left_child(Node* node, Node* child)
171 {
172 if (!node || !child)
173 return;
174
175 node->left(child);
176 child->parent(node);
177 }
178
179 static void add_right_child(Node* node, Node* child)
180 {
181 if (!node || !child)
182 return;
183
184 node->right(child);
185 child->parent(node);
186 }
187
188 static void swap(Node* node1, Node* node2)
189 {
190 if (!node1 || !node2)
191 return;
192
193 auto parent1 = node1->parent();
194 auto left1 = node1->left();
195 auto right1 = node1->right();
196 auto is_right1 = is_right_child(node1);
197
198 auto parent2 = node2->parent();
199 auto left2 = node2->left();
200 auto right2 = node2->right();
201 auto is_right2 = is_right_child(node2);
202
203 assimilate(node1, parent2, left2, right2, is_right2);
204 assimilate(node2, parent1, left1, right1, is_right1);
205 }
206
207 static void assimilate(
208 Node* node, Node* p, Node* l, Node* r, bool is_r
209 )
210 {
211 if (!node)
212 return;
213
214 node->parent(p);
215 if (node->parent())
216 {
217 if (is_r)
218 node->parent()->right(node);
219 else
220 node->parent()->left(node);
221 }
222
223 node->left(l);
224 if (node->left())
225 node->left()->parent(node);
226
227 node->right(r);
228 if (node->right())
229 node->right()->parent(node);
230 }
231 };
232
233 template<class T>
234 struct rbtree_single_node
235 {
236 using utils = rbtree_utils<rbtree_single_node<T>>;
237
238 public:
239 T value;
240 rbcolor color;
241
242 template<class... Args>
243 rbtree_single_node(Args&&... args)
244 : value{forward<Args>(args)...}, color{rbcolor::red},
245 parent_{}, left_{}, right_{}
246 { /* DUMMY BODY */ }
247
248 rbtree_single_node* parent() const
249 {
250 return parent_;
251 }
252
253 void parent(rbtree_single_node* node)
254 {
255 parent_ = node;
256 }
257
258 rbtree_single_node* left() const
259 {
260 return left_;
261 }
262
263 void left(rbtree_single_node* node)
264 {
265 left_ = node;
266 }
267
268 rbtree_single_node* right() const
269 {
270 return right_;
271 }
272
273 void right(rbtree_single_node* node)
274 {
275 right_ = node;
276 }
277
278 rbtree_single_node* grandparent()
279 {
280 return utils::grandparent(this);
281 }
282
283 rbtree_single_node* brother()
284 {
285 return utils::brother(this);
286 }
287
288 rbtree_single_node* uncle()
289 {
290 return utils::uncle(this);
291 }
292
293 bool is_left_child() const
294 {
295 return utils::is_left_child(this);
296 }
297
298 bool is_right_child() const
299 {
300 return utils::is_right_child(this);
301 }
302
303 void rotate_left()
304 {
305 utils::rotate_left(this);
306 }
307
308 void rotate_right()
309 {
310 utils::rotate_right(this);
311 }
312
313 rbtree_single_node* find_smallest()
314 {
315 return utils::find_smallest(this);
316 }
317
318 const rbtree_single_node* find_smallest() const
319 {
320 return utils::find_smallest(this);
321 }
322
323 rbtree_single_node* find_largest()
324 {
325 return utils::find_largest(this);
326 }
327
328 const rbtree_single_node* find_largest() const
329 {
330 return utils::find_largest(this);
331 }
332
333 rbtree_single_node* successor()
334 {
335 return utils::successor(this);
336 }
337
338 const rbtree_single_node* successor() const
339 {
340 return utils::successor(this);
341 }
342
343 rbtree_single_node* predecessor()
344 {
345 return utils::predecessor(this);
346 }
347
348 const rbtree_single_node* predecessor() const
349 {
350 return utils::predecessor(this);
351 }
352
353 void add_left_child(rbtree_single_node* node)
354 {
355 utils::add_left_child(this, node);
356 }
357
358 void add_right_child(rbtree_single_node* node)
359 {
360 utils::add_right_child(this, node);
361 }
362
363 void swap(rbtree_single_node* other)
364 {
365 utils::swap(this, other);
366 }
367
368 void unlink()
369 {
370 if (is_left_child())
371 parent_->left_ = nullptr;
372 else if (is_right_child())
373 parent_->right_ = nullptr;
374 }
375
376 rbtree_single_node* get_node_for_deletion()
377 {
378 return nullptr;
379 }
380
381 rbtree_single_node* get_end()
382 {
383 return this;
384 }
385
386 const rbtree_single_node* get_end() const
387 {
388 return this;
389 }
390
391 ~rbtree_single_node()
392 {
393 parent_ = nullptr;
394 if (left_)
395 delete left_;
396 if (right_)
397 delete right_;
398 }
399
400 private:
401 rbtree_single_node* parent_;
402 rbtree_single_node* left_;
403 rbtree_single_node* right_;
404 };
405
406 template<class T>
407 struct rbtree_multi_node
408 {
409 using utils = rbtree_utils<rbtree_multi_node<T>>;
410
411 public:
412 T value;
413 rbcolor color;
414
415 template<class... Args>
416 rbtree_multi_node(Args&&... args)
417 : value{forward<Args>(args)...}, color{rbcolor::red},
418 parent_{}, left_{}, right_{}, next_{}, first_{}
419 {
420 first_ = this;
421 }
422
423 rbtree_multi_node* parent() const
424 {
425 return parent_;
426 }
427
428 void parent(rbtree_multi_node* node)
429 {
430 parent_ = node;
431
432 auto tmp = first_;
433 while (tmp)
434 {
435 tmp->parent_ = node;
436 tmp = tmp->next_;
437 }
438 }
439
440 rbtree_multi_node* left() const
441 {
442 return left_;
443 }
444
445 void left(rbtree_multi_node* node)
446 {
447 left_ = node;
448
449 auto tmp = first_;
450 while (tmp)
451 {
452 tmp->left_ = node;
453 tmp = tmp->next_;
454 }
455 }
456
457 rbtree_multi_node* right() const
458 {
459 return right_;
460 }
461
462 void right(rbtree_multi_node* node)
463 {
464 right_ = node;
465
466 auto tmp = first_;
467 while (tmp)
468 {
469 tmp->right_ = node;
470 tmp = tmp->next_;
471 }
472 }
473
474 rbtree_multi_node* grandparent()
475 {
476 return utils::grandparent(this);
477 }
478
479 rbtree_multi_node* brother()
480 {
481 return utils::brother(this);
482 }
483
484 rbtree_multi_node* uncle()
485 {
486 return utils::uncle(this);
487 }
488
489 bool is_left_child() const
490 {
491 return utils::is_left_child(this);
492 }
493
494 bool is_right_child()
495 {
496 return utils::is_right_child(this);
497 }
498
499 void rotate_left()
500 {
501 utils::rotate_left(this);
502 }
503
504 void rotate_right()
505 {
506 utils::rotate_right(this);
507 }
508
509 rbtree_multi_node* find_smallest()
510 {
511 return utils::find_smallest(this);
512 }
513
514 const rbtree_multi_node* find_smallest() const
515 {
516 return utils::find_smallest(this);
517 }
518
519 rbtree_multi_node* find_largest()
520 {
521 return utils::find_largest(this);
522 }
523
524 const rbtree_multi_node* find_largest() const
525 {
526 return utils::find_largest(this);
527 }
528
529 rbtree_multi_node* successor()
530 {
531 return const_cast<
532 rbtree_multi_node*
533 >(const_cast<const rbtree_multi_node*>(this)->successor());
534 }
535
536 const rbtree_multi_node* successor() const
537 {
538 if (next_)
539 return next_;
540 else
541 return utils::successor(this);
542 }
543
544 rbtree_multi_node* predecessor()
545 {
546 return const_cast<
547 rbtree_multi_node*
548 >(const_cast<const rbtree_multi_node*>(this)->predecessor());
549 }
550
551 const rbtree_multi_node* predecessor() const
552 {
553 if (this != first_)
554 {
555 auto tmp = first_;
556 while (tmp->next_ != this)
557 tmp = tmp->next_;
558
559 return tmp;
560 }
561 else
562 {
563 auto tmp = utils::predecessor(this);
564
565 /**
566 * If tmp was duplicate, we got a pointer
567 * to the first node in the list. So we need
568 * to move to the end.
569 */
570 while (tmp->next_ != nullptr)
571 tmp = tmp->next_;
572
573 return tmp;
574 }
575 }
576
577 void add_left_child(rbtree_multi_node* node)
578 {
579 utils::add_left_child(this, node);
580 }
581
582 void add_right_child(rbtree_multi_node* node)
583 {
584 utils::add_right_child(this, node);
585 }
586
587 void swap(rbtree_multi_node* other)
588 {
589 utils::swap(this, other);
590 }
591
592 rbtree_multi_node* get_node_for_deletion()
593 {
594 /**
595 * To make sure we delete nodes in
596 * the order of their insertion
597 * (not required, but sensical), we
598 * update then list and return this
599 * for deletion.
600 */
601 if (next_)
602 {
603 // Make next the new this.
604 next_->first_ = next_;
605 if (is_left_child())
606 parent_->left_ = next_;
607 else if (is_right_child())
608 parent_->right_ = next_;
609
610 if (left_)
611 left_->parent_ = next_;
612 if (right_)
613 right_->parent_ = next_;
614
615 /**
616 * Update the first_ pointer
617 * of the rest of the list.
618 */
619 auto tmp = next_->next_;
620 while (tmp)
621 {
622 tmp->first_ = next_;
623 tmp = tmp->next_;
624 }
625
626 /**
627 * Otherwise destructor could
628 * destroy them.
629 */
630 parent_ = nullptr;
631 left_ = nullptr;
632 right_ = nullptr;
633 next_ = nullptr;
634 first_ = nullptr;
635
636 return this; // This will get deleted.
637 }
638 else
639 return nullptr;
640 }
641
642 void unlink()
643 {
644 if (is_left_child())
645 parent_->left_ = nullptr;
646 else if (is_right_child())
647 parent_->right_ = nullptr;
648 }
649
650 void add(rbtree_multi_node* node)
651 {
652 if (next_)
653 next_->add(node);
654 else
655 {
656 next_ = node;
657 next_->first_ = first_;
658 next_->parent_ = parent_;
659 next_->left_ = left_;
660 next_->right_ = right_;
661 }
662 }
663
664 rbtree_multi_node* get_end()
665 {
666 return const_cast<rbtree_multi_node*>(
667 const_cast<const rbtree_multi_node*>(this)->get_end()
668 );
669 }
670
671 const rbtree_multi_node* get_end() const
672 {
673 if (!next_)
674 return this;
675 else
676 {
677 auto tmp = next_;
678 while (tmp->next_)
679 tmp = tmp->next_;
680
681 return tmp;
682 }
683 }
684
685 ~rbtree_multi_node()
686 {
687 parent_ = nullptr;
688 if (left_)
689 delete left_;
690 if (right_)
691 delete right_;
692
693 // TODO: delete the list
694 }
695
696 private:
697 rbtree_multi_node* parent_;
698 rbtree_multi_node* left_;
699 rbtree_multi_node* right_;
700
701 rbtree_multi_node* next_;
702 rbtree_multi_node* first_;
703 };
704}
705
706#endif
Note: See TracBrowser for help on using the repository browser.