Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // List implementation (out of line) -*- C++ -*-
  2.  
  3. // Copyright (C) 2001-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. /*
  26.  *
  27.  * Copyright (c) 1994
  28.  * Hewlett-Packard Company
  29.  *
  30.  * Permission to use, copy, modify, distribute and sell this software
  31.  * and its documentation for any purpose is hereby granted without fee,
  32.  * provided that the above copyright notice appear in all copies and
  33.  * that both that copyright notice and this permission notice appear
  34.  * in supporting documentation.  Hewlett-Packard Company makes no
  35.  * representations about the suitability of this software for any
  36.  * purpose.  It is provided "as is" without express or implied warranty.
  37.  *
  38.  *
  39.  * Copyright (c) 1996,1997
  40.  * Silicon Graphics Computer Systems, Inc.
  41.  *
  42.  * Permission to use, copy, modify, distribute and sell this software
  43.  * and its documentation for any purpose is hereby granted without fee,
  44.  * provided that the above copyright notice appear in all copies and
  45.  * that both that copyright notice and this permission notice appear
  46.  * in supporting documentation.  Silicon Graphics makes no
  47.  * representations about the suitability of this software for any
  48.  * purpose.  It is provided "as is" without express or implied warranty.
  49.  */
  50.  
  51. /** @file bits/list.tcc
  52.  *  This is an internal header file, included by other library headers.
  53.  *  Do not attempt to use it directly. @headername{list}
  54.  */
  55.  
  56. #ifndef _LIST_TCC
  57. #define _LIST_TCC 1
  58.  
  59. namespace std _GLIBCXX_VISIBILITY(default)
  60. {
  61. _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  62.  
  63.   template<typename _Tp, typename _Alloc>
  64.     void
  65.     _List_base<_Tp, _Alloc>::
  66.     _M_clear() _GLIBCXX_NOEXCEPT
  67.     {
  68.       typedef _List_node<_Tp>  _Node;
  69.       __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
  70.       while (__cur != &_M_impl._M_node)
  71.         {
  72.           _Node* __tmp = static_cast<_Node*>(__cur);
  73.           __cur = __tmp->_M_next;
  74. #if __cplusplus >= 201103L
  75.           _M_get_Node_allocator().destroy(__tmp);
  76. #else
  77.           _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
  78. #endif
  79.           _M_put_node(__tmp);
  80.         }
  81.     }
  82.  
  83. #if __cplusplus >= 201103L
  84.   template<typename _Tp, typename _Alloc>
  85.     template<typename... _Args>
  86.       typename list<_Tp, _Alloc>::iterator
  87.       list<_Tp, _Alloc>::
  88.       emplace(const_iterator __position, _Args&&... __args)
  89.       {
  90.         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
  91.         __tmp->_M_hook(__position._M_const_cast()._M_node);
  92.         this->_M_inc_size(1);
  93.         return iterator(__tmp);
  94.       }
  95. #endif
  96.  
  97.   template<typename _Tp, typename _Alloc>
  98.     typename list<_Tp, _Alloc>::iterator
  99.     list<_Tp, _Alloc>::
  100. #if __cplusplus >= 201103L
  101.     insert(const_iterator __position, const value_type& __x)
  102. #else
  103.     insert(iterator __position, const value_type& __x)
  104. #endif
  105.     {
  106.       _Node* __tmp = _M_create_node(__x);
  107.       __tmp->_M_hook(__position._M_const_cast()._M_node);
  108.       this->_M_inc_size(1);
  109.       return iterator(__tmp);
  110.     }
  111.  
  112. #if __cplusplus >= 201103L
  113.   template<typename _Tp, typename _Alloc>
  114.     typename list<_Tp, _Alloc>::iterator
  115.     list<_Tp, _Alloc>::
  116.     insert(const_iterator __position, size_type __n, const value_type& __x)
  117.     {
  118.       if (__n)
  119.         {
  120.           list __tmp(__n, __x, get_allocator());
  121.           iterator __it = __tmp.begin();
  122.           splice(__position, __tmp);
  123.           return __it;
  124.         }
  125.       return __position._M_const_cast();
  126.     }
  127.  
  128.   template<typename _Tp, typename _Alloc>
  129.     template<typename _InputIterator, typename>
  130.       typename list<_Tp, _Alloc>::iterator
  131.       list<_Tp, _Alloc>::
  132.       insert(const_iterator __position, _InputIterator __first,
  133.              _InputIterator __last)
  134.       {
  135.         list __tmp(__first, __last, get_allocator());
  136.         if (!__tmp.empty())
  137.           {
  138.             iterator __it = __tmp.begin();
  139.             splice(__position, __tmp);
  140.             return __it;
  141.           }
  142.         return __position._M_const_cast();
  143.       }
  144. #endif
  145.  
  146.   template<typename _Tp, typename _Alloc>
  147.     typename list<_Tp, _Alloc>::iterator
  148.     list<_Tp, _Alloc>::
  149. #if __cplusplus >= 201103L
  150.     erase(const_iterator __position) noexcept
  151. #else
  152.     erase(iterator __position)
  153. #endif
  154.     {
  155.       iterator __ret = iterator(__position._M_node->_M_next);
  156.       _M_erase(__position._M_const_cast());
  157.       return __ret;
  158.     }
  159.  
  160. #if __cplusplus >= 201103L
  161.   template<typename _Tp, typename _Alloc>
  162.     void
  163.     list<_Tp, _Alloc>::
  164.     _M_default_append(size_type __n)
  165.     {
  166.       size_type __i = 0;
  167.       __try
  168.         {
  169.           for (; __i < __n; ++__i)
  170.             emplace_back();
  171.         }
  172.       __catch(...)
  173.         {
  174.           for (; __i; --__i)
  175.             pop_back();
  176.           __throw_exception_again;
  177.         }
  178.     }
  179.  
  180.   template<typename _Tp, typename _Alloc>
  181.     void
  182.     list<_Tp, _Alloc>::
  183.     resize(size_type __new_size)
  184.     {
  185.       iterator __i = begin();
  186.       size_type __len = 0;
  187.       for (; __i != end() && __len < __new_size; ++__i, ++__len)
  188.         ;
  189.       if (__len == __new_size)
  190.         erase(__i, end());
  191.       else                          // __i == end()
  192.         _M_default_append(__new_size - __len);
  193.     }
  194.  
  195.   template<typename _Tp, typename _Alloc>
  196.     void
  197.     list<_Tp, _Alloc>::
  198.     resize(size_type __new_size, const value_type& __x)
  199.     {
  200.       iterator __i = begin();
  201.       size_type __len = 0;
  202.       for (; __i != end() && __len < __new_size; ++__i, ++__len)
  203.         ;
  204.       if (__len == __new_size)
  205.         erase(__i, end());
  206.       else                          // __i == end()
  207.         insert(end(), __new_size - __len, __x);
  208.     }
  209. #else
  210.   template<typename _Tp, typename _Alloc>
  211.     void
  212.     list<_Tp, _Alloc>::
  213.     resize(size_type __new_size, value_type __x)
  214.     {
  215.       iterator __i = begin();
  216.       size_type __len = 0;
  217.       for (; __i != end() && __len < __new_size; ++__i, ++__len)
  218.         ;
  219.       if (__len == __new_size)
  220.         erase(__i, end());
  221.       else                          // __i == end()
  222.         insert(end(), __new_size - __len, __x);
  223.     }
  224. #endif
  225.  
  226.   template<typename _Tp, typename _Alloc>
  227.     list<_Tp, _Alloc>&
  228.     list<_Tp, _Alloc>::
  229.     operator=(const list& __x)
  230.     {
  231.       if (this != &__x)
  232.         {
  233.           iterator __first1 = begin();
  234.           iterator __last1 = end();
  235.           const_iterator __first2 = __x.begin();
  236.           const_iterator __last2 = __x.end();
  237.           for (; __first1 != __last1 && __first2 != __last2;
  238.                ++__first1, ++__first2)
  239.             *__first1 = *__first2;
  240.           if (__first2 == __last2)
  241.             erase(__first1, __last1);
  242.           else
  243.             insert(__last1, __first2, __last2);
  244.         }
  245.       return *this;
  246.     }
  247.  
  248.   template<typename _Tp, typename _Alloc>
  249.     void
  250.     list<_Tp, _Alloc>::
  251.     _M_fill_assign(size_type __n, const value_type& __val)
  252.     {
  253.       iterator __i = begin();
  254.       for (; __i != end() && __n > 0; ++__i, --__n)
  255.         *__i = __val;
  256.       if (__n > 0)
  257.         insert(end(), __n, __val);
  258.       else
  259.         erase(__i, end());
  260.     }
  261.  
  262.   template<typename _Tp, typename _Alloc>
  263.     template <typename _InputIterator>
  264.       void
  265.       list<_Tp, _Alloc>::
  266.       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
  267.                          __false_type)
  268.       {
  269.         iterator __first1 = begin();
  270.         iterator __last1 = end();
  271.         for (; __first1 != __last1 && __first2 != __last2;
  272.              ++__first1, ++__first2)
  273.           *__first1 = *__first2;
  274.         if (__first2 == __last2)
  275.           erase(__first1, __last1);
  276.         else
  277.           insert(__last1, __first2, __last2);
  278.       }
  279.  
  280.   template<typename _Tp, typename _Alloc>
  281.     void
  282.     list<_Tp, _Alloc>::
  283.     remove(const value_type& __value)
  284.     {
  285.       iterator __first = begin();
  286.       iterator __last = end();
  287.       iterator __extra = __last;
  288.       while (__first != __last)
  289.         {
  290.           iterator __next = __first;
  291.           ++__next;
  292.           if (*__first == __value)
  293.             {
  294.               // _GLIBCXX_RESOLVE_LIB_DEFECTS
  295.               // 526. Is it undefined if a function in the standard changes
  296.               // in parameters?
  297.               if (std::__addressof(*__first) != std::__addressof(__value))
  298.                 _M_erase(__first);
  299.               else
  300.                 __extra = __first;
  301.             }
  302.           __first = __next;
  303.         }
  304.       if (__extra != __last)
  305.         _M_erase(__extra);
  306.     }
  307.  
  308.   template<typename _Tp, typename _Alloc>
  309.     void
  310.     list<_Tp, _Alloc>::
  311.     unique()
  312.     {
  313.       iterator __first = begin();
  314.       iterator __last = end();
  315.       if (__first == __last)
  316.         return;
  317.       iterator __next = __first;
  318.       while (++__next != __last)
  319.         {
  320.           if (*__first == *__next)
  321.             _M_erase(__next);
  322.           else
  323.             __first = __next;
  324.           __next = __first;
  325.         }
  326.     }
  327.  
  328.   template<typename _Tp, typename _Alloc>
  329.     void
  330.     list<_Tp, _Alloc>::
  331. #if __cplusplus >= 201103L
  332.     merge(list&& __x)
  333. #else
  334.     merge(list& __x)
  335. #endif
  336.     {
  337.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  338.       // 300. list::merge() specification incomplete
  339.       if (this != &__x)
  340.         {
  341.           _M_check_equal_allocators(__x);
  342.  
  343.           iterator __first1 = begin();
  344.           iterator __last1 = end();
  345.           iterator __first2 = __x.begin();
  346.           iterator __last2 = __x.end();
  347.           while (__first1 != __last1 && __first2 != __last2)
  348.             if (*__first2 < *__first1)
  349.               {
  350.                 iterator __next = __first2;
  351.                 _M_transfer(__first1, __first2, ++__next);
  352.                 __first2 = __next;
  353.               }
  354.             else
  355.               ++__first1;
  356.           if (__first2 != __last2)
  357.             _M_transfer(__last1, __first2, __last2);
  358.  
  359.           this->_M_inc_size(__x._M_get_size());
  360.           __x._M_set_size(0);
  361.         }
  362.     }
  363.  
  364.   template<typename _Tp, typename _Alloc>
  365.     template <typename _StrictWeakOrdering>
  366.       void
  367.       list<_Tp, _Alloc>::
  368. #if __cplusplus >= 201103L
  369.       merge(list&& __x, _StrictWeakOrdering __comp)
  370. #else
  371.       merge(list& __x, _StrictWeakOrdering __comp)
  372. #endif
  373.       {
  374.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  375.         // 300. list::merge() specification incomplete
  376.         if (this != &__x)
  377.           {
  378.             _M_check_equal_allocators(__x);
  379.  
  380.             iterator __first1 = begin();
  381.             iterator __last1 = end();
  382.             iterator __first2 = __x.begin();
  383.             iterator __last2 = __x.end();
  384.             while (__first1 != __last1 && __first2 != __last2)
  385.               if (__comp(*__first2, *__first1))
  386.                 {
  387.                   iterator __next = __first2;
  388.                   _M_transfer(__first1, __first2, ++__next);
  389.                   __first2 = __next;
  390.                 }
  391.               else
  392.                 ++__first1;
  393.             if (__first2 != __last2)
  394.               _M_transfer(__last1, __first2, __last2);
  395.  
  396.             this->_M_inc_size(__x._M_get_size());
  397.             __x._M_set_size(0);
  398.           }
  399.       }
  400.  
  401.   template<typename _Tp, typename _Alloc>
  402.     void
  403.     list<_Tp, _Alloc>::
  404.     sort()
  405.     {
  406.       // Do nothing if the list has length 0 or 1.
  407.       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
  408.           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
  409.       {
  410.         list __carry;
  411.         list __tmp[64];
  412.         list * __fill = &__tmp[0];
  413.         list * __counter;
  414.  
  415.         do
  416.           {
  417.             __carry.splice(__carry.begin(), *this, begin());
  418.  
  419.             for(__counter = &__tmp[0];
  420.                 __counter != __fill && !__counter->empty();
  421.                 ++__counter)
  422.               {
  423.                 __counter->merge(__carry);
  424.                 __carry.swap(*__counter);
  425.               }
  426.             __carry.swap(*__counter);
  427.             if (__counter == __fill)
  428.               ++__fill;
  429.           }
  430.         while ( !empty() );
  431.  
  432.         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
  433.           __counter->merge(*(__counter - 1));
  434.         swap( *(__fill - 1) );
  435.       }
  436.     }
  437.  
  438.   template<typename _Tp, typename _Alloc>
  439.     template <typename _Predicate>
  440.       void
  441.       list<_Tp, _Alloc>::
  442.       remove_if(_Predicate __pred)
  443.       {
  444.         iterator __first = begin();
  445.         iterator __last = end();
  446.         while (__first != __last)
  447.           {
  448.             iterator __next = __first;
  449.             ++__next;
  450.             if (__pred(*__first))
  451.               _M_erase(__first);
  452.             __first = __next;
  453.           }
  454.       }
  455.  
  456.   template<typename _Tp, typename _Alloc>
  457.     template <typename _BinaryPredicate>
  458.       void
  459.       list<_Tp, _Alloc>::
  460.       unique(_BinaryPredicate __binary_pred)
  461.       {
  462.         iterator __first = begin();
  463.         iterator __last = end();
  464.         if (__first == __last)
  465.           return;
  466.         iterator __next = __first;
  467.         while (++__next != __last)
  468.           {
  469.             if (__binary_pred(*__first, *__next))
  470.               _M_erase(__next);
  471.             else
  472.               __first = __next;
  473.             __next = __first;
  474.           }
  475.       }
  476.  
  477.   template<typename _Tp, typename _Alloc>
  478.     template <typename _StrictWeakOrdering>
  479.       void
  480.       list<_Tp, _Alloc>::
  481.       sort(_StrictWeakOrdering __comp)
  482.       {
  483.         // Do nothing if the list has length 0 or 1.
  484.         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
  485.             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
  486.           {
  487.             list __carry;
  488.             list __tmp[64];
  489.             list * __fill = &__tmp[0];
  490.             list * __counter;
  491.  
  492.             do
  493.               {
  494.                 __carry.splice(__carry.begin(), *this, begin());
  495.  
  496.                 for(__counter = &__tmp[0];
  497.                     __counter != __fill && !__counter->empty();
  498.                     ++__counter)
  499.                   {
  500.                     __counter->merge(__carry, __comp);
  501.                     __carry.swap(*__counter);
  502.                   }
  503.                 __carry.swap(*__counter);
  504.                 if (__counter == __fill)
  505.                   ++__fill;
  506.               }
  507.             while ( !empty() );
  508.  
  509.             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
  510.               __counter->merge(*(__counter - 1), __comp);
  511.             swap(*(__fill - 1));
  512.           }
  513.       }
  514.  
  515. _GLIBCXX_END_NAMESPACE_CONTAINER
  516. } // namespace std
  517.  
  518. #endif /* _LIST_TCC */
  519.  
  520.