Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. // Debugging multiset implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2003-2013 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 debug/multiset.h
  26.  *  This file is a GNU debug extension to the Standard C++ Library.
  27.  */
  28.  
  29. #ifndef _GLIBCXX_DEBUG_MULTISET_H
  30. #define _GLIBCXX_DEBUG_MULTISET_H 1
  31.  
  32. #include <debug/safe_sequence.h>
  33. #include <debug/safe_iterator.h>
  34. #include <utility>
  35.  
  36. namespace std _GLIBCXX_VISIBILITY(default)
  37. {
  38. namespace __debug
  39. {
  40.   /// Class std::multiset with safety/checking/debug instrumentation.
  41.   template<typename _Key, typename _Compare = std::less<_Key>,
  42.            typename _Allocator = std::allocator<_Key> >
  43.     class multiset
  44.     : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
  45.       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
  46.     {
  47.       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
  48.  
  49.       typedef typename _Base::const_iterator _Base_const_iterator;
  50.       typedef typename _Base::iterator _Base_iterator;
  51.       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  52.     public:
  53.       // types:
  54.       typedef _Key                                   key_type;
  55.       typedef _Key                                   value_type;
  56.       typedef _Compare                               key_compare;
  57.       typedef _Compare                               value_compare;
  58.       typedef _Allocator                             allocator_type;
  59.       typedef typename _Base::reference              reference;
  60.       typedef typename _Base::const_reference        const_reference;
  61.  
  62.       typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
  63.       iterator;
  64.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  65.                                           multiset> const_iterator;
  66.  
  67.       typedef typename _Base::size_type              size_type;
  68.       typedef typename _Base::difference_type        difference_type;
  69.       typedef typename _Base::pointer                pointer;
  70.       typedef typename _Base::const_pointer          const_pointer;
  71.       typedef std::reverse_iterator<iterator>        reverse_iterator;
  72.       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
  73.  
  74.       // 23.3.3.1 construct/copy/destroy:
  75.       explicit multiset(const _Compare& __comp = _Compare(),
  76.                         const _Allocator& __a = _Allocator())
  77.       : _Base(__comp, __a) { }
  78.  
  79.       template<typename _InputIterator>
  80.         multiset(_InputIterator __first, _InputIterator __last,
  81.                  const _Compare& __comp = _Compare(),
  82.                  const _Allocator& __a = _Allocator())
  83.         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  84.                                                                      __last)),
  85.                 __gnu_debug::__base(__last),
  86.                 __comp, __a) { }
  87.  
  88.       multiset(const multiset& __x)
  89.       : _Base(__x) { }
  90.  
  91.       multiset(const _Base& __x)
  92.       : _Base(__x) { }
  93.  
  94. #if __cplusplus >= 201103L
  95.       multiset(multiset&& __x)
  96.       noexcept(is_nothrow_copy_constructible<_Compare>::value)
  97.       : _Base(std::move(__x))
  98.       { this->_M_swap(__x); }
  99.  
  100.       multiset(initializer_list<value_type> __l,
  101.                const _Compare& __comp = _Compare(),
  102.                const allocator_type& __a = allocator_type())
  103.       : _Base(__l, __comp, __a) { }
  104. #endif
  105.  
  106.       ~multiset() _GLIBCXX_NOEXCEPT { }
  107.  
  108.       multiset&
  109.       operator=(const multiset& __x)
  110.       {
  111.         *static_cast<_Base*>(this) = __x;
  112.         this->_M_invalidate_all();
  113.         return *this;
  114.       }
  115.  
  116. #if __cplusplus >= 201103L
  117.       multiset&
  118.       operator=(multiset&& __x)
  119.       {
  120.         // NB: DR 1204.
  121.         // NB: DR 675.
  122.         __glibcxx_check_self_move_assign(__x);
  123.         clear();
  124.         swap(__x);
  125.         return *this;
  126.       }
  127.  
  128.       multiset&
  129.       operator=(initializer_list<value_type> __l)
  130.       {
  131.         this->clear();
  132.         this->insert(__l);
  133.         return *this;
  134.       }
  135. #endif
  136.  
  137.       using _Base::get_allocator;
  138.  
  139.       // iterators:
  140.       iterator
  141.       begin() _GLIBCXX_NOEXCEPT
  142.       { return iterator(_Base::begin(), this); }
  143.  
  144.       const_iterator
  145.       begin() const _GLIBCXX_NOEXCEPT
  146.       { return const_iterator(_Base::begin(), this); }
  147.  
  148.       iterator
  149.       end() _GLIBCXX_NOEXCEPT
  150.       { return iterator(_Base::end(), this); }
  151.  
  152.       const_iterator
  153.       end() const _GLIBCXX_NOEXCEPT
  154.       { return const_iterator(_Base::end(), this); }
  155.  
  156.       reverse_iterator
  157.       rbegin() _GLIBCXX_NOEXCEPT
  158.       { return reverse_iterator(end()); }
  159.  
  160.       const_reverse_iterator
  161.       rbegin() const _GLIBCXX_NOEXCEPT
  162.       { return const_reverse_iterator(end()); }
  163.  
  164.       reverse_iterator
  165.       rend() _GLIBCXX_NOEXCEPT
  166.       { return reverse_iterator(begin()); }
  167.  
  168.       const_reverse_iterator
  169.       rend() const _GLIBCXX_NOEXCEPT
  170.       { return const_reverse_iterator(begin()); }
  171.  
  172. #if __cplusplus >= 201103L
  173.       const_iterator
  174.       cbegin() const noexcept
  175.       { return const_iterator(_Base::begin(), this); }
  176.  
  177.       const_iterator
  178.       cend() const noexcept
  179.       { return const_iterator(_Base::end(), this); }
  180.  
  181.       const_reverse_iterator
  182.       crbegin() const noexcept
  183.       { return const_reverse_iterator(end()); }
  184.  
  185.       const_reverse_iterator
  186.       crend() const noexcept
  187.       { return const_reverse_iterator(begin()); }
  188. #endif
  189.  
  190.       // capacity:
  191.       using _Base::empty;
  192.       using _Base::size;
  193.       using _Base::max_size;
  194.  
  195.       // modifiers:
  196. #if __cplusplus >= 201103L
  197.       template<typename... _Args>
  198.         iterator
  199.         emplace(_Args&&... __args)
  200.         {
  201.           return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
  202.         }
  203.  
  204.       template<typename... _Args>
  205.         iterator
  206.         emplace_hint(const_iterator __pos, _Args&&... __args)
  207.         {
  208.           __glibcxx_check_insert(__pos);
  209.           return iterator(_Base::emplace_hint(__pos.base(),
  210.                                               std::forward<_Args>(__args)...),
  211.                           this);
  212.         }
  213. #endif
  214.  
  215.       iterator
  216.       insert(const value_type& __x)
  217.       { return iterator(_Base::insert(__x), this); }
  218.  
  219. #if __cplusplus >= 201103L
  220.       iterator
  221.       insert(value_type&& __x)
  222.       { return iterator(_Base::insert(std::move(__x)), this); }
  223. #endif
  224.  
  225.       iterator
  226.       insert(const_iterator __position, const value_type& __x)
  227.       {
  228.         __glibcxx_check_insert(__position);
  229.         return iterator(_Base::insert(__position.base(), __x), this);
  230.       }
  231.  
  232. #if __cplusplus >= 201103L
  233.       iterator
  234.       insert(const_iterator __position, value_type&& __x)
  235.       {
  236.         __glibcxx_check_insert(__position);
  237.         return iterator(_Base::insert(__position.base(), std::move(__x)),
  238.                         this);
  239.       }
  240. #endif
  241.  
  242.       template<typename _InputIterator>
  243.         void
  244.         insert(_InputIterator __first, _InputIterator __last)
  245.         {
  246.           __glibcxx_check_valid_range(__first, __last);
  247.           _Base::insert(__gnu_debug::__base(__first),
  248.                         __gnu_debug::__base(__last));
  249.         }
  250.  
  251. #if __cplusplus >= 201103L
  252.       void
  253.       insert(initializer_list<value_type> __l)
  254.       { _Base::insert(__l); }
  255. #endif
  256.  
  257. #if __cplusplus >= 201103L
  258.       iterator
  259.       erase(const_iterator __position)
  260.       {
  261.         __glibcxx_check_erase(__position);
  262.         this->_M_invalidate_if(_Equal(__position.base()));
  263.         return iterator(_Base::erase(__position.base()), this);
  264.       }
  265. #else
  266.       void
  267.       erase(iterator __position)
  268.       {
  269.         __glibcxx_check_erase(__position);
  270.         this->_M_invalidate_if(_Equal(__position.base()));
  271.         _Base::erase(__position.base());
  272.       }
  273. #endif
  274.  
  275.       size_type
  276.       erase(const key_type& __x)
  277.       {
  278.         std::pair<_Base_iterator, _Base_iterator> __victims =
  279.           _Base::equal_range(__x);
  280.         size_type __count = 0;
  281.         _Base_iterator __victim = __victims.first;
  282.         while (__victim != __victims.second)
  283.           {
  284.             this->_M_invalidate_if(_Equal(__victim));
  285.             _Base::erase(__victim++);
  286.             ++__count;
  287.           }
  288.         return __count;
  289.       }
  290.  
  291. #if __cplusplus >= 201103L
  292.       iterator
  293.       erase(const_iterator __first, const_iterator __last)
  294.       {
  295.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  296.         // 151. can't currently clear() empty container
  297.         __glibcxx_check_erase_range(__first, __last);
  298.         for (_Base_const_iterator __victim = __first.base();
  299.              __victim != __last.base(); ++__victim)
  300.           {
  301.             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
  302.                                   _M_message(__gnu_debug::__msg_valid_range)
  303.                                   ._M_iterator(__first, "first")
  304.                                   ._M_iterator(__last, "last"));
  305.             this->_M_invalidate_if(_Equal(__victim));
  306.           }
  307.         return iterator(_Base::erase(__first.base(), __last.base()), this);
  308.       }
  309. #else
  310.       void
  311.       erase(iterator __first, iterator __last)
  312.       {
  313.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  314.         // 151. can't currently clear() empty container
  315.         __glibcxx_check_erase_range(__first, __last);
  316.         for (_Base_iterator __victim = __first.base();
  317.              __victim != __last.base(); ++__victim)
  318.           {
  319.             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
  320.                                   _M_message(__gnu_debug::__msg_valid_range)
  321.                                   ._M_iterator(__first, "first")
  322.                                   ._M_iterator(__last, "last"));
  323.             this->_M_invalidate_if(_Equal(__victim));
  324.           }
  325.         _Base::erase(__first.base(), __last.base());
  326.       }
  327. #endif
  328.  
  329.       void
  330.       swap(multiset& __x)
  331.       {
  332.         _Base::swap(__x);
  333.         this->_M_swap(__x);
  334.       }
  335.  
  336.       void
  337.       clear() _GLIBCXX_NOEXCEPT
  338.       {
  339.         this->_M_invalidate_all();
  340.         _Base::clear();
  341.       }
  342.  
  343.       // observers:
  344.       using _Base::key_comp;
  345.       using _Base::value_comp;
  346.  
  347.       // multiset operations:
  348.       iterator
  349.       find(const key_type& __x)
  350.       { return iterator(_Base::find(__x), this); }
  351.  
  352.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  353.       // 214. set::find() missing const overload
  354.       const_iterator
  355.       find(const key_type& __x) const
  356.       { return const_iterator(_Base::find(__x), this); }
  357.  
  358.       using _Base::count;
  359.  
  360.       iterator
  361.       lower_bound(const key_type& __x)
  362.       { return iterator(_Base::lower_bound(__x), this); }
  363.  
  364.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  365.       // 214. set::find() missing const overload
  366.       const_iterator
  367.       lower_bound(const key_type& __x) const
  368.       { return const_iterator(_Base::lower_bound(__x), this); }
  369.  
  370.       iterator
  371.       upper_bound(const key_type& __x)
  372.       { return iterator(_Base::upper_bound(__x), this); }
  373.  
  374.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  375.       // 214. set::find() missing const overload
  376.       const_iterator
  377.       upper_bound(const key_type& __x) const
  378.       { return const_iterator(_Base::upper_bound(__x), this); }
  379.  
  380.       std::pair<iterator,iterator>
  381.       equal_range(const key_type& __x)
  382.       {
  383.         std::pair<_Base_iterator, _Base_iterator> __res =
  384.           _Base::equal_range(__x);
  385.         return std::make_pair(iterator(__res.first, this),
  386.                               iterator(__res.second, this));
  387.       }
  388.  
  389.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  390.       // 214. set::find() missing const overload
  391.       std::pair<const_iterator,const_iterator>
  392.       equal_range(const key_type& __x) const
  393.       {
  394.         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
  395.           _Base::equal_range(__x);
  396.         return std::make_pair(const_iterator(__res.first, this),
  397.                               const_iterator(__res.second, this));
  398.       }
  399.  
  400.       _Base&
  401.       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
  402.  
  403.       const _Base&
  404.       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
  405.  
  406.     private:
  407.       void
  408.       _M_invalidate_all()
  409.       {
  410.         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
  411.         this->_M_invalidate_if(_Not_equal(_Base::end()));
  412.       }
  413.     };
  414.  
  415.   template<typename _Key, typename _Compare, typename _Allocator>
  416.     inline bool
  417.     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
  418.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  419.     { return __lhs._M_base() == __rhs._M_base(); }
  420.  
  421.   template<typename _Key, typename _Compare, typename _Allocator>
  422.     inline bool
  423.     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
  424.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  425.     { return __lhs._M_base() != __rhs._M_base(); }
  426.  
  427.   template<typename _Key, typename _Compare, typename _Allocator>
  428.     inline bool
  429.     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
  430.               const multiset<_Key, _Compare, _Allocator>& __rhs)
  431.     { return __lhs._M_base() < __rhs._M_base(); }
  432.  
  433.   template<typename _Key, typename _Compare, typename _Allocator>
  434.     inline bool
  435.     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
  436.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  437.     { return __lhs._M_base() <= __rhs._M_base(); }
  438.  
  439.   template<typename _Key, typename _Compare, typename _Allocator>
  440.     inline bool
  441.     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
  442.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  443.     { return __lhs._M_base() >= __rhs._M_base(); }
  444.  
  445.   template<typename _Key, typename _Compare, typename _Allocator>
  446.     inline bool
  447.     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
  448.               const multiset<_Key, _Compare, _Allocator>& __rhs)
  449.     { return __lhs._M_base() > __rhs._M_base(); }
  450.  
  451.   template<typename _Key, typename _Compare, typename _Allocator>
  452.     void
  453.     swap(multiset<_Key, _Compare, _Allocator>& __x,
  454.          multiset<_Key, _Compare, _Allocator>& __y)
  455.     { return __x.swap(__y); }
  456.  
  457. } // namespace __debug
  458. } // namespace std
  459.  
  460. #endif
  461.