parent_list.hpp (24717B)
1 #ifndef GUARD_OVER_HERE_TRANSFLUVIAL_ANTHRACITISM_MYTHOPOETICIZES_9087 2 #define GUARD_OVER_HERE_TRANSFLUVIAL_ANTHRACITISM_MYTHOPOETICIZES_9087 3 #pragma once 4 5 #include "libshit/container/intrusive.hpp" /* IWYU pragma: keep */ // exceptions 6 7 #include "libshit/assert.hpp" 8 #include "libshit/check.hpp" 9 #include "libshit/meta.hpp" 10 #include "libshit/lua/type_traits.hpp" 11 #include "libshit/lua/dynamic_object.hpp" 12 13 #include <cstddef> 14 #include <functional> 15 #include <iterator> 16 #include <stdexcept> 17 #include <type_traits> 18 #include <utility> 19 20 #include <boost/intrusive/circular_list_algorithms.hpp> 21 #include <boost/intrusive/pointer_traits.hpp> 22 23 namespace Libshit 24 { 25 26 struct ParentListNode 27 { 28 ParentListNode* prev; 29 ParentListNode* next; 30 ParentListNode* parent = nullptr; 31 }; 32 33 struct ParentListNodeTraits 34 { 35 using node = ParentListNode; 36 using node_ptr = node*; 37 using const_node_ptr = const node*; 38 39 static node_ptr get_previous(const_node_ptr n) noexcept { return n->prev; } 40 static void set_previous(node_ptr n, node_ptr v) noexcept { n->prev = v; } 41 static node_ptr get_next(const_node_ptr n) noexcept { return n->next; } 42 static void set_next(node_ptr n, node_ptr v) noexcept { n->next = v; } 43 static node_ptr get_parent(const_node_ptr n) noexcept { return n->parent; } 44 static void set_parent(node_ptr n, node_ptr v) noexcept { n->parent = v; } 45 }; 46 47 class ParentListHook : private ParentListNode 48 { 49 public: 50 ParentListHook() = default; 51 ParentListHook(const ParentListHook&) = delete; 52 void operator=(const ParentListHook&) = delete; 53 54 ~ParentListHook() noexcept 55 { 56 LIBSHIT_ASSERT_MSG(!is_linked(), "destroying linked node"); 57 } 58 59 bool is_root() const noexcept { return parent == this; } 60 bool is_linked() const noexcept { return parent; } 61 62 void unlink() noexcept 63 { 64 LIBSHIT_ASSERT(is_linked()); 65 LIBSHIT_ASSERT(!is_root()); 66 next->prev = prev; 67 prev->next = next; 68 parent = nullptr; 69 } 70 71 template <typename T, typename Tag> friend struct ParentListBaseHookTraits; 72 }; 73 74 template <typename Tag = struct DefaultTag> 75 struct ParentListBaseHook : ParentListHook {}; 76 77 template <typename T, typename Tag = DefaultTag> 78 struct ParentListBaseHookTraits 79 { 80 using Hook = ParentListBaseHook<Tag>; 81 static_assert(std::is_base_of_v<Hook, T>, 82 "T must inherit from ParentListBaseHook<Tag>"); 83 84 using node_traits = ParentListNodeTraits; 85 using value_type = T; 86 using node_ptr = node_traits::node_ptr; 87 using const_node_ptr = node_traits::const_node_ptr; 88 using pointer = T*; 89 using const_pointer = const T*; 90 91 static node_ptr to_node_ptr(value_type& v) noexcept 92 { return static_cast<Hook*>(&v); } 93 static const_node_ptr to_node_ptr(const value_type& v) noexcept 94 { return static_cast<const Hook*>(&v); } 95 static pointer to_value_ptr(node_ptr n) noexcept 96 { return static_cast<pointer>(static_cast<Hook*>(n)); } 97 static const_pointer to_value_ptr(const_node_ptr n) noexcept 98 { return static_cast<const_pointer>(static_cast<const Hook*>(n)); } 99 }; 100 101 template <typename Traits, bool IsConst> 102 class ParentListIterator 103 : public std::iterator<std::bidirectional_iterator_tag, 104 typename Traits::value_type> 105 { 106 using NodePtr = typename Traits::node_ptr; 107 using ConstNodePtr = typename Traits::const_node_ptr; 108 using NodeTraits = typename Traits::node_traits; 109 110 ParentListIterator(ConstNodePtr ptr) noexcept 111 : ptr{const_cast<NodePtr>(ptr)} {} 112 public: 113 using RawT = typename Traits::value_type; 114 using T = std::conditional_t<IsConst, const RawT, RawT>; 115 116 ParentListIterator() = default; 117 ParentListIterator(const ParentListIterator<Traits, false>& o) noexcept 118 : ptr{o.ptr} {} 119 ParentListIterator(T& val) noexcept 120 : ptr{const_cast<NodePtr>(Traits::to_node_ptr(val))} {} 121 122 ParentListIterator& operator=( 123 const ParentListIterator<Traits, false>& o) noexcept 124 { 125 ptr = o.ptr; 126 return *this; 127 } 128 129 T& operator*() const noexcept { return *Traits::to_value_ptr(ptr); } 130 T* operator->() const noexcept { return Traits::to_value_ptr(ptr); } 131 132 bool operator==(const ParentListIterator& o) const noexcept 133 { return ptr == o.ptr; } 134 bool operator!=(const ParentListIterator& o) const noexcept 135 { return ptr != o.ptr; } 136 137 #define LIBSHIT_GEN(op, fun) \ 138 ParentListIterator& operator op() noexcept \ 139 { \ 140 ptr = NodeTraits::fun(ptr); \ 141 return *this; \ 142 } \ 143 ParentListIterator operator op(int) noexcept \ 144 { \ 145 auto ret = *this; \ 146 ptr = NodeTraits::fun(ptr); \ 147 return ret; \ 148 } 149 LIBSHIT_GEN(++, get_next) LIBSHIT_GEN(--, get_previous) 150 #undef LIBSHIT_GEN 151 152 // with Throw checker only!! 153 bool is_end() const noexcept 154 { return !ptr || NodeTraits::get_parent(ptr) == ptr; } 155 156 private: 157 NodePtr ptr = nullptr; 158 159 template <typename, bool> friend class ParentListIterator; 160 template <typename, typename, typename> friend class ParentList; 161 }; 162 163 struct NullTraits {}; 164 165 template <typename T, typename LifetimeTraits = NullTraits, 166 typename Traits = ParentListBaseHookTraits<T>> 167 class ParentList : 168 public Libshit::Lua::SmartObject, private Traits::node_traits::node 169 { 170 LIBSHIT_LUA_CLASS; 171 public: 172 using value_traits = Traits; 173 using pointer = typename value_traits::pointer; 174 using const_pointer = typename value_traits::const_pointer; 175 using value_type = typename boost::intrusive::pointer_traits<pointer>::element_type; 176 using reference = typename boost::intrusive::pointer_traits<pointer>::reference; 177 using const_reference = typename boost::intrusive::pointer_traits<const_pointer>::reference; 178 using difference_type = typename boost::intrusive::pointer_traits<pointer>::difference_type; 179 using size_type = std::size_t; 180 using iterator = ParentListIterator<Traits, false>; 181 using const_iterator = ParentListIterator<Traits, true>; 182 using reverse_iterator = std::reverse_iterator<iterator>; 183 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 184 using node_traits = typename Traits::node_traits; 185 using node = typename node_traits::node; 186 using node_ptr = typename node_traits::node_ptr; 187 using const_node_ptr = typename node_traits::const_node_ptr; 188 private: 189 using ListAlgo = boost::intrusive::circular_list_algorithms<node_traits>; 190 public: 191 192 // O(1) 193 ParentList() noexcept { Init(); } 194 template <typename Iterator> 195 LIBSHIT_NOLUA ParentList(Iterator b, Iterator e) 196 { 197 Init(); 198 insert(end(), b, e); 199 } 200 201 // warning! O(n.size()) 202 LIBSHIT_NOLUA ParentList(ParentList&& o) noexcept 203 { 204 for (auto n = node_traits::get_next(o.GetRoot()); n != o.GetRoot(); 205 n = node_traits::get_next(n)) 206 node_traits::set_parent(n, GetRoot()); 207 Init(); 208 ListAlgo::swap_nodes(GetRoot(), o.GetRoot()); 209 } 210 211 ParentList& operator=(ParentList&& o) noexcept 212 { 213 clear(); 214 swap(o); 215 return *this; 216 } 217 218 // O(size()) 219 ~ParentList() noexcept { clear(); } 220 221 // warning! O(n) 222 void swap(ParentList& o) noexcept 223 { 224 ListAlgo::swap_nodes(GetRoot(), o.GetRoot()); 225 226 for (auto it = node_traits::get_next(GetRoot()); it != GetRoot(); 227 it = node_traits::get_next(it)) 228 node_traits::set_parent(it, GetRoot()); 229 230 for (auto it = node_traits::get_next(o.GetRoot()); it != o.GetRoot(); 231 it = node_traits::get_next(it)) 232 node_traits::set_parent(it, o.GetRoot()); 233 } 234 235 // push*, pop*, front, back, *begin, *end -> O(1) 236 #define LIBSHIT_GEN(name, link_dir, get_dir) \ 237 template <typename Checker = Libshit::Check::Assert> \ 238 void push_##name(reference ref) noexcept(Checker::IS_NOEXCEPT) \ 239 { \ 240 auto node = Traits::to_node_ptr(ref); \ 241 CheckUnlinked<Checker>(node); \ 242 ListAlgo::link_dir(GetRoot(), node); \ 243 NodeAdded(node); \ 244 } \ 245 template <typename Checker = Libshit::Check::Assert> \ 246 void pop_##name() noexcept(Checker::IS_NOEXCEPT) \ 247 { \ 248 LIBSHIT_CHECK(std::out_of_range, !empty(), \ 249 "ParentList::pop_" #name); \ 250 auto node = node_traits::get_dir(GetRoot()); \ 251 ListAlgo::unlink(node); \ 252 NodeRemoved(node); \ 253 } 254 LIBSHIT_GEN(back, link_before, get_previous) 255 LIBSHIT_GEN(front, link_after, get_next) 256 #undef LIBSHIT_GEN 257 258 #define LIBSHIT_GEN(ret, name, opt_const, fun) \ 259 template <typename Checker = Libshit::Check::Assert> \ 260 ret name() opt_const noexcept(Checker::IS_NOEXCEPT) \ 261 { \ 262 LIBSHIT_CHECK(std::out_of_range, !empty(), "ParentList::" #name); \ 263 return *Traits::to_value_ptr(node_traits::fun(GetRoot())); \ 264 } 265 LIBSHIT_GEN(reference, front, , get_next) 266 LIBSHIT_GEN(LIBSHIT_NOLUA const_reference, front, const, get_next) 267 LIBSHIT_GEN(reference, back, , get_previous) 268 LIBSHIT_GEN(LIBSHIT_NOLUA const_reference, back, const, get_previous) 269 #undef LIBSHIT_GEN 270 271 #define LIBSHIT_GEN(ret, name, opt_const, node) \ 272 LIBSHIT_NOLUA ret name() opt_const noexcept { return ret{node}; } 273 #define LIBSHIT_GEN2(ret, const_ret, name, node) \ 274 LIBSHIT_GEN(ret, name, , node) \ 275 LIBSHIT_GEN(const_ret, name, const, node) \ 276 LIBSHIT_GEN(const_ret, c##name, const, node) 277 #define LIBSHIT_GEN3(name, rname, node) \ 278 LIBSHIT_GEN2(iterator, const_iterator, name, node) \ 279 LIBSHIT_GEN2(reverse_iterator, const_reverse_iterator, rname, node) 280 281 LIBSHIT_GEN3(begin, rend, node_traits::get_next(GetRoot())) 282 LIBSHIT_GEN3(end, rbegin, GetRoot()) 283 #undef LIBSHIT_GEN3 284 #undef LIBSHIT_GEN2 285 #undef LIBSHIT_GEN 286 287 // O(size()) 288 size_type size() const noexcept { return ListAlgo::count(GetRoot())-1; } 289 // O(1) 290 bool empty() const noexcept { return ListAlgo::unique(GetRoot()); } 291 292 // O(n) both 293 void shift_backwards(size_type n = 1) noexcept 294 { ListAlgo::move_forward(GetRoot(), n); } 295 void shift_forward(size_type n = 1) noexcept 296 { ListAlgo::move_backwards(GetRoot(), n); } 297 298 // O(1) 299 template <typename Checker = Libshit::Check::Assert> 300 iterator erase(const_iterator it) noexcept(Checker::IS_NOEXCEPT) 301 { 302 CheckNodePtr<Checker>(it.ptr); 303 auto ret = it; ++ret; 304 ListAlgo::unlink(it.ptr); 305 NodeRemoved(it.ptr); 306 return ret.ptr; 307 } 308 309 // O(distance(b, e)) 310 template <typename Checker = Libshit::Check::Assert> 311 iterator erase(const_iterator b, const_iterator e) 312 noexcept(Checker::IS_NOEXCEPT) 313 { 314 CheckNodePtr<Checker>(b.ptr); 315 CheckNodePtrEnd<Checker>(e.ptr); 316 if constexpr (!Checker::IS_NOP) 317 for (auto it = b; it != e; ++it) 318 LIBSHIT_CHECK(ItemNotInContainer, it.ptr != GetRoot(), 319 "Invalid range"); 320 321 for (auto it = b; it != e; ++it) 322 NodeRemoved(it.ptr); 323 324 ListAlgo::unlink(b.ptr, e.ptr); 325 return e.ptr; 326 } 327 328 // O(size()) 329 void clear() noexcept 330 { 331 for (auto it = begin(); it != end(); ) 332 { 333 auto rem = it++; 334 NodeRemoved(rem.ptr); 335 } 336 ListAlgo::init_header(GetRoot()); 337 } 338 339 // clone_from? 340 341 // O(1) 342 template <typename Checker = Libshit::Check::Assert> 343 iterator insert(const_iterator p, reference ref) 344 noexcept(Checker::IS_NOEXCEPT) 345 { 346 CheckNodePtrEnd<Checker>(p.ptr); 347 348 auto node = Traits::to_node_ptr(ref); 349 CheckUnlinked<Checker>(node); 350 ListAlgo::link_before(p.ptr, node); 351 NodeAdded(node); 352 return node; 353 } 354 355 // O(distance(b, e)) 356 template <typename Checker = Libshit::Check::Assert, typename Iterator> 357 LIBSHIT_NOLUA void insert(const_iterator p, Iterator b, Iterator e) 358 noexcept(Checker::IS_NOEXCEPT) 359 { 360 CheckNodePtrEnd<Checker>(p.ptr); 361 if constexpr (!Checker::IS_NOP) 362 for (auto it = b; it != e; ++it) 363 CheckUnlinked<Checker>(Traits::to_node_ptr(*it)); 364 365 for (auto it = b; it != e; ++it) 366 { 367 auto node = Traits::to_node_ptr(*it); 368 ListAlgo::link_before(p.ptr, node); 369 NodeAdded(node); 370 } 371 } 372 373 // O(distance(b, e)) 374 template <typename Checker = Libshit::Check::Assert, typename Iterator> 375 LIBSHIT_NOLUA void assign(Iterator b, Iterator e) 376 noexcept(Checker::IS_NOEXCEPT) 377 { 378 auto old_last = --end(); 379 insert<Checker>(end(), b, e); // may throw 380 erase<std::conditional_t< 381 std::is_same_v<Checker, Libshit::Check::No>, 382 Libshit::Check::No, Libshit::Check::Assert>>( 383 begin(), ++old_last); 384 } 385 386 // O(x.size()) 387 template <typename Checker = Libshit::Check::Assert> 388 void splice(const_iterator p, ParentList& x) noexcept(Checker::IS_NOEXCEPT) 389 { 390 CheckNodePtrEnd<Checker>(p.ptr); 391 392 for (auto it = x.begin(); it != x.end(); ++it) 393 node_traits::set_parent(it.ptr, GetRoot()); 394 ListAlgo::transfer(p.ptr, x.begin().ptr, x.end().ptr); 395 } 396 // O(1) 397 template <typename Checker = Libshit::Check::Assert> 398 void splice(const_iterator p, ParentList& x, const_iterator new_ele) 399 noexcept(Checker::IS_NOEXCEPT) 400 { 401 CheckNodePtrEnd<Checker>(p.ptr); 402 x.CheckNodePtr<Checker>(new_ele.ptr); 403 404 node_traits::set_parent(new_ele.ptr, GetRoot()); 405 ListAlgo::transfer(p.ptr, new_ele.ptr); 406 } 407 // O(distance(b, e)) 408 template <typename Checker = Libshit::Check::Assert> 409 void splice(const_iterator p, ParentList& x, const_iterator b, 410 const_iterator e) noexcept(Checker::IS_NOEXCEPT) 411 { 412 CheckNodePtrEnd<Checker>(p.ptr); 413 x.CheckNodePtr<Checker>(b.ptr); 414 x.CheckNodePtrEnd<Checker>(e.ptr); 415 416 for (auto it = b; it != e; ++it) 417 node_traits::set_parent(it.ptr, GetRoot()); 418 ListAlgo::transfer(p.ptr, b.ptr, e.ptr); 419 } 420 421 // O(n log n), n=size(); exception->basic guarantee 422 LIBSHIT_LUAGEN(hidden: !cls.template_alias.comparable) 423 void sort() { sort(std::less<value_type>{}); } 424 template <typename Predicate> 425 LIBSHIT_LUAGEN(template_params: %w(::Libshit::Lua::FunctionWrapGen<bool>)) 426 void sort(Predicate cmp) 427 { 428 // based on 429 // http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html 430 for (size_type k = 1; ; k *= 2) 431 { 432 // break cycle 433 node_traits::set_next(node_traits::get_previous(GetRoot()), nullptr); 434 auto p = node_traits::get_next(GetRoot()); 435 ListAlgo::init_header(GetRoot()); // GetRoot(): L in paper 436 size_type merges = 0; 437 438 while (p) 439 { 440 ++merges; 441 auto q = p; 442 443 size_type psize; 444 for (psize = 0; q && psize < k; ++psize) 445 q = node_traits::get_next(q); 446 447 size_type qsize = k; 448 try 449 { 450 while (psize > 0 || (qsize > 0 && q)) 451 { 452 node_ptr e; 453 if (psize == 0 || (qsize > 0 && q && cmp( 454 *Traits::to_value_ptr(q), *Traits::to_value_ptr(p)))) 455 { 456 e = q; 457 q = node_traits::get_next(q); 458 --qsize; 459 } 460 else 461 { 462 e = p; 463 p = node_traits::get_next(p); 464 --psize; 465 } 466 ListAlgo::link_before(GetRoot(), e); 467 } 468 } 469 catch (...) 470 { 471 // uh-oh. Basic guarantee, make sure no node is lost... 472 for (; psize > 0; --psize) 473 { 474 auto e = p; 475 p = node_traits::get_next(p); 476 ListAlgo::link_before(GetRoot(), e); 477 } 478 for (; q; ) 479 { 480 auto e = q; 481 q = node_traits::get_next(q); 482 ListAlgo::link_before(GetRoot(), e); 483 } 484 throw; 485 } 486 p = q; 487 } 488 489 if (merges <= 1) return; 490 } 491 } 492 493 // O(size() + o.size()); exception->basic guarantee 494 template <typename Checker = Libshit::Check::Assert> 495 LIBSHIT_LUAGEN(hidden: !cls.template_alias.comparable) 496 void merge(ParentList& o) { merge<Checker>(o, std::less<value_type>{}); } 497 template <typename Checker = Libshit::Check::Assert, typename Predicate> 498 LIBSHIT_LUAGEN(template_params: %w( 499 ::Libshit::Check::Throw ::Libshit::Lua::FunctionWrapGen<bool>)) 500 void merge(ParentList& o, Predicate cmp) 501 { 502 LIBSHIT_CHECK(ContainerConsistency, &o != this, 503 "Trying to merge ParentList with itself"); 504 auto tit = begin(), oit = o.begin(); 505 auto tend = end(), oend = o.end(); 506 while (oit != oend) 507 { 508 if (tit == tend || cmp(*oit, *tit)) splice(tit, o, oit++); 509 else ++tit; 510 } 511 LIBSHIT_ASSERT(o.empty()); 512 } 513 514 // O(size()) 515 void reverse() noexcept { ListAlgo::reverse(GetRoot()); } 516 517 // O(size()); exception->basic guarantee 518 LIBSHIT_LUAGEN(hidden: !cls.template_alias.comparable) 519 void remove(const_reference val) 520 { remove_if([&val](auto& x) { return x == val; }); } 521 template <typename Predicate> 522 LIBSHIT_LUAGEN(template_params: %w(::Libshit::Lua::FunctionWrapGen<bool>)) 523 void remove_if(Predicate p) 524 { 525 for (auto it = begin(); it != end();) 526 if (p(*it)) it = erase(it); 527 else ++it; 528 } 529 530 // O(size()); exception->basic guarantee 531 LIBSHIT_LUAGEN(hidden: !cls.template_alias.comparable) 532 void unique() { unique(std::equal_to<value_type>{}); } 533 template <typename Predicate> 534 LIBSHIT_LUAGEN(template_params: %w(::Libshit::Lua::FunctionWrapGen<bool>)) 535 void unique(Predicate p) 536 { 537 auto it = begin(); 538 auto next = it; ++next; 539 LIBSHIT_ASSERT((next == end()) == (size() <= 1)); 540 541 while (next != end()) 542 if (p(*it, *next)) next = erase(next); 543 else it = next++; 544 } 545 546 // O(1) 547 template <typename Checker = Libshit::Check::Assert> 548 LIBSHIT_NOLUA iterator iterator_to(reference ref) 549 noexcept(Checker::IS_NOEXCEPT) 550 { 551 node_ptr node = Traits::to_node_ptr(ref); 552 CheckLinkedThis<Checker>(node); 553 return node; 554 } 555 556 template <typename Checker = Libshit::Check::Assert> 557 LIBSHIT_NOLUA const_iterator iterator_to(const_reference ref) const 558 noexcept(Checker::IS_NOEXCEPT) 559 { 560 const_node_ptr node = Traits::to_node_ptr(ref); 561 CheckLinkedThis<Checker>(node); 562 return node; 563 } 564 565 // static funs 566 template <typename Checker = Libshit::Check::Assert> 567 LIBSHIT_NOLUA static ParentList& container_from_iterator(iterator it) 568 noexcept(Checker::IS_NOEXCEPT) 569 { 570 CheckLinkedAny<Checker>(it.ptr); 571 return *static_cast<ParentList*>(node_traits::get_parent(it.ptr)); 572 } 573 574 template <typename Checker = Libshit::Check::Assert> 575 LIBSHIT_NOLUA static const ParentList& container_from_iterator( 576 const_iterator it) noexcept(Checker::IS_NOEXCEPT) 577 { 578 CheckLinkedAny<Checker>(it.ptr); 579 return *static_cast<const ParentList*>(node_traits::get_parent(it.ptr)); 580 } 581 582 583 template <typename Checker = Libshit::Check::Assert> 584 LIBSHIT_NOLUA static iterator s_iterator_to(reference ref) 585 noexcept(Checker::IS_NOEXCEPT) 586 { 587 node_ptr node = Traits::to_node_ptr(ref); 588 CheckLinkedAny<Checker>(node); 589 return node; 590 } 591 592 template <typename Checker = Libshit::Check::Assert> 593 LIBSHIT_NOLUA static const_iterator s_iterator_to(const_reference ref) 594 noexcept(Checker::IS_NOEXCEPT) 595 { 596 const_node_ptr node = Traits::to_node_ptr(ref); 597 CheckLinkedAny<Checker>(node); 598 return node; 599 } 600 601 template <typename Checker = Libshit::Check::Assert> 602 LIBSHIT_NOLUA static ParentList& get_parent(reference ref) 603 noexcept(Checker::IS_NOEXCEPT) 604 { 605 node_ptr node = Traits::to_node_ptr(ref); 606 CheckLinkedAny<Checker>(node); 607 return *static_cast<ParentList*>(node_traits::get_parent(node)); 608 } 609 610 template <typename Checker = Libshit::Check::Assert> 611 LIBSHIT_NOLUA static const ParentList& get_parent(const_reference ref) 612 noexcept(Checker::IS_NOEXCEPT) 613 { 614 const_node_ptr node = Traits::to_node_ptr(ref); 615 CheckLinkedAny<Checker>(node); 616 return *static_cast<const ParentList*>(node_traits::get_parent(node)); 617 } 618 619 LIBSHIT_NOLUA static ParentList* opt_get_parent(reference ref) noexcept 620 { 621 return static_cast<ParentList*>(node_traits::get_parent( 622 Traits::to_node_ptr(ref))); 623 } 624 LIBSHIT_NOLUA static const ParentList* opt_get_parent( 625 const_reference ref) noexcept 626 { 627 return static_cast<ParentList*>(node_traits::get_parent( 628 Traits::to_node_ptr(ref))); 629 } 630 private: 631 void Init() noexcept 632 { 633 ListAlgo::init_header(GetRoot()); 634 node_traits::set_parent(GetRoot(), GetRoot()); 635 } 636 637 template <typename U, typename = void> struct HasAdd : std::false_type {}; 638 template <typename U> struct HasAdd<U, std::void_t<decltype(U::add)>> 639 : std::true_type {}; 640 641 template <typename U, typename = void> struct HasRemove : std::false_type {}; 642 template <typename U> struct HasRemove<U, std::void_t<decltype(U::remove)>> 643 : std::true_type {}; 644 645 void NodeAdded(node_ptr nd) noexcept 646 { 647 node_traits::set_parent(nd, GetRoot()); 648 if constexpr (HasAdd<LifetimeTraits>::value) 649 { 650 static_assert( 651 noexcept(LifetimeTraits::add(*this, std::declval<reference>())), 652 "LifetimeTraits::add must be noexcept"); 653 LifetimeTraits::add(*this, *Traits::to_value_ptr(nd)); 654 } 655 } 656 657 void NodeRemoved(node_ptr nd) noexcept 658 { 659 node_traits::set_parent(nd, nullptr); 660 if constexpr (HasRemove<LifetimeTraits>::value) 661 { 662 static_assert( 663 noexcept(LifetimeTraits::remove(*this, std::declval<reference>())), 664 "LifetimeTraits::remove must be noexcept"); 665 LifetimeTraits::remove(*this, *Traits::to_value_ptr(nd)); 666 } 667 } 668 669 template <typename Checker> 670 void CheckNodePtr(node_ptr& ptr) noexcept(Checker::IS_NOEXCEPT) 671 { 672 CheckNodePtrEnd<Checker>(ptr); 673 LIBSHIT_CHECK( 674 ItemNotInContainer, ptr != GetRoot(), "Item is the root item"); 675 } 676 677 template <typename Checker> 678 void CheckNodePtrEnd(node_ptr& ptr) noexcept(Checker::IS_NOEXCEPT) 679 { 680 if constexpr (std::is_same_v<Checker, Check::Throw>) 681 if (!ptr) ptr = GetRoot(); 682 LIBSHIT_CHECK( 683 ItemNotInContainer, node_traits::get_parent(ptr) == GetRoot(), 684 "Item not in this list"); 685 } 686 687 template <typename Checker> 688 static void CheckUnlinked(const_node_ptr ptr) noexcept(Checker::IS_NOEXCEPT) 689 { 690 LIBSHIT_CHECK(InvalidItem, ptr, "nullptr item"); 691 LIBSHIT_CHECK( 692 ItemAlreadyAdded, node_traits::get_parent(ptr) == nullptr, 693 "Item already linked"); 694 } 695 696 template <typename Checker> 697 static void CheckLinkedAny(const_node_ptr ptr) noexcept(Checker::IS_NOEXCEPT) 698 { 699 LIBSHIT_CHECK(InvalidItem, ptr, "nullptr item"); 700 LIBSHIT_CHECK( 701 ItemNotInContainer, node_traits::get_parent(ptr), 702 "Item not in any container"); 703 } 704 705 template <typename Checker> 706 void CheckLinkedThis(const_node_ptr ptr) const noexcept(Checker::IS_NOEXCEPT) 707 { 708 LIBSHIT_CHECK(InvalidItem, ptr, "nullptr item"); 709 LIBSHIT_CHECK( 710 ItemNotInContainer, node_traits::get_parent(ptr) == GetRoot(), 711 "Item not in this container"); 712 } 713 714 node_ptr GetRoot() noexcept { return this; } 715 const_node_ptr GetRoot() const noexcept { return this; } 716 }; 717 718 template <typename T, typename A, typename B> 719 inline void swap(ParentList<T,A,B>& a, ParentList<T,A,B>& b) noexcept 720 { a.swap(b); } 721 722 } 723 724 #endif