l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.8/include/bits/list.tcc

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2013 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()
  67     {
  68       typedef _List_node<_Tp>  _Node;
  69       _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
  70       while (__cur != &_M_impl._M_node)
  71         {
  72           _Node* __tmp = __cur;
  73           __cur = static_cast<_Node*>(__cur->_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(iterator __position, _Args&&... __args)
  89       {
  90         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
  91         __tmp->_M_hook(__position._M_node);
  92         return iterator(__tmp);
  93       }
  94 #endif
  95
  96   template<typename _Tp, typename _Alloc>
  97     typename list<_Tp, _Alloc>::iterator
  98     list<_Tp, _Alloc>::
  99     insert(iterator __position, const value_type& __x)
 100     {
 101       _Node* __tmp = _M_create_node(__x);
 102       __tmp->_M_hook(__position._M_node);
 103       return iterator(__tmp);
 104     }
 105
 106   template<typename _Tp, typename _Alloc>
 107     typename list<_Tp, _Alloc>::iterator
 108     list<_Tp, _Alloc>::
 109     erase(iterator __position)
 110     {
 111       iterator __ret = iterator(__position._M_node->_M_next);
 112       _M_erase(__position);
 113       return __ret;
 114     }
 115
 116 #if __cplusplus >= 201103L
 117   template<typename _Tp, typename _Alloc>
 118     void
 119     list<_Tp, _Alloc>::
 120     _M_default_append(size_type __n)
 121     {
 122       size_type __i = 0;
 123       __try
 124         {
 125           for (; __i < __n; ++__i)
 126             emplace_back();
 127         }
 128       __catch(...)
 129         {
 130           for (; __i; --__i)
 131             pop_back();
 132           __throw_exception_again;
 133         }
 134     }
 135
 136   template<typename _Tp, typename _Alloc>
 137     void
 138     list<_Tp, _Alloc>::
 139     resize(size_type __new_size)
 140     {
 141       iterator __i = begin();
 142       size_type __len = 0;
 143       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 144         ;
 145       if (__len == __new_size)
 146         erase(__i, end());
 147       else                          // __i == end()
 148         _M_default_append(__new_size - __len);
 149     }
 150
 151   template<typename _Tp, typename _Alloc>
 152     void
 153     list<_Tp, _Alloc>::
 154     resize(size_type __new_size, const value_type& __x)
 155     {
 156       iterator __i = begin();
 157       size_type __len = 0;
 158       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 159         ;
 160       if (__len == __new_size)
 161         erase(__i, end());
 162       else                          // __i == end()
 163         insert(end(), __new_size - __len, __x);
 164     }
 165 #else
 166   template<typename _Tp, typename _Alloc>
 167     void
 168     list<_Tp, _Alloc>::
 169     resize(size_type __new_size, value_type __x)
 170     {
 171       iterator __i = begin();
 172       size_type __len = 0;
 173       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 174         ;
 175       if (__len == __new_size)
 176         erase(__i, end());
 177       else                          // __i == end()
 178         insert(end(), __new_size - __len, __x);
 179     }
 180 #endif
 181
 182   template<typename _Tp, typename _Alloc>
 183     list<_Tp, _Alloc>&
 184     list<_Tp, _Alloc>::
 185     operator=(const list& __x)
 186     {
 187       if (this != &__x)
 188         {
 189           iterator __first1 = begin();
 190           iterator __last1 = end();
 191           const_iterator __first2 = __x.begin();
 192           const_iterator __last2 = __x.end();
 193           for (; __first1 != __last1 && __first2 != __last2;
 194                ++__first1, ++__first2)
 195             *__first1 = *__first2;
 196           if (__first2 == __last2)
 197             erase(__first1, __last1);
 198           else
 199             insert(__last1, __first2, __last2);
 200         }
 201       return *this;
 202     }
 203
 204   template<typename _Tp, typename _Alloc>
 205     void
 206     list<_Tp, _Alloc>::
 207     _M_fill_assign(size_type __n, const value_type& __val)
 208     {
 209       iterator __i = begin();
 210       for (; __i != end() && __n > 0; ++__i, --__n)
 211         *__i = __val;
 212       if (__n > 0)
 213         insert(end(), __n, __val);
 214       else
 215         erase(__i, end());
 216     }
 217
 218   template<typename _Tp, typename _Alloc>
 219     template <typename _InputIterator>
 220       void
 221       list<_Tp, _Alloc>::
 222       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 223                          __false_type)
 224       {
 225         iterator __first1 = begin();
 226         iterator __last1 = end();
 227         for (; __first1 != __last1 && __first2 != __last2;
 228              ++__first1, ++__first2)
 229           *__first1 = *__first2;
 230         if (__first2 == __last2)
 231           erase(__first1, __last1);
 232         else
 233           insert(__last1, __first2, __last2);
 234       }
 235
 236   template<typename _Tp, typename _Alloc>
 237     void
 238     list<_Tp, _Alloc>::
 239     remove(const value_type& __value)
 240     {
 241       iterator __first = begin();
 242       iterator __last = end();
 243       iterator __extra = __last;
 244       while (__first != __last)
 245         {
 246           iterator __next = __first;
 247           ++__next;
 248           if (*__first == __value)
 249             {
 250               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 251               // 526. Is it undefined if a function in the standard changes
 252               // in parameters?
 253               if (std::__addressof(*__first) != std::__addressof(__value))
 254                 _M_erase(__first);
 255               else
 256                 __extra = __first;
 257             }
 258           __first = __next;
 259         }
 260       if (__extra != __last)
 261         _M_erase(__extra);
 262     }
 263
 264   template<typename _Tp, typename _Alloc>
 265     void
 266     list<_Tp, _Alloc>::
 267     unique()
 268     {
 269       iterator __first = begin();
 270       iterator __last = end();
 271       if (__first == __last)
 272         return;
 273       iterator __next = __first;
 274       while (++__next != __last)
 275         {
 276           if (*__first == *__next)
 277             _M_erase(__next);
 278           else
 279             __first = __next;
 280           __next = __first;
 281         }
 282     }
 283
 284   template<typename _Tp, typename _Alloc>
 285     void
 286     list<_Tp, _Alloc>::
 287 #if __cplusplus >= 201103L
 288     merge(list&& __x)
 289 #else
 290     merge(list& __x)
 291 #endif
 292     {
 293       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 294       // 300. list::merge() specification incomplete
 295       if (this != &__x)
 296         {
 297           _M_check_equal_allocators(__x);
 298
 299           iterator __first1 = begin();
 300           iterator __last1 = end();
 301           iterator __first2 = __x.begin();
 302           iterator __last2 = __x.end();
 303           while (__first1 != __last1 && __first2 != __last2)
 304             if (*__first2 < *__first1)
 305               {
 306                 iterator __next = __first2;
 307                 _M_transfer(__first1, __first2, ++__next);
 308                 __first2 = __next;
 309               }
 310             else
 311               ++__first1;
 312           if (__first2 != __last2)
 313             _M_transfer(__last1, __first2, __last2);
 314         }
 315     }
 316
 317   template<typename _Tp, typename _Alloc>
 318     template <typename _StrictWeakOrdering>
 319       void
 320       list<_Tp, _Alloc>::
 321 #if __cplusplus >= 201103L
 322       merge(list&& __x, _StrictWeakOrdering __comp)
 323 #else
 324       merge(list& __x, _StrictWeakOrdering __comp)
 325 #endif
 326       {
 327         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 328         // 300. list::merge() specification incomplete
 329         if (this != &__x)
 330           {
 331             _M_check_equal_allocators(__x);
 332
 333             iterator __first1 = begin();
 334             iterator __last1 = end();
 335             iterator __first2 = __x.begin();
 336             iterator __last2 = __x.end();
 337             while (__first1 != __last1 && __first2 != __last2)
 338               if (__comp(*__first2, *__first1))
 339                 {
 340                   iterator __next = __first2;
 341                   _M_transfer(__first1, __first2, ++__next);
 342                   __first2 = __next;
 343                 }
 344               else
 345                 ++__first1;
 346             if (__first2 != __last2)
 347               _M_transfer(__last1, __first2, __last2);
 348           }
 349       }
 350
 351   template<typename _Tp, typename _Alloc>
 352     void
 353     list<_Tp, _Alloc>::
 354     sort()
 355     {
 356       // Do nothing if the list has length 0 or 1.
 357       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 358           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 359       {
 360         list __carry;
 361         list __tmp[64];
 362         list * __fill = &__tmp[0];
 363         list * __counter;
 364
 365         do
 366           {
 367             __carry.splice(__carry.begin(), *this, begin());
 368
 369             for(__counter = &__tmp[0];
 370                 __counter != __fill && !__counter->empty();
 371                 ++__counter)
 372               {
 373                 __counter->merge(__carry);
 374                 __carry.swap(*__counter);
 375               }
 376             __carry.swap(*__counter);
 377             if (__counter == __fill)
 378               ++__fill;
 379           }
 380         while ( !empty() );
 381
 382         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 383           __counter->merge(*(__counter - 1));
 384         swap( *(__fill - 1) );
 385       }
 386     }
 387
 388   template<typename _Tp, typename _Alloc>
 389     template <typename _Predicate>
 390       void
 391       list<_Tp, _Alloc>::
 392       remove_if(_Predicate __pred)
 393       {
 394         iterator __first = begin();
 395         iterator __last = end();
 396         while (__first != __last)
 397           {
 398             iterator __next = __first;
 399             ++__next;
 400             if (__pred(*__first))
 401               _M_erase(__first);
 402             __first = __next;
 403           }
 404       }
 405
 406   template<typename _Tp, typename _Alloc>
 407     template <typename _BinaryPredicate>
 408       void
 409       list<_Tp, _Alloc>::
 410       unique(_BinaryPredicate __binary_pred)
 411       {
 412         iterator __first = begin();
 413         iterator __last = end();
 414         if (__first == __last)
 415           return;
 416         iterator __next = __first;
 417         while (++__next != __last)
 418           {
 419             if (__binary_pred(*__first, *__next))
 420               _M_erase(__next);
 421             else
 422               __first = __next;
 423             __next = __first;
 424           }
 425       }
 426
 427   template<typename _Tp, typename _Alloc>
 428     template <typename _StrictWeakOrdering>
 429       void
 430       list<_Tp, _Alloc>::
 431       sort(_StrictWeakOrdering __comp)
 432       {
 433         // Do nothing if the list has length 0 or 1.
 434         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 435             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 436           {
 437             list __carry;
 438             list __tmp[64];
 439             list * __fill = &__tmp[0];
 440             list * __counter;
 441
 442             do
 443               {
 444                 __carry.splice(__carry.begin(), *this, begin());
 445
 446                 for(__counter = &__tmp[0];
 447                     __counter != __fill && !__counter->empty();
 448                     ++__counter)
 449                   {
 450                     __counter->merge(__carry, __comp);
 451                     __carry.swap(*__counter);
 452                   }
 453                 __carry.swap(*__counter);
 454                 if (__counter == __fill)
 455                   ++__fill;
 456               }
 457             while ( !empty() );
 458
 459             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 460               __counter->merge(*(__counter - 1), __comp);
 461             swap(*(__fill - 1));
 462           }
 463       }
 464
 465 _GLIBCXX_END_NAMESPACE_CONTAINER
 466 } // namespace std
 467
 468 #endif /* _LIST_TCC */
 469