source: mainline/uspace/lib/cpp/include/__bits/rbtree_node.hpp@ 7bbf91e

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 7bbf91e was 7bbf91e, checked in by Dzejrou <dzejrou@…>, 7 years ago

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