31#ifndef ETL_INTRUSIVE_LINKS_INCLUDED
32#define ETL_INTRUSIVE_LINKS_INCLUDED
96 : etl_next(ETL_NULLPTR)
108 : etl_next(
other.etl_next)
115 etl_next =
other.etl_next;
123 etl_next = ETL_NULLPTR;
128 bool is_linked()
const
130 return etl_next != ETL_NULLPTR;
135 bool has_next()
const
137 return etl_next != ETL_NULLPTR;
163 template <
typename TLink>
171 template <
typename TLink>
179 template <
typename TLink>
188 template <
typename TLink>
190 link(TLink* lhs, TLink* rhs)
192 if (lhs != ETL_NULLPTR)
200 template <
typename TLink>
202 link(TLink& lhs, TLink* rhs)
209 template <
typename TLink>
211 link(TLink* lhs, TLink& rhs)
213 if (lhs != ETL_NULLPTR)
215 lhs->etl_next = &rhs;
223 template <
typename TLink>
225 link_splice(TLink& lhs, TLink& rhs)
227 rhs.etl_next = lhs.etl_next;
233 template <
typename TLink>
235 link_splice(TLink* lhs, TLink* rhs)
237 if (lhs != ETL_NULLPTR)
239 if (rhs != ETL_NULLPTR)
241 rhs->etl_next = lhs->etl_next;
250 template <
typename TLink>
252 link_splice(TLink& lhs, TLink* rhs)
254 if (rhs != ETL_NULLPTR)
256 rhs->etl_next = lhs.etl_next;
264 template <
typename TLink>
266 link_splice(TLink* lhs, TLink& rhs)
268 if (lhs != ETL_NULLPTR)
270 rhs.etl_next = lhs->etl_next;
271 lhs->etl_next = &rhs;
277 template <
typename TLink>
279 link_splice(TLink& lhs, TLink& first, TLink& last)
281 last.etl_next = lhs.etl_next;
282 lhs.etl_next = &first;
287 template <
typename TLink>
289 link_splice(TLink* lhs, TLink& first, TLink& last)
291 if (lhs != ETL_NULLPTR)
293 last.etl_next = lhs->etl_next;
294 lhs->etl_next = &first;
298 last.etl_next = ETL_NULLPTR;
306 template <
typename TLink>
308 unlink_after(TLink& node)
310 if (node.etl_next != ETL_NULLPTR)
312 TLink* unlinked_node = node.etl_next;
313 node.etl_next = unlinked_node->etl_next;
314 unlinked_node->clear();
315 return unlinked_node;
318 return node.etl_next;
323 template <
typename TLink>
325 unlink_after(TLink& before, TLink& last)
327 TLink* first = before.etl_next;
329 if (&before != &last)
331 before.etl_next = last.etl_next;
339 template <
typename TLink>
341 is_linked(TLink& node)
343 return node.is_linked();
347 template <
typename TLink>
349 is_linked(TLink* node)
351 return node->is_linked();
358 template <
typename TLink>
360 link_clear(TLink& start)
362 start.etl_next = ETL_NULLPTR;
367 template <
typename TLink>
369 link_clear(TLink* start)
371 if (start != ETL_NULLPTR)
373 etl::link_clear(*start);
381 template <
typename TLink>
383 link_clear_range(TLink& start)
385 TLink* current = &start;
387 while (current != ETL_NULLPTR)
389 TLink* next = current->etl_next;
397 template <
typename TLink>
399 link_clear_range(TLink* start)
401 if (start != ETL_NULLPTR)
403 etl::link_clear_range(*start);
410 template <
size_t ID_>
420 : etl_previous(ETL_NULLPTR)
421 , etl_next(ETL_NULLPTR)
434 : etl_previous(
other.etl_previous)
435 , etl_next(
other.etl_next)
442 etl_previous =
other.etl_previous;
443 etl_next =
other.etl_next;
451 etl_previous = ETL_NULLPTR;
452 etl_next = ETL_NULLPTR;
457 bool is_linked()
const
459 return (etl_previous != ETL_NULLPTR) || (etl_next != ETL_NULLPTR);
464 bool has_next()
const
466 return etl_next != ETL_NULLPTR;
471 bool has_previous()
const
473 return etl_previous != ETL_NULLPTR;
517 using ETL_OR_STD::swap;
518 swap(etl_previous, etl_next);
525 if (etl_previous != ETL_NULLPTR)
527 etl_previous->etl_next = etl_next;
531 if (etl_next != ETL_NULLPTR)
533 etl_next->etl_previous = etl_previous;
544 template <
typename TLink>
552 template <
typename TLink>
560 template <
typename TLink>
570 template <
typename TLink>
572 link(TLink* lhs, TLink* rhs)
574 if (lhs != ETL_NULLPTR)
579 if (rhs != ETL_NULLPTR)
581 rhs->etl_previous = lhs;
587 template <
typename TLink>
589 link(TLink& lhs, TLink* rhs)
593 if (rhs != ETL_NULLPTR)
595 rhs->etl_previous = &lhs;
601 template <
typename TLink>
603 link(TLink* lhs, TLink& rhs)
605 if (lhs != ETL_NULLPTR)
607 lhs->etl_next = &rhs;
610 rhs.etl_previous = lhs;
615 template <
typename TLink>
617 link_splice(TLink& lhs, TLink& rhs)
619 rhs.etl_next = lhs.etl_next;
620 rhs.etl_previous = &lhs;
622 if (lhs.etl_next != ETL_NULLPTR)
624 lhs.etl_next->etl_previous = &rhs;
634 template <
typename TLink>
636 link_splice(TLink* lhs, TLink* rhs)
638 if (rhs != ETL_NULLPTR)
640 if (lhs != ETL_NULLPTR)
642 rhs->etl_next = lhs->etl_next;
645 rhs->etl_previous = lhs;
648 if (lhs != ETL_NULLPTR)
650 if (lhs->etl_next != ETL_NULLPTR)
652 lhs->etl_next->etl_previous = rhs;
661 template <
typename TLink>
663 link_splice(TLink& lhs, TLink* rhs)
665 if (rhs != ETL_NULLPTR)
667 rhs->etl_next = lhs.etl_next;
668 rhs->etl_previous = &lhs;
671 if (lhs.etl_next != ETL_NULLPTR)
673 lhs.etl_next->etl_previous = rhs;
681 template <
typename TLink>
683 link_splice(TLink* lhs, TLink& rhs)
685 if (lhs != ETL_NULLPTR)
687 rhs.etl_next = lhs->etl_next;
690 rhs.etl_previous = lhs;
692 if (lhs != ETL_NULLPTR)
694 if (lhs->etl_next != ETL_NULLPTR)
696 lhs->etl_next->etl_previous = &rhs;
699 lhs->etl_next = &rhs;
705 template <
typename TLink>
707 link_splice(TLink& lhs, TLink& first, TLink& last)
709 last.etl_next = lhs.etl_next;
710 first.etl_previous = &lhs;
712 if (last.etl_next != ETL_NULLPTR)
714 last.etl_next->etl_previous = &last;
717 lhs.etl_next = &first;
722 template <
typename TLink>
724 link_splice(TLink* lhs, TLink& first, TLink& last)
726 if (lhs != ETL_NULLPTR)
728 last.etl_next = lhs->etl_next;
732 last.etl_next = ETL_NULLPTR;
735 first.etl_previous = lhs;
737 if (last.etl_next != ETL_NULLPTR)
739 last.etl_next->etl_previous = &last;
742 if (lhs != ETL_NULLPTR)
744 lhs->etl_next = &first;
752 template <
typename TLink>
761 template <
typename TLink>
763 unlink(TLink& first, TLink& last)
771 if (last.etl_next != ETL_NULLPTR)
773 last.etl_next->etl_previous = first.etl_previous;
776 if (first.etl_previous != ETL_NULLPTR)
778 first.etl_previous->etl_next = last.etl_next;
782 first.etl_previous = ETL_NULLPTR;
783 last.etl_next = ETL_NULLPTR;
790 template <
typename TLink>
792 is_linked(TLink& node)
794 return node.is_linked();
798 template <
typename TLink>
800 is_linked(TLink* node)
802 return node->is_linked();
809 template <
typename TLink>
811 link_clear_range(TLink& start)
813 TLink* current = &start;
815 while (current != ETL_NULLPTR)
817 TLink* next = current->etl_next;
825 template <
typename TLink>
827 link_clear_range(TLink* start)
829 etl::link_clear_range(*start);
835 template <
size_t ID_>
845 : etl_parent(ETL_NULLPTR)
846 , etl_left(ETL_NULLPTR)
847 , etl_right(ETL_NULLPTR)
853 : etl_parent(p_parent)
861 : etl_parent(
other.etl_parent)
862 , etl_left(
other.etl_left)
863 , etl_right(
other.etl_right)
870 etl_parent =
other.etl_parent;
871 etl_left =
other.etl_left;
872 etl_right =
other.etl_right;
880 etl_parent = ETL_NULLPTR;
881 etl_left = ETL_NULLPTR;
882 etl_right = ETL_NULLPTR;
886 bool is_linked()
const
888 return (etl_parent != ETL_NULLPTR) || (etl_left != ETL_NULLPTR) || (etl_right != ETL_NULLPTR);
893 bool has_parent()
const
895 return etl_parent != ETL_NULLPTR;
900 bool has_left()
const
902 return etl_left != ETL_NULLPTR;
907 bool has_right()
const
909 return etl_right != ETL_NULLPTR;
972 using ETL_OR_STD::swap;
973 swap(etl_left, etl_right);
982 template <
typename TLink>
990 template <
typename TLink>
999 template <
typename TLink>
1003 parent.etl_left = &
leaf;
1004 leaf.etl_parent = &parent;
1009 template <
typename TLink>
1011 link_left(TLink* parent, TLink* leaf)
1013 if (parent != ETL_NULLPTR)
1015 parent->etl_left = leaf;
1018 if (leaf != ETL_NULLPTR)
1020 leaf->etl_parent = parent;
1026 template <
typename TLink>
1028 link_left(TLink& parent, TLink* leaf)
1030 parent.etl_left = leaf;
1032 if (leaf != ETL_NULLPTR)
1034 leaf->etl_parent = &parent;
1040 template <
typename TLink>
1042 link_left(TLink* parent, TLink& leaf)
1044 if (parent != ETL_NULLPTR)
1046 parent->etl_left = &leaf;
1049 leaf.etl_parent = parent;
1056 template <
typename TLink>
1058 link_right(TLink& parent, TLink& leaf)
1060 parent.etl_right = &leaf;
1061 leaf.etl_parent = &parent;
1065 template <
typename TLink>
1067 link_right(TLink* parent, TLink* leaf)
1069 if (parent != ETL_NULLPTR)
1071 parent->etl_right = leaf;
1074 if (leaf != ETL_NULLPTR)
1076 leaf->etl_parent = parent;
1081 template <
typename TLink>
1083 link_right(TLink& parent, TLink* leaf)
1085 parent.etl_right = leaf;
1087 if (leaf != ETL_NULLPTR)
1089 leaf->etl_parent = &parent;
1094 template <
typename TLink>
1096 link_right(TLink* parent, TLink& leaf)
1098 if (parent != ETL_NULLPTR)
1100 parent->etl_right = &leaf;
1103 leaf.etl_parent = parent;
1110 template <
typename TLink>
1112 link_rotate_left(TLink& parent, TLink& leaf)
1114 parent.etl_right = leaf.etl_left;
1116 if (parent.etl_right != ETL_NULLPTR)
1118 parent.etl_right->etl_parent = &parent;
1121 leaf.etl_parent = parent.etl_parent;
1122 parent.etl_parent = &leaf;
1123 leaf.etl_left = &parent;
1128 template <
typename TLink>
1130 link_rotate_left(TLink* parent, TLink* leaf)
1132 if ((parent != ETL_NULLPTR) && (leaf != ETL_NULLPTR))
1134 link_rotate_left(*parent, *leaf);
1140 template <
typename TLink>
1142 link_rotate_left(TLink& parent, TLink* leaf)
1144 if (leaf != ETL_NULLPTR)
1146 link_rotate_left(parent, *leaf);
1152 template <
typename TLink>
1154 link_rotate_left(TLink* parent, TLink& leaf)
1156 if (parent != ETL_NULLPTR)
1158 link_rotate_left(*parent, leaf);
1165 template <
typename TLink>
1167 link_rotate_right(TLink& parent, TLink& leaf)
1169 parent.etl_left = leaf.etl_right;
1171 if (parent.etl_left != ETL_NULLPTR)
1173 parent.etl_left->etl_parent = &parent;
1176 leaf.etl_parent = parent.etl_parent;
1177 parent.etl_parent = &leaf;
1178 leaf.etl_right = &parent;
1182 template <
typename TLink>
1184 link_rotate_right(TLink* parent, TLink* leaf)
1186 if ((parent != ETL_NULLPTR) && (leaf != ETL_NULLPTR))
1188 link_rotate_right(*parent, *leaf);
1192 template <
typename TLink>
1194 link_rotate_right(TLink& parent, TLink* leaf)
1196 if (leaf != ETL_NULLPTR)
1198 link_rotate_right(parent, *leaf);
1203 template <
typename TLink>
1205 link_rotate_right(TLink* parent, TLink& leaf)
1207 if (parent != ETL_NULLPTR)
1209 link_rotate_right(*parent, leaf);
1218 template <
typename TLink>
1222 if (parent.etl_left == &
leaf)
1224 etl::link_rotate_right(parent,
leaf);
1228 etl::link_rotate_left(parent,
leaf);
1235 template <
typename TLink>
1239 if ((parent != ETL_NULLPTR) && (
leaf != ETL_NULLPTR))
1241 if (parent->etl_left ==
leaf)
1243 etl::link_rotate_right(*parent, *
leaf);
1247 etl::link_rotate_left(*parent, *
leaf);
1255 template <
typename TLink>
1259 if (
leaf != ETL_NULLPTR)
1261 if (parent.etl_left ==
leaf)
1263 etl::link_rotate_right(parent, *
leaf);
1267 etl::link_rotate_left(parent, *
leaf);
1275 template <
typename TLink>
1279 if (parent != ETL_NULLPTR)
1281 if (parent->etl_left == &
leaf)
1283 etl::link_rotate_right(*parent,
leaf);
1287 etl::link_rotate_left(*parent,
leaf);
1293 template <
typename TLink>
1295 link_clear(TLink& node)
1301 template <
typename TLink>
1303 link_clear(TLink* node)
1309 template <
typename TLink>
1311 is_linked(TLink& node)
1313 return node.is_linked();
1317 template <
typename TLink>
1319 is_linked(TLink* node)
1321 return node->is_linked();
Link exception.
Definition intrusive_links.h:61
not unlinked exception.
Definition intrusive_links.h:74
Definition exception.h:47
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:630
A bidirectional link.
Definition intrusive_links.h:412
A forward link.
Definition intrusive_links.h:88
Definition intrusive_links.h:546
Definition intrusive_links.h:165
Definition intrusive_links.h:984
pair holds two objects of arbitrary type
Definition utility.h:164
A binary tree link.
Definition intrusive_links.h:837