Subversion Repositories Kolibri OS

Rev

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

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