libstdc++-v3/include/bits/list.tcc

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996,1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/list.tcc
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{list}
  54  */
  55
  56 #ifndef _LIST_TCC
  57 #define _LIST_TCC 1
  58
  59 namespace std _GLIBCXX_VISIBILITY(default)
  60 {
  61 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  62
  63   template<typename _Tp, typename _Alloc>
  64     void
  65     _List_base<_Tp, _Alloc>::
  66     _M_clear() _GLIBCXX_NOEXCEPT
  67     {
  68       typedef _List_node<_Tp>  _Node;
  69       __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
  70       while (__cur != &_M_impl._M_node)
  71         {
  72           _Node* __tmp = static_cast<_Node*>(__cur);
  73           __cur = __tmp->_M_next;
  74 #if __cplusplus >= 201103L
  75           _M_get_Node_allocator().destroy(__tmp);
  76 #else
  77           _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
  78 #endif
  79           _M_put_node(__tmp);
  80         }
  81     }
  82
  83 #if __cplusplus >= 201103L
  84   template<typename _Tp, typename _Alloc>
  85     template<typename... _Args>
  86       typename list<_Tp, _Alloc>::iterator
  87       list<_Tp, _Alloc>::
  88       emplace(const_iterator __position, _Args&&... __args)
  89       {
  90         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
  91         __tmp->_M_hook(__position._M_const_cast()._M_node);
  92         this->_M_inc_size(1);
  93         return iterator(__tmp);
  94       }
  95 #endif
  96
  97   template<typename _Tp, typename _Alloc>
  98     typename list<_Tp, _Alloc>::iterator
  99     list<_Tp, _Alloc>::
 100 #if __cplusplus >= 201103L
 101     insert(const_iterator __position, const value_type& __x)
 102 #else
 103     insert(iterator __position, const value_type& __x)
 104 #endif
 105     {
 106       _Node* __tmp = _M_create_node(__x);
 107       __tmp->_M_hook(__position._M_const_cast()._M_node);
 108       this->_M_inc_size(1);
 109       return iterator(__tmp);
 110     }
 111
 112 #if __cplusplus >= 201103L
 113   template<typename _Tp, typename _Alloc>
 114     typename list<_Tp, _Alloc>::iterator
 115     list<_Tp, _Alloc>::
 116     insert(const_iterator __position, size_type __n, const value_type& __x)
 117     {
 118       if (__n)
 119         {
 120           list __tmp(__n, __x, get_allocator());
 121           iterator __it = __tmp.begin();
 122           splice(__position, __tmp);
 123           return __it;
 124         }
 125       return __position._M_const_cast();
 126     }
 127
 128   template<typename _Tp, typename _Alloc>
 129     template<typename _InputIterator, typename>
 130       typename list<_Tp, _Alloc>::iterator
 131       list<_Tp, _Alloc>::
 132       insert(const_iterator __position, _InputIterator __first,
 133              _InputIterator __last)
 134       {
 135         list __tmp(__first, __last, get_allocator());
 136         if (!__tmp.empty())
 137           {
 138             iterator __it = __tmp.begin();
 139             splice(__position, __tmp);
 140             return __it;
 141           }
 142         return __position._M_const_cast();
 143       }
 144 #endif
 145
 146   template<typename _Tp, typename _Alloc>
 147     typename list<_Tp, _Alloc>::iterator
 148     list<_Tp, _Alloc>::
 149 #if __cplusplus >= 201103L
 150     erase(const_iterator __position) noexcept
 151 #else
 152     erase(iterator __position)
 153 #endif
 154     {
 155       iterator __ret = iterator(__position._M_node->_M_next);
 156       _M_erase(__position._M_const_cast());
 157       return __ret;
 158     }
 159
 160   // Return a const_iterator indicating the position to start inserting or
 161   // erasing elements (depending whether the list is growing or shrinking),
 162   // and set __new_size to the number of new elements that must be appended.
 163   // Equivalent to the following, but performed optimally:
 164   // if (__new_size < size()) {
 165   //   __new_size = 0;
 166   //   return std::next(begin(), __new_size);
 167   // } else {
 168   //   __newsize -= size();
 169   //   return end();
 170   // }
 171   template<typename _Tp, typename _Alloc>
 172     typename list<_Tp, _Alloc>::const_iterator
 173     list<_Tp, _Alloc>::
 174     _M_resize_pos(size_type& __new_size) const
 175     {
 176       const_iterator __i;
 177 #if _GLIBCXX_USE_CXX11_ABI
 178       const size_type __len = size();
 179       if (__new_size < __len)
 180         {
 181           if (__new_size <= __len / 2)
 182             {
 183               __i = begin();
 184               std::advance(__i, __new_size);
 185             }
 186           else
 187             {
 188               __i = end();
 189               ptrdiff_t __num_erase = __len - __new_size;
 190               std::advance(__i, -__num_erase);
 191             }
 192           __new_size = 0;
 193           return __i;
 194         }
 195       else
 196         __i = end();
 197 #else
 198       size_type __len = 0;
 199       for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
 200         ;
 201 #endif
 202       __new_size -= __len;
 203       return __i;
 204     }
 205
 206 #if __cplusplus >= 201103L
 207   template<typename _Tp, typename _Alloc>
 208     void
 209     list<_Tp, _Alloc>::
 210     _M_default_append(size_type __n)
 211     {
 212       size_type __i = 0;
 213       __try
 214         {
 215           for (; __i < __n; ++__i)
 216             emplace_back();
 217         }
 218       __catch(...)
 219         {
 220           for (; __i; --__i)
 221             pop_back();
 222           __throw_exception_again;
 223         }
 224     }
 225
 226   template<typename _Tp, typename _Alloc>
 227     void
 228     list<_Tp, _Alloc>::
 229     resize(size_type __new_size)
 230     {
 231       const_iterator __i = _M_resize_pos(__new_size);
 232       if (__new_size)
 233         _M_default_append(__new_size);
 234       else
 235         erase(__i, end());
 236     }
 237
 238   template<typename _Tp, typename _Alloc>
 239     void
 240     list<_Tp, _Alloc>::
 241     resize(size_type __new_size, const value_type& __x)
 242     {
 243       const_iterator __i = _M_resize_pos(__new_size);
 244       if (__new_size)
 245         insert(end(), __new_size, __x);
 246       else
 247         erase(__i, end());
 248     }
 249 #else
 250   template<typename _Tp, typename _Alloc>
 251     void
 252     list<_Tp, _Alloc>::
 253     resize(size_type __new_size, value_type __x)
 254     {
 255       const_iterator __i = _M_resize_pos(__new_size);
 256       if (__new_size)
 257         insert(end(), __new_size, __x);
 258       else
 259         erase(__i._M_const_cast(), end());
 260     }
 261 #endif
 262
 263   template<typename _Tp, typename _Alloc>
 264     list<_Tp, _Alloc>&
 265     list<_Tp, _Alloc>::
 266     operator=(const list& __x)
 267     {
 268       if (this != std::__addressof(__x))
 269         {
 270           iterator __first1 = begin();
 271           iterator __last1 = end();
 272           const_iterator __first2 = __x.begin();
 273           const_iterator __last2 = __x.end();
 274           for (; __first1 != __last1 && __first2 != __last2;
 275                ++__first1, ++__first2)
 276             *__first1 = *__first2;
 277           if (__first2 == __last2)
 278             erase(__first1, __last1);
 279           else
 280             insert(__last1, __first2, __last2);
 281         }
 282       return *this;
 283     }
 284
 285   template<typename _Tp, typename _Alloc>
 286     void
 287     list<_Tp, _Alloc>::
 288     _M_fill_assign(size_type __n, const value_type& __val)
 289     {
 290       iterator __i = begin();
 291       for (; __i != end() && __n > 0; ++__i, --__n)
 292         *__i = __val;
 293       if (__n > 0)
 294         insert(end(), __n, __val);
 295       else
 296         erase(__i, end());
 297     }
 298
 299   template<typename _Tp, typename _Alloc>
 300     template <typename _InputIterator>
 301       void
 302       list<_Tp, _Alloc>::
 303       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 304                          __false_type)
 305       {
 306         iterator __first1 = begin();
 307         iterator __last1 = end();
 308         for (; __first1 != __last1 && __first2 != __last2;
 309              ++__first1, ++__first2)
 310           *__first1 = *__first2;
 311         if (__first2 == __last2)
 312           erase(__first1, __last1);
 313         else
 314           insert(__last1, __first2, __last2);
 315       }
 316
 317   template<typename _Tp, typename _Alloc>
 318     void
 319     list<_Tp, _Alloc>::
 320     remove(const value_type& __value)
 321     {
 322       iterator __first = begin();
 323       iterator __last = end();
 324       iterator __extra = __last;
 325       while (__first != __last)
 326         {
 327           iterator __next = __first;
 328           ++__next;
 329           if (*__first == __value)
 330             {
 331               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 332               // 526. Is it undefined if a function in the standard changes
 333               // in parameters?
 334               if (std::__addressof(*__first) != std::__addressof(__value))
 335                 _M_erase(__first);
 336               else
 337                 __extra = __first;
 338             }
 339           __first = __next;
 340         }
 341       if (__extra != __last)
 342         _M_erase(__extra);
 343     }
 344
 345   template<typename _Tp, typename _Alloc>
 346     void
 347     list<_Tp, _Alloc>::
 348     unique()
 349     {
 350       iterator __first = begin();
 351       iterator __last = end();
 352       if (__first == __last)
 353         return;
 354       iterator __next = __first;
 355       while (++__next != __last)
 356         {
 357           if (*__first == *__next)
 358             _M_erase(__next);
 359           else
 360             __first = __next;
 361           __next = __first;
 362         }
 363     }
 364
 365   template<typename _Tp, typename _Alloc>
 366     void
 367     list<_Tp, _Alloc>::
 368 #if __cplusplus >= 201103L
 369     merge(list&& __x)
 370 #else
 371     merge(list& __x)
 372 #endif
 373     {
 374       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 375       // 300. list::merge() specification incomplete
 376       if (this != std::__addressof(__x))
 377         {
 378           _M_check_equal_allocators(__x);
 379
 380           iterator __first1 = begin();
 381           iterator __last1 = end();
 382           iterator __first2 = __x.begin();
 383           iterator __last2 = __x.end();
 384           while (__first1 != __last1 && __first2 != __last2)
 385             if (*__first2 < *__first1)
 386               {
 387                 iterator __next = __first2;
 388                 _M_transfer(__first1, __first2, ++__next);
 389                 __first2 = __next;
 390               }
 391             else
 392               ++__first1;
 393           if (__first2 != __last2)
 394             _M_transfer(__last1, __first2, __last2);
 395
 396           this->_M_inc_size(__x._M_get_size());
 397           __x._M_set_size(0);
 398         }
 399     }
 400
 401   template<typename _Tp, typename _Alloc>
 402     template <typename _StrictWeakOrdering>
 403       void
 404       list<_Tp, _Alloc>::
 405 #if __cplusplus >= 201103L
 406       merge(list&& __x, _StrictWeakOrdering __comp)
 407 #else
 408       merge(list& __x, _StrictWeakOrdering __comp)
 409 #endif
 410       {
 411         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 412         // 300. list::merge() specification incomplete
 413         if (this != std::__addressof(__x))
 414           {
 415             _M_check_equal_allocators(__x);
 416
 417             iterator __first1 = begin();
 418             iterator __last1 = end();
 419             iterator __first2 = __x.begin();
 420             iterator __last2 = __x.end();
 421             while (__first1 != __last1 && __first2 != __last2)
 422               if (__comp(*__first2, *__first1))
 423                 {
 424                   iterator __next = __first2;
 425                   _M_transfer(__first1, __first2, ++__next);
 426                   __first2 = __next;
 427                 }
 428               else
 429                 ++__first1;
 430             if (__first2 != __last2)
 431               _M_transfer(__last1, __first2, __last2);
 432
 433             this->_M_inc_size(__x._M_get_size());
 434             __x._M_set_size(0);
 435           }
 436       }
 437
 438   template<typename _Tp, typename _Alloc>
 439     void
 440     list<_Tp, _Alloc>::
 441     sort()
 442     {
 443       // Do nothing if the list has length 0 or 1.
 444       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 445           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 446       {
 447         list __carry;
 448         list __tmp[64];
 449         list * __fill = __tmp;
 450         list * __counter;
 451
 452         do
 453           {
 454             __carry.splice(__carry.begin(), *this, begin());
 455
 456             for(__counter = __tmp;
 457                 __counter != __fill && !__counter->empty();
 458                 ++__counter)
 459               {
 460                 __counter->merge(__carry);
 461                 __carry.swap(*__counter);
 462               }
 463             __carry.swap(*__counter);
 464             if (__counter == __fill)
 465               ++__fill;
 466           }
 467         while ( !empty() );
 468
 469         for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 470           __counter->merge(*(__counter - 1));
 471         swap( *(__fill - 1) );
 472       }
 473     }
 474
 475   template<typename _Tp, typename _Alloc>
 476     template <typename _Predicate>
 477       void
 478       list<_Tp, _Alloc>::
 479       remove_if(_Predicate __pred)
 480       {
 481         iterator __first = begin();
 482         iterator __last = end();
 483         while (__first != __last)
 484           {
 485             iterator __next = __first;
 486             ++__next;
 487             if (__pred(*__first))
 488               _M_erase(__first);
 489             __first = __next;
 490           }
 491       }
 492
 493   template<typename _Tp, typename _Alloc>
 494     template <typename _BinaryPredicate>
 495       void
 496       list<_Tp, _Alloc>::
 497       unique(_BinaryPredicate __binary_pred)
 498       {
 499         iterator __first = begin();
 500         iterator __last = end();
 501         if (__first == __last)
 502           return;
 503         iterator __next = __first;
 504         while (++__next != __last)
 505           {
 506             if (__binary_pred(*__first, *__next))
 507               _M_erase(__next);
 508             else
 509               __first = __next;
 510             __next = __first;
 511           }
 512       }
 513
 514   template<typename _Tp, typename _Alloc>
 515     template <typename _StrictWeakOrdering>
 516       void
 517       list<_Tp, _Alloc>::
 518       sort(_StrictWeakOrdering __comp)
 519       {
 520         // Do nothing if the list has length 0 or 1.
 521         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 522             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 523           {
 524             list __carry;
 525             list __tmp[64];
 526             list * __fill = __tmp;
 527             list * __counter;
 528
 529             do
 530               {
 531                 __carry.splice(__carry.begin(), *this, begin());
 532
 533                 for(__counter = __tmp;
 534                     __counter != __fill && !__counter->empty();
 535                     ++__counter)
 536                   {
 537                     __counter->merge(__carry, __comp);
 538                     __carry.swap(*__counter);
 539                   }
 540                 __carry.swap(*__counter);
 541                 if (__counter == __fill)
 542                   ++__fill;
 543               }
 544             while ( !empty() );
 545
 546             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 547               __counter->merge(*(__counter - 1), __comp);
 548             swap(*(__fill - 1));
 549           }
 550       }
 551
 552 _GLIBCXX_END_NAMESPACE_CONTAINER
 553 } // namespace std
 554
 555 #endif /* _LIST_TCC */
 556