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

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