contrib/gcc-5.0/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 #if __cplusplus >= 201103L
 161   template<typename _Tp, typename _Alloc>
 162     void
 163     list<_Tp, _Alloc>::
 164     _M_default_append(size_type __n)
 165     {
 166       size_type __i = 0;
 167       __try
 168         {
 169           for (; __i < __n; ++__i)
 170             emplace_back();
 171         }
 172       __catch(...)
 173         {
 174           for (; __i; --__i)
 175             pop_back();
 176           __throw_exception_again;
 177         }
 178     }
 179
 180   template<typename _Tp, typename _Alloc>
 181     void
 182     list<_Tp, _Alloc>::
 183     resize(size_type __new_size)
 184     {
 185       iterator __i = begin();
 186       size_type __len = 0;
 187       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 188         ;
 189       if (__len == __new_size)
 190         erase(__i, end());
 191       else                          // __i == end()
 192         _M_default_append(__new_size - __len);
 193     }
 194
 195   template<typename _Tp, typename _Alloc>
 196     void
 197     list<_Tp, _Alloc>::
 198     resize(size_type __new_size, const value_type& __x)
 199     {
 200       iterator __i = begin();
 201       size_type __len = 0;
 202       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 203         ;
 204       if (__len == __new_size)
 205         erase(__i, end());
 206       else                          // __i == end()
 207         insert(end(), __new_size - __len, __x);
 208     }
 209 #else
 210   template<typename _Tp, typename _Alloc>
 211     void
 212     list<_Tp, _Alloc>::
 213     resize(size_type __new_size, value_type __x)
 214     {
 215       iterator __i = begin();
 216       size_type __len = 0;
 217       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 218         ;
 219       if (__len == __new_size)
 220         erase(__i, end());
 221       else                          // __i == end()
 222         insert(end(), __new_size - __len, __x);
 223     }
 224 #endif
 225
 226   template<typename _Tp, typename _Alloc>
 227     list<_Tp, _Alloc>&
 228     list<_Tp, _Alloc>::
 229     operator=(const list& __x)
 230     {
 231       if (this != &__x)
 232         {
 233           iterator __first1 = begin();
 234           iterator __last1 = end();
 235           const_iterator __first2 = __x.begin();
 236           const_iterator __last2 = __x.end();
 237           for (; __first1 != __last1 && __first2 != __last2;
 238                ++__first1, ++__first2)
 239             *__first1 = *__first2;
 240           if (__first2 == __last2)
 241             erase(__first1, __last1);
 242           else
 243             insert(__last1, __first2, __last2);
 244         }
 245       return *this;
 246     }
 247
 248   template<typename _Tp, typename _Alloc>
 249     void
 250     list<_Tp, _Alloc>::
 251     _M_fill_assign(size_type __n, const value_type& __val)
 252     {
 253       iterator __i = begin();
 254       for (; __i != end() && __n > 0; ++__i, --__n)
 255         *__i = __val;
 256       if (__n > 0)
 257         insert(end(), __n, __val);
 258       else
 259         erase(__i, end());
 260     }
 261
 262   template<typename _Tp, typename _Alloc>
 263     template <typename _InputIterator>
 264       void
 265       list<_Tp, _Alloc>::
 266       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 267                          __false_type)
 268       {
 269         iterator __first1 = begin();
 270         iterator __last1 = end();
 271         for (; __first1 != __last1 && __first2 != __last2;
 272              ++__first1, ++__first2)
 273           *__first1 = *__first2;
 274         if (__first2 == __last2)
 275           erase(__first1, __last1);
 276         else
 277           insert(__last1, __first2, __last2);
 278       }
 279
 280   template<typename _Tp, typename _Alloc>
 281     void
 282     list<_Tp, _Alloc>::
 283     remove(const value_type& __value)
 284     {
 285       iterator __first = begin();
 286       iterator __last = end();
 287       iterator __extra = __last;
 288       while (__first != __last)
 289         {
 290           iterator __next = __first;
 291           ++__next;
 292           if (*__first == __value)
 293             {
 294               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 295               // 526. Is it undefined if a function in the standard changes
 296               // in parameters?
 297               if (std::__addressof(*__first) != std::__addressof(__value))
 298                 _M_erase(__first);
 299               else
 300                 __extra = __first;
 301             }
 302           __first = __next;
 303         }
 304       if (__extra != __last)
 305         _M_erase(__extra);
 306     }
 307
 308   template<typename _Tp, typename _Alloc>
 309     void
 310     list<_Tp, _Alloc>::
 311     unique()
 312     {
 313       iterator __first = begin();
 314       iterator __last = end();
 315       if (__first == __last)
 316         return;
 317       iterator __next = __first;
 318       while (++__next != __last)
 319         {
 320           if (*__first == *__next)
 321             _M_erase(__next);
 322           else
 323             __first = __next;
 324           __next = __first;
 325         }
 326     }
 327
 328   template<typename _Tp, typename _Alloc>
 329     void
 330     list<_Tp, _Alloc>::
 331 #if __cplusplus >= 201103L
 332     merge(list&& __x)
 333 #else
 334     merge(list& __x)
 335 #endif
 336     {
 337       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 338       // 300. list::merge() specification incomplete
 339       if (this != &__x)
 340         {
 341           _M_check_equal_allocators(__x);
 342
 343           iterator __first1 = begin();
 344           iterator __last1 = end();
 345           iterator __first2 = __x.begin();
 346           iterator __last2 = __x.end();
 347           while (__first1 != __last1 && __first2 != __last2)
 348             if (*__first2 < *__first1)
 349               {
 350                 iterator __next = __first2;
 351                 _M_transfer(__first1, __first2, ++__next);
 352                 __first2 = __next;
 353               }
 354             else
 355               ++__first1;
 356           if (__first2 != __last2)
 357             _M_transfer(__last1, __first2, __last2);
 358
 359           this->_M_inc_size(__x._M_get_size());
 360           __x._M_set_size(0);
 361         }
 362     }
 363
 364   template<typename _Tp, typename _Alloc>
 365     template <typename _StrictWeakOrdering>
 366       void
 367       list<_Tp, _Alloc>::
 368 #if __cplusplus >= 201103L
 369       merge(list&& __x, _StrictWeakOrdering __comp)
 370 #else
 371       merge(list& __x, _StrictWeakOrdering __comp)
 372 #endif
 373       {
 374         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 375         // 300. list::merge() specification incomplete
 376         if (this != &__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 (__comp(*__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     void
 403     list<_Tp, _Alloc>::
 404     sort()
 405     {
 406       // Do nothing if the list has length 0 or 1.
 407       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 408           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 409       {
 410         list __carry;
 411         list __tmp[64];
 412         list * __fill = &__tmp[0];
 413         list * __counter;
 414
 415         do
 416           {
 417             __carry.splice(__carry.begin(), *this, begin());
 418
 419             for(__counter = &__tmp[0];
 420                 __counter != __fill && !__counter->empty();
 421                 ++__counter)
 422               {
 423                 __counter->merge(__carry);
 424                 __carry.swap(*__counter);
 425               }
 426             __carry.swap(*__counter);
 427             if (__counter == __fill)
 428               ++__fill;
 429           }
 430         while ( !empty() );
 431
 432         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 433           __counter->merge(*(__counter - 1));
 434         swap( *(__fill - 1) );
 435       }
 436     }
 437
 438   template<typename _Tp, typename _Alloc>
 439     template <typename _Predicate>
 440       void
 441       list<_Tp, _Alloc>::
 442       remove_if(_Predicate __pred)
 443       {
 444         iterator __first = begin();
 445         iterator __last = end();
 446         while (__first != __last)
 447           {
 448             iterator __next = __first;
 449             ++__next;
 450             if (__pred(*__first))
 451               _M_erase(__first);
 452             __first = __next;
 453           }
 454       }
 455
 456   template<typename _Tp, typename _Alloc>
 457     template <typename _BinaryPredicate>
 458       void
 459       list<_Tp, _Alloc>::
 460       unique(_BinaryPredicate __binary_pred)
 461       {
 462         iterator __first = begin();
 463         iterator __last = end();
 464         if (__first == __last)
 465           return;
 466         iterator __next = __first;
 467         while (++__next != __last)
 468           {
 469             if (__binary_pred(*__first, *__next))
 470               _M_erase(__next);
 471             else
 472               __first = __next;
 473             __next = __first;
 474           }
 475       }
 476
 477   template<typename _Tp, typename _Alloc>
 478     template <typename _StrictWeakOrdering>
 479       void
 480       list<_Tp, _Alloc>::
 481       sort(_StrictWeakOrdering __comp)
 482       {
 483         // Do nothing if the list has length 0 or 1.
 484         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 485             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 486           {
 487             list __carry;
 488             list __tmp[64];
 489             list * __fill = &__tmp[0];
 490             list * __counter;
 491
 492             do
 493               {
 494                 __carry.splice(__carry.begin(), *this, begin());
 495
 496                 for(__counter = &__tmp[0];
 497                     __counter != __fill && !__counter->empty();
 498                     ++__counter)
 499                   {
 500                     __counter->merge(__carry, __comp);
 501                     __carry.swap(*__counter);
 502                   }
 503                 __carry.swap(*__counter);
 504                 if (__counter == __fill)
 505                   ++__fill;
 506               }
 507             while ( !empty() );
 508
 509             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 510               __counter->merge(*(__counter - 1), __comp);
 511             swap(*(__fill - 1));
 512           }
 513       }
 514
 515 _GLIBCXX_END_NAMESPACE_CONTAINER
 516 } // namespace std
 517
 518 #endif /* _LIST_TCC */
 519