Lines Matching +full:merge +full:- +full:base
1 // -*- C++ -*-
2 //===---------------------------- list ------------------------------------===//
9 //===----------------------------------------------------------------------===//
32 typedef implementation-defined iterator;
33 typedef implementation-defined const_iterator;
34 typedef implementation-defined size_type;
35 typedef implementation-defined difference_type;
138 void merge(list& x);
139 void merge(list&& x);
141 void merge(list& x, Compare comp);
143 void merge(list&& x, Compare comp);
286 __get_db()->__insert_ic(this, __c);
309 __get_db()->__insert_i(this);
319 __get_db()->__iterator_copy(this, &__p);
325 __get_db()->__erase_i(this);
333 __get_db()->__iterator_copy(this, &__p);
345 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
346 "Attempted to dereference a non-dereferenceable list::iterator");
348 return __ptr_->__as_node()->__value_;
351 pointer operator->() const
354 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
355 "Attempted to dereference a non-dereferenceable list::iterator");
357 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
364 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
365 "Attempted to increment non-incrementable list::iterator");
367 __ptr_ = __ptr_->__next_;
374 __list_iterator& operator--()
377 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
378 "Attempted to decrement non-decrementable list::iterator");
380 __ptr_ = __ptr_->__prev_;
384 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
409 __get_db()->__insert_ic(this, __c);
429 __get_db()->__insert_i(this);
437 __get_db()->__iterator_copy(this, &__p);
447 __get_db()->__iterator_copy(this, &__p);
453 __get_db()->__erase_i(this);
461 __get_db()->__iterator_copy(this, &__p);
472 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
473 "Attempted to dereference a non-dereferenceable list::const_iterator");
475 return __ptr_->__as_node()->__value_;
478 pointer operator->() const
481 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
482 "Attempted to dereference a non-dereferenceable list::iterator");
484 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
491 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
492 "Attempted to increment non-incrementable list::const_iterator");
494 __ptr_ = __ptr_->__next_;
501 __list_const_iterator& operator--()
504 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
505 "Attempted to decrement non-decrementable list::const_iterator");
507 __ptr_ = __ptr_->__prev_;
511 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
676 __get_db()->__invalidate_all(this);
688 __f->__prev_->__next_ = __l->__next_;
689 __l->__next_->__prev_ = __f->__prev_;
712 __get_db()->__erase_c(this);
725 __unlink_nodes(__f, __l->__prev_);
729 __node_pointer __np = __f->__as_node();
730 __f = __f->__next_;
731 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
749 this->__node_alloc() == __c.__node_alloc(),
759 __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
763 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
767 __c_node* __cn1 = __db->__find_c_and_lock(this);
768 __c_node* __cn2 = __db->__find_c(&__c);
769 std::swap(__cn1->beg_, __cn2->beg_);
770 std::swap(__cn1->end_, __cn2->end_);
771 std::swap(__cn1->cap_, __cn2->cap_);
772 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
774 --__p;
775 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
776 if (__i->__ptr_ == __c.__end_as_link())
778 __cn2->__add(*__p);
779 if (--__cn1->end_ != __p)
780 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
783 (*__p)->__c_ = __cn1;
785 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
787 --__p;
788 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
789 if (__i->__ptr_ == __end_as_link())
791 __cn1->__add(*__p);
792 if (--__cn2->end_ != __p)
793 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
796 (*__p)->__c_ = __cn2;
798 __db->unlock();
806 typedef __list_imp<_Tp, _Alloc> base;
807 typedef typename base::__node __node;
808 typedef typename base::__node_allocator __node_allocator;
809 typedef typename base::__node_pointer __node_pointer;
810 typedef typename base::__node_alloc_traits __node_alloc_traits;
811 typedef typename base::__node_base __node_base;
812 typedef typename base::__node_base_pointer __node_base_pointer;
813 typedef typename base::__link_pointer __link_pointer;
822 typedef typename base::pointer pointer;
823 typedef typename base::const_pointer const_pointer;
824 typedef typename base::size_type size_type;
825 typedef typename base::difference_type difference_type;
826 typedef typename base::iterator iterator;
827 typedef typename base::const_iterator const_iterator;
836 __get_db()->__insert_c(this);
840 explicit list(const allocator_type& __a) : base(__a)
843 __get_db()->__insert_c(this);
899 size_type size() const _NOEXCEPT {return base::__sz();}
901 bool empty() const _NOEXCEPT {return base::empty();}
906 base::__node_alloc_max_size(),
911 iterator begin() _NOEXCEPT {return base::begin();}
913 const_iterator begin() const _NOEXCEPT {return base::begin();}
915 iterator end() _NOEXCEPT {return base::end();}
917 const_iterator end() const _NOEXCEPT {return base::end();}
919 const_iterator cbegin() const _NOEXCEPT {return base::begin();}
921 const_iterator cend() const _NOEXCEPT {return base::end();}
946 return base::__end_.__next_->__as_node()->__value_;
952 return base::__end_.__next_->__as_node()->__value_;
958 return base::__end_.__prev_->__as_node()->__value_;
964 return base::__end_.__prev_->__as_node()->__value_;
1011 {base::swap(__c);}
1013 void clear() _NOEXCEPT {base::clear();}
1049 void merge(list& __c);
1052 void merge(list&& __c) {merge(__c);}
1055 void merge(list& __c, _Comp __comp);
1059 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1102 __p->__prev_->__next_ = __f;
1103 __f->__prev_ = __p->__prev_;
1104 __p->__prev_ = __l;
1105 __l->__next_ = __p;
1114 __f->__prev_ = base::__end_as_link();
1115 __l->__next_ = base::__end_.__next_;
1116 __l->__next_->__prev_ = __l;
1117 base::__end_.__next_ = __f;
1126 __l->__next_ = base::__end_as_link();
1127 __f->__prev_ = base::__end_.__prev_;
1128 __f->__prev_->__next_ = __f;
1129 base::__end_.__prev_ = __l;
1138 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1139 : _VSTD::prev(end(), base::__sz() - __n);
1146 __get_db()->__insert_c(this);
1148 for (; __n > 0; --__n)
1158 list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a)
1161 __get_db()->__insert_c(this);
1163 for (; __n > 0; --__n)
1176 __get_db()->__insert_c(this);
1178 for (; __n > 0; --__n)
1184 : base(__a)
1187 __get_db()->__insert_c(this);
1189 for (; __n > 0; --__n)
1199 __get_db()->__insert_c(this);
1209 : base(__a)
1212 __get_db()->__insert_c(this);
1220 : base(allocator_type(
1225 __get_db()->__insert_c(this);
1233 : base(__a)
1236 __get_db()->__insert_c(this);
1246 : base(__a)
1249 __get_db()->__insert_c(this);
1260 __get_db()->__insert_c(this);
1276 base::__copy_assign_alloc(__c);
1288 : base(allocator_type(_VSTD::move(__c.__node_alloc())))
1291 __get_db()->__insert_c(this);
1299 : base(__a)
1302 __get_db()->__insert_c(this);
1330 if (base::__node_alloc() != __c.__node_alloc())
1345 base::__move_assign_alloc(__c);
1366 __get_db()->__invalidate_all(this);
1376 for (; __n > 0 && __i != __e; --__n, ++__i)
1383 __get_db()->__invalidate_all(this);
1392 return allocator_type(base::__node_alloc());
1400 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1404 __node_allocator& __na = base::__node_alloc();
1407 __hold->__prev_ = 0;
1408 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1409 __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link());
1410 ++base::__sz();
1412 return iterator(__hold.release()->__as_link(), this);
1414 return iterator(__hold.release()->__as_link());
1423 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1433 __node_allocator& __na = base::__node_alloc();
1436 __hold->__prev_ = 0;
1437 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1440 __r = iterator(__hold->__as_link(), this);
1442 __r = iterator(__hold->__as_link());
1450 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1453 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1454 __e.__ptr_->__next_ = __hold->__as_link();
1455 __hold->__prev_ = __e.__ptr_;
1465 __link_pointer __prev = __e.__ptr_->__prev_;
1466 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1479 base::__sz() += __ds;
1491 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1501 __node_allocator& __na = base::__node_alloc();
1504 __hold->__prev_ = 0;
1505 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1508 __r = iterator(__hold.get()->__as_link(), this);
1510 __r = iterator(__hold.get()->__as_link());
1521 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1522 __e.__ptr_->__next_ = __hold.get()->__as_link();
1523 __hold->__prev_ = __e.__ptr_;
1533 __link_pointer __prev = __e.__ptr_->__prev_;
1534 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1547 base::__sz() += __ds;
1556 __node_allocator& __na = base::__node_alloc();
1559 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1560 __link_pointer __nl = __hold->__as_link();
1562 ++base::__sz();
1570 __node_allocator& __na = base::__node_alloc();
1573 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1574 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1575 ++base::__sz();
1585 __node_allocator& __na = base::__node_alloc();
1588 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1589 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1590 ++base::__sz();
1598 __node_allocator& __na = base::__node_alloc();
1601 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1602 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1603 ++base::__sz();
1618 __node_allocator& __na = base::__node_alloc();
1621 …__node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__a…
1622 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1623 ++base::__sz();
1625 return __hold.release()->__value_;
1640 __node_allocator& __na = base::__node_alloc();
1643 …__node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__a…
1644 __link_pointer __nl = __hold->__as_link();
1646 ++base::__sz();
1648 return __hold.release()->__value_;
1660 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1664 __node_allocator& __na = base::__node_alloc();
1667 __hold->__prev_ = 0;
1668 …__node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__a…
1669 __link_pointer __nl = __hold.get()->__as_link();
1671 ++base::__sz();
1687 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1691 __node_allocator& __na = base::__node_alloc();
1694 __hold->__prev_ = 0;
1695 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1696 __link_pointer __nl = __hold->__as_link();
1698 ++base::__sz();
1714 __node_allocator& __na = base::__node_alloc();
1715 __link_pointer __n = base::__end_.__next_;
1716 base::__unlink_nodes(__n, __n);
1717 --base::__sz();
1719 __c_node* __c = __get_db()->__find_c_and_lock(this);
1720 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1722 --__p;
1723 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1724 if (__i->__ptr_ == __n)
1726 (*__p)->__c_ = nullptr;
1727 if (--__c->end_ != __p)
1728 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1731 __get_db()->unlock();
1733 __node_pointer __np = __n->__as_node();
1734 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1743 __node_allocator& __na = base::__node_alloc();
1744 __link_pointer __n = base::__end_.__prev_;
1745 base::__unlink_nodes(__n, __n);
1746 --base::__sz();
1748 __c_node* __c = __get_db()->__find_c_and_lock(this);
1749 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1751 --__p;
1752 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1753 if (__i->__ptr_ == __n)
1755 (*__p)->__c_ = nullptr;
1756 if (--__c->end_ != __p)
1757 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1760 __get_db()->unlock();
1762 __node_pointer __np = __n->__as_node();
1763 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1772 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1777 "list::erase(iterator) called with a non-dereferenceable iterator");
1778 __node_allocator& __na = base::__node_alloc();
1780 __link_pointer __r = __n->__next_;
1781 base::__unlink_nodes(__n, __n);
1782 --base::__sz();
1784 __c_node* __c = __get_db()->__find_c_and_lock(this);
1785 for (__i_node** __ip = __c->end_; __ip != __c->beg_; )
1787 --__ip;
1788 iterator* __i = static_cast<iterator*>((*__ip)->__i_);
1789 if (__i->__ptr_ == __n)
1791 (*__ip)->__c_ = nullptr;
1792 if (--__c->end_ != __ip)
1793 memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*));
1796 __get_db()->unlock();
1798 __node_pointer __np = __n->__as_node();
1799 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1813 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1816 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__l) == this,
1822 __node_allocator& __na = base::__node_alloc();
1823 base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1828 --base::__sz();
1830 __c_node* __c = __get_db()->__find_c_and_lock(this);
1831 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1833 --__p;
1834 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1835 if (__i->__ptr_ == __n)
1837 (*__p)->__c_ = nullptr;
1838 if (--__c->end_ != __p)
1839 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1842 __get_db()->unlock();
1844 __node_pointer __np = __n->__as_node();
1845 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1860 if (__n < base::__sz())
1862 else if (__n > base::__sz())
1864 __n -= base::__sz();
1866 __node_allocator& __na = base::__node_alloc();
1869 __hold->__prev_ = 0;
1870 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1873 iterator __r = iterator(__hold.release()->__as_link(), this);
1875 iterator __r = iterator(__hold.release()->__as_link());
1882 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1885 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1886 __e.__ptr_->__next_ = __hold.get()->__as_link();
1887 __hold->__prev_ = __e.__ptr_;
1897 __link_pointer __prev = __e.__ptr_->__prev_;
1898 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1911 base::__sz() += __ds;
1919 if (__n < base::__sz())
1921 else if (__n > base::__sz())
1923 __n -= base::__sz();
1925 __node_allocator& __na = base::__node_alloc();
1928 __hold->__prev_ = 0;
1929 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1931 __link_pointer __nl = __hold.release()->__as_link();
1942 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1945 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1946 __e.__ptr_->__next_ = __hold.get()->__as_link();
1947 __hold->__prev_ = __e.__ptr_;
1957 __link_pointer __prev = __e.__ptr_->__prev_;
1958 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1970 __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_);
1971 base::__sz() += __ds;
1982 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1990 base::__unlink_nodes(__f, __l);
1992 base::__sz() += __c.__sz();
1996 __c_node* __cn1 = __db->__find_c_and_lock(this);
1997 __c_node* __cn2 = __db->__find_c(&__c);
1998 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2000 --__ip;
2001 iterator* __i = static_cast<iterator*>((*__ip)->__i_);
2002 if (__i->__ptr_ != __c.__end_as_link())
2004 __cn1->__add(*__ip);
2005 (*__ip)->__c_ = __cn1;
2006 if (--__cn2->end_ != __ip)
2007 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2010 __db->unlock();
2020 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2023 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
2026 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
2030 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
2033 base::__unlink_nodes(__f, __f);
2035 --__c.__sz();
2036 ++base::__sz();
2039 __c_node* __cn1 = __db->__find_c_and_lock(this);
2040 __c_node* __cn2 = __db->__find_c(&__c);
2041 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2043 --__ip;
2044 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2045 if (__j->__ptr_ == __f)
2047 __cn1->__add(*__ip);
2048 (*__ip)->__c_ = __cn1;
2049 if (--__cn2->end_ != __ip)
2050 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2053 __db->unlock();
2063 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2066 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
2083 __c.__sz() -= __s;
2084 base::__sz() += __s;
2087 --__l;
2089 base::__unlink_nodes(__first, __last);
2093 __c_node* __cn1 = __db->__find_c_and_lock(this);
2094 __c_node* __cn2 = __db->__find_c(&__c);
2095 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2097 --__ip;
2098 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2100 __k != __l.__ptr_; __k = __k->__next_)
2102 if (__j->__ptr_ == __k)
2104 __cn1->__add(*__ip);
2105 (*__ip)->__c_ = __cn1;
2106 if (--__cn2->end_ != __ip)
2107 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2111 __db->unlock();
2185 list<_Tp, _Alloc>::merge(list& __c)
2187 merge(__c, __less<value_type>());
2193 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2209 base::__sz() += __ds;
2210 __c.__sz() -= __ds;
2212 __link_pointer __l = __m2.__ptr_->__prev_;
2214 base::__unlink_nodes(__f, __l);
2225 __c_node* __cn1 = __db->__find_c_and_lock(this);
2226 __c_node* __cn2 = __db->__find_c(&__c);
2227 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2229 --__p;
2230 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2231 if (__i->__ptr_ != __c.__end_as_link())
2233 __cn1->__add(*__p);
2234 (*__p)->__c_ = __cn1;
2235 if (--__cn2->end_ != __p)
2236 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2239 __db->unlock();
2258 __sort(begin(), end(), base::__sz(), __comp);
2272 if (__comp(*--__e2, *__f1))
2275 base::__unlink_nodes(__f, __f);
2284 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2291 __link_pointer __l = __m2.__ptr_->__prev_;
2294 base::__unlink_nodes(__f, __l);
2309 __link_pointer __l = __m2.__ptr_->__prev_;
2313 base::__unlink_nodes(__f, __l);
2328 if (base::__sz() > 1)
2333 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2334 __i.__ptr_ = __i.__ptr_->__prev_;
2336 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2353 return __i->__ptr_ != this->__end_as_link();
2360 return !empty() && __i->__ptr_ != base::__end_.__next_;