contrib/libstdc++/include/bits/list.tcc

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
   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       while (__first != __last)
 180         {
 181           iterator __next = __first;
 182           ++__next;
 183           if (*__first == __value)
 184             _M_erase(__first);
 185           __first = __next;
 186         }
 187     }
 188
 189   template<typename _Tp, typename _Alloc>
 190     void
 191     list<_Tp, _Alloc>::
 192     unique()
 193     {
 194       iterator __first = begin();
 195       iterator __last = end();
 196       if (__first == __last)
 197         return;
 198       iterator __next = __first;
 199       while (++__next != __last)
 200         {
 201           if (*__first == *__next)
 202             _M_erase(__next);
 203           else
 204             __first = __next;
 205           __next = __first;
 206         }
 207     }
 208
 209   template<typename _Tp, typename _Alloc>
 210     void
 211     list<_Tp, _Alloc>::
 212     merge(list& __x)
 213     {
 214       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 215       // 300. list::merge() specification incomplete
 216       if (this != &__x)
 217         {
 218           _M_check_equal_allocators(__x);
 219
 220           iterator __first1 = begin();
 221           iterator __last1 = end();
 222           iterator __first2 = __x.begin();
 223           iterator __last2 = __x.end();
 224           while (__first1 != __last1 && __first2 != __last2)
 225             if (*__first2 < *__first1)
 226               {
 227                 iterator __next = __first2;
 228                 _M_transfer(__first1, __first2, ++__next);
 229                 __first2 = __next;
 230               }
 231             else
 232               ++__first1;
 233           if (__first2 != __last2)
 234             _M_transfer(__last1, __first2, __last2);
 235         }
 236     }
 237
 238   template<typename _Tp, typename _Alloc>
 239     template <typename _StrictWeakOrdering>
 240       void
 241       list<_Tp, _Alloc>::
 242       merge(list& __x, _StrictWeakOrdering __comp)
 243       {
 244         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 245         // 300. list::merge() specification incomplete
 246         if (this != &__x)
 247           {
 248             _M_check_equal_allocators(__x);
 249
 250             iterator __first1 = begin();
 251             iterator __last1 = end();
 252             iterator __first2 = __x.begin();
 253             iterator __last2 = __x.end();
 254             while (__first1 != __last1 && __first2 != __last2)
 255               if (__comp(*__first2, *__first1))
 256                 {
 257                   iterator __next = __first2;
 258                   _M_transfer(__first1, __first2, ++__next);
 259                   __first2 = __next;
 260                 }
 261               else
 262                 ++__first1;
 263             if (__first2 != __last2)
 264               _M_transfer(__last1, __first2, __last2);
 265           }
 266       }
 267
 268   template<typename _Tp, typename _Alloc>
 269     void
 270     list<_Tp, _Alloc>::
 271     sort()
 272     {
 273       // Do nothing if the list has length 0 or 1.
 274       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 275           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 276       {
 277         list __carry;
 278         list __tmp[64];
 279         list * __fill = &__tmp[0];
 280         list * __counter;
 281
 282         do
 283           {
 284             __carry.splice(__carry.begin(), *this, begin());
 285
 286             for(__counter = &__tmp[0];
 287                 __counter != __fill && !__counter->empty();
 288                 ++__counter)
 289               {
 290                 __counter->merge(__carry);
 291                 __carry.swap(*__counter);
 292               }
 293             __carry.swap(*__counter);
 294             if (__counter == __fill)
 295               ++__fill;
 296           }
 297         while ( !empty() );
 298
 299         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 300           __counter->merge(*(__counter - 1));
 301         swap( *(__fill - 1) );
 302       }
 303     }
 304
 305   template<typename _Tp, typename _Alloc>
 306     template <typename _Predicate>
 307       void
 308       list<_Tp, _Alloc>::
 309       remove_if(_Predicate __pred)
 310       {
 311         iterator __first = begin();
 312         iterator __last = end();
 313         while (__first != __last)
 314           {
 315             iterator __next = __first;
 316             ++__next;
 317             if (__pred(*__first))
 318               _M_erase(__first);
 319             __first = __next;
 320           }
 321       }
 322
 323   template<typename _Tp, typename _Alloc>
 324     template <typename _BinaryPredicate>
 325       void
 326       list<_Tp, _Alloc>::
 327       unique(_BinaryPredicate __binary_pred)
 328       {
 329         iterator __first = begin();
 330         iterator __last = end();
 331         if (__first == __last)
 332           return;
 333         iterator __next = __first;
 334         while (++__next != __last)
 335           {
 336             if (__binary_pred(*__first, *__next))
 337               _M_erase(__next);
 338             else
 339               __first = __next;
 340             __next = __first;
 341           }
 342       }
 343
 344   template<typename _Tp, typename _Alloc>
 345     template <typename _StrictWeakOrdering>
 346       void
 347       list<_Tp, _Alloc>::
 348       sort(_StrictWeakOrdering __comp)
 349       {
 350         // Do nothing if the list has length 0 or 1.
 351         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 352             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 353           {
 354             list __carry;
 355             list __tmp[64];
 356             list * __fill = &__tmp[0];
 357             list * __counter;
 358
 359             do
 360               {
 361                 __carry.splice(__carry.begin(), *this, begin());
 362
 363                 for(__counter = &__tmp[0];
 364                     __counter != __fill && !__counter->empty();
 365                     ++__counter)
 366                   {
 367                     __counter->merge(__carry, __comp);
 368                     __carry.swap(*__counter);
 369                   }
 370                 __carry.swap(*__counter);
 371                 if (__counter == __fill)
 372                   ++__fill;
 373               }
 374             while ( !empty() );
 375
 376             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 377               __counter->merge(*(__counter - 1), __comp);
 378             swap(*(__fill - 1));
 379           }
 380       }
 381
 382 _GLIBCXX_END_NESTED_NAMESPACE
 383
 384 #endif /* _LIST_TCC */
 385