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