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

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