l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.7/include/bits/forward_list.tcc

   1 // <forward_list.tcc> -*- C++ -*-
   2
   3 // Copyright (C) 2008, 2009, 2010, 2011 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file bits/forward_list.tcc
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{forward_list}
  28  */
  29
  30 #ifndef _FORWARD_LIST_TCC
  31 #define _FORWARD_LIST_TCC 1
  32
  33 namespace std _GLIBCXX_VISIBILITY(default)
  34 {
  35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  36
  37   template<typename _Tp, typename _Alloc>
  38     _Fwd_list_base<_Tp, _Alloc>::
  39     _Fwd_list_base(const _Fwd_list_base& __lst, const _Node_alloc_type& __a)
  40     : _M_impl(__a)
  41     {
  42       this->_M_impl._M_head._M_next = 0;
  43       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
  44       _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
  45
  46       while (__curr)
  47         {
  48           __to->_M_next = _M_create_node(__curr->_M_value);
  49           __to = __to->_M_next;
  50           __curr = static_cast<_Node*>(__curr->_M_next);
  51         }
  52     }
  53
  54   template<typename _Tp, typename _Alloc>
  55     template<typename... _Args>
  56       _Fwd_list_node_base*
  57       _Fwd_list_base<_Tp, _Alloc>::
  58       _M_insert_after(const_iterator __pos, _Args&&... __args)
  59       {
  60         _Fwd_list_node_base* __to
  61           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
  62         _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
  63         __thing->_M_next = __to->_M_next;
  64         __to->_M_next = __thing;
  65         return __to->_M_next;
  66       }
  67
  68   template<typename _Tp, typename _Alloc>
  69     _Fwd_list_node_base*
  70     _Fwd_list_base<_Tp, _Alloc>::
  71     _M_erase_after(_Fwd_list_node_base* __pos)
  72     {
  73       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
  74       __pos->_M_next = __curr->_M_next;
  75       _M_get_Node_allocator().destroy(__curr);
  76       _M_put_node(__curr);
  77       return __pos->_M_next;
  78     }
  79
  80   template<typename _Tp, typename _Alloc>
  81     _Fwd_list_node_base*
  82     _Fwd_list_base<_Tp, _Alloc>::
  83     _M_erase_after(_Fwd_list_node_base* __pos,
  84                    _Fwd_list_node_base* __last)
  85     {
  86       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
  87       while (__curr != __last)
  88         {
  89           _Node* __temp = __curr;
  90           __curr = static_cast<_Node*>(__curr->_M_next);
  91           _M_get_Node_allocator().destroy(__temp);
  92           _M_put_node(__temp);
  93         }
  94       __pos->_M_next = __last;
  95       return __last;
  96     }
  97
  98   // Called by the range constructor to implement [23.1.1]/9
  99   template<typename _Tp, typename _Alloc>
 100     template<typename _InputIterator>
 101       void
 102       forward_list<_Tp, _Alloc>::
 103       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
 104                              __false_type)
 105       {
 106         _Node_base* __to = &this->_M_impl._M_head;
 107         for (; __first != __last; ++__first)
 108           {
 109             __to->_M_next = this->_M_create_node(*__first);
 110             __to = __to->_M_next;
 111           }
 112       }
 113
 114   // Called by forward_list(n,v,a), and the range constructor
 115   // when it turns out to be the same thing.
 116   template<typename _Tp, typename _Alloc>
 117     void
 118     forward_list<_Tp, _Alloc>::
 119     _M_fill_initialize(size_type __n, const value_type& __value)
 120     {
 121       _Node_base* __to = &this->_M_impl._M_head;
 122       for (; __n; --__n)
 123         {
 124           __to->_M_next = this->_M_create_node(__value);
 125           __to = __to->_M_next;
 126         }
 127     }
 128
 129   template<typename _Tp, typename _Alloc>
 130     void
 131     forward_list<_Tp, _Alloc>::
 132     _M_default_initialize(size_type __n)
 133     {
 134       _Node_base* __to = &this->_M_impl._M_head;
 135       for (; __n; --__n)
 136         {
 137           __to->_M_next = this->_M_create_node();
 138           __to = __to->_M_next;
 139         }
 140     }
 141
 142   template<typename _Tp, typename _Alloc>
 143     forward_list<_Tp, _Alloc>&
 144     forward_list<_Tp, _Alloc>::
 145     operator=(const forward_list& __list)
 146     {
 147       if (&__list != this)
 148         {
 149           iterator __prev1 = before_begin();
 150           iterator __curr1 = begin();
 151           iterator __last1 = end();
 152           const_iterator __first2 = __list.cbegin();
 153           const_iterator __last2 = __list.cend();
 154           while (__curr1 != __last1 && __first2 != __last2)
 155             {
 156               *__curr1 = *__first2;
 157               ++__prev1;
 158               ++__curr1;
 159               ++__first2;
 160             }
 161           if (__first2 == __last2)
 162             erase_after(__prev1, __last1);
 163           else
 164             insert_after(__prev1, __first2, __last2);
 165         }
 166       return *this;
 167     }
 168
 169   template<typename _Tp, typename _Alloc>
 170     void
 171     forward_list<_Tp, _Alloc>::
 172     _M_default_insert_after(const_iterator __pos, size_type __n)
 173     {
 174       const_iterator __saved_pos = __pos;
 175       __try
 176         {
 177           for (; __n; --__n)
 178             __pos = emplace_after(__pos);
 179         }
 180       __catch(...)
 181         {
 182           erase_after(__saved_pos, ++__pos);
 183           __throw_exception_again;
 184         }
 185     }
 186
 187   template<typename _Tp, typename _Alloc>
 188     void
 189     forward_list<_Tp, _Alloc>::
 190     resize(size_type __sz)
 191     {
 192       iterator __k = before_begin();
 193
 194       size_type __len = 0;
 195       while (__k._M_next() != end() && __len < __sz)
 196         {
 197           ++__k;
 198           ++__len;
 199         }
 200       if (__len == __sz)
 201         erase_after(__k, end());
 202       else
 203         _M_default_insert_after(__k, __sz - __len);
 204     }
 205
 206   template<typename _Tp, typename _Alloc>
 207     void
 208     forward_list<_Tp, _Alloc>::
 209     resize(size_type __sz, const value_type& __val)
 210     {
 211       iterator __k = before_begin();
 212
 213       size_type __len = 0;
 214       while (__k._M_next() != end() && __len < __sz)
 215         {
 216           ++__k;
 217           ++__len;
 218         }
 219       if (__len == __sz)
 220         erase_after(__k, end());
 221       else
 222         insert_after(__k, __sz - __len, __val);
 223     }
 224
 225   template<typename _Tp, typename _Alloc>
 226     typename forward_list<_Tp, _Alloc>::iterator
 227     forward_list<_Tp, _Alloc>::
 228     _M_splice_after(const_iterator __pos,
 229                     const_iterator __before, const_iterator __last)
 230     {
 231       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
 232       _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
 233       _Node_base* __end = __b;
 234
 235       while (__end && __end->_M_next != __last._M_node)
 236         __end = __end->_M_next;
 237
 238       if (__b != __end)
 239         return iterator(__tmp->_M_transfer_after(__b, __end));
 240       else
 241         return iterator(__tmp);
 242     }
 243
 244   template<typename _Tp, typename _Alloc>
 245     void
 246     forward_list<_Tp, _Alloc>::
 247     splice_after(const_iterator __pos, forward_list&&,
 248                  const_iterator __i)
 249     {
 250       const_iterator __j = __i;
 251       ++__j;
 252
 253       if (__pos == __i || __pos == __j)
 254         return;
 255
 256       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
 257       __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
 258                                const_cast<_Node_base*>(__j._M_node));
 259     }
 260
 261   template<typename _Tp, typename _Alloc>
 262     typename forward_list<_Tp, _Alloc>::iterator
 263     forward_list<_Tp, _Alloc>::
 264     insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
 265     {
 266       if (__n)
 267         {
 268           forward_list __tmp(__n, __val, get_allocator());
 269           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
 270         }
 271       else
 272         return iterator(const_cast<_Node_base*>(__pos._M_node));
 273     }
 274
 275   template<typename _Tp, typename _Alloc>
 276     template<typename _InputIterator>
 277       typename forward_list<_Tp, _Alloc>::iterator
 278       forward_list<_Tp, _Alloc>::
 279       insert_after(const_iterator __pos,
 280                    _InputIterator __first, _InputIterator __last)
 281       {
 282         forward_list __tmp(__first, __last, get_allocator());
 283         if (!__tmp.empty())
 284           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
 285         else
 286           return iterator(const_cast<_Node_base*>(__pos._M_node));
 287       }
 288
 289   template<typename _Tp, typename _Alloc>
 290     void
 291     forward_list<_Tp, _Alloc>::
 292     remove(const _Tp& __val)
 293     {
 294       _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
 295       _Node* __extra = 0;
 296
 297       while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
 298         {
 299           if (__tmp->_M_value == __val)
 300             {
 301               if (std::__addressof(__tmp->_M_value)
 302                   != std::__addressof(__val))
 303                 {
 304                   this->_M_erase_after(__curr);
 305                   continue;
 306                 }
 307               else
 308                 __extra = __curr;
 309             }
 310           __curr = static_cast<_Node*>(__curr->_M_next);
 311         }
 312
 313       if (__extra)
 314         this->_M_erase_after(__extra);
 315     }
 316
 317   template<typename _Tp, typename _Alloc>
 318     template<typename _Pred>
 319       void
 320       forward_list<_Tp, _Alloc>::
 321       remove_if(_Pred __pred)
 322       {
 323         _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
 324         while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
 325           {
 326             if (__pred(__tmp->_M_value))
 327               this->_M_erase_after(__curr);
 328             else
 329               __curr = static_cast<_Node*>(__curr->_M_next);
 330           }
 331       }
 332
 333   template<typename _Tp, typename _Alloc>
 334     template<typename _BinPred>
 335       void
 336       forward_list<_Tp, _Alloc>::
 337       unique(_BinPred __binary_pred)
 338       {
 339         iterator __first = begin();
 340         iterator __last = end();
 341         if (__first == __last)
 342           return;
 343         iterator __next = __first;
 344         while (++__next != __last)
 345         {
 346           if (__binary_pred(*__first, *__next))
 347             erase_after(__first);
 348           else
 349             __first = __next;
 350           __next = __first;
 351         }
 352       }
 353
 354   template<typename _Tp, typename _Alloc>
 355     template<typename _Comp>
 356       void
 357       forward_list<_Tp, _Alloc>::
 358       merge(forward_list&& __list, _Comp __comp)
 359       {
 360         _Node_base* __node = &this->_M_impl._M_head;
 361         while (__node->_M_next && __list._M_impl._M_head._M_next)
 362           {
 363             if (__comp(static_cast<_Node*>
 364                        (__list._M_impl._M_head._M_next)->_M_value,
 365                        static_cast<_Node*>
 366                        (__node->_M_next)->_M_value))
 367               __node->_M_transfer_after(&__list._M_impl._M_head,
 368                                         __list._M_impl._M_head._M_next);
 369             __node = __node->_M_next;
 370           }
 371         if (__list._M_impl._M_head._M_next)
 372           {
 373             __node->_M_next = __list._M_impl._M_head._M_next;
 374             __list._M_impl._M_head._M_next = 0;
 375           }
 376       }
 377
 378   template<typename _Tp, typename _Alloc>
 379     bool
 380     operator==(const forward_list<_Tp, _Alloc>& __lx,
 381                const forward_list<_Tp, _Alloc>& __ly)
 382     {
 383       //  We don't have size() so we need to walk through both lists
 384       //  making sure both iterators are valid.
 385       auto __ix = __lx.cbegin();
 386       auto __iy = __ly.cbegin();
 387       while (__ix != __lx.cend() && __iy != __ly.cend())
 388         {
 389           if (*__ix != *__iy)
 390             return false;
 391           ++__ix;
 392           ++__iy;
 393         }
 394       if (__ix == __lx.cend() && __iy == __ly.cend())
 395         return true;
 396       else
 397         return false;
 398     }
 399
 400   template<typename _Tp, class _Alloc>
 401     template<typename _Comp>
 402       void
 403       forward_list<_Tp, _Alloc>::
 404       sort(_Comp __comp)
 405       {
 406         // If `next' is 0, return immediately.
 407         _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
 408         if (!__list)
 409           return;
 410
 411         unsigned long __insize = 1;
 412
 413         while (1)
 414           {
 415             _Node* __p = __list;
 416             __list = 0;
 417             _Node* __tail = 0;
 418
 419             // Count number of merges we do in this pass.
 420             unsigned long __nmerges = 0;
 421
 422             while (__p)
 423               {
 424                 ++__nmerges;
 425                 // There exists a merge to be done.
 426                 // Step `insize' places along from p.
 427                 _Node* __q = __p;
 428                 unsigned long __psize = 0;
 429                 for (unsigned long __i = 0; __i < __insize; ++__i)
 430                   {
 431                     ++__psize;
 432                     __q = static_cast<_Node*>(__q->_M_next);
 433                     if (!__q)
 434                       break;
 435                   }
 436
 437                 // If q hasn't fallen off end, we have two lists to merge.
 438                 unsigned long __qsize = __insize;
 439
 440                 // Now we have two lists; merge them.
 441                 while (__psize > 0 || (__qsize > 0 && __q))
 442                   {
 443                     // Decide whether next node of merge comes from p or q.
 444                     _Node* __e;
 445                     if (__psize == 0)
 446                       {
 447                         // p is empty; e must come from q.
 448                         __e = __q;
 449                         __q = static_cast<_Node*>(__q->_M_next);
 450                         --__qsize;
 451                       }
 452                     else if (__qsize == 0 || !__q)
 453                       {
 454                         // q is empty; e must come from p.
 455                         __e = __p;
 456                         __p = static_cast<_Node*>(__p->_M_next);
 457                         --__psize;
 458                       }
 459                     else if (__comp(__p->_M_value, __q->_M_value))
 460                       {
 461                         // First node of p is lower; e must come from p.
 462                         __e = __p;
 463                         __p = static_cast<_Node*>(__p->_M_next);
 464                         --__psize;
 465                       }
 466                     else
 467                       {
 468                         // First node of q is lower; e must come from q.
 469                         __e = __q;
 470                         __q = static_cast<_Node*>(__q->_M_next);
 471                         --__qsize;
 472                       }
 473
 474                     // Add the next node to the merged list.
 475                     if (__tail)
 476                       __tail->_M_next = __e;
 477                     else
 478                       __list = __e;
 479                     __tail = __e;
 480                   }
 481
 482                 // Now p has stepped `insize' places along, and q has too.
 483                 __p = __q;
 484               }
 485             __tail->_M_next = 0;
 486
 487             // If we have done only one merge, we're finished.
 488             // Allow for nmerges == 0, the empty list case.
 489             if (__nmerges <= 1)
 490               {
 491                 this->_M_impl._M_head._M_next = __list;
 492                 return;
 493               }
 494
 495             // Otherwise repeat, merging lists twice the size.
 496             __insize *= 2;
 497           }
 498       }
 499
 500 _GLIBCXX_END_NAMESPACE_CONTAINER
 501 } // namespace std
 502
 503 #endif /* _FORWARD_LIST_TCC */
 504