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, class _Alloc>
  45     template<typename _Comp>
  46       void
  47       _Fwd_list_node<_Tp, _Alloc>::
  48       _M_sort_after(_Comp __comp)
  49       {
  50         // If `next' is 0, return immediately.
  51         _Pointer __list = __static_pointer_cast<_Pointer>(this->_M_next);
  52         if (!__list)
  53           return;
  54
  55         unsigned long __insize = 1;
  56
  57         while (1)
  58           {
  59             _Pointer __p = __list;
  60             __list = 0;
  61             _Pointer __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                 _Pointer __q = __p;
  72                 unsigned long __psize = 0;
  73                 for (unsigned long __i = 0; __i < __insize; ++__i)
  74                   {
  75                     ++__psize;
  76                     __q = __static_pointer_cast<_Pointer>(__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                     _Pointer __e;
  89                     if (__psize == 0)
  90                       {
  91                         // p is empty; e must come from q.
  92                         __e = __q;
  93                         __q = __static_pointer_cast<_Pointer>(__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_pointer_cast<_Pointer>(__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_pointer_cast<_Pointer>(__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_pointer_cast<_Pointer>(__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       typename _Node_base::_Pointer __to = &this->_M_impl._M_head;
 151       typename _Node::_Pointer __curr
 152         = __static_pointer_cast<typename _Node::_Pointer>
 153                                (__lst._M_impl._M_head._M_next);
 154       while (__curr)
 155         {
 156           __to->_M_next = _M_create_node(__curr->_M_value);
 157           __to = __to->_M_next;
 158           __curr = __static_pointer_cast<typename _Node::_Pointer>
 159                                         (__curr->_M_next);
 160         }
 161     }
 162
 163   template<typename _Tp, typename _Alloc>
 164     template<typename... _Args>
 165       typename _Fwd_list_base<_Tp, _Alloc>::_Node_base::_Pointer
 166       _Fwd_list_base<_Tp, _Alloc>::
 167       _M_insert_after(const_iterator __pos, _Args&&... __args)
 168       {
 169         typename _Node_base::_Pointer __to
 170           = __const_pointer_cast<typename _Node_base::_Pointer>
 171                                 (__pos._M_node);
 172         typename _Node::_Pointer __thing
 173           = __static_pointer_cast<typename _Node::_Pointer>(
 174                 _M_create_node(std::forward<_Args>(__args)...) );
 175         __thing->_M_next = __to->_M_next;
 176         __to->_M_next = __thing;
 177         return __static_pointer_cast<typename _Node_base::_Pointer>
 178                                     (__to->_M_next);
 179       }
 180
 181   template<typename _Tp, typename _Alloc>
 182     typename _Fwd_list_base<_Tp, _Alloc>::_Node_base::_Pointer
 183     _Fwd_list_base<_Tp, _Alloc>::
 184     _M_erase_after(typename _Node_base::_Pointer __pos)
 185     {
 186       typename _Node::_Pointer __curr
 187         = __static_pointer_cast<typename _Node::_Pointer>(__pos->_M_next);
 188       if (__curr)
 189         {
 190           typename _Node_base::_Pointer __next = __curr->_M_next;
 191           __pos->_M_next = __next;
 192           _M_get_Node_allocator().destroy(__curr);
 193           _M_put_node(__curr);
 194         }
 195       return __pos;
 196     }
 197
 198   template<typename _Tp, typename _Alloc>
 199     typename _Fwd_list_base<_Tp, _Alloc>::_Node_base::_Pointer
 200     _Fwd_list_base<_Tp, _Alloc>::
 201     _M_erase_after(typename _Node_base::_Pointer __pos,
 202                    typename _Node_base::_Pointer __last)
 203     {
 204       typename _Node::_Pointer __curr
 205         = __static_pointer_cast<typename _Node::_Pointer>(__pos->_M_next);
 206       while (__curr)
 207         {
 208           typename _Node::_Pointer __temp = __curr;
 209           __curr = __static_pointer_cast<typename _Node::_Pointer>
 210                                         (__curr->_M_next);
 211           _M_get_Node_allocator().destroy(__temp);
 212           _M_put_node(__temp);
 213           __pos->_M_next = __curr;
 214           if (__temp == __last)
 215             break;
 216         }
 217       return __pos;
 218     }
 219
 220   // Called by the range constructor to implement [23.1.1]/9
 221   template<typename _Tp, typename _Alloc>
 222     template<typename _InputIterator>
 223       void
 224       forward_list<_Tp, _Alloc>::
 225       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
 226                              __false_type)
 227       {
 228         typename _Node_base::_Pointer __to = &this->_M_impl._M_head;
 229         for (; __first != __last; ++__first)
 230           {
 231             __to->_M_next = this->_M_create_node(*__first);
 232             __to = __to->_M_next;
 233           }
 234       }
 235
 236   // Called by forward_list(n,v,a), and the range constructor
 237   // when it turns out to be the same thing.
 238   template<typename _Tp, typename _Alloc>
 239     void
 240     forward_list<_Tp, _Alloc>::
 241     _M_fill_initialize(size_type __n, const value_type& __value)
 242     {
 243       typename _Node_base::_Pointer __to = &this->_M_impl._M_head;
 244       for (; __n > 0; --__n)
 245         {
 246           __to->_M_next = this->_M_create_node(__value);
 247           __to = __to->_M_next;
 248         }
 249     }
 250
 251   template<typename _Tp, typename _Alloc>
 252     forward_list<_Tp, _Alloc>&
 253     forward_list<_Tp, _Alloc>::
 254     operator=(const forward_list& __list)
 255     {
 256       if (&__list != this)
 257         {
 258           iterator __prev1 = before_begin();
 259           iterator __curr1 = begin();
 260           iterator __last1 = end();
 261           const_iterator __first2 = __list.cbegin();
 262           const_iterator __last2 = __list.cend();
 263           while (__curr1 != __last1 && __first2 != __last2)
 264             {
 265               *__curr1 = *__first2;
 266               ++__prev1;
 267               ++__curr1;
 268               ++__first2;
 269             }
 270           if (__first2 == __last2)
 271             erase_after(__prev1, __last1);
 272           else
 273             insert_after(__prev1, __first2, __last2);
 274         }
 275       return *this;
 276     }
 277
 278   template<typename _Tp, typename _Alloc>
 279     void
 280     forward_list<_Tp, _Alloc>::
 281     resize(size_type __sz, value_type __val)
 282     {
 283       iterator __k = before_begin();
 284
 285       size_type __len = 0;
 286       while (__k._M_next() != end() && __len < __sz)
 287         {
 288           ++__k;
 289           ++__len;
 290         }
 291       if (__len == __sz)
 292         erase_after(__k, end());
 293       else
 294         insert_after(__k, __sz - __len, __val);
 295     }
 296
 297   template<typename _Tp, typename _Alloc>
 298     void
 299     forward_list<_Tp, _Alloc>::
 300     splice_after(const_iterator __pos, forward_list&& __list)
 301     {
 302       if (!__list.empty() && &__list != this)
 303         {
 304           typename _Node_base::_Pointer __tmp
 305             = __const_pointer_cast<typename _Node_base::_Pointer>
 306                                   (__pos._M_node);
 307           const_iterator __before = __list.cbefore_begin();
 308           __tmp->_M_transfer_after(__const_pointer_cast
 309                                      <typename _Node_base::_Pointer>
 310                                      (__before._M_node));
 311         }
 312     }
 313
 314   template<typename _Tp, typename _Alloc>
 315     void
 316     forward_list<_Tp, _Alloc>::
 317     splice_after(const_iterator __pos, forward_list&& __list,
 318                  const_iterator __before, const_iterator __last)
 319     {
 320       typename _Node_base::_Pointer __tmp
 321         = __const_pointer_cast<typename _Node_base::_Pointer>(__pos._M_node);
 322       __tmp->_M_transfer_after(__const_pointer_cast
 323                                  <typename _Node_base::_Pointer>
 324                                  (__before._M_node),
 325                                __const_pointer_cast
 326                                  <typename _Node_base::_Pointer>
 327                                  (__last._M_node));
 328     }
 329
 330   template<typename _Tp, typename _Alloc>
 331     void
 332     forward_list<_Tp, _Alloc>::
 333     remove(const _Tp& __val)
 334     {
 335       typename _Node::_Pointer __curr
 336         = __static_pointer_cast<typename _Node::_Pointer>
 337                                (&this->_M_impl._M_head);
 338       while (typename _Node::_Pointer __temp =
 339              __static_pointer_cast<typename _Node::_Pointer>(__curr->_M_next))
 340         {
 341           if (__temp->_M_value == __val)
 342             this->_M_erase_after(__curr);
 343           else
 344             __curr = __static_pointer_cast<typename _Node::_Pointer>
 345                                           (__curr->_M_next);
 346         }
 347     }
 348
 349   template<typename _Tp, typename _Alloc>
 350     template<typename _Pred>
 351       void
 352       forward_list<_Tp, _Alloc>::
 353       remove_if(_Pred __pred)
 354       {
 355         typename _Node::_Pointer __curr
 356           = __static_pointer_cast<typename _Node::_Pointer>
 357                                  (&this->_M_impl._M_head);
 358         while (typename _Node::_Pointer __temp =
 359                __static_pointer_cast<typename _Node::_Pointer>(__curr->_M_next))
 360           {
 361             if (__pred(__temp->_M_value))
 362               this->_M_erase_after(__curr);
 363             else
 364               __curr = __static_pointer_cast<typename _Node::_Pointer>
 365                                             (__curr->_M_next);
 366           }
 367       }
 368
 369   template<typename _Tp, typename _Alloc>
 370     template<typename _BinPred>
 371       void
 372       forward_list<_Tp, _Alloc>::
 373       unique(_BinPred __binary_pred)
 374       {
 375         iterator __first = begin();
 376         iterator __last = end();
 377         if (__first == __last)
 378           return;
 379         iterator __next = __first;
 380         while (++__next != __last)
 381         {
 382           if (__binary_pred(*__first, *__next))
 383             erase_after(__first);
 384           else
 385             __first = __next;
 386           __next = __first;
 387         }
 388       }
 389
 390   template<typename _Tp, typename _Alloc>
 391     template<typename _Comp>
 392       void
 393       forward_list<_Tp, _Alloc>::
 394       merge(forward_list&& __list, _Comp __comp)
 395       {
 396         typename _Node_base::_Pointer __node = &this->_M_impl._M_head;
 397         while (__node->_M_next && __list._M_impl._M_head._M_next)
 398           {
 399             if (__comp(__static_pointer_cast<typename _Node::_Pointer>
 400                        (__list._M_impl._M_head._M_next)->_M_value,
 401                        __static_pointer_cast<typename _Node::_Pointer>
 402                        (__node->_M_next)->_M_value))
 403               __node->_M_transfer_after(&__list._M_impl._M_head,
 404                                         __list._M_impl._M_head._M_next);
 405             __node = __node->_M_next;
 406           }
 407         if (__list._M_impl._M_head._M_next)
 408           {
 409             __node->_M_next = __list._M_impl._M_head._M_next;
 410             __list._M_impl._M_head._M_next = 0;
 411           }
 412       }
 413
 414   template<typename _Tp, typename _Alloc>
 415     void
 416     forward_list<_Tp, _Alloc>::
 417     reverse()
 418     { this->_M_impl._M_head._M_reverse_after(); }
 419
 420   template<typename _Tp, typename _Alloc>
 421     bool
 422     operator==(const forward_list<_Tp, _Alloc>& __lx,
 423                const forward_list<_Tp, _Alloc>& __ly)
 424     {
 425       //  We don't have size() so we need to walk through both lists
 426       //  making sure both iterators are valid.
 427       auto __ix = __lx.cbegin();
 428       auto __iy = __ly.cbegin();
 429       while (__ix != __lx.cend() && __iy != __ly.cend())
 430         {
 431           if (*__ix != *__iy)
 432             return false;
 433           ++__ix;
 434           ++__iy;
 435         }
 436       if (__ix == __lx.cend() && __iy == __ly.cend())
 437         return true;
 438       else
 439         return false;
 440     }
 441
 442 _GLIBCXX_END_NAMESPACE // namespace std
 443
 444 #endif /* _FORWARD_LIST_TCC */
 445