Embedded Template Library 1.0
intrusive_links.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2016 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_INTRUSIVE_LINKS_INCLUDED
32#define ETL_INTRUSIVE_LINKS_INCLUDED
33
34#include "platform.h"
35#include "nullptr.h"
36#include "type_traits.h"
37#include "exception.h"
38#include "error_handler.h"
39#include "utility.h"
40#include "algorithm.h"
41
42#include <assert.h>
43
44//*****************************************************************************
45// Note:
46// The link functions work slightly differently to the STL 'insert' convention
47// in that the second link parameter will be inserted after the first.
48// i.e.
49// If the list contains '1', '2', '3', '4' and "link_splice '2','5'" is invoked the
50// resulting list will contain '1', '2', '5', '3', '4'
51// This is to maintain consistency between forward and bidirectional links
52// and also is intuitive.
53//*****************************************************************************
54
55namespace etl
56{
57 //***************************************************************************
59 //***************************************************************************
61 {
62 public:
63
64 link_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
65 : exception(reason_, file_name_, line_number_)
66 {
67 }
68 };
69
70 //***************************************************************************
72 //***************************************************************************
74 {
75 public:
76
77 not_unlinked_exception(string_type file_name_, numeric_type line_number_)
78 : link_exception(ETL_ERROR_TEXT("link:still linked", ETL_INTRUSIVE_LINKS_FILE_ID"A"), file_name_, line_number_)
79 {
80 }
81 };
82
83 //***************************************************************************
85 //***************************************************************************
86 template <size_t ID_>
88 {
89 enum
90 {
91 ID = ID_,
92 };
93
94 //***********************************
96 : etl_next(ETL_NULLPTR)
97 {
98 }
99
100 //***********************************
102 : etl_next(p_next)
103 {
104 }
105
106 //***********************************
107 forward_link(const forward_link& other)
108 : etl_next(other.etl_next)
109 {
110 }
111
112 //***********************************
113 forward_link& operator =(const forward_link& other)
114 {
115 etl_next = other.etl_next;
116
117 return *this;
118 }
119
120 //***********************************
121 void clear()
122 {
123 etl_next = ETL_NULLPTR;
124 }
125
126 //***********************************
127 ETL_NODISCARD
128 bool is_linked() const
129 {
130 return etl_next != ETL_NULLPTR;
131 }
132
133 //***********************************
134 ETL_NODISCARD
135 bool has_next() const
136 {
137 return etl_next != ETL_NULLPTR;
138 }
139
140 //***********************************
141 void set_next(forward_link* n)
142 {
143 etl_next = n;
144 }
145
146 //***********************************
147 void set_next(forward_link& n)
148 {
149 etl_next = &n;
150 }
151
152 //***********************************
153 ETL_NODISCARD
154 forward_link* get_next() const
155 {
156 return etl_next;
157 }
158
159 forward_link* etl_next;
160 };
161
162 //***********************************
163 template <typename TLink>
165 {
166 static ETL_CONSTANT bool value = etl::is_same<TLink, etl::forward_link<TLink::ID> >::value;
167 };
168
169 //***********************************
170#if ETL_USING_CPP17
171 template <typename TLink>
172 inline constexpr bool is_forward_link_v = etl::is_forward_link<TLink>::value;
173#endif
174
175 //***************************************************************************
176 // link
177 //***************************************************************************
178 // Reference, Reference
179 template <typename TLink>
181 link(TLink& lhs, TLink& rhs)
182 {
183 lhs.etl_next = &rhs;
184 }
185
186 //***********************************
187 // Pointer, Pointer
188 template <typename TLink>
190 link(TLink* lhs, TLink* rhs)
191 {
192 if (lhs != ETL_NULLPTR)
193 {
194 lhs->etl_next = rhs;
195 }
196 }
197
198 //***********************************
199 // Reference, Pointer
200 template <typename TLink>
202 link(TLink& lhs, TLink* rhs)
203 {
204 lhs.etl_next = rhs;
205 }
206
207 //***********************************
208 // Pointer, Reference
209 template <typename TLink>
211 link(TLink* lhs, TLink& rhs)
212 {
213 if (lhs != ETL_NULLPTR)
214 {
215 lhs->etl_next = &rhs;
216 }
217 }
218
219 //***************************************************************************
220 // link_splice
221 //***************************************************************************
222 // Reference, Reference
223 template <typename TLink>
225 link_splice(TLink& lhs, TLink& rhs)
226 {
227 rhs.etl_next = lhs.etl_next;
228 lhs.etl_next = &rhs;
229 }
230
231 //***********************************
232 // Pointer, Pointer
233 template <typename TLink>
235 link_splice(TLink* lhs, TLink* rhs)
236 {
237 if (lhs != ETL_NULLPTR)
238 {
239 if (rhs != ETL_NULLPTR)
240 {
241 rhs->etl_next = lhs->etl_next;
242 }
243
244 lhs->etl_next = rhs;
245 }
246 }
247
248 //***********************************
249 // Reference, Pointer
250 template <typename TLink>
252 link_splice(TLink& lhs, TLink* rhs)
253 {
254 if (rhs != ETL_NULLPTR)
255 {
256 rhs->etl_next = lhs.etl_next;
257 }
258
259 lhs.etl_next = rhs;
260 }
261
262 //***********************************
263 // Pointer, Reference
264 template <typename TLink>
266 link_splice(TLink* lhs, TLink& rhs)
267 {
268 if (lhs != ETL_NULLPTR)
269 {
270 rhs.etl_next = lhs->etl_next;
271 lhs->etl_next = &rhs;
272 }
273 }
274
275 //***********************************
276 // Reference, Reference, Reference
277 template <typename TLink>
279 link_splice(TLink& lhs, TLink& first, TLink& last)
280 {
281 last.etl_next = lhs.etl_next;
282 lhs.etl_next = &first;
283 }
284
285 //***********************************
286 // Pointer, Reference, Reference
287 template <typename TLink>
289 link_splice(TLink* lhs, TLink& first, TLink& last)
290 {
291 if (lhs != ETL_NULLPTR)
292 {
293 last.etl_next = lhs->etl_next;
294 lhs->etl_next = &first;
295 }
296 else
297 {
298 last.etl_next = ETL_NULLPTR;
299 }
300 }
301
302 //***************************************************************************
303 // unlink_after
304 //***************************************************************************
305 // Reference
306 template <typename TLink>
308 unlink_after(TLink& node)
309 {
310 if (node.etl_next != ETL_NULLPTR)
311 {
312 TLink* unlinked_node = node.etl_next;
313 node.etl_next = unlinked_node->etl_next;
314 unlinked_node->clear();
315 return unlinked_node;
316 }
317
318 return node.etl_next;
319 }
320
321 //***********************************
322 // Reference, Reference
323 template <typename TLink>
325 unlink_after(TLink& before, TLink& last)
326 {
327 TLink* first = before.etl_next;
328
329 if (&before != &last)
330 {
331 before.etl_next = last.etl_next;
332 last.clear();
333 }
334
335 return first;
336 }
337
338 // Reference
339 template <typename TLink>
341 is_linked(TLink& node)
342 {
343 return node.is_linked();
344 }
345
346 // Pointer
347 template <typename TLink>
349 is_linked(TLink* node)
350 {
351 return node->is_linked();
352 }
353
354 //***************************************************************************
355 // link_clear
356 //***************************************************************************
357 // Reference
358 template <typename TLink>
360 link_clear(TLink& start)
361 {
362 start.etl_next = ETL_NULLPTR;
363 }
364
365 //***********************************
366 // Pointer
367 template <typename TLink>
369 link_clear(TLink* start)
370 {
371 if (start != ETL_NULLPTR)
372 {
373 etl::link_clear(*start);
374 }
375 }
376
377 //***************************************************************************
378 // link_clear
379 //***************************************************************************
380 // Reference
381 template <typename TLink>
383 link_clear_range(TLink& start)
384 {
385 TLink* current = &start;
386
387 while (current != ETL_NULLPTR)
388 {
389 TLink* next = current->etl_next;
390 current->clear();
391 current = next;
392 }
393 }
394
395 //***********************************
396 // Pointer
397 template <typename TLink>
399 link_clear_range(TLink* start)
400 {
401 if (start != ETL_NULLPTR)
402 {
403 etl::link_clear_range(*start);
404 }
405 }
406
407 //***************************************************************************
409 //***************************************************************************
410 template <size_t ID_>
412 {
413 enum
414 {
415 ID = ID_,
416 };
417
418 //***********************************
420 : etl_previous(ETL_NULLPTR)
421 , etl_next(ETL_NULLPTR)
422 {
423 }
424
425 //***********************************
427 : etl_previous(p_previous)
428 , etl_next(p_next)
429 {
430 }
431
432 //***********************************
434 : etl_previous(other.etl_previous)
435 , etl_next(other.etl_next)
436 {
437 }
438
439 //***********************************
440 bidirectional_link& operator =(const bidirectional_link& other)
441 {
442 etl_previous = other.etl_previous;
443 etl_next = other.etl_next;
444
445 return *this;
446 }
447
448 //***********************************
449 void clear()
450 {
451 etl_previous = ETL_NULLPTR;
452 etl_next = ETL_NULLPTR;
453 }
454
455 //***********************************
456 ETL_NODISCARD
457 bool is_linked() const
458 {
459 return (etl_previous != ETL_NULLPTR) || (etl_next != ETL_NULLPTR);
460 }
461
462 //***********************************
463 ETL_NODISCARD
464 bool has_next() const
465 {
466 return etl_next != ETL_NULLPTR;
467 }
468
469 //***********************************
470 ETL_NODISCARD
471 bool has_previous() const
472 {
473 return etl_previous != ETL_NULLPTR;
474 }
475
476 //***********************************
477 void set_next(bidirectional_link* n)
478 {
479 etl_next = n;
480 }
481
482 //***********************************
483 void set_next(bidirectional_link& n)
484 {
485 etl_next = &n;
486 }
487
488 //***********************************
489 ETL_NODISCARD
490 bidirectional_link* get_next() const
491 {
492 return etl_next;
493 }
494
495 //***********************************
496 void set_previous(bidirectional_link* n)
497 {
498 etl_previous = n;
499 }
500
501 //***********************************
502 void set_previous(bidirectional_link& n)
503 {
504 etl_previous = &n;
505 }
506
507 //***********************************
508 ETL_NODISCARD
509 bidirectional_link* get_previous() const
510 {
511 return etl_previous;
512 }
513
514 //***********************************
515 void reverse()
516 {
517 using ETL_OR_STD::swap; // Allow ADL
518 swap(etl_previous, etl_next);
519 }
520
521 //***********************************
522 void unlink()
523 {
524 // Connect the previous link with the next.
525 if (etl_previous != ETL_NULLPTR)
526 {
527 etl_previous->etl_next = etl_next;
528 }
529
530 // Connect the next link with the previous.
531 if (etl_next != ETL_NULLPTR)
532 {
533 etl_next->etl_previous = etl_previous;
534 }
535
536 clear();
537 }
538
539 bidirectional_link* etl_previous;
540 bidirectional_link* etl_next;
541 };
542
543 //***********************************
544 template <typename TLink>
546 {
547 static ETL_CONSTANT bool value = etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value;
548 };
549
550 //***********************************
551#if ETL_USING_CPP17
552 template <typename TLink>
553 inline constexpr bool is_bidirectional_link_v = etl::is_bidirectional_link<TLink>::value;
554#endif
555
556 //***************************************************************************
557 // link
558 //***************************************************************************
559 // Reference, Reference
560 template <typename TLink>
562 link(TLink& lhs, TLink& rhs)
563 {
564 lhs.etl_next = &rhs;
565 rhs.etl_previous = &lhs;
566 }
567
568 //***********************************
569 // Pointer, Pointer
570 template <typename TLink>
572 link(TLink* lhs, TLink* rhs)
573 {
574 if (lhs != ETL_NULLPTR)
575 {
576 lhs->etl_next = rhs;
577 }
578
579 if (rhs != ETL_NULLPTR)
580 {
581 rhs->etl_previous = lhs;
582 }
583 }
584
585 //***********************************
586 // Reference, Pointer
587 template <typename TLink>
589 link(TLink& lhs, TLink* rhs)
590 {
591 lhs.etl_next = rhs;
592
593 if (rhs != ETL_NULLPTR)
594 {
595 rhs->etl_previous = &lhs;
596 }
597 }
598
599 //***********************************
600 // Pointer, Reference
601 template <typename TLink>
603 link(TLink* lhs, TLink& rhs)
604 {
605 if (lhs != ETL_NULLPTR)
606 {
607 lhs->etl_next = &rhs;
608 }
609
610 rhs.etl_previous = lhs;
611 }
612
613 //***********************************
614 // Reference, Reference
615 template <typename TLink>
617 link_splice(TLink& lhs, TLink& rhs)
618 {
619 rhs.etl_next = lhs.etl_next;
620 rhs.etl_previous = &lhs;
621
622 if (lhs.etl_next != ETL_NULLPTR)
623 {
624 lhs.etl_next->etl_previous = &rhs;
625 }
626
627 lhs.etl_next = &rhs;
628 }
629
630 //***************************************************************************
631 // link_splice
632 //***************************************************************************
633 // Pointer, Pointer
634 template <typename TLink>
636 link_splice(TLink* lhs, TLink* rhs)
637 {
638 if (rhs != ETL_NULLPTR)
639 {
640 if (lhs != ETL_NULLPTR)
641 {
642 rhs->etl_next = lhs->etl_next;
643 }
644
645 rhs->etl_previous = lhs;
646 }
647
648 if (lhs != ETL_NULLPTR)
649 {
650 if (lhs->etl_next != ETL_NULLPTR)
651 {
652 lhs->etl_next->etl_previous = rhs;
653 }
654
655 lhs->etl_next = rhs;
656 }
657 }
658
659 //***********************************
660 // Reference, Pointer
661 template <typename TLink>
663 link_splice(TLink& lhs, TLink* rhs)
664 {
665 if (rhs != ETL_NULLPTR)
666 {
667 rhs->etl_next = lhs.etl_next;
668 rhs->etl_previous = &lhs;
669 }
670
671 if (lhs.etl_next != ETL_NULLPTR)
672 {
673 lhs.etl_next->etl_previous = rhs;
674 }
675
676 lhs.etl_next = rhs;
677 }
678
679 //***********************************
680 // Pointer, Reference
681 template <typename TLink>
683 link_splice(TLink* lhs, TLink& rhs)
684 {
685 if (lhs != ETL_NULLPTR)
686 {
687 rhs.etl_next = lhs->etl_next;
688 }
689
690 rhs.etl_previous = lhs;
691
692 if (lhs != ETL_NULLPTR)
693 {
694 if (lhs->etl_next != ETL_NULLPTR)
695 {
696 lhs->etl_next->etl_previous = &rhs;
697 }
698
699 lhs->etl_next = &rhs;
700 }
701 }
702
703 //***********************************
704 // Reference, Reference, Reference
705 template <typename TLink>
707 link_splice(TLink& lhs, TLink& first, TLink& last)
708 {
709 last.etl_next = lhs.etl_next;
710 first.etl_previous = &lhs;
711
712 if (last.etl_next != ETL_NULLPTR)
713 {
714 last.etl_next->etl_previous = &last;
715 }
716
717 lhs.etl_next = &first;
718 }
719
720 //***********************************
721 // Pointer, Reference, Reference
722 template <typename TLink>
724 link_splice(TLink* lhs, TLink& first, TLink& last)
725 {
726 if (lhs != ETL_NULLPTR)
727 {
728 last.etl_next = lhs->etl_next;
729 }
730 else
731 {
732 last.etl_next = ETL_NULLPTR;
733 }
734
735 first.etl_previous = lhs;
736
737 if (last.etl_next != ETL_NULLPTR)
738 {
739 last.etl_next->etl_previous = &last;
740 }
741
742 if (lhs != ETL_NULLPTR)
743 {
744 lhs->etl_next = &first;
745 }
746 }
747
748 //***************************************************************************
749 // unlink
750 //***************************************************************************
751 // Reference
752 template <typename TLink>
754 unlink(TLink& node)
755 {
756 node.unlink();
757 }
758
759 //***********************************
760 // Reference Reference
761 template <typename TLink>
763 unlink(TLink& first, TLink& last)
764 {
765 if (&first == &last)
766 {
767 first.unlink();
768 }
769 else
770 {
771 if (last.etl_next != ETL_NULLPTR)
772 {
773 last.etl_next->etl_previous = first.etl_previous;
774 }
775
776 if (first.etl_previous != ETL_NULLPTR)
777 {
778 first.etl_previous->etl_next = last.etl_next;
779 last.clear();
780 }
781
782 first.etl_previous = ETL_NULLPTR;
783 last.etl_next = ETL_NULLPTR;
784 }
785
786 return first;
787 }
788
789 // Reference
790 template <typename TLink>
792 is_linked(TLink& node)
793 {
794 return node.is_linked();
795 }
796
797 // Pointer
798 template <typename TLink>
800 is_linked(TLink* node)
801 {
802 return node->is_linked();
803 }
804
805 //***************************************************************************
806 // link_clear_range
807 //***************************************************************************
808 // Reference
809 template <typename TLink>
811 link_clear_range(TLink& start)
812 {
813 TLink* current = &start;
814
815 while (current != ETL_NULLPTR)
816 {
817 TLink* next = current->etl_next;
818 current->clear();
819 current = next;
820 }
821 }
822
823 //***********************************
824 // Pointer
825 template <typename TLink>
827 link_clear_range(TLink* start)
828 {
829 etl::link_clear_range(*start);
830 }
831
832 //***************************************************************************
834 //***************************************************************************
835 template <size_t ID_>
837 {
838 enum
839 {
840 ID = ID_,
841 };
842
843 //***********************************
844 tree_link()
845 : etl_parent(ETL_NULLPTR)
846 , etl_left(ETL_NULLPTR)
847 , etl_right(ETL_NULLPTR)
848 {
849 }
850
851 //***********************************
852 tree_link(tree_link* p_parent, tree_link* p_left, tree_link* p_right)
853 : etl_parent(p_parent)
854 , etl_left(p_left)
855 , etl_right(p_right)
856 {
857 }
858
859 //***********************************
860 tree_link(const tree_link& other)
861 : etl_parent(other.etl_parent)
862 , etl_left(other.etl_left)
863 , etl_right(other.etl_right)
864 {
865 }
866
867 //***********************************
868 tree_link& operator =(const tree_link& other)
869 {
870 etl_parent = other.etl_parent;
871 etl_left = other.etl_left;
872 etl_right = other.etl_right;
873
874 return *this;
875 }
876
877 //***********************************
878 void clear()
879 {
880 etl_parent = ETL_NULLPTR;
881 etl_left = ETL_NULLPTR;
882 etl_right = ETL_NULLPTR;
883 }
884
885 //***********************************
886 bool is_linked() const
887 {
888 return (etl_parent != ETL_NULLPTR) || (etl_left != ETL_NULLPTR) || (etl_right != ETL_NULLPTR);
889 }
890
891 //***********************************
892 ETL_NODISCARD
893 bool has_parent() const
894 {
895 return etl_parent != ETL_NULLPTR;
896 }
897
898 //***********************************
899 ETL_NODISCARD
900 bool has_left() const
901 {
902 return etl_left != ETL_NULLPTR;
903 }
904
905 //***********************************
906 ETL_NODISCARD
907 bool has_right() const
908 {
909 return etl_right != ETL_NULLPTR;
910 }
911
912 //***********************************
913 void set_parent(tree_link* p)
914 {
915 etl_parent = p;
916 }
917
918 //***********************************
919 void set_left(tree_link* l)
920 {
921 etl_left = l;
922 }
923
924 //***********************************
925 void set_right(tree_link* r)
926 {
927 etl_right = r;
928 }
929
930 //***********************************
931 void set_parent(tree_link& p)
932 {
933 etl_parent = &p;
934 }
935
936 //***********************************
937 void set_left(tree_link& l)
938 {
939 etl_left = &l;
940 }
941
942 //***********************************
943 void set_right(tree_link& r)
944 {
945 etl_right = &r;
946 }
947
948 //***********************************
949 ETL_NODISCARD
950 tree_link* get_parent() const
951 {
952 return etl_parent;
953 }
954
955 //***********************************
956 ETL_NODISCARD
957 tree_link* get_left() const
958 {
959 return etl_left;
960 }
961
962 //***********************************
963 ETL_NODISCARD
964 tree_link* get_right() const
965 {
966 return etl_right;
967 }
968
969 //***********************************
970 void mirror()
971 {
972 using ETL_OR_STD::swap;
973 swap(etl_left, etl_right);
974 }
975
976 tree_link* etl_parent;
977 tree_link* etl_left;
978 tree_link* etl_right;
979 };
980
981 //***********************************
982 template <typename TLink>
984 {
985 static ETL_CONSTANT bool value = etl::is_same<TLink, etl::tree_link<TLink::ID> >::value;
986 };
987
988 //***********************************
989#if ETL_USING_CPP17
990 template <typename TLink>
991 inline constexpr bool is_tree_link_v = etl::is_tree_link<TLink>::value;
992#endif
993
994 //***************************************************************************
995 // link_left
996 // Sets the left link.
997 //***************************************************************************
998 // Reference, Reference
999 template <typename TLink>
1001 link_left(TLink& parent, TLink& leaf)
1002 {
1003 parent.etl_left = &leaf;
1004 leaf.etl_parent = &parent;
1005 }
1006
1007 //***********************************
1008 // Pointer, Pointer
1009 template <typename TLink>
1011 link_left(TLink* parent, TLink* leaf)
1012 {
1013 if (parent != ETL_NULLPTR)
1014 {
1015 parent->etl_left = leaf;
1016 }
1017
1018 if (leaf != ETL_NULLPTR)
1019 {
1020 leaf->etl_parent = parent;
1021 }
1022 }
1023
1024 //***********************************
1025 // Reference, Pointer
1026 template <typename TLink>
1028 link_left(TLink& parent, TLink* leaf)
1029 {
1030 parent.etl_left = leaf;
1031
1032 if (leaf != ETL_NULLPTR)
1033 {
1034 leaf->etl_parent = &parent;
1035 }
1036 }
1037
1038 //***********************************
1039 // Pointer, Reference
1040 template <typename TLink>
1042 link_left(TLink* parent, TLink& leaf)
1043 {
1044 if (parent != ETL_NULLPTR)
1045 {
1046 parent->etl_left = &leaf;
1047 }
1048
1049 leaf.etl_parent = parent;
1050 }
1051
1052 //***************************************************************************
1053 // link_right
1054 // Sets the right link.
1055 //***************************************************************************
1056 template <typename TLink>
1058 link_right(TLink& parent, TLink& leaf)
1059 {
1060 parent.etl_right = &leaf;
1061 leaf.etl_parent = &parent;
1062 }
1063
1064 //***********************************
1065 template <typename TLink>
1067 link_right(TLink* parent, TLink* leaf)
1068 {
1069 if (parent != ETL_NULLPTR)
1070 {
1071 parent->etl_right = leaf;
1072 }
1073
1074 if (leaf != ETL_NULLPTR)
1075 {
1076 leaf->etl_parent = parent;
1077 }
1078 }
1079
1080 //***********************************
1081 template <typename TLink>
1083 link_right(TLink& parent, TLink* leaf)
1084 {
1085 parent.etl_right = leaf;
1086
1087 if (leaf != ETL_NULLPTR)
1088 {
1089 leaf->etl_parent = &parent;
1090 }
1091 }
1092
1093 //***********************************
1094 template <typename TLink>
1096 link_right(TLink* parent, TLink& leaf)
1097 {
1098 if (parent != ETL_NULLPTR)
1099 {
1100 parent->etl_right = &leaf;
1101 }
1102
1103 leaf.etl_parent = parent;
1104 }
1105
1106 //***************************************************************************
1107 // link_rotate_left
1108 //***************************************************************************
1109 // Reference, Reference
1110 template <typename TLink>
1112 link_rotate_left(TLink& parent, TLink& leaf)
1113 {
1114 parent.etl_right = leaf.etl_left;
1115
1116 if (parent.etl_right != ETL_NULLPTR)
1117 {
1118 parent.etl_right->etl_parent = &parent;
1119 }
1120
1121 leaf.etl_parent = parent.etl_parent;
1122 parent.etl_parent = &leaf;
1123 leaf.etl_left = &parent;
1124 }
1125
1126 //***********************************
1127 // Pointer, Pointer
1128 template <typename TLink>
1130 link_rotate_left(TLink* parent, TLink* leaf)
1131 {
1132 if ((parent != ETL_NULLPTR) && (leaf != ETL_NULLPTR))
1133 {
1134 link_rotate_left(*parent, *leaf);
1135 }
1136 }
1137
1138 //***********************************
1139 // Reference, Pointer
1140 template <typename TLink>
1142 link_rotate_left(TLink& parent, TLink* leaf)
1143 {
1144 if (leaf != ETL_NULLPTR)
1145 {
1146 link_rotate_left(parent, *leaf);
1147 }
1148 }
1149
1150 //***********************************
1151 // Pointer, Reference
1152 template <typename TLink>
1154 link_rotate_left(TLink* parent, TLink& leaf)
1155 {
1156 if (parent != ETL_NULLPTR)
1157 {
1158 link_rotate_left(*parent, leaf);
1159 }
1160 }
1161
1162 //***************************************************************************
1163 // link_rotate_right
1164 //***************************************************************************
1165 template <typename TLink>
1167 link_rotate_right(TLink& parent, TLink& leaf)
1168 {
1169 parent.etl_left = leaf.etl_right;
1170
1171 if (parent.etl_left != ETL_NULLPTR)
1172 {
1173 parent.etl_left->etl_parent = &parent;
1174 }
1175
1176 leaf.etl_parent = parent.etl_parent;
1177 parent.etl_parent = &leaf;
1178 leaf.etl_right = &parent;
1179 }
1180
1181
1182 template <typename TLink>
1184 link_rotate_right(TLink* parent, TLink* leaf)
1185 {
1186 if ((parent != ETL_NULLPTR) && (leaf != ETL_NULLPTR))
1187 {
1188 link_rotate_right(*parent, *leaf);
1189 }
1190 }
1191
1192 template <typename TLink>
1194 link_rotate_right(TLink& parent, TLink* leaf)
1195 {
1196 if (leaf != ETL_NULLPTR)
1197 {
1198 link_rotate_right(parent, *leaf);
1199 }
1200 }
1201
1202 //***********************************
1203 template <typename TLink>
1205 link_rotate_right(TLink* parent, TLink& leaf)
1206 {
1207 if (parent != ETL_NULLPTR)
1208 {
1209 link_rotate_right(*parent, leaf);
1210 }
1211 }
1212
1213 //***************************************************************************
1214 // link_rotate
1215 //***************************************************************************
1216 // Reference, Reference
1218 template <typename TLink>
1220 link_rotate(TLink& parent, TLink& leaf)
1221 {
1222 if (parent.etl_left == &leaf)
1223 {
1224 etl::link_rotate_right(parent, leaf);
1225 }
1226 else
1227 {
1228 etl::link_rotate_left(parent, leaf);
1229 }
1230 }
1231
1232 //***********************************
1233 // Pointer, Pointer
1235 template <typename TLink>
1237 link_rotate(TLink* parent, TLink* leaf)
1238 {
1239 if ((parent != ETL_NULLPTR) && (leaf != ETL_NULLPTR))
1240 {
1241 if (parent->etl_left == leaf)
1242 {
1243 etl::link_rotate_right(*parent, *leaf);
1244 }
1245 else
1246 {
1247 etl::link_rotate_left(*parent, *leaf);
1248 }
1249 }
1250 }
1251
1252 //***********************************
1253 // Reference, Pointer
1255 template <typename TLink>
1257 link_rotate(TLink& parent, TLink* leaf)
1258 {
1259 if (leaf != ETL_NULLPTR)
1260 {
1261 if (parent.etl_left == leaf)
1262 {
1263 etl::link_rotate_right(parent, *leaf);
1264 }
1265 else
1266 {
1267 etl::link_rotate_left(parent, *leaf);
1268 }
1269 }
1270 }
1271
1272 //***********************************
1273 // Pointer, Reference
1275 template <typename TLink>
1277 link_rotate(TLink* parent, TLink& leaf)
1278 {
1279 if (parent != ETL_NULLPTR)
1280 {
1281 if (parent->etl_left == &leaf)
1282 {
1283 etl::link_rotate_right(*parent, leaf);
1284 }
1285 else
1286 {
1287 etl::link_rotate_left(*parent, leaf);
1288 }
1289 }
1290 }
1291
1292 // Reference
1293 template <typename TLink>
1295 link_clear(TLink& node)
1296 {
1297 node.clear();
1298 }
1299
1300 // Pointer
1301 template <typename TLink>
1303 link_clear(TLink* node)
1304 {
1305 node->clear();
1306 }
1307
1308 // Reference
1309 template <typename TLink>
1311 is_linked(TLink& node)
1312 {
1313 return node.is_linked();
1314 }
1315
1316 // Pointer
1317 template <typename TLink>
1319 is_linked(TLink* node)
1320 {
1321 return node->is_linked();
1322 }
1323}
1324
1325#endif
not unlinked exception.
Definition: intrusive_links.h:74
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
Definition: exception.h:47
enable_if
Definition: type_traits_generator.h:1191
is_same
Definition: type_traits_generator.h:1041
bitset_ext
Definition: absolute.h:38
etl::enable_if< etl::is_same< TLink, etl::tree_link< TLink::ID > >::value, void >::type link_rotate(TLink &parent, TLink &leaf)
Automatically detects whether a left or right rotate is expected.
Definition: intrusive_links.h:1220
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition: array.h:621