Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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