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

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