Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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