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

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   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)
  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           _M_get_Tp_allocator().destroy(&__tmp->_M_data);
  79           _M_put_node(__tmp);
  80         }
  81     }
  82
  83   template<typename _Tp, typename _Alloc>
  84     typename list<_Tp, _Alloc>::iterator
  85     list<_Tp, _Alloc>::
  86     insert(iterator __position, const value_type& __x)
  87     {
  88       _Node* __tmp = _M_create_node(__x);
  89       __tmp->hook(__position._M_node);
  90       return iterator(__tmp);
  91     }
  92
  93   template<typename _Tp, typename _Alloc>
  94     typename list<_Tp, _Alloc>::iterator
  95     list<_Tp, _Alloc>::
  96     erase(iterator __position)
  97     {
  98       iterator __ret = iterator(__position._M_node->_M_next);
  99       _M_erase(__position);
 100       return __ret;
 101     }
 102
 103   template<typename _Tp, typename _Alloc>
 104     void
 105     list<_Tp, _Alloc>::
 106     resize(size_type __new_size, value_type __x)
 107     {
 108       iterator __i = begin();
 109       size_type __len = 0;
 110       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 111         ;
 112       if (__len == __new_size)
 113         erase(__i, end());
 114       else                          // __i == end()
 115         insert(end(), __new_size - __len, __x);
 116     }
 117
 118   template<typename _Tp, typename _Alloc>
 119     list<_Tp, _Alloc>&
 120     list<_Tp, _Alloc>::
 121     operator=(const list& __x)
 122     {
 123       if (this != &__x)
 124         {
 125           iterator __first1 = begin();
 126           iterator __last1 = end();
 127           const_iterator __first2 = __x.begin();
 128           const_iterator __last2 = __x.end();
 129           for (; __first1 != __last1 && __first2 != __last2;
 130                ++__first1, ++__first2)
 131             *__first1 = *__first2;
 132           if (__first2 == __last2)
 133             erase(__first1, __last1);
 134           else
 135             insert(__last1, __first2, __last2);
 136         }
 137       return *this;
 138     }
 139
 140   template<typename _Tp, typename _Alloc>
 141     void
 142     list<_Tp, _Alloc>::
 143     _M_fill_assign(size_type __n, const value_type& __val)
 144     {
 145       iterator __i = begin();
 146       for (; __i != end() && __n > 0; ++__i, --__n)
 147         *__i = __val;
 148       if (__n > 0)
 149         insert(end(), __n, __val);
 150       else
 151         erase(__i, end());
 152     }
 153
 154   template<typename _Tp, typename _Alloc>
 155     template <typename _InputIterator>
 156       void
 157       list<_Tp, _Alloc>::
 158       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 159                          __false_type)
 160       {
 161         iterator __first1 = begin();
 162         iterator __last1 = end();
 163         for (; __first1 != __last1 && __first2 != __last2;
 164              ++__first1, ++__first2)
 165           *__first1 = *__first2;
 166         if (__first2 == __last2)
 167           erase(__first1, __last1);
 168         else
 169           insert(__last1, __first2, __last2);
 170       }
 171
 172   template<typename _Tp, typename _Alloc>
 173     void
 174     list<_Tp, _Alloc>::
 175     remove(const value_type& __value)
 176     {
 177       iterator __first = begin();
 178       iterator __last = end();
 179       iterator __extra = __last;
 180       while (__first != __last)
 181         {
 182           iterator __next = __first;
 183           ++__next;
 184           if (*__first == __value)
 185             {
 186               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 187               // 526. Is it undefined if a function in the standard changes
 188               // in parameters?
 189               if (&*__first != &__value)
 190                 _M_erase(__first);
 191               else
 192                 __extra = __first;
 193             }
 194           __first = __next;
 195         }
 196       if (__extra != __last)
 197         _M_erase(__extra);
 198     }
 199
 200   template<typename _Tp, typename _Alloc>
 201     void
 202     list<_Tp, _Alloc>::
 203     unique()
 204     {
 205       iterator __first = begin();
 206       iterator __last = end();
 207       if (__first == __last)
 208         return;
 209       iterator __next = __first;
 210       while (++__next != __last)
 211         {
 212           if (*__first == *__next)
 213             _M_erase(__next);
 214           else
 215             __first = __next;
 216           __next = __first;
 217         }
 218     }
 219
 220   template<typename _Tp, typename _Alloc>
 221     void
 222     list<_Tp, _Alloc>::
 223     merge(list& __x)
 224     {
 225       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 226       // 300. list::merge() specification incomplete
 227       if (this != &__x)
 228         {
 229           _M_check_equal_allocators(__x);
 230
 231           iterator __first1 = begin();
 232           iterator __last1 = end();
 233           iterator __first2 = __x.begin();
 234           iterator __last2 = __x.end();
 235           while (__first1 != __last1 && __first2 != __last2)
 236             if (*__first2 < *__first1)
 237               {
 238                 iterator __next = __first2;
 239                 _M_transfer(__first1, __first2, ++__next);
 240                 __first2 = __next;
 241               }
 242             else
 243               ++__first1;
 244           if (__first2 != __last2)
 245             _M_transfer(__last1, __first2, __last2);
 246         }
 247     }
 248
 249   template<typename _Tp, typename _Alloc>
 250     template <typename _StrictWeakOrdering>
 251       void
 252       list<_Tp, _Alloc>::
 253       merge(list& __x, _StrictWeakOrdering __comp)
 254       {
 255         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 256         // 300. list::merge() specification incomplete
 257         if (this != &__x)
 258           {
 259             _M_check_equal_allocators(__x);
 260
 261             iterator __first1 = begin();
 262             iterator __last1 = end();
 263             iterator __first2 = __x.begin();
 264             iterator __last2 = __x.end();
 265             while (__first1 != __last1 && __first2 != __last2)
 266               if (__comp(*__first2, *__first1))
 267                 {
 268                   iterator __next = __first2;
 269                   _M_transfer(__first1, __first2, ++__next);
 270                   __first2 = __next;
 271                 }
 272               else
 273                 ++__first1;
 274             if (__first2 != __last2)
 275               _M_transfer(__last1, __first2, __last2);
 276           }
 277       }
 278
 279   template<typename _Tp, typename _Alloc>
 280     void
 281     list<_Tp, _Alloc>::
 282     sort()
 283     {
 284       // Do nothing if the list has length 0 or 1.
 285       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 286           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 287       {
 288         list __carry;
 289         list __tmp[64];
 290         list * __fill = &__tmp[0];
 291         list * __counter;
 292
 293         do
 294           {
 295             __carry.splice(__carry.begin(), *this, begin());
 296
 297             for(__counter = &__tmp[0];
 298                 __counter != __fill && !__counter->empty();
 299                 ++__counter)
 300               {
 301                 __counter->merge(__carry);
 302                 __carry.swap(*__counter);
 303               }
 304             __carry.swap(*__counter);
 305             if (__counter == __fill)
 306               ++__fill;
 307           }
 308         while ( !empty() );
 309
 310         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 311           __counter->merge(*(__counter - 1));
 312         swap( *(__fill - 1) );
 313       }
 314     }
 315
 316   template<typename _Tp, typename _Alloc>
 317     template <typename _Predicate>
 318       void
 319       list<_Tp, _Alloc>::
 320       remove_if(_Predicate __pred)
 321       {
 322         iterator __first = begin();
 323         iterator __last = end();
 324         while (__first != __last)
 325           {
 326             iterator __next = __first;
 327             ++__next;
 328             if (__pred(*__first))
 329               _M_erase(__first);
 330             __first = __next;
 331           }
 332       }
 333
 334   template<typename _Tp, typename _Alloc>
 335     template <typename _BinaryPredicate>
 336       void
 337       list<_Tp, _Alloc>::
 338       unique(_BinaryPredicate __binary_pred)
 339       {
 340         iterator __first = begin();
 341         iterator __last = end();
 342         if (__first == __last)
 343           return;
 344         iterator __next = __first;
 345         while (++__next != __last)
 346           {
 347             if (__binary_pred(*__first, *__next))
 348               _M_erase(__next);
 349             else
 350               __first = __next;
 351             __next = __first;
 352           }
 353       }
 354
 355   template<typename _Tp, typename _Alloc>
 356     template <typename _StrictWeakOrdering>
 357       void
 358       list<_Tp, _Alloc>::
 359       sort(_StrictWeakOrdering __comp)
 360       {
 361         // Do nothing if the list has length 0 or 1.
 362         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 363             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 364           {
 365             list __carry;
 366             list __tmp[64];
 367             list * __fill = &__tmp[0];
 368             list * __counter;
 369
 370             do
 371               {
 372                 __carry.splice(__carry.begin(), *this, begin());
 373
 374                 for(__counter = &__tmp[0];
 375                     __counter != __fill && !__counter->empty();
 376                     ++__counter)
 377                   {
 378                     __counter->merge(__carry, __comp);
 379                     __carry.swap(*__counter);
 380                   }
 381                 __carry.swap(*__counter);
 382                 if (__counter == __fill)
 383                   ++__fill;
 384               }
 385             while ( !empty() );
 386
 387             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 388               __counter->merge(*(__counter - 1), __comp);
 389             swap(*(__fill - 1));
 390           }
 391       }
 392
 393 _GLIBCXX_END_NESTED_NAMESPACE
 394
 395 #endif /* _LIST_TCC */
 396