Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Debugging set 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/set.h
  26.  *  This file is a GNU debug extension to the Standard C++ Library.
  27.  */
  28.  
  29. #ifndef _GLIBCXX_DEBUG_SET_H
  30. #define _GLIBCXX_DEBUG_SET_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::set with safety/checking/debug instrumentation.
  41.   template<typename _Key, typename _Compare = std::less<_Key>,
  42.            typename _Allocator = std::allocator<_Key> >
  43.     class set
  44.     : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
  45.       public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
  46.     {
  47.       typedef _GLIBCXX_STD_C::set<_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, set>
  63.                                                     iterator;
  64.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
  65.                                                     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 set(const _Compare& __comp = _Compare(),
  76.                    const _Allocator& __a = _Allocator())
  77.       : _Base(__comp, __a) { }
  78.  
  79.       template<typename _InputIterator>
  80.         set(_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.       set(const set& __x)
  89.       : _Base(__x) { }
  90.  
  91.       set(const _Base& __x)
  92.       : _Base(__x) { }
  93.  
  94. #if __cplusplus >= 201103L
  95.       set(set&& __x)
  96.       noexcept(is_nothrow_copy_constructible<_Compare>::value)
  97.       : _Base(std::move(__x))
  98.       { this->_M_swap(__x); }
  99.  
  100.       set(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.       ~set() _GLIBCXX_NOEXCEPT { }
  107.  
  108.       set&
  109.       operator=(const set& __x)
  110.       {
  111.         *static_cast<_Base*>(this) = __x;
  112.         this->_M_invalidate_all();
  113.         return *this;
  114.       }
  115.  
  116. #if __cplusplus >= 201103L
  117.       set&
  118.       operator=(set&& __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.       set&
  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.         std::pair<iterator, bool>
  199.         emplace(_Args&&... __args)
  200.         {
  201.           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
  202.           return std::pair<iterator, bool>(iterator(__res.first, this),
  203.                                            __res.second);
  204.         }
  205.  
  206.       template<typename... _Args>
  207.         iterator
  208.         emplace_hint(const_iterator __pos, _Args&&... __args)
  209.         {
  210.           __glibcxx_check_insert(__pos);
  211.           return iterator(_Base::emplace_hint(__pos.base(),
  212.                                               std::forward<_Args>(__args)...),
  213.                           this);
  214.         }
  215. #endif
  216.  
  217.       std::pair<iterator, bool>
  218.       insert(const value_type& __x)
  219.       {
  220.         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
  221.         return std::pair<iterator, bool>(iterator(__res.first, this),
  222.                                          __res.second);
  223.       }
  224.  
  225. #if __cplusplus >= 201103L
  226.       std::pair<iterator, bool>
  227.       insert(value_type&& __x)
  228.       {
  229.         std::pair<_Base_iterator, bool> __res
  230.           = _Base::insert(std::move(__x));
  231.         return std::pair<iterator, bool>(iterator(__res.first, this),
  232.                                          __res.second);
  233.       }
  234. #endif
  235.  
  236.       iterator
  237.       insert(const_iterator __position, const value_type& __x)
  238.       {
  239.         __glibcxx_check_insert(__position);
  240.         return iterator(_Base::insert(__position.base(), __x), this);
  241.       }
  242.  
  243. #if __cplusplus >= 201103L
  244.       iterator
  245.       insert(const_iterator __position, value_type&& __x)
  246.       {
  247.         __glibcxx_check_insert(__position);
  248.         return iterator(_Base::insert(__position.base(), std::move(__x)),
  249.                         this);
  250.       }
  251. #endif
  252.  
  253.       template <typename _InputIterator>
  254.         void
  255.         insert(_InputIterator __first, _InputIterator __last)
  256.         {
  257.           __glibcxx_check_valid_range(__first, __last);
  258.           _Base::insert(__gnu_debug::__base(__first),
  259.                         __gnu_debug::__base(__last));
  260.         }
  261.  
  262. #if __cplusplus >= 201103L
  263.       void
  264.       insert(initializer_list<value_type> __l)
  265.       { _Base::insert(__l); }
  266. #endif
  267.  
  268. #if __cplusplus >= 201103L
  269.       iterator
  270.       erase(const_iterator __position)
  271.       {
  272.         __glibcxx_check_erase(__position);
  273.         this->_M_invalidate_if(_Equal(__position.base()));
  274.         return iterator(_Base::erase(__position.base()), this);
  275.       }
  276. #else
  277.       void
  278.       erase(iterator __position)
  279.       {
  280.         __glibcxx_check_erase(__position);
  281.         this->_M_invalidate_if(_Equal(__position.base()));
  282.         _Base::erase(__position.base());
  283.       }
  284. #endif
  285.  
  286.       size_type
  287.       erase(const key_type& __x)
  288.       {
  289.         _Base_iterator __victim = _Base::find(__x);
  290.         if (__victim == _Base::end())
  291.           return 0;
  292.         else
  293.           {
  294.             this->_M_invalidate_if(_Equal(__victim));
  295.             _Base::erase(__victim);
  296.             return 1;
  297.           }
  298.       }
  299.  
  300. #if __cplusplus >= 201103L
  301.       iterator
  302.       erase(const_iterator __first, const_iterator __last)
  303.       {
  304.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  305.         // 151. can't currently clear() empty container
  306.         __glibcxx_check_erase_range(__first, __last);
  307.         for (_Base_const_iterator __victim = __first.base();
  308.              __victim != __last.base(); ++__victim)
  309.           {
  310.             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
  311.                                   _M_message(__gnu_debug::__msg_valid_range)
  312.                                   ._M_iterator(__first, "first")
  313.                                   ._M_iterator(__last, "last"));
  314.             this->_M_invalidate_if(_Equal(__victim));
  315.           }
  316.         return iterator(_Base::erase(__first.base(), __last.base()), this);
  317.       }
  318. #else
  319.       void
  320.       erase(iterator __first, iterator __last)
  321.       {
  322.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  323.         // 151. can't currently clear() empty container
  324.         __glibcxx_check_erase_range(__first, __last);
  325.         for (_Base_iterator __victim = __first.base();
  326.              __victim != __last.base(); ++__victim)
  327.           {
  328.             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
  329.                                   _M_message(__gnu_debug::__msg_valid_range)
  330.                                   ._M_iterator(__first, "first")
  331.                                   ._M_iterator(__last, "last"));
  332.             this->_M_invalidate_if(_Equal(__victim));
  333.           }
  334.         _Base::erase(__first.base(), __last.base());
  335.       }
  336. #endif
  337.  
  338.       void
  339.       swap(set& __x)
  340.       {
  341.         _Base::swap(__x);
  342.         this->_M_swap(__x);
  343.       }
  344.  
  345.       void
  346.       clear() _GLIBCXX_NOEXCEPT
  347.       {
  348.         this->_M_invalidate_all();
  349.         _Base::clear();
  350.       }
  351.  
  352.       // observers:
  353.       using _Base::key_comp;
  354.       using _Base::value_comp;
  355.  
  356.       // set operations:
  357.       iterator
  358.       find(const key_type& __x)
  359.       { return iterator(_Base::find(__x), this); }
  360.  
  361.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  362.       // 214. set::find() missing const overload
  363.       const_iterator
  364.       find(const key_type& __x) const
  365.       { return const_iterator(_Base::find(__x), this); }
  366.  
  367.       using _Base::count;
  368.  
  369.       iterator
  370.       lower_bound(const key_type& __x)
  371.       { return iterator(_Base::lower_bound(__x), this); }
  372.  
  373.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  374.       // 214. set::find() missing const overload
  375.       const_iterator
  376.       lower_bound(const key_type& __x) const
  377.       { return const_iterator(_Base::lower_bound(__x), this); }
  378.  
  379.       iterator
  380.       upper_bound(const key_type& __x)
  381.       { return iterator(_Base::upper_bound(__x), this); }
  382.  
  383.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  384.       // 214. set::find() missing const overload
  385.       const_iterator
  386.       upper_bound(const key_type& __x) const
  387.       { return const_iterator(_Base::upper_bound(__x), this); }
  388.  
  389.       std::pair<iterator,iterator>
  390.       equal_range(const key_type& __x)
  391.       {
  392.         std::pair<_Base_iterator, _Base_iterator> __res =
  393.         _Base::equal_range(__x);
  394.         return std::make_pair(iterator(__res.first, this),
  395.                               iterator(__res.second, this));
  396.       }
  397.  
  398.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  399.       // 214. set::find() missing const overload
  400.       std::pair<const_iterator,const_iterator>
  401.       equal_range(const key_type& __x) const
  402.       {
  403.         std::pair<_Base_iterator, _Base_iterator> __res =
  404.         _Base::equal_range(__x);
  405.         return std::make_pair(const_iterator(__res.first, this),
  406.                               const_iterator(__res.second, this));
  407.       }
  408.  
  409.       _Base&
  410.       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
  411.  
  412.       const _Base&
  413.       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
  414.  
  415.     private:
  416.       void
  417.       _M_invalidate_all()
  418.       {
  419.         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
  420.         this->_M_invalidate_if(_Not_equal(_M_base().end()));
  421.       }
  422.     };
  423.  
  424.   template<typename _Key, typename _Compare, typename _Allocator>
  425.     inline bool
  426.     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
  427.                const set<_Key, _Compare, _Allocator>& __rhs)
  428.     { return __lhs._M_base() == __rhs._M_base(); }
  429.  
  430.   template<typename _Key, typename _Compare, typename _Allocator>
  431.     inline bool
  432.     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
  433.                const set<_Key, _Compare, _Allocator>& __rhs)
  434.     { return __lhs._M_base() != __rhs._M_base(); }
  435.  
  436.   template<typename _Key, typename _Compare, typename _Allocator>
  437.     inline bool
  438.     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
  439.               const set<_Key, _Compare, _Allocator>& __rhs)
  440.     { return __lhs._M_base() < __rhs._M_base(); }
  441.  
  442.   template<typename _Key, typename _Compare, typename _Allocator>
  443.     inline bool
  444.     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
  445.                const set<_Key, _Compare, _Allocator>& __rhs)
  446.     { return __lhs._M_base() <= __rhs._M_base(); }
  447.  
  448.   template<typename _Key, typename _Compare, typename _Allocator>
  449.     inline bool
  450.     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
  451.                const set<_Key, _Compare, _Allocator>& __rhs)
  452.     { return __lhs._M_base() >= __rhs._M_base(); }
  453.  
  454.   template<typename _Key, typename _Compare, typename _Allocator>
  455.     inline bool
  456.     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
  457.               const set<_Key, _Compare, _Allocator>& __rhs)
  458.     { return __lhs._M_base() > __rhs._M_base(); }
  459.  
  460.   template<typename _Key, typename _Compare, typename _Allocator>
  461.     void
  462.     swap(set<_Key, _Compare, _Allocator>& __x,
  463.          set<_Key, _Compare, _Allocator>& __y)
  464.     { return __x.swap(__y); }
  465.  
  466. } // namespace __debug
  467. } // namespace std
  468.  
  469. #endif
  470.