Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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