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

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  *
  45  * Copyright (c) 1996,1997
  46  * Silicon Graphics Computer Systems, Inc.
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.  Silicon Graphics makes no
  53  * representations about the suitability of this software for any
  54  * purpose.  It is provided "as is" without express or implied warranty.
  55  */
  56
  57 /** @file list.tcc
  58  *  This is an internal header file, included by other library headers.
  59  *  You should not attempt to use it directly.
  60  */
  61
  62 #ifndef _LIST_TCC
  63 #define _LIST_TCC 1
  64
  65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  66
  67   template<typename _Tp, typename _Alloc>
  68     void
  69     _List_base<_Tp, _Alloc>::
  70     _M_clear()
  71     {
  72       typedef _List_node<_Tp>  _Node;
  73       _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
  74       while (__cur != &this->_M_impl._M_node)
  75         {
  76           _Node* __tmp = __cur;
  77           __cur = static_cast<_Node*>(__cur->_M_next);
  78 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  79           _M_get_Node_allocator().destroy(__tmp);
  80 #else
  81           _M_get_Tp_allocator().destroy(&__tmp->_M_data);
  82 #endif
  83           _M_put_node(__tmp);
  84         }
  85     }
  86
  87 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  88   template<typename _Tp, typename _Alloc>
  89     template<typename... _Args>
  90       typename list<_Tp, _Alloc>::iterator
  91       list<_Tp, _Alloc>::
  92       emplace(iterator __position, _Args&&... __args)
  93       {
  94         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
  95         __tmp->hook(__position._M_node);
  96         return iterator(__tmp);
  97       }
  98 #endif
  99
 100   template<typename _Tp, typename _Alloc>
 101     typename list<_Tp, _Alloc>::iterator
 102     list<_Tp, _Alloc>::
 103     insert(iterator __position, const value_type& __x)
 104     {
 105       _Node* __tmp = _M_create_node(__x);
 106       __tmp->hook(__position._M_node);
 107       return iterator(__tmp);
 108     }
 109
 110   template<typename _Tp, typename _Alloc>
 111     typename list<_Tp, _Alloc>::iterator
 112     list<_Tp, _Alloc>::
 113     erase(iterator __position)
 114     {
 115       iterator __ret = iterator(__position._M_node->_M_next);
 116       _M_erase(__position);
 117       return __ret;
 118     }
 119
 120   template<typename _Tp, typename _Alloc>
 121     void
 122     list<_Tp, _Alloc>::
 123     resize(size_type __new_size, value_type __x)
 124     {
 125       iterator __i = begin();
 126       size_type __len = 0;
 127       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 128         ;
 129       if (__len == __new_size)
 130         erase(__i, end());
 131       else                          // __i == end()
 132         insert(end(), __new_size - __len, __x);
 133     }
 134
 135   template<typename _Tp, typename _Alloc>
 136     list<_Tp, _Alloc>&
 137     list<_Tp, _Alloc>::
 138     operator=(const list& __x)
 139     {
 140       if (this != &__x)
 141         {
 142           iterator __first1 = begin();
 143           iterator __last1 = end();
 144           const_iterator __first2 = __x.begin();
 145           const_iterator __last2 = __x.end();
 146           for (; __first1 != __last1 && __first2 != __last2;
 147                ++__first1, ++__first2)
 148             *__first1 = *__first2;
 149           if (__first2 == __last2)
 150             erase(__first1, __last1);
 151           else
 152             insert(__last1, __first2, __last2);
 153         }
 154       return *this;
 155     }
 156
 157   template<typename _Tp, typename _Alloc>
 158     void
 159     list<_Tp, _Alloc>::
 160     _M_fill_assign(size_type __n, const value_type& __val)
 161     {
 162       iterator __i = begin();
 163       for (; __i != end() && __n > 0; ++__i, --__n)
 164         *__i = __val;
 165       if (__n > 0)
 166         insert(end(), __n, __val);
 167       else
 168         erase(__i, end());
 169     }
 170
 171   template<typename _Tp, typename _Alloc>
 172     template <typename _InputIterator>
 173       void
 174       list<_Tp, _Alloc>::
 175       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 176                          __false_type)
 177       {
 178         iterator __first1 = begin();
 179         iterator __last1 = end();
 180         for (; __first1 != __last1 && __first2 != __last2;
 181              ++__first1, ++__first2)
 182           *__first1 = *__first2;
 183         if (__first2 == __last2)
 184           erase(__first1, __last1);
 185         else
 186           insert(__last1, __first2, __last2);
 187       }
 188
 189   template<typename _Tp, typename _Alloc>
 190     void
 191     list<_Tp, _Alloc>::
 192     remove(const value_type& __value)
 193     {
 194       iterator __first = begin();
 195       iterator __last = end();
 196       iterator __extra = __last;
 197       while (__first != __last)
 198         {
 199           iterator __next = __first;
 200           ++__next;
 201           if (*__first == __value)
 202             {
 203               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 204               // 526. Is it undefined if a function in the standard changes
 205               // in parameters?
 206               if (&*__first != &__value)
 207                 _M_erase(__first);
 208               else
 209                 __extra = __first;
 210             }
 211           __first = __next;
 212         }
 213       if (__extra != __last)
 214         _M_erase(__extra);
 215     }
 216
 217   template<typename _Tp, typename _Alloc>
 218     void
 219     list<_Tp, _Alloc>::
 220     unique()
 221     {
 222       iterator __first = begin();
 223       iterator __last = end();
 224       if (__first == __last)
 225         return;
 226       iterator __next = __first;
 227       while (++__next != __last)
 228         {
 229           if (*__first == *__next)
 230             _M_erase(__next);
 231           else
 232             __first = __next;
 233           __next = __first;
 234         }
 235     }
 236
 237   template<typename _Tp, typename _Alloc>
 238     void
 239     list<_Tp, _Alloc>::
 240 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 241     merge(list&& __x)
 242 #else
 243     merge(list& __x)
 244 #endif
 245     {
 246       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 247       // 300. list::merge() specification incomplete
 248       if (this != &__x)
 249         {
 250           _M_check_equal_allocators(__x);
 251
 252           iterator __first1 = begin();
 253           iterator __last1 = end();
 254           iterator __first2 = __x.begin();
 255           iterator __last2 = __x.end();
 256           while (__first1 != __last1 && __first2 != __last2)
 257             if (*__first2 < *__first1)
 258               {
 259                 iterator __next = __first2;
 260                 _M_transfer(__first1, __first2, ++__next);
 261                 __first2 = __next;
 262               }
 263             else
 264               ++__first1;
 265           if (__first2 != __last2)
 266             _M_transfer(__last1, __first2, __last2);
 267         }
 268     }
 269
 270   template<typename _Tp, typename _Alloc>
 271     template <typename _StrictWeakOrdering>
 272       void
 273       list<_Tp, _Alloc>::
 274 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 275       merge(list&& __x, _StrictWeakOrdering __comp)
 276 #else
 277       merge(list& __x, _StrictWeakOrdering __comp)
 278 #endif
 279       {
 280         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 281         // 300. list::merge() specification incomplete
 282         if (this != &__x)
 283           {
 284             _M_check_equal_allocators(__x);
 285
 286             iterator __first1 = begin();
 287             iterator __last1 = end();
 288             iterator __first2 = __x.begin();
 289             iterator __last2 = __x.end();
 290             while (__first1 != __last1 && __first2 != __last2)
 291               if (__comp(*__first2, *__first1))
 292                 {
 293                   iterator __next = __first2;
 294                   _M_transfer(__first1, __first2, ++__next);
 295                   __first2 = __next;
 296                 }
 297               else
 298                 ++__first1;
 299             if (__first2 != __last2)
 300               _M_transfer(__last1, __first2, __last2);
 301           }
 302       }
 303
 304   template<typename _Tp, typename _Alloc>
 305     void
 306     list<_Tp, _Alloc>::
 307     sort()
 308     {
 309       // Do nothing if the list has length 0 or 1.
 310       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 311           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 312       {
 313         list __carry;
 314         list __tmp[64];
 315         list * __fill = &__tmp[0];
 316         list * __counter;
 317
 318         do
 319           {
 320             __carry.splice(__carry.begin(), *this, begin());
 321
 322             for(__counter = &__tmp[0];
 323                 __counter != __fill && !__counter->empty();
 324                 ++__counter)
 325               {
 326                 __counter->merge(__carry);
 327                 __carry.swap(*__counter);
 328               }
 329             __carry.swap(*__counter);
 330             if (__counter == __fill)
 331               ++__fill;
 332           }
 333         while ( !empty() );
 334
 335         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 336           __counter->merge(*(__counter - 1));
 337         swap( *(__fill - 1) );
 338       }
 339     }
 340
 341   template<typename _Tp, typename _Alloc>
 342     template <typename _Predicate>
 343       void
 344       list<_Tp, _Alloc>::
 345       remove_if(_Predicate __pred)
 346       {
 347         iterator __first = begin();
 348         iterator __last = end();
 349         while (__first != __last)
 350           {
 351             iterator __next = __first;
 352             ++__next;
 353             if (__pred(*__first))
 354               _M_erase(__first);
 355             __first = __next;
 356           }
 357       }
 358
 359   template<typename _Tp, typename _Alloc>
 360     template <typename _BinaryPredicate>
 361       void
 362       list<_Tp, _Alloc>::
 363       unique(_BinaryPredicate __binary_pred)
 364       {
 365         iterator __first = begin();
 366         iterator __last = end();
 367         if (__first == __last)
 368           return;
 369         iterator __next = __first;
 370         while (++__next != __last)
 371           {
 372             if (__binary_pred(*__first, *__next))
 373               _M_erase(__next);
 374             else
 375               __first = __next;
 376             __next = __first;
 377           }
 378       }
 379
 380   template<typename _Tp, typename _Alloc>
 381     template <typename _StrictWeakOrdering>
 382       void
 383       list<_Tp, _Alloc>::
 384       sort(_StrictWeakOrdering __comp)
 385       {
 386         // Do nothing if the list has length 0 or 1.
 387         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 388             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 389           {
 390             list __carry;
 391             list __tmp[64];
 392             list * __fill = &__tmp[0];
 393             list * __counter;
 394
 395             do
 396               {
 397                 __carry.splice(__carry.begin(), *this, begin());
 398
 399                 for(__counter = &__tmp[0];
 400                     __counter != __fill && !__counter->empty();
 401                     ++__counter)
 402                   {
 403                     __counter->merge(__carry, __comp);
 404                     __carry.swap(*__counter);
 405                   }
 406                 __carry.swap(*__counter);
 407                 if (__counter == __fill)
 408                   ++__fill;
 409               }
 410             while ( !empty() );
 411
 412             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 413               __counter->merge(*(__counter - 1), __comp);
 414             swap(*(__fill - 1));
 415           }
 416       }
 417
 418 _GLIBCXX_END_NESTED_NAMESPACE
 419
 420 #endif /* _LIST_TCC */
 421