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

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2016 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           _Tp* __val = __tmp->_M_valptr();
  75 #if __cplusplus >= 201103L
  76           _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
  77 #else
  78           _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
  79 #endif
  80           _M_put_node(__tmp);
  81         }
  82     }
  83
  84 #if __cplusplus >= 201103L
  85   template<typename _Tp, typename _Alloc>
  86     template<typename... _Args>
  87       typename list<_Tp, _Alloc>::iterator
  88       list<_Tp, _Alloc>::
  89       emplace(const_iterator __position, _Args&&... __args)
  90       {
  91         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
  92         __tmp->_M_hook(__position._M_const_cast()._M_node);
  93         this->_M_inc_size(1);
  94         return iterator(__tmp);
  95       }
  96 #endif
  97
  98   template<typename _Tp, typename _Alloc>
  99     typename list<_Tp, _Alloc>::iterator
 100     list<_Tp, _Alloc>::
 101 #if __cplusplus >= 201103L
 102     insert(const_iterator __position, const value_type& __x)
 103 #else
 104     insert(iterator __position, const value_type& __x)
 105 #endif
 106     {
 107       _Node* __tmp = _M_create_node(__x);
 108       __tmp->_M_hook(__position._M_const_cast()._M_node);
 109       this->_M_inc_size(1);
 110       return iterator(__tmp);
 111     }
 112
 113 #if __cplusplus >= 201103L
 114   template<typename _Tp, typename _Alloc>
 115     typename list<_Tp, _Alloc>::iterator
 116     list<_Tp, _Alloc>::
 117     insert(const_iterator __position, size_type __n, const value_type& __x)
 118     {
 119       if (__n)
 120         {
 121           list __tmp(__n, __x, get_allocator());
 122           iterator __it = __tmp.begin();
 123           splice(__position, __tmp);
 124           return __it;
 125         }
 126       return __position._M_const_cast();
 127     }
 128
 129   template<typename _Tp, typename _Alloc>
 130     template<typename _InputIterator, typename>
 131       typename list<_Tp, _Alloc>::iterator
 132       list<_Tp, _Alloc>::
 133       insert(const_iterator __position, _InputIterator __first,
 134              _InputIterator __last)
 135       {
 136         list __tmp(__first, __last, get_allocator());
 137         if (!__tmp.empty())
 138           {
 139             iterator __it = __tmp.begin();
 140             splice(__position, __tmp);
 141             return __it;
 142           }
 143         return __position._M_const_cast();
 144       }
 145 #endif
 146
 147   template<typename _Tp, typename _Alloc>
 148     typename list<_Tp, _Alloc>::iterator
 149     list<_Tp, _Alloc>::
 150 #if __cplusplus >= 201103L
 151     erase(const_iterator __position) noexcept
 152 #else
 153     erase(iterator __position)
 154 #endif
 155     {
 156       iterator __ret = iterator(__position._M_node->_M_next);
 157       _M_erase(__position._M_const_cast());
 158       return __ret;
 159     }
 160
 161   // Return a const_iterator indicating the position to start inserting or
 162   // erasing elements (depending whether the list is growing or shrinking),
 163   // and set __new_size to the number of new elements that must be appended.
 164   // Equivalent to the following, but performed optimally:
 165   // if (__new_size < size()) {
 166   //   __new_size = 0;
 167   //   return std::next(begin(), __new_size);
 168   // } else {
 169   //   __newsize -= size();
 170   //   return end();
 171   // }
 172   template<typename _Tp, typename _Alloc>
 173     typename list<_Tp, _Alloc>::const_iterator
 174     list<_Tp, _Alloc>::
 175     _M_resize_pos(size_type& __new_size) const
 176     {
 177       const_iterator __i;
 178 #if _GLIBCXX_USE_CXX11_ABI
 179       const size_type __len = size();
 180       if (__new_size < __len)
 181         {
 182           if (__new_size <= __len / 2)
 183             {
 184               __i = begin();
 185               std::advance(__i, __new_size);
 186             }
 187           else
 188             {
 189               __i = end();
 190               ptrdiff_t __num_erase = __len - __new_size;
 191               std::advance(__i, -__num_erase);
 192             }
 193           __new_size = 0;
 194           return __i;
 195         }
 196       else
 197         __i = end();
 198 #else
 199       size_type __len = 0;
 200       for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
 201         ;
 202 #endif
 203       __new_size -= __len;
 204       return __i;
 205     }
 206
 207 #if __cplusplus >= 201103L
 208   template<typename _Tp, typename _Alloc>
 209     void
 210     list<_Tp, _Alloc>::
 211     _M_default_append(size_type __n)
 212     {
 213       size_type __i = 0;
 214       __try
 215         {
 216           for (; __i < __n; ++__i)
 217             emplace_back();
 218         }
 219       __catch(...)
 220         {
 221           for (; __i; --__i)
 222             pop_back();
 223           __throw_exception_again;
 224         }
 225     }
 226
 227   template<typename _Tp, typename _Alloc>
 228     void
 229     list<_Tp, _Alloc>::
 230     resize(size_type __new_size)
 231     {
 232       const_iterator __i = _M_resize_pos(__new_size);
 233       if (__new_size)
 234         _M_default_append(__new_size);
 235       else
 236         erase(__i, end());
 237     }
 238
 239   template<typename _Tp, typename _Alloc>
 240     void
 241     list<_Tp, _Alloc>::
 242     resize(size_type __new_size, const value_type& __x)
 243     {
 244       const_iterator __i = _M_resize_pos(__new_size);
 245       if (__new_size)
 246         insert(end(), __new_size, __x);
 247       else
 248         erase(__i, end());
 249     }
 250 #else
 251   template<typename _Tp, typename _Alloc>
 252     void
 253     list<_Tp, _Alloc>::
 254     resize(size_type __new_size, value_type __x)
 255     {
 256       const_iterator __i = _M_resize_pos(__new_size);
 257       if (__new_size)
 258         insert(end(), __new_size, __x);
 259       else
 260         erase(__i._M_const_cast(), end());
 261     }
 262 #endif
 263
 264   template<typename _Tp, typename _Alloc>
 265     list<_Tp, _Alloc>&
 266     list<_Tp, _Alloc>::
 267     operator=(const list& __x)
 268     {
 269       if (this != std::__addressof(__x))
 270         {
 271 #if __cplusplus >= 201103L
 272           if (_Node_alloc_traits::_S_propagate_on_copy_assign())
 273             {
 274               auto& __this_alloc = this->_M_get_Node_allocator();
 275               auto& __that_alloc = __x._M_get_Node_allocator();
 276               if (!_Node_alloc_traits::_S_always_equal()
 277                   && __this_alloc != __that_alloc)
 278                 {
 279                   // replacement allocator cannot free existing storage
 280                   clear();
 281                 }
 282               std::__alloc_on_copy(__this_alloc, __that_alloc);
 283             }
 284 #endif
 285           _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
 286         }
 287       return *this;
 288     }
 289
 290   template<typename _Tp, typename _Alloc>
 291     void
 292     list<_Tp, _Alloc>::
 293     _M_fill_assign(size_type __n, const value_type& __val)
 294     {
 295       iterator __i = begin();
 296       for (; __i != end() && __n > 0; ++__i, --__n)
 297         *__i = __val;
 298       if (__n > 0)
 299         insert(end(), __n, __val);
 300       else
 301         erase(__i, end());
 302     }
 303
 304   template<typename _Tp, typename _Alloc>
 305     template <typename _InputIterator>
 306       void
 307       list<_Tp, _Alloc>::
 308       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 309                          __false_type)
 310       {
 311         iterator __first1 = begin();
 312         iterator __last1 = end();
 313         for (; __first1 != __last1 && __first2 != __last2;
 314              ++__first1, ++__first2)
 315           *__first1 = *__first2;
 316         if (__first2 == __last2)
 317           erase(__first1, __last1);
 318         else
 319           insert(__last1, __first2, __last2);
 320       }
 321
 322   template<typename _Tp, typename _Alloc>
 323     void
 324     list<_Tp, _Alloc>::
 325     remove(const value_type& __value)
 326     {
 327       iterator __first = begin();
 328       iterator __last = end();
 329       iterator __extra = __last;
 330       while (__first != __last)
 331         {
 332           iterator __next = __first;
 333           ++__next;
 334           if (*__first == __value)
 335             {
 336               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 337               // 526. Is it undefined if a function in the standard changes
 338               // in parameters?
 339               if (std::__addressof(*__first) != std::__addressof(__value))
 340                 _M_erase(__first);
 341               else
 342                 __extra = __first;
 343             }
 344           __first = __next;
 345         }
 346       if (__extra != __last)
 347         _M_erase(__extra);
 348     }
 349
 350   template<typename _Tp, typename _Alloc>
 351     void
 352     list<_Tp, _Alloc>::
 353     unique()
 354     {
 355       iterator __first = begin();
 356       iterator __last = end();
 357       if (__first == __last)
 358         return;
 359       iterator __next = __first;
 360       while (++__next != __last)
 361         {
 362           if (*__first == *__next)
 363             _M_erase(__next);
 364           else
 365             __first = __next;
 366           __next = __first;
 367         }
 368     }
 369
 370   template<typename _Tp, typename _Alloc>
 371     void
 372     list<_Tp, _Alloc>::
 373 #if __cplusplus >= 201103L
 374     merge(list&& __x)
 375 #else
 376     merge(list& __x)
 377 #endif
 378     {
 379       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 380       // 300. list::merge() specification incomplete
 381       if (this != std::__addressof(__x))
 382         {
 383           _M_check_equal_allocators(__x);
 384
 385           iterator __first1 = begin();
 386           iterator __last1 = end();
 387           iterator __first2 = __x.begin();
 388           iterator __last2 = __x.end();
 389           while (__first1 != __last1 && __first2 != __last2)
 390             if (*__first2 < *__first1)
 391               {
 392                 iterator __next = __first2;
 393                 _M_transfer(__first1, __first2, ++__next);
 394                 __first2 = __next;
 395               }
 396             else
 397               ++__first1;
 398           if (__first2 != __last2)
 399             _M_transfer(__last1, __first2, __last2);
 400
 401           this->_M_inc_size(__x._M_get_size());
 402           __x._M_set_size(0);
 403         }
 404     }
 405
 406   template<typename _Tp, typename _Alloc>
 407     template <typename _StrictWeakOrdering>
 408       void
 409       list<_Tp, _Alloc>::
 410 #if __cplusplus >= 201103L
 411       merge(list&& __x, _StrictWeakOrdering __comp)
 412 #else
 413       merge(list& __x, _StrictWeakOrdering __comp)
 414 #endif
 415       {
 416         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 417         // 300. list::merge() specification incomplete
 418         if (this != std::__addressof(__x))
 419           {
 420             _M_check_equal_allocators(__x);
 421
 422             iterator __first1 = begin();
 423             iterator __last1 = end();
 424             iterator __first2 = __x.begin();
 425             iterator __last2 = __x.end();
 426             while (__first1 != __last1 && __first2 != __last2)
 427               if (__comp(*__first2, *__first1))
 428                 {
 429                   iterator __next = __first2;
 430                   _M_transfer(__first1, __first2, ++__next);
 431                   __first2 = __next;
 432                 }
 433               else
 434                 ++__first1;
 435             if (__first2 != __last2)
 436               _M_transfer(__last1, __first2, __last2);
 437
 438             this->_M_inc_size(__x._M_get_size());
 439             __x._M_set_size(0);
 440           }
 441       }
 442
 443   template<typename _Tp, typename _Alloc>
 444     void
 445     list<_Tp, _Alloc>::
 446     sort()
 447     {
 448       // Do nothing if the list has length 0 or 1.
 449       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 450           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 451       {
 452         list __carry;
 453         list __tmp[64];
 454         list * __fill = __tmp;
 455         list * __counter;
 456
 457         do
 458           {
 459             __carry.splice(__carry.begin(), *this, begin());
 460
 461             for(__counter = __tmp;
 462                 __counter != __fill && !__counter->empty();
 463                 ++__counter)
 464               {
 465                 __counter->merge(__carry);
 466                 __carry.swap(*__counter);
 467               }
 468             __carry.swap(*__counter);
 469             if (__counter == __fill)
 470               ++__fill;
 471           }
 472         while ( !empty() );
 473
 474         for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 475           __counter->merge(*(__counter - 1));
 476         swap( *(__fill - 1) );
 477       }
 478     }
 479
 480   template<typename _Tp, typename _Alloc>
 481     template <typename _Predicate>
 482       void
 483       list<_Tp, _Alloc>::
 484       remove_if(_Predicate __pred)
 485       {
 486         iterator __first = begin();
 487         iterator __last = end();
 488         while (__first != __last)
 489           {
 490             iterator __next = __first;
 491             ++__next;
 492             if (__pred(*__first))
 493               _M_erase(__first);
 494             __first = __next;
 495           }
 496       }
 497
 498   template<typename _Tp, typename _Alloc>
 499     template <typename _BinaryPredicate>
 500       void
 501       list<_Tp, _Alloc>::
 502       unique(_BinaryPredicate __binary_pred)
 503       {
 504         iterator __first = begin();
 505         iterator __last = end();
 506         if (__first == __last)
 507           return;
 508         iterator __next = __first;
 509         while (++__next != __last)
 510           {
 511             if (__binary_pred(*__first, *__next))
 512               _M_erase(__next);
 513             else
 514               __first = __next;
 515             __next = __first;
 516           }
 517       }
 518
 519   template<typename _Tp, typename _Alloc>
 520     template <typename _StrictWeakOrdering>
 521       void
 522       list<_Tp, _Alloc>::
 523       sort(_StrictWeakOrdering __comp)
 524       {
 525         // Do nothing if the list has length 0 or 1.
 526         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 527             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 528           {
 529             list __carry;
 530             list __tmp[64];
 531             list * __fill = __tmp;
 532             list * __counter;
 533
 534             do
 535               {
 536                 __carry.splice(__carry.begin(), *this, begin());
 537
 538                 for(__counter = __tmp;
 539                     __counter != __fill && !__counter->empty();
 540                     ++__counter)
 541                   {
 542                     __counter->merge(__carry, __comp);
 543                     __carry.swap(*__counter);
 544                   }
 545                 __carry.swap(*__counter);
 546                 if (__counter == __fill)
 547                   ++__fill;
 548               }
 549             while ( !empty() );
 550
 551             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 552               __counter->merge(*(__counter - 1), __comp);
 553             swap(*(__fill - 1));
 554           }
 555       }
 556
 557 _GLIBCXX_END_NAMESPACE_CONTAINER
 558 } // namespace std
 559
 560 #endif /* _LIST_TCC */
 561