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

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