Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Debugging deque 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/deque
  26.  *  This file is a GNU debug extension to the Standard C++ Library.
  27.  */
  28.  
  29. #ifndef _GLIBCXX_DEBUG_DEQUE
  30. #define _GLIBCXX_DEBUG_DEQUE 1
  31.  
  32. #include <deque>
  33. #include <debug/safe_sequence.h>
  34. #include <debug/safe_container.h>
  35. #include <debug/safe_iterator.h>
  36.  
  37. namespace std _GLIBCXX_VISIBILITY(default)
  38. {
  39. namespace __debug
  40. {
  41.   /// Class std::deque with safety/checking/debug instrumentation.
  42.   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  43.     class deque
  44.     : public __gnu_debug::_Safe_container<
  45.         deque<_Tp, _Allocator>, _Allocator,
  46.         __gnu_debug::_Safe_sequence>,
  47.       public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
  48.     {
  49.       typedef  _GLIBCXX_STD_C::deque<_Tp, _Allocator>           _Base;
  50.       typedef __gnu_debug::_Safe_container<
  51.         deque, _Allocator, __gnu_debug::_Safe_sequence> _Safe;
  52.  
  53.       typedef typename _Base::const_iterator    _Base_const_iterator;
  54.       typedef typename _Base::iterator          _Base_iterator;
  55.       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  56.  
  57.     public:
  58.       typedef typename _Base::reference                 reference;
  59.       typedef typename _Base::const_reference           const_reference;
  60.  
  61.       typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
  62.                                                         iterator;
  63.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
  64.                                                         const_iterator;
  65.  
  66.       typedef typename _Base::size_type                 size_type;
  67.       typedef typename _Base::difference_type           difference_type;
  68.  
  69.       typedef _Tp                                       value_type;
  70.       typedef _Allocator                                allocator_type;
  71.       typedef typename _Base::pointer                   pointer;
  72.       typedef typename _Base::const_pointer             const_pointer;
  73.       typedef std::reverse_iterator<iterator>           reverse_iterator;
  74.       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  75.  
  76.       // 23.2.1.1 construct/copy/destroy:
  77.  
  78. #if __cplusplus < 201103L
  79.       deque()
  80.       : _Base() { }
  81.  
  82.       deque(const deque& __x)
  83.       : _Base(__x) { }
  84.  
  85.       ~deque() { }
  86. #else
  87.       deque() = default;
  88.       deque(const deque&) = default;
  89.       deque(deque&&) = default;
  90.  
  91.       deque(const deque& __d, const _Allocator& __a)
  92.       : _Base(__d, __a) { }
  93.  
  94.       deque(deque&& __d, const _Allocator& __a)
  95.       : _Safe(std::move(__d)), _Base(std::move(__d), __a) { }
  96.  
  97.       deque(initializer_list<value_type> __l,
  98.             const allocator_type& __a = allocator_type())
  99.       : _Base(__l, __a) { }
  100.  
  101.       ~deque() = default;
  102. #endif
  103.  
  104.       explicit
  105.       deque(const _Allocator& __a)
  106.       : _Base(__a) { }
  107.  
  108. #if __cplusplus >= 201103L
  109.       explicit
  110.       deque(size_type __n, const _Allocator& __a = _Allocator())
  111.       : _Base(__n, __a) { }
  112.  
  113.       deque(size_type __n, const _Tp& __value,
  114.             const _Allocator& __a = _Allocator())
  115.       : _Base(__n, __value, __a) { }
  116. #else
  117.       explicit
  118.       deque(size_type __n, const _Tp& __value = _Tp(),
  119.             const _Allocator& __a = _Allocator())
  120.       : _Base(__n, __value, __a) { }
  121. #endif
  122.  
  123. #if __cplusplus >= 201103L
  124.       template<class _InputIterator,
  125.                typename = std::_RequireInputIter<_InputIterator>>
  126. #else
  127.       template<class _InputIterator>
  128. #endif
  129.         deque(_InputIterator __first, _InputIterator __last,
  130.               const _Allocator& __a = _Allocator())
  131.         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  132.                                                                      __last)),
  133.                 __gnu_debug::__base(__last), __a)
  134.         { }
  135.  
  136.       deque(const _Base& __x)
  137.       : _Base(__x) { }
  138.  
  139. #if __cplusplus < 201103L
  140.       deque&
  141.       operator=(const deque& __x)
  142.       {
  143.         this->_M_safe() = __x;
  144.         _M_base() = __x;
  145.         return *this;
  146.       }
  147. #else
  148.       deque&
  149.       operator=(const deque&) = default;
  150.  
  151.       deque&
  152.       operator=(deque&&) = default;
  153.  
  154.       deque&
  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. #if __cplusplus >= 201103L
  164.       template<class _InputIterator,
  165.                typename = std::_RequireInputIter<_InputIterator>>
  166. #else
  167.       template<class _InputIterator>
  168. #endif
  169.         void
  170.         assign(_InputIterator __first, _InputIterator __last)
  171.         {
  172.           __glibcxx_check_valid_range(__first, __last);
  173.           _Base::assign(__gnu_debug::__base(__first),
  174.                         __gnu_debug::__base(__last));
  175.           this->_M_invalidate_all();
  176.         }
  177.  
  178.       void
  179.       assign(size_type __n, const _Tp& __t)
  180.       {
  181.         _Base::assign(__n, __t);
  182.         this->_M_invalidate_all();
  183.       }
  184.  
  185. #if __cplusplus >= 201103L
  186.       void
  187.       assign(initializer_list<value_type> __l)
  188.       {
  189.         _Base::assign(__l);
  190.         this->_M_invalidate_all();
  191.       }
  192. #endif
  193.  
  194.       using _Base::get_allocator;
  195.  
  196.       // iterators:
  197.       iterator
  198.       begin() _GLIBCXX_NOEXCEPT
  199.       { return iterator(_Base::begin(), this); }
  200.  
  201.       const_iterator
  202.       begin() const _GLIBCXX_NOEXCEPT
  203.       { return const_iterator(_Base::begin(), this); }
  204.  
  205.       iterator
  206.       end() _GLIBCXX_NOEXCEPT
  207.       { return iterator(_Base::end(), this); }
  208.  
  209.       const_iterator
  210.       end() const _GLIBCXX_NOEXCEPT
  211.       { return const_iterator(_Base::end(), this); }
  212.  
  213.       reverse_iterator
  214.       rbegin() _GLIBCXX_NOEXCEPT
  215.       { return reverse_iterator(end()); }
  216.  
  217.       const_reverse_iterator
  218.       rbegin() const _GLIBCXX_NOEXCEPT
  219.       { return const_reverse_iterator(end()); }
  220.  
  221.       reverse_iterator
  222.       rend() _GLIBCXX_NOEXCEPT
  223.       { return reverse_iterator(begin()); }
  224.  
  225.       const_reverse_iterator
  226.       rend() const _GLIBCXX_NOEXCEPT
  227.       { return const_reverse_iterator(begin()); }
  228.  
  229. #if __cplusplus >= 201103L
  230.       const_iterator
  231.       cbegin() const noexcept
  232.       { return const_iterator(_Base::begin(), this); }
  233.  
  234.       const_iterator
  235.       cend() const noexcept
  236.       { return const_iterator(_Base::end(), this); }
  237.  
  238.       const_reverse_iterator
  239.       crbegin() const noexcept
  240.       { return const_reverse_iterator(end()); }
  241.  
  242.       const_reverse_iterator
  243.       crend() const noexcept
  244.       { return const_reverse_iterator(begin()); }
  245. #endif
  246.  
  247.     private:
  248.       void
  249.       _M_invalidate_after_nth(difference_type __n)
  250.       {
  251.         typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
  252.         this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
  253.       }
  254.  
  255.     public:
  256.       // 23.2.1.2 capacity:
  257.       using _Base::size;
  258.       using _Base::max_size;
  259.  
  260. #if __cplusplus >= 201103L
  261.       void
  262.       resize(size_type __sz)
  263.       {
  264.         bool __invalidate_all = __sz > this->size();
  265.         if (__sz < this->size())
  266.           this->_M_invalidate_after_nth(__sz);
  267.  
  268.         _Base::resize(__sz);
  269.  
  270.         if (__invalidate_all)
  271.           this->_M_invalidate_all();
  272.       }
  273.  
  274.       void
  275.       resize(size_type __sz, const _Tp& __c)
  276.       {
  277.         bool __invalidate_all = __sz > this->size();
  278.         if (__sz < this->size())
  279.           this->_M_invalidate_after_nth(__sz);
  280.  
  281.         _Base::resize(__sz, __c);
  282.  
  283.         if (__invalidate_all)
  284.           this->_M_invalidate_all();
  285.       }
  286. #else
  287.       void
  288.       resize(size_type __sz, _Tp __c = _Tp())
  289.       {
  290.         bool __invalidate_all = __sz > this->size();
  291.         if (__sz < this->size())
  292.           this->_M_invalidate_after_nth(__sz);
  293.  
  294.         _Base::resize(__sz, __c);
  295.  
  296.         if (__invalidate_all)
  297.           this->_M_invalidate_all();
  298.       }
  299. #endif
  300.  
  301. #if __cplusplus >= 201103L
  302.       void
  303.       shrink_to_fit() noexcept
  304.       {
  305.         if (_Base::_M_shrink_to_fit())
  306.           this->_M_invalidate_all();
  307.       }
  308. #endif
  309.  
  310.       using _Base::empty;
  311.  
  312.       // element access:
  313.       reference
  314.       operator[](size_type __n) _GLIBCXX_NOEXCEPT
  315.       {
  316.         __glibcxx_check_subscript(__n);
  317.         return _M_base()[__n];
  318.       }
  319.  
  320.       const_reference
  321.       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
  322.       {
  323.         __glibcxx_check_subscript(__n);
  324.         return _M_base()[__n];
  325.       }
  326.  
  327.       using _Base::at;
  328.  
  329.       reference
  330.       front() _GLIBCXX_NOEXCEPT
  331.       {
  332.         __glibcxx_check_nonempty();
  333.         return _Base::front();
  334.       }
  335.  
  336.       const_reference
  337.       front() const _GLIBCXX_NOEXCEPT
  338.       {
  339.         __glibcxx_check_nonempty();
  340.         return _Base::front();
  341.       }
  342.  
  343.       reference
  344.       back() _GLIBCXX_NOEXCEPT
  345.       {
  346.         __glibcxx_check_nonempty();
  347.         return _Base::back();
  348.       }
  349.  
  350.       const_reference
  351.       back() const _GLIBCXX_NOEXCEPT
  352.       {
  353.         __glibcxx_check_nonempty();
  354.         return _Base::back();
  355.       }
  356.  
  357.       // 23.2.1.3 modifiers:
  358.       void
  359.       push_front(const _Tp& __x)
  360.       {
  361.         _Base::push_front(__x);
  362.         this->_M_invalidate_all();
  363.       }
  364.  
  365.       void
  366.       push_back(const _Tp& __x)
  367.       {
  368.         _Base::push_back(__x);
  369.         this->_M_invalidate_all();
  370.       }
  371.  
  372. #if __cplusplus >= 201103L
  373.       void
  374.       push_front(_Tp&& __x)
  375.       { emplace_front(std::move(__x)); }
  376.  
  377.       void
  378.       push_back(_Tp&& __x)
  379.       { emplace_back(std::move(__x)); }
  380.  
  381.       template<typename... _Args>
  382.         void
  383.         emplace_front(_Args&&... __args)
  384.         {
  385.           _Base::emplace_front(std::forward<_Args>(__args)...);
  386.           this->_M_invalidate_all();
  387.         }
  388.  
  389.       template<typename... _Args>
  390.         void
  391.         emplace_back(_Args&&... __args)
  392.         {
  393.           _Base::emplace_back(std::forward<_Args>(__args)...);
  394.           this->_M_invalidate_all();
  395.         }
  396.  
  397.       template<typename... _Args>
  398.         iterator
  399.         emplace(const_iterator __position, _Args&&... __args)
  400.         {
  401.           __glibcxx_check_insert(__position);
  402.           _Base_iterator __res = _Base::emplace(__position.base(),
  403.                                                 std::forward<_Args>(__args)...);
  404.           this->_M_invalidate_all();
  405.           return iterator(__res, this);
  406.         }
  407. #endif
  408.  
  409.       iterator
  410. #if __cplusplus >= 201103L
  411.       insert(const_iterator __position, const _Tp& __x)
  412. #else
  413.       insert(iterator __position, const _Tp& __x)
  414. #endif
  415.       {
  416.         __glibcxx_check_insert(__position);
  417.         _Base_iterator __res = _Base::insert(__position.base(), __x);
  418.         this->_M_invalidate_all();
  419.         return iterator(__res, this);
  420.       }
  421.  
  422. #if __cplusplus >= 201103L
  423.       iterator
  424.       insert(const_iterator __position, _Tp&& __x)
  425.       { return emplace(__position, std::move(__x)); }
  426.  
  427.       iterator
  428.       insert(const_iterator __position, initializer_list<value_type> __l)
  429.       {
  430.         __glibcxx_check_insert(__position);
  431.         _Base_iterator __res = _Base::insert(__position.base(), __l);
  432.         this->_M_invalidate_all();
  433.         return iterator(__res, this);
  434.       }
  435. #endif
  436.  
  437. #if __cplusplus >= 201103L
  438.       iterator
  439.       insert(const_iterator __position, size_type __n, const _Tp& __x)
  440.       {
  441.         __glibcxx_check_insert(__position);
  442.         _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
  443.         this->_M_invalidate_all();
  444.         return iterator(__res, this);
  445.       }
  446. #else
  447.       void
  448.       insert(iterator __position, size_type __n, const _Tp& __x)
  449.       {
  450.         __glibcxx_check_insert(__position);
  451.         _Base::insert(__position.base(), __n, __x);
  452.         this->_M_invalidate_all();
  453.       }
  454. #endif
  455.  
  456. #if __cplusplus >= 201103L
  457.       template<class _InputIterator,
  458.                typename = std::_RequireInputIter<_InputIterator>>
  459.         iterator
  460.         insert(const_iterator __position,
  461.                _InputIterator __first, _InputIterator __last)
  462.         {
  463.           __glibcxx_check_insert_range(__position, __first, __last);
  464.           _Base_iterator __res = _Base::insert(__position.base(),
  465.                                                __gnu_debug::__base(__first),
  466.                                                __gnu_debug::__base(__last));
  467.           this->_M_invalidate_all();
  468.           return iterator(__res, this);
  469.         }
  470. #else
  471.       template<class _InputIterator>
  472.         void
  473.         insert(iterator __position,
  474.                _InputIterator __first, _InputIterator __last)
  475.         {
  476.           __glibcxx_check_insert_range(__position, __first, __last);
  477.           _Base::insert(__position.base(), __gnu_debug::__base(__first),
  478.                                            __gnu_debug::__base(__last));
  479.           this->_M_invalidate_all();
  480.         }
  481. #endif
  482.  
  483.       void
  484.       pop_front() _GLIBCXX_NOEXCEPT
  485.       {
  486.         __glibcxx_check_nonempty();
  487.         this->_M_invalidate_if(_Equal(_Base::begin()));
  488.         _Base::pop_front();
  489.       }
  490.  
  491.       void
  492.       pop_back() _GLIBCXX_NOEXCEPT
  493.       {
  494.         __glibcxx_check_nonempty();
  495.         this->_M_invalidate_if(_Equal(--_Base::end()));
  496.         _Base::pop_back();
  497.       }
  498.  
  499.       iterator
  500. #if __cplusplus >= 201103L
  501.       erase(const_iterator __position)
  502. #else
  503.       erase(iterator __position)       
  504. #endif
  505.       {
  506.         __glibcxx_check_erase(__position);
  507. #if __cplusplus >= 201103L
  508.         _Base_const_iterator __victim = __position.base();
  509. #else
  510.         _Base_iterator __victim = __position.base();
  511. #endif
  512.         if (__victim == _Base::begin() || __victim == _Base::end() - 1)
  513.           {
  514.             this->_M_invalidate_if(_Equal(__victim));
  515.             return iterator(_Base::erase(__victim), this);
  516.           }
  517.         else
  518.           {
  519.             _Base_iterator __res = _Base::erase(__victim);
  520.             this->_M_invalidate_all();
  521.             return iterator(__res, this);
  522.           }
  523.       }
  524.  
  525.       iterator
  526. #if __cplusplus >= 201103L
  527.       erase(const_iterator __first, const_iterator __last)
  528. #else
  529.       erase(iterator __first, iterator __last)
  530. #endif
  531.       {
  532.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  533.         // 151. can't currently clear() empty container
  534.         __glibcxx_check_erase_range(__first, __last);
  535.  
  536.         if (__first.base() == __last.base())
  537. #if __cplusplus >= 201103L
  538.           return iterator(__first.base()._M_const_cast(), this);
  539. #else
  540.           return __first;
  541. #endif
  542.         else if (__first.base() == _Base::begin()
  543.                  || __last.base() == _Base::end())
  544.           {
  545.             this->_M_detach_singular();
  546.             for (_Base_const_iterator __position = __first.base();
  547.                  __position != __last.base(); ++__position)
  548.               {
  549.                 this->_M_invalidate_if(_Equal(__position));
  550.               }
  551.             __try
  552.               {
  553.                 return iterator(_Base::erase(__first.base(), __last.base()),
  554.                                 this);
  555.               }
  556.             __catch(...)
  557.               {
  558.                 this->_M_revalidate_singular();
  559.                 __throw_exception_again;
  560.               }
  561.           }
  562.         else
  563.           {
  564.             _Base_iterator __res = _Base::erase(__first.base(),
  565.                                                 __last.base());
  566.             this->_M_invalidate_all();
  567.             return iterator(__res, this);
  568.           }
  569.       }
  570.  
  571.       void
  572.       swap(deque& __x)
  573. #if __cplusplus >= 201103L
  574.         noexcept( noexcept(declval<_Base>().swap(__x)) )
  575. #endif
  576.       {
  577.         _Safe::_M_swap(__x);
  578.         _Base::swap(__x);
  579.       }
  580.  
  581.       void
  582.       clear() _GLIBCXX_NOEXCEPT
  583.       {
  584.         _Base::clear();
  585.         this->_M_invalidate_all();
  586.       }
  587.  
  588.       _Base&
  589.       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
  590.  
  591.       const _Base&
  592.       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
  593.     };
  594.  
  595.   template<typename _Tp, typename _Alloc>
  596.     inline bool
  597.     operator==(const deque<_Tp, _Alloc>& __lhs,
  598.                const deque<_Tp, _Alloc>& __rhs)
  599.     { return __lhs._M_base() == __rhs._M_base(); }
  600.  
  601.   template<typename _Tp, typename _Alloc>
  602.     inline bool
  603.     operator!=(const deque<_Tp, _Alloc>& __lhs,
  604.                const deque<_Tp, _Alloc>& __rhs)
  605.     { return __lhs._M_base() != __rhs._M_base(); }
  606.  
  607.   template<typename _Tp, typename _Alloc>
  608.     inline bool
  609.     operator<(const deque<_Tp, _Alloc>& __lhs,
  610.               const deque<_Tp, _Alloc>& __rhs)
  611.     { return __lhs._M_base() < __rhs._M_base(); }
  612.  
  613.   template<typename _Tp, typename _Alloc>
  614.     inline bool
  615.     operator<=(const deque<_Tp, _Alloc>& __lhs,
  616.                const deque<_Tp, _Alloc>& __rhs)
  617.     { return __lhs._M_base() <= __rhs._M_base(); }
  618.  
  619.   template<typename _Tp, typename _Alloc>
  620.     inline bool
  621.     operator>=(const deque<_Tp, _Alloc>& __lhs,
  622.                const deque<_Tp, _Alloc>& __rhs)
  623.     { return __lhs._M_base() >= __rhs._M_base(); }
  624.  
  625.   template<typename _Tp, typename _Alloc>
  626.     inline bool
  627.     operator>(const deque<_Tp, _Alloc>& __lhs,
  628.               const deque<_Tp, _Alloc>& __rhs)
  629.     { return __lhs._M_base() > __rhs._M_base(); }
  630.  
  631.   template<typename _Tp, typename _Alloc>
  632.     inline void
  633.     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
  634.     { __lhs.swap(__rhs); }
  635.  
  636. } // namespace __debug
  637. } // namespace std
  638.  
  639. #endif
  640.