gnu/dist/gcc4/libstdc++-v3/include/bits/list.tcc

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