source: mainline/uspace/lib/cpp/include/internal/rbtree_node.hpp@ 73e3791

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

cpp: revamped rbtree so that it now stores equivalent keys in a list
  • Property mode set to 100644
File size: 16.3 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_INTERNAL_RBTREE_NODE
30#define LIBCPP_INTERNAL_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()
404 {
405 parent_ = nullptr;
406 if (left_)
407 delete left_;
408 if (right_)
409 delete right_;
410 }
411
412 private:
413 rbtree_single_node* parent_;
414 rbtree_single_node* left_;
415 rbtree_single_node* right_;
416 };
417
418 template<class T>
419 struct rbtree_multi_node
420 {
421 using utils = rbtree_utils<rbtree_multi_node<T>>;
422
423 public:
424 T value;
425 rbcolor color;
426
427 template<class... Args>
428 rbtree_multi_node(Args&&... args)
429 : value{forward<Args>(args)...}, color{rbcolor::red},
430 parent_{}, left_{}, right_{}, next_{}, first_{this}
431 { /* DUMMY BODY */ }
432
433 rbtree_multi_node* parent() const
434 {
435 return parent_;
436 }
437
438 void parent(rbtree_multi_node* node)
439 {
440 parent_ = node;
441
442 auto tmp = first_;
443 while (tmp)
444 {
445 tmp->parent_ = node;
446 tmp = tmp->next_;
447 }
448 }
449
450 rbtree_multi_node* left() const
451 {
452 return left_;
453 }
454
455 void left(rbtree_multi_node* node)
456 {
457 left_ = node;
458
459 auto tmp = first_;
460 while (tmp)
461 {
462 tmp->left_ = node;
463 tmp = tmp->next_;
464 }
465 }
466
467 rbtree_multi_node* right() const
468 {
469 return right_;
470 }
471
472 void right(rbtree_multi_node* node)
473 {
474 right_ = node;
475
476 auto tmp = first_;
477 while (tmp)
478 {
479 tmp->right_ = node;
480 tmp = tmp->next_;
481 }
482 }
483
484 rbtree_multi_node* grandparent()
485 {
486 return utils::grandparent(this);
487 }
488
489 rbtree_multi_node* brother()
490 {
491 return utils::brother(this);
492 }
493
494 rbtree_multi_node* uncle()
495 {
496 return utils::uncle(this);
497 }
498
499 bool is_left_child() const
500 {
501 return utils::is_left_child(this);
502 }
503
504 bool is_right_child()
505 {
506 return utils::is_right_child(this);
507 }
508
509 void rotate_left()
510 {
511 utils::rotate_left(this);
512 }
513
514 void rotate_right()
515 {
516 utils::rotate_right(this);
517 }
518
519 rbtree_multi_node* find_smallest()
520 {
521 return utils::find_smallest(this);
522 }
523
524 const rbtree_multi_node* find_smallest() const
525 {
526 return utils::find_smallest(this);
527 }
528
529 rbtree_multi_node* find_largest()
530 {
531 return utils::find_largest(this);
532 }
533
534 const rbtree_multi_node* find_largest() const
535 {
536 return utils::find_largest(this);
537 }
538
539 rbtree_multi_node* successor()
540 {
541 return const_cast<
542 rbtree_multi_node*
543 >(const_cast<const rbtree_multi_node*>(this)->successor());
544 }
545
546 const rbtree_multi_node* successor() const
547 {
548 if (next_)
549 return next_;
550 else
551 return utils::successor(this);
552 }
553
554 rbtree_multi_node* predecessor()
555 {
556 return const_cast<
557 rbtree_multi_node*
558 >(const_cast<const rbtree_multi_node*>(this)->predecessor());
559 }
560
561 const rbtree_multi_node* predecessor() const
562 {
563 return utils::predecessor(this);
564 }
565
566 void add_left_child(rbtree_multi_node* node)
567 {
568 utils::add_left_child(this, node);
569 }
570
571 void add_right_child(rbtree_multi_node* node)
572 {
573 utils::add_right_child(this, node);
574 }
575
576 void swap(rbtree_multi_node* other)
577 {
578 utils::swap(this, other);
579 }
580
581 rbtree_multi_node<T>* get_node_for_deletion()
582 {
583 if (next_)
584 {
585 auto tmp = next_;
586 while (tmp && tmp->next_ != this)
587 tmp = tmp->next_;
588
589 return tmp; // This will get deleted.
590 }
591 else
592 return nullptr;
593 }
594
595 void unlink()
596 {
597 if (is_left_child())
598 parent->left_ = nullptr;
599 else if (is_right_child())
600 parent->right_ = nullptr;
601 }
602
603 void add(rbtree_multi_node* node)
604 {
605 if (next_)
606 next_->add(node);
607 else
608 {
609 next_ = node;
610 next_->first_ = first_;
611 next_->parent_ = parent_;
612 next_->left_ = left_;
613 next_->right_ = right_;
614 }
615 }
616
617 ~rbtree_multi_node()
618 {
619 parent_ = nullptr;
620 if (left_)
621 delete left_;
622 if (right)
623 delete right_;
624
625 // TODO: delete the list
626 }
627
628 private:
629 rbtree_multi_node* parent_;
630 rbtree_multi_node* left_;
631 rbtree_multi_node* right_;
632
633 rbtree_multi_node* next_;
634 rbtree_multi_node* first_;
635 };
636}
637
638#endif
Note: See TracBrowser for help on using the repository browser.