diff options
Diffstat (limited to 'libstdc++-v3/include')
21 files changed, 1464 insertions, 229 deletions
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index c926a3133aa..52e94cc0c42 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -701,8 +701,13 @@ debug_headers = \ ${debug_srcdir}/safe_base.h \ ${debug_srcdir}/safe_iterator.h \ ${debug_srcdir}/safe_iterator.tcc \ + ${debug_srcdir}/safe_local_iterator.h \ + ${debug_srcdir}/safe_local_iterator.tcc \ ${debug_srcdir}/safe_sequence.h \ ${debug_srcdir}/safe_sequence.tcc \ + ${debug_srcdir}/safe_unordered_base.h \ + ${debug_srcdir}/safe_unordered_sequence.h \ + ${debug_srcdir}/safe_unordered_sequence.tcc \ ${debug_srcdir}/set \ ${debug_srcdir}/set.h \ ${debug_srcdir}/string \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index c26eab0c6a0..76d4123da96 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -946,8 +946,13 @@ debug_headers = \ ${debug_srcdir}/safe_base.h \ ${debug_srcdir}/safe_iterator.h \ ${debug_srcdir}/safe_iterator.tcc \ + ${debug_srcdir}/safe_local_iterator.h \ + ${debug_srcdir}/safe_local_iterator.tcc \ ${debug_srcdir}/safe_sequence.h \ ${debug_srcdir}/safe_sequence.tcc \ + ${debug_srcdir}/safe_unordered_base.h \ + ${debug_srcdir}/safe_unordered_sequence.h \ + ${debug_srcdir}/safe_unordered_sequence.tcc \ ${debug_srcdir}/set \ ${debug_srcdir}/set.h \ ${debug_srcdir}/string \ diff --git a/libstdc++-v3/include/bits/shared_ptr.h b/libstdc++-v3/include/bits/shared_ptr.h index 2158de6bf81..2c45f3d7ba3 100644 --- a/libstdc++-v3/include/bits/shared_ptr.h +++ b/libstdc++-v3/include/bits/shared_ptr.h @@ -614,7 +614,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// std::hash specialization for shared_ptr. template<typename _Tp> struct hash<shared_ptr<_Tp>> - : public std::unary_function<shared_ptr<_Tp>, size_t> + : public __hash_base<size_t, shared_ptr<_Tp>> { size_t operator()(const shared_ptr<_Tp>& __s) const diff --git a/libstdc++-v3/include/bits/unique_ptr.h b/libstdc++-v3/include/bits/unique_ptr.h index a6f457ee59e..869d931330c 100644 --- a/libstdc++-v3/include/bits/unique_ptr.h +++ b/libstdc++-v3/include/bits/unique_ptr.h @@ -542,7 +542,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// std::hash specialization for unique_ptr. template<typename _Tp, typename _Dp> struct hash<unique_ptr<_Tp, _Dp>> - : public std::unary_function<unique_ptr<_Tp, _Dp>, size_t> + : public __hash_base<size_t, unique_ptr<_Tp, _Dp>> { size_t operator()(const unique_ptr<_Tp, _Dp>& __u) const diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h index 065a50274c5..8da171972eb 100644 --- a/libstdc++-v3/include/debug/formatter.h +++ b/libstdc++-v3/include/debug/formatter.h @@ -1,6 +1,6 @@ // Debug-mode error formatting implementation -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -46,6 +46,9 @@ namespace __gnu_debug template<typename _Iterator, typename _Sequence> class _Safe_iterator; + template<typename _Iterator, typename _Sequence> + class _Safe_local_iterator; + template<typename _Sequence> class _Safe_sequence; @@ -103,7 +106,9 @@ namespace __gnu_debug // forward_list __msg_insert_after_end, __msg_erase_after_bad, - __msg_valid_range2 + __msg_valid_range2, + // unordered sequence local iterators + __msg_local_iter_compare_bad }; class _Error_formatter @@ -236,6 +241,42 @@ namespace __gnu_debug } } + template<typename _Iterator, typename _Sequence> + _Parameter(const _Safe_local_iterator<_Iterator, _Sequence>& __it, + const char* __name, _Is_iterator) + : _M_kind(__iterator), _M_variant() + { + _M_variant._M_iterator._M_name = __name; + _M_variant._M_iterator._M_address = &__it; +#ifdef __GXX_RTTI + _M_variant._M_iterator._M_type = &typeid(__it); +#else + _M_variant._M_iterator._M_type = 0; +#endif + _M_variant._M_iterator._M_constness = + std::__are_same<_Safe_local_iterator<_Iterator, _Sequence>, + typename _Sequence::local_iterator>:: + __value ? __mutable_iterator : __const_iterator; + _M_variant._M_iterator._M_sequence = __it._M_get_sequence(); +#ifdef __GXX_RTTI + _M_variant._M_iterator._M_seq_type = &typeid(_Sequence); +#else + _M_variant._M_iterator._M_seq_type = 0; +#endif + + if (__it._M_singular()) + _M_variant._M_iterator._M_state = __singular; + else + { + if (__it._M_is_end()) + _M_variant._M_iterator._M_state = __end; + else if (__it._M_is_begin()) + _M_variant._M_iterator._M_state = __begin; + else + _M_variant._M_iterator._M_state = __middle; + } + } + template<typename _Type> _Parameter(const _Type*& __it, const char* __name, _Is_iterator) : _M_kind(__iterator), _M_variant() diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h index 75ed9ef057f..ea12589e3c0 100644 --- a/libstdc++-v3/include/debug/functions.h +++ b/libstdc++-v3/include/debug/functions.h @@ -1,6 +1,6 @@ // Debugging support implementation -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -144,6 +144,13 @@ namespace __gnu_debug const _Safe_iterator<_Iterator, _Sequence>& __last) { return __first._M_valid_range(__last); } + /** Safe local iterators know how to check if they form a valid range. */ + template<typename _Iterator, typename _Sequence> + inline bool + __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, + const _Safe_local_iterator<_Iterator, _Sequence>& __last) + { return __first._M_valid_range(__last); } + /* Checks that [first, last) is a valid range, and then returns * __first. This routine is useful when we can't use a separate * assertion statement because, e.g., we are in a constructor. diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index 127c3ba72d4..016ec7b9418 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -62,6 +62,43 @@ namespace __gnu_debug __check_singular_aux(const _Safe_iterator_base* __x) { return __x->_M_singular(); } + /** The precision to which we can calculate the distance between + * two iterators. + */ + enum _Distance_precision + { + __dp_equality, //< Can compare iterator equality, only + __dp_sign, //< Can determine equality and ordering + __dp_exact //< Can determine distance precisely + }; + + /** Determine the distance between two iterators with some known + * precision. + */ + template<typename _Iterator1, typename _Iterator2> + inline std::pair<typename std::iterator_traits<_Iterator1>::difference_type, + _Distance_precision> + __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, + std::random_access_iterator_tag) + { return std::make_pair(__rhs - __lhs, __dp_exact); } + + template<typename _Iterator1, typename _Iterator2> + inline std::pair<typename std::iterator_traits<_Iterator1>::difference_type, + _Distance_precision> + __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, + std::forward_iterator_tag) + { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); } + + template<typename _Iterator1, typename _Iterator2> + inline std::pair<typename std::iterator_traits<_Iterator1>::difference_type, + _Distance_precision> + __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs) + { + typedef typename std::iterator_traits<_Iterator1>::iterator_category + _Category; + return __get_distance(__lhs, __rhs, _Category()); + } + /** \brief Safe iterator wrapper. * * The class template %_Safe_iterator is a wrapper around an @@ -78,16 +115,6 @@ namespace __gnu_debug { typedef _Safe_iterator _Self; - /** The precision to which we can calculate the distance between - * two iterators. - */ - enum _Distance_precision - { - __dp_equality, //< Can compare iterator equality, only - __dp_sign, //< Can determine equality and ordering - __dp_exact //< Can determine distance precisely - }; - /// The underlying iterator _Iterator _M_current; @@ -380,30 +407,6 @@ namespace __gnu_debug _M_get_sequence() const { return static_cast<const _Sequence*>(_M_sequence); } - /** Determine the distance between two iterators with some known - * precision. - */ - template<typename _Iterator1, typename _Iterator2> - static std::pair<difference_type, _Distance_precision> - _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs) - { - typedef typename std::iterator_traits<_Iterator1>::iterator_category - _Category; - return _M_get_distance(__lhs, __rhs, _Category()); - } - - template<typename _Iterator1, typename _Iterator2> - static std::pair<difference_type, _Distance_precision> - _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, - std::random_access_iterator_tag) - { return std::make_pair(__rhs - __lhs, __dp_exact); } - - template<typename _Iterator1, typename _Iterator2> - static std::pair<difference_type, _Distance_precision> - _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, - std::forward_iterator_tag) - { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); } - /// Is this iterator equal to the sequence's begin() iterator? bool _M_is_begin() const { return base() == _M_get_sequence()->_M_base().begin(); } diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc index 942640c651d..777a707e7f3 100644 --- a/libstdc++-v3/include/debug/safe_iterator.tcc +++ b/libstdc++-v3/include/debug/safe_iterator.tcc @@ -1,6 +1,6 @@ // Debugging iterator implementation (out of line) -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -48,7 +48,7 @@ namespace __gnu_debug { const_iterator __begin = _M_get_sequence()->_M_base().begin(); std::pair<difference_type, _Distance_precision> __dist = - this->_M_get_distance(__begin, base()); + __get_distance(__begin, base()); bool __ok = ((__dist.second == __dp_exact && __dist.first >= -__n) || (__dist.second != __dp_exact && __dist.first > 0)); return __ok; @@ -57,7 +57,7 @@ namespace __gnu_debug { const_iterator __end = _M_get_sequence()->_M_base().end(); std::pair<difference_type, _Distance_precision> __dist = - this->_M_get_distance(base(), __end); + __get_distance(base(), __end); bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n) || (__dist.second != __dp_exact && __dist.first > 0)); return __ok; @@ -76,7 +76,7 @@ namespace __gnu_debug /* Determine if we can order the iterators without the help of the container */ std::pair<difference_type, _Distance_precision> __dist = - this->_M_get_distance(base(), __rhs.base()); + __get_distance(base(), __rhs.base()); switch (__dist.second) { case __dp_equality: if (__dist.first == 0) diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h new file mode 100644 index 00000000000..de0cbee2a62 --- /dev/null +++ b/libstdc++-v3/include/debug/safe_local_iterator.h @@ -0,0 +1,369 @@ +// Safe iterator implementation -*- C++ -*- + +// Copyright (C) 2011 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file debug/safe_local_iterator.h + * This file is a GNU debug extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H +#define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1 + +#include <debug/debug.h> +#include <debug/macros.h> +#include <debug/functions.h> +#include <debug/safe_unordered_base.h> +#include <ext/type_traits.h> + +namespace __gnu_debug +{ + /** \brief Safe iterator wrapper. + * + * The class template %_Safe_local_iterator is a wrapper around an + * iterator that tracks the iterator's movement among sequences and + * checks that operations performed on the "safe" iterator are + * legal. In additional to the basic iterator operations (which are + * validated, and then passed to the underlying iterator), + * %_Safe_local_iterator has member functions for iterator invalidation, + * attaching/detaching the iterator from sequences, and querying + * the iterator's state. + */ + template<typename _Iterator, typename _Sequence> + class _Safe_local_iterator : public _Safe_local_iterator_base + { + typedef _Safe_local_iterator _Self; + typedef typename _Sequence::size_type size_type; + + /// The underlying iterator + _Iterator _M_current; + + /// The bucket this local iterator belongs to + size_type _M_bucket; + + /// Determine if this is a constant iterator. + bool + _M_constant() const + { + typedef typename _Sequence::const_local_iterator const_iterator; + return std::__are_same<const_iterator, _Safe_local_iterator>::__value; + } + + typedef std::iterator_traits<_Iterator> _Traits; + + public: + typedef _Iterator iterator_type; + typedef typename _Traits::iterator_category iterator_category; + typedef typename _Traits::value_type value_type; + typedef typename _Traits::difference_type difference_type; + typedef typename _Traits::reference reference; + typedef typename _Traits::pointer pointer; + + /// @post the iterator is singular and unattached + _Safe_local_iterator() : _M_current() { } + + /** + * @brief Safe iterator construction from an unsafe iterator and + * its sequence. + * + * @pre @p seq is not NULL + * @post this is not singular + */ + _Safe_local_iterator(const _Iterator& __i, size_type __bucket, + const _Sequence* __seq) + : _Safe_local_iterator_base(__seq, _M_constant()), _M_current(__i), + _M_bucket(__bucket) + { + _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), + _M_message(__msg_init_singular) + ._M_iterator(*this, "this")); + } + + /** + * @brief Copy construction. + */ + _Safe_local_iterator(const _Safe_local_iterator& __x) + : _Safe_local_iterator_base(__x, _M_constant()), + _M_current(__x._M_current), _M_bucket(__x._M_bucket) + { + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 408. Is vector<reverse_iterator<char*> > forbidden? + _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() + || __x._M_current == _Iterator(), + _M_message(__msg_init_copy_singular) + ._M_iterator(*this, "this") + ._M_iterator(__x, "other")); + } + + /** + * @brief Converting constructor from a mutable iterator to a + * constant iterator. + */ + template<typename _MutableIterator> + _Safe_local_iterator( + const _Safe_local_iterator<_MutableIterator, + typename __gnu_cxx::__enable_if<std::__are_same< + _MutableIterator, + typename _Sequence::local_iterator::iterator_type>::__value, + _Sequence>::__type>& __x) + : _Safe_local_iterator_base(__x, _M_constant()), + _M_current(__x.base()), _M_bucket(__x._M_bucket) + { + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 408. Is vector<reverse_iterator<char*> > forbidden? + _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() + || __x.base() == _Iterator(), + _M_message(__msg_init_const_singular) + ._M_iterator(*this, "this") + ._M_iterator(__x, "other")); + } + + /** + * @brief Copy assignment. + */ + _Safe_local_iterator& + operator=(const _Safe_local_iterator& __x) + { + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 408. Is vector<reverse_iterator<char*> > forbidden? + _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() + || __x._M_current == _Iterator(), + _M_message(__msg_copy_singular) + ._M_iterator(*this, "this") + ._M_iterator(__x, "other")); + _M_current = __x._M_current; + _M_bucket = __x._M_bucket; + this->_M_attach(__x._M_sequence); + return *this; + } + + /** + * @brief Iterator dereference. + * @pre iterator is dereferenceable + */ + reference + operator*() const + { + _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), + _M_message(__msg_bad_deref) + ._M_iterator(*this, "this")); + return *_M_current; + } + + /** + * @brief Iterator dereference. + * @pre iterator is dereferenceable + * @todo Make this correct w.r.t. iterators that return proxies + * @todo Use addressof() instead of & operator + */ + pointer + operator->() const + { + _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), + _M_message(__msg_bad_deref) + ._M_iterator(*this, "this")); + return &*_M_current; + } + + // ------ Input iterator requirements ------ + /** + * @brief Iterator preincrement + * @pre iterator is incrementable + */ + _Safe_local_iterator& + operator++() + { + _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), + _M_message(__msg_bad_inc) + ._M_iterator(*this, "this")); + ++_M_current; + return *this; + } + + /** + * @brief Iterator postincrement + * @pre iterator is incrementable + */ + _Safe_local_iterator + operator++(int) + { + _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), + _M_message(__msg_bad_inc) + ._M_iterator(*this, "this")); + _Safe_local_iterator __tmp(*this); + ++_M_current; + return __tmp; + } + + // ------ Utilities ------ + /** + * @brief Return the underlying iterator + */ + _Iterator + base() const { return _M_current; } + + /** + * @brief Return the bucket + */ + size_type + bucket() const { return _M_bucket; } + + /** + * @brief Conversion to underlying non-debug iterator to allow + * better interaction with non-debug containers. + */ + operator _Iterator() const { return _M_current; } + + /** Attach iterator to the given sequence. */ + void + _M_attach(_Safe_sequence_base* __seq) + { _Safe_iterator_base::_M_attach(__seq, _M_constant()); } + + /** Likewise, but not thread-safe. */ + void + _M_attach_single(_Safe_sequence_base* __seq) + { _Safe_iterator_base::_M_attach_single(__seq, _M_constant()); } + + /// Is the iterator dereferenceable? + bool + _M_dereferenceable() const + { return !this->_M_singular() && !_M_is_end(); } + + /// Is the iterator incrementable? + bool + _M_incrementable() const + { return !this->_M_singular() && !_M_is_end(); } + + // Is the iterator range [*this, __rhs) valid? + template<typename _Other> + bool + _M_valid_range(const _Safe_local_iterator<_Other, + _Sequence>& __rhs) const; + + // The sequence this iterator references. + const _Sequence* + _M_get_sequence() const + { return static_cast<const _Sequence*>(_M_sequence); } + + /// Is this iterator equal to the sequence's begin() iterator? + bool _M_is_begin() const + { return base() == _M_get_sequence()->_M_base().begin(_M_bucket); } + + /// Is this iterator equal to the sequence's end() iterator? + bool _M_is_end() const + { return base() == _M_get_sequence()->_M_base().end(_M_bucket); } + + /// Is this iterator part of the same bucket as the other one? + template <typename _Other> + bool _M_in_same_bucket(const _Safe_local_iterator<_Other, + _Sequence>& __other) const + { return _M_bucket == __other.bucket(); } + }; + + template<typename _IteratorL, typename _IteratorR, typename _Sequence> + inline bool + operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, + const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) + { + _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), + _M_message(__msg_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), + _M_message(__msg_compare_different) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), + _M_message(__msg_compare_different) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), + _M_message(__msg_local_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + return __lhs.base() == __rhs.base(); + } + + template<typename _Iterator, typename _Sequence> + inline bool + operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, + const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) + { + _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), + _M_message(__msg_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), + _M_message(__msg_compare_different) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), + _M_message(__msg_local_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + return __lhs.base() == __rhs.base(); + } + + template<typename _IteratorL, typename _IteratorR, typename _Sequence> + inline bool + operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, + const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) + { + _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), + _M_message(__msg_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), + _M_message(__msg_compare_different) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), + _M_message(__msg_local_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + return __lhs.base() != __rhs.base(); + } + + template<typename _Iterator, typename _Sequence> + inline bool + operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, + const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) + { + _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), + _M_message(__msg_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), + _M_message(__msg_compare_different) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), + _M_message(__msg_local_iter_compare_bad) + ._M_iterator(__lhs, "lhs") + ._M_iterator(__rhs, "rhs")); + return __lhs.base() != __rhs.base(); + } +} // namespace __gnu_debug + +#include <debug/safe_local_iterator.tcc> + +#endif diff --git a/libstdc++-v3/include/debug/safe_local_iterator.tcc b/libstdc++-v3/include/debug/safe_local_iterator.tcc new file mode 100644 index 00000000000..e91e6bfbf08 --- /dev/null +++ b/libstdc++-v3/include/debug/safe_local_iterator.tcc @@ -0,0 +1,75 @@ +// Debugging iterator implementation (out of line) -*- C++ -*- + +// Copyright (C) 2011 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file debug/safe_locale_iterator.tcc + * This file is a GNU debug extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_TCC +#define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_TCC 1 + +namespace __gnu_debug +{ + template<typename _Iterator, typename _Sequence> + template<typename _Other> + bool + _Safe_local_iterator<_Iterator, _Sequence>:: + _M_valid_range(const _Safe_local_iterator<_Other, _Sequence>& __rhs) const + { + if (!_M_can_compare(__rhs)) + return false; + if (_M_bucket != __rhs._M_bucket) + return false; + + /* Determine if we can order the iterators without the help of + the container */ + std::pair<difference_type, _Distance_precision> __dist = + __get_distance(base(), __rhs.base()); + switch (__dist.second) + { + case __dp_equality: + if (__dist.first == 0) + return true; + break; + + case __dp_sign: + case __dp_exact: + return __dist.first >= 0; + } + + /* We can only test for equality, but check if one of the + iterators is at an extreme. */ + /* Optim for classic [begin, it) or [it, end) ranges, limit checks + * when code is valid. */ + if (_M_is_begin() || __rhs._M_is_end()) + return true; + if (_M_is_end() || __rhs._M_is_begin()) + return false; + + // Assume that this is a valid range; we can't check anything else + return true; + } +} // namespace __gnu_debug + +#endif diff --git a/libstdc++-v3/include/debug/safe_unordered_base.h b/libstdc++-v3/include/debug/safe_unordered_base.h new file mode 100644 index 00000000000..14d83bc49fb --- /dev/null +++ b/libstdc++-v3/include/debug/safe_unordered_base.h @@ -0,0 +1,175 @@ +// Safe sequence/iterator base implementation -*- C++ -*- + +// Copyright (C) 2011 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file debug/safe_unordered_base.h + * This file is a GNU debug extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_DEBUG_SAFE_UNORDERED_BASE_H +#define _GLIBCXX_DEBUG_SAFE_UNORDERED_BASE_H 1 + +#include <debug/safe_base.h> + +namespace __gnu_debug +{ + class _Safe_unordered_sequence_base; + + /** \brief Basic functionality for a @a safe iterator. + * + * The %_Safe_local_iterator_base base class implements the functionality + * of a safe local iterator that is not specific to a particular iterator + * type. It contains a pointer back to the sequence it references + * along with iterator version information and pointers to form a + * doubly-linked list of local iterators referenced by the container. + * + * This class must not perform any operations that can throw an + * exception, or the exception guarantees of derived iterators will + * be broken. + */ + class _Safe_local_iterator_base : public _Safe_iterator_base + { + protected: + /** Initializes the iterator and makes it singular. */ + _Safe_local_iterator_base() + { } + + /** Initialize the iterator to reference the sequence pointed to + * by @p__seq. @p __constant is true when we are initializing a + * constant local iterator, and false if it is a mutable local iterator. + * Note that @p __seq may be NULL, in which case the iterator will be + * singular. Otherwise, the iterator will reference @p __seq and + * be nonsingular. + */ + _Safe_local_iterator_base(const _Safe_sequence_base* __seq, bool __constant) + { this->_M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); } + + /** Initializes the iterator to reference the same sequence that + @p __x does. @p __constant is true if this is a constant + iterator, and false if it is mutable. */ + _Safe_local_iterator_base(const _Safe_local_iterator_base& __x, + bool __constant) + { this->_M_attach(__x._M_sequence, __constant); } + + _Safe_local_iterator_base& + operator=(const _Safe_local_iterator_base&); + + explicit + _Safe_local_iterator_base(const _Safe_local_iterator_base&); + + ~_Safe_local_iterator_base() { this->_M_detach(); } + + _Safe_unordered_sequence_base* + _M_get_sequence() const _GLIBCXX_NOEXCEPT; + + public: + /** Attaches this iterator to the given sequence, detaching it + * from whatever sequence it was attached to originally. If the + * new sequence is the NULL pointer, the iterator is left + * unattached. + */ + void _M_attach(_Safe_sequence_base* __seq, bool __constant); + + /** Likewise, but not thread-safe. */ + void _M_attach_single(_Safe_sequence_base* __seq, bool __constant) throw (); + + /** Detach the iterator for whatever sequence it is attached to, + * if any. + */ + void _M_detach(); + + /** Likewise, but not thread-safe. */ + void _M_detach_single() throw (); + }; + + /** + * @brief Base class that supports tracking of local iterators that + * reference an unordered sequence. + * + * The %_Safe_unordered_sequence_base class provides basic support for + * tracking iterators into an unordered sequence. Sequences that track + * iterators must derived from %_Safe_sequence_base publicly, so + * that safe iterators (which inherit _Safe_iterator_base) can + * attach to them. This class contains four linked lists of + * iterators, one for constant iterators, one for mutable + * iterators, one for constant local iterators, one for mutable local + * iterator and a version number that allows very fast + * invalidation of all iterators that reference the container. + * + * This class must ensure that no operation on it may throw an + * exception, otherwise @a safe sequences may fail to provide the + * exception-safety guarantees required by the C++ standard. + */ + class _Safe_unordered_sequence_base : public _Safe_sequence_base + { + typedef _Safe_sequence_base _Base; + public: + /// The list of mutable local iterators that reference this container + _Safe_iterator_base* _M_local_iterators; + + /// The list of constant local iterators that reference this container + _Safe_iterator_base* _M_const_local_iterators; + + protected: + // Initialize with a version number of 1 and no iterators + _Safe_unordered_sequence_base() + : _M_local_iterators(0), _M_const_local_iterators(0) + { } + + /** Notify all iterators that reference this sequence that the + sequence is being destroyed. */ + ~_Safe_unordered_sequence_base() + { this->_M_detach_all(); } + + /** Detach all iterators, leaving them singular. */ + void + _M_detach_all(); + + /** Swap this sequence with the given sequence. This operation + * also swaps ownership of the iterators, so that when the + * operation is complete all iterators that originally referenced + * one container now reference the other container. + */ + void + _M_swap(_Safe_unordered_sequence_base& __x); + + public: + /** Attach an iterator to this sequence. */ + void + _M_attach_local(_Safe_iterator_base* __it, bool __constant); + + /** Likewise but not thread safe. */ + void + _M_attach_local_single(_Safe_iterator_base* __it, bool __constant) throw (); + + /** Detach an iterator from this sequence */ + void + _M_detach_local(_Safe_iterator_base* __it); + + /** Likewise but not thread safe. */ + void + _M_detach_local_single(_Safe_iterator_base* __it) throw (); + }; +} // namespace __gnu_debug + +#endif diff --git a/libstdc++-v3/include/debug/safe_unordered_sequence.h b/libstdc++-v3/include/debug/safe_unordered_sequence.h new file mode 100644 index 00000000000..f32b9113e6f --- /dev/null +++ b/libstdc++-v3/include/debug/safe_unordered_sequence.h @@ -0,0 +1,75 @@ +// Safe sequence implementation -*- C++ -*- + +// Copyright (C) 2011 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file debug/safe_unordered_sequence.h + * This file is a GNU debug extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_DEBUG_SAFE_UNORDERED_SEQUENCE_H +#define _GLIBCXX_DEBUG_SAFE_UNORDERED_SEQUENCE_H 1 + +#include <debug/debug.h> +#include <debug/macros.h> +#include <debug/functions.h> +#include <debug/safe_unordered_base.h> + +namespace __gnu_debug +{ + /** + * @brief Base class for constructing a @a safe unordered sequence type + * that tracks iterators that reference it. + * + * The class template %_Safe_unordered_sequence simplifies the + * construction of @a safe unordered sequences that track the iterators + * that reference the sequence, so that the iterators are notified of + * changes in the sequence that may affect their operation, e.g., if + * the container invalidates its iterators or is destructed. This class + * template may only be used by deriving from it and passing the name + * of the derived class as its template parameter via the curiously + * recurring template pattern. The derived class must have @c + * iterator and @const_iterator types that are instantiations of + * class template _Safe_iterator for this sequence. Iterators will + * then be tracked automatically. + */ + template<typename _Sequence> + class _Safe_unordered_sequence : public _Safe_unordered_sequence_base + { + public: + /** Invalidates all iterators @c x that reference this sequence, + are not singular, and for which @c pred(x) returns @c + true. @c pred will be invoked with the normal iterators nested + in the safe ones. */ + template<typename _Predicate> + void + _M_invalidate_if(_Predicate __pred); + + template<typename _Predicate> + void + _M_invalidate_local_if(_Predicate __pred); + }; +} // namespace __gnu_debug + +#include <debug/safe_unordered_sequence.tcc> + +#endif diff --git a/libstdc++-v3/include/debug/safe_unordered_sequence.tcc b/libstdc++-v3/include/debug/safe_unordered_sequence.tcc new file mode 100644 index 00000000000..88907e8839d --- /dev/null +++ b/libstdc++-v3/include/debug/safe_unordered_sequence.tcc @@ -0,0 +1,100 @@ +// Safe sequence implementation -*- C++ -*- + +// Copyright (C) 2011 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file debug/safe_unordered_sequence.tcc + * This file is a GNU debug extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_DEBUG_SAFE_UNORDERED_SEQUENCE_TCC +#define _GLIBCXX_DEBUG_SAFE_UNORDERED_SEQUENCE_TCC 1 + +namespace __gnu_debug +{ + template<typename _Sequence> + template<typename _Predicate> + void + _Safe_unordered_sequence<_Sequence>:: + _M_invalidate_if(_Predicate __pred) + { + typedef typename _Sequence::iterator iterator; + typedef typename _Sequence::const_iterator const_iterator; + + __gnu_cxx::__scoped_lock sentry(this->_M_get_mutex()); + for (_Safe_iterator_base* __iter = _M_iterators; __iter;) + { + iterator* __victim = static_cast<iterator*>(__iter); + __iter = __iter->_M_next; + if (!__victim->_M_singular() && __pred(__victim->base())) + { + __victim->_M_invalidate(); + } + } + + for (_Safe_iterator_base* __iter2 = _M_const_iterators; __iter2;) + { + const_iterator* __victim = static_cast<const_iterator*>(__iter2); + __iter2 = __iter2->_M_next; + if (!__victim->_M_singular() && __pred(__victim->base())) + { + __victim->_M_invalidate(); + } + } + } + + + template<typename _Sequence> + template<typename _Predicate> + void + _Safe_unordered_sequence<_Sequence>:: + _M_invalidate_local_if(_Predicate __pred) + { + typedef typename _Sequence::local_iterator local_iterator; + typedef typename _Sequence::const_local_iterator const_local_iterator; + + __gnu_cxx::__scoped_lock sentry(this->_M_get_mutex()); + for (_Safe_iterator_base* __iter = _M_local_iterators; __iter;) + { + local_iterator* __victim = static_cast<local_iterator*>(__iter); + __iter = __iter->_M_next; + if (!__victim->_M_singular() && __pred(__victim->base())) + { + __victim->_M_invalidate(); + } + } + + for (_Safe_iterator_base* __iter2 = _M_const_local_iterators; __iter2;) + { + const_local_iterator* __victim = + static_cast<const_local_iterator*>(__iter2); + __iter2 = __iter2->_M_next; + if (!__victim->_M_singular() && __pred(__victim->base())) + { + __victim->_M_invalidate(); + } + } + } + +} // namespace __gnu_debug + +#endif diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index 4f087b75992..93ce517b1f7 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -35,8 +35,9 @@ #else # include <unordered_map> -#include <debug/safe_sequence.h> +#include <debug/safe_unordered_sequence.h> #include <debug/safe_iterator.h> +#include <debug/safe_local_iterator.h> namespace std _GLIBCXX_VISIBILITY(default) { @@ -49,15 +50,16 @@ namespace __debug typename _Alloc = std::allocator<_Key> > class unordered_map : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, - public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash, - _Pred, _Alloc> > + public __gnu_debug::_Safe_unordered_sequence<unordered_map<_Key, _Tp, + _Hash, _Pred, _Alloc> > { typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; - typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence<unordered_map> _Safe_base; typedef typename _Base::const_iterator _Base_const_iterator; typedef typename _Base::iterator _Base_iterator; - typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; + typedef typename _Base::const_local_iterator _Base_const_local_iterator; + typedef typename _Base::local_iterator _Base_local_iterator; public: typedef typename _Base::size_type size_type; @@ -72,6 +74,10 @@ namespace __debug unordered_map> iterator; typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, unordered_map> const_iterator; + typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator, + unordered_map> local_iterator; + typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator, + unordered_map> const_local_iterator; explicit unordered_map(size_type __n = 10, @@ -81,7 +87,7 @@ namespace __debug : _Base(__n, __hf, __eql, __a) { } template<typename _InputIterator> - unordered_map(_InputIterator __first, _InputIterator __last, + unordered_map(_InputIterator __first, _InputIterator __last, size_type __n = 0, const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), @@ -176,15 +182,36 @@ namespace __debug { return const_iterator(_Base::end(), this); } // local versions - using _Base::begin; - using _Base::end; - using _Base::cbegin; - using _Base::cend; + local_iterator + begin(size_type __b) + { return local_iterator(_Base::begin(__b), __b, this); } + + local_iterator + end(size_type __b) + { return local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + begin(size_type __b) const + { return const_local_iterator(_Base::begin(__b), __b, this); } + + const_local_iterator + end(size_type __b) const + { return const_local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + cbegin(size_type __b) const + { return const_local_iterator(_Base::cbegin(__b), __b, this); } + + const_local_iterator + cend(size_type __b) const + { return const_local_iterator(_Base::cend(__b), __b, this); } std::pair<iterator, bool> insert(const value_type& __obj) { + size_type __bucket_count = this->bucket_count(); std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); + _M_check_rehashed(__bucket_count); return std::make_pair(iterator(__res.first, this), __res.second); } @@ -192,43 +219,56 @@ namespace __debug insert(const_iterator __hint, const value_type& __obj) { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), __obj), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__hint.base(), __obj); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } template<typename _Pair, typename = typename std::enable_if<std::is_convertible<_Pair, value_type>::value>::type> - std::pair<iterator, bool> - insert(_Pair&& __obj) - { + std::pair<iterator, bool> + insert(_Pair&& __obj) + { + size_type __bucket_count = this->bucket_count(); std::pair<_Base_iterator, bool> __res = _Base::insert(std::forward<_Pair>(__obj)); + _M_check_rehashed(__bucket_count); return std::make_pair(iterator(__res.first, this), __res.second); } template<typename _Pair, typename = typename std::enable_if<std::is_convertible<_Pair, value_type>::value>::type> - iterator - insert(const_iterator __hint, _Pair&& __obj) - { + iterator + insert(const_iterator __hint, _Pair&& __obj) + { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), - std::forward<_Pair>(__obj)), - this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = + _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } void insert(std::initializer_list<value_type> __l) - { _Base::insert(__l); } + { + size_type __bucket_count = this->bucket_count(); + _Base::insert(__l); + _M_check_rehashed(__bucket_count); + } template<typename _InputIterator> - void - insert(_InputIterator __first, _InputIterator __last) - { + void + insert(_InputIterator __first, _InputIterator __last) + { __glibcxx_check_valid_range(__first, __last); + size_type __bucket_count = this->bucket_count(); _Base::insert(__gnu_debug::__base(__first), __gnu_debug::__base(__last)); + _M_check_rehashed(__bucket_count); } iterator @@ -264,8 +304,15 @@ namespace __debug _Base_iterator __victim(_Base::find(__key)); if (__victim != _Base::end()) { - this->_M_invalidate_if(_Equal(__victim)); + this->_M_invalidate_if([__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); + size_type __bucket_count = this->bucket_count(); _Base::erase(__victim); + _M_check_rehashed(__bucket_count); __ret = 1; } return __ret; @@ -275,8 +322,17 @@ namespace __debug erase(const_iterator __it) { __glibcxx_check_erase(__it); - this->_M_invalidate_if(_Equal(__it.base())); - return iterator(_Base::erase(__it.base()), this); + _Base_const_iterator __victim = __it.base(); + this->_M_invalidate_if([__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_const_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __next = _Base::erase(__it.base()); + _M_check_rehashed(__bucket_count); + return iterator(__next, this); } iterator @@ -290,10 +346,17 @@ namespace __debug _M_message(__gnu_debug::__msg_valid_range) ._M_iterator(__first, "first") ._M_iterator(__last, "last")); - this->_M_invalidate_if(_Equal(__tmp)); + this->_M_invalidate_if([__tmp](_Base_const_iterator __it) + { return __it == __tmp; }); + _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); + this->_M_invalidate_local_if( + [__local_tmp](_Base_const_local_iterator __it) + { return __it == __local_tmp; }); } - return iterator(_Base::erase(__first.base(), - __last.base()), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __next = _Base::erase(__first.base(), __last.base()); + _M_check_rehashed(__bucket_count); + return iterator(__next, this); } _Base& @@ -304,11 +367,37 @@ namespace __debug private: void + _M_invalidate_locals() + { + _Base_local_iterator __local_end = _Base::end(0); + this->_M_invalidate_local_if( + [__local_end](_Base_const_local_iterator __it) + { return __it != __local_end; }); + } + + void _M_invalidate_all() { - typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; - this->_M_invalidate_if(_Not_equal(_Base::end())); + _Base_iterator __end = _Base::end(); + this->_M_invalidate_if([__end](_Base_const_iterator __it) + { return __it != __end; }); + _M_invalidate_locals(); } + + void + _M_check_rehashed(size_type __prev_count) + { + if (__prev_count != this->bucket_count()) + _M_invalidate_locals(); + } + + static _Base_local_iterator + _S_to_local(_Base_iterator __it) + { return _Base_local_iterator(__it._M_cur_node); } + + static _Base_const_local_iterator + _S_to_local(_Base_const_iterator __it) + { return _Base_const_local_iterator(__it._M_cur_node); } }; template<typename _Key, typename _Tp, typename _Hash, @@ -341,15 +430,17 @@ namespace __debug class unordered_multimap : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, - public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash, - _Pred, _Alloc> > + public __gnu_debug::_Safe_unordered_sequence<unordered_multimap<_Key, + _Tp, _Hash, _Pred, _Alloc> > { typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; - typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence<unordered_multimap> + _Safe_base; typedef typename _Base::const_iterator _Base_const_iterator; typedef typename _Base::iterator _Base_iterator; - typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; + typedef typename _Base::const_local_iterator _Base_const_local_iterator; + typedef typename _Base::local_iterator _Base_local_iterator; public: typedef typename _Base::size_type size_type; @@ -364,6 +455,10 @@ namespace __debug unordered_multimap> iterator; typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, unordered_multimap> const_iterator; + typedef __gnu_debug::_Safe_local_iterator< + _Base_local_iterator, unordered_multimap> local_iterator; + typedef __gnu_debug::_Safe_local_iterator< + _Base_const_local_iterator, unordered_multimap> const_local_iterator; explicit unordered_multimap(size_type __n = 10, @@ -373,7 +468,7 @@ namespace __debug : _Base(__n, __hf, __eql, __a) { } template<typename _InputIterator> - unordered_multimap(_InputIterator __first, _InputIterator __last, + unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n = 0, const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), @@ -468,28 +563,60 @@ namespace __debug { return const_iterator(_Base::end(), this); } // local versions - using _Base::begin; - using _Base::end; - using _Base::cbegin; - using _Base::cend; + local_iterator + begin(size_type __b) + { return local_iterator(_Base::begin(__b), __b, this); } + + local_iterator + end(size_type __b) + { return local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + begin(size_type __b) const + { return const_local_iterator(_Base::begin(__b), __b, this); } + + const_local_iterator + end(size_type __b) const + { return const_local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + cbegin(size_type __b) const + { return const_local_iterator(_Base::cbegin(__b), __b, this); } + + const_local_iterator + cend(size_type __b) const + { return const_local_iterator(_Base::cend(__b), __b, this); } iterator insert(const value_type& __obj) - { return iterator(_Base::insert(__obj), this); } + { + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__obj); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); + } iterator insert(const_iterator __hint, const value_type& __obj) { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), __obj), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__hint.base(), __obj); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } template<typename _Pair, typename = typename std::enable_if<std::is_convertible<_Pair, value_type>::value>::type> - iterator - insert(_Pair&& __obj) - { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); } + iterator + insert(_Pair&& __obj) + { + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); + } template<typename _Pair, typename = typename std::enable_if<std::is_convertible<_Pair, @@ -498,9 +625,11 @@ namespace __debug insert(const_iterator __hint, _Pair&& __obj) { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), - std::forward<_Pair>(__obj)), - this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = + _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } void @@ -508,12 +637,14 @@ namespace __debug { _Base::insert(__l); } template<typename _InputIterator> - void - insert(_InputIterator __first, _InputIterator __last) - { + void + insert(_InputIterator __first, _InputIterator __last) + { __glibcxx_check_valid_range(__first, __last); + size_type __bucket_count = this->bucket_count(); _Base::insert(__gnu_debug::__base(__first), __gnu_debug::__base(__last)); + _M_check_rehashed(__bucket_count); } iterator @@ -546,14 +677,21 @@ namespace __debug erase(const key_type& __key) { size_type __ret(0); + size_type __bucket_count = this->bucket_count(); std::pair<_Base_iterator, _Base_iterator> __pair = _Base::equal_range(__key); for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) { - this->_M_invalidate_if(_Equal(__victim)); + this->_M_invalidate_if([__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); _Base::erase(__victim++); ++__ret; } + _M_check_rehashed(__bucket_count); return __ret; } @@ -561,8 +699,17 @@ namespace __debug erase(const_iterator __it) { __glibcxx_check_erase(__it); - this->_M_invalidate_if(_Equal(__it.base())); - return iterator(_Base::erase(__it.base()), this); + _Base_const_iterator __victim = __it.base(); + this->_M_invalidate_if([__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_const_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __next = _Base::erase(__it.base()); + _M_check_rehashed(__bucket_count); + return iterator(__next, this); } iterator @@ -576,10 +723,17 @@ namespace __debug _M_message(__gnu_debug::__msg_valid_range) ._M_iterator(__first, "first") ._M_iterator(__last, "last")); - this->_M_invalidate_if(_Equal(__tmp)); + this->_M_invalidate_if([__tmp](_Base_const_iterator __it) + { return __it == __tmp; }); + _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); + this->_M_invalidate_local_if( + [__local_tmp](_Base_const_local_iterator __it) + { return __it == __local_tmp; }); } - return iterator(_Base::erase(__first.base(), - __last.base()), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __next = _Base::erase(__first.base(), __last.base()); + _M_check_rehashed(__bucket_count); + return iterator(__next, this); } _Base& @@ -590,11 +744,37 @@ namespace __debug private: void + _M_invalidate_locals() + { + _Base_local_iterator __local_end = _Base::end(0); + this->_M_invalidate_local_if( + [__local_end](_Base_const_local_iterator __it) + { return __it != __local_end; }); + } + + void _M_invalidate_all() { - typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; - this->_M_invalidate_if(_Not_equal(_Base::end())); + _Base_iterator __end = _Base::end(); + this->_M_invalidate_if([__end](_Base_const_iterator __it) + { return __it != __end; }); + _M_invalidate_locals(); } + + void + _M_check_rehashed(size_type __prev_count) + { + if (__prev_count != this->bucket_count()) + _M_invalidate_locals(); + } + + static _Base_local_iterator + _S_to_local(_Base_iterator __it) + { return _Base_local_iterator(__it._M_cur_node); } + + static _Base_const_local_iterator + _S_to_local(_Base_const_iterator __it) + { return _Base_const_local_iterator(__it._M_cur_node); } }; template<typename _Key, typename _Tp, typename _Hash, diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index c0b245d95a0..981db4a83e6 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -35,8 +35,9 @@ #else # include <unordered_set> -#include <debug/safe_sequence.h> +#include <debug/safe_unordered_sequence.h> #include <debug/safe_iterator.h> +#include <debug/safe_local_iterator.h> namespace std _GLIBCXX_VISIBILITY(default) { @@ -49,15 +50,16 @@ namespace __debug typename _Alloc = std::allocator<_Value> > class unordered_set : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>, - public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash, + public __gnu_debug::_Safe_unordered_sequence<unordered_set<_Value, _Hash, _Pred, _Alloc> > { typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; - typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence<unordered_set> _Safe_base; typedef typename _Base::const_iterator _Base_const_iterator; typedef typename _Base::iterator _Base_iterator; - typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; + typedef typename _Base::const_local_iterator _Base_const_local_iterator; + typedef typename _Base::local_iterator _Base_local_iterator; public: typedef typename _Base::size_type size_type; @@ -72,6 +74,10 @@ namespace __debug unordered_set> iterator; typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, unordered_set> const_iterator; + typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator, + unordered_set> local_iterator; + typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator, + unordered_set> const_local_iterator; explicit unordered_set(size_type __n = 10, @@ -176,16 +182,37 @@ namespace __debug { return const_iterator(_Base::end(), this); } // local versions - using _Base::begin; - using _Base::end; - using _Base::cbegin; - using _Base::cend; + local_iterator + begin(size_type __b) + { return local_iterator(_Base::begin(__b), __b, this); } + + local_iterator + end(size_type __b) + { return local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + begin(size_type __b) const + { return const_local_iterator(_Base::begin(__b), __b, this); } + + const_local_iterator + end(size_type __b) const + { return const_local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + cbegin(size_type __b) const + { return const_local_iterator(_Base::cbegin(__b), __b, this); } + + const_local_iterator + cend(size_type __b) const + { return const_local_iterator(_Base::cend(__b), __b, this); } std::pair<iterator, bool> insert(const value_type& __obj) { + size_type __bucket_count = this->bucket_count(); typedef std::pair<_Base_iterator, bool> __pair_type; - __pair_type __res = _Base::insert(__obj); + __pair_type __res = _Base::insert(__obj); + _M_check_rehashed(__bucket_count); return std::make_pair(iterator(__res.first, this), __res.second); } @@ -193,14 +220,19 @@ namespace __debug insert(const_iterator __hint, const value_type& __obj) { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), __obj), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__hint.base(), __obj); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } std::pair<iterator, bool> insert(value_type&& __obj) { + size_type __bucket_count = this->bucket_count(); typedef std::pair<typename _Base::iterator, bool> __pair_type; - __pair_type __res = _Base::insert(std::move(__obj)); + __pair_type __res = _Base::insert(std::move(__obj)); + _M_check_rehashed(__bucket_count); return std::make_pair(iterator(__res.first, this), __res.second); } @@ -208,20 +240,29 @@ namespace __debug insert(const_iterator __hint, value_type&& __obj) { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), std::move(__obj)), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } void insert(std::initializer_list<value_type> __l) - { _Base::insert(__l); } + { + size_type __bucket_count = this->bucket_count(); + _Base::insert(__l); + _M_check_rehashed(__bucket_count); + } template<typename _InputIterator> - void - insert(_InputIterator __first, _InputIterator __last) - { + void + insert(_InputIterator __first, _InputIterator __last) + { __glibcxx_check_valid_range(__first, __last); + size_type __bucket_count = this->bucket_count(); _Base::insert(__gnu_debug::__base(__first), __gnu_debug::__base(__last)); + _M_check_rehashed(__bucket_count); } iterator @@ -257,8 +298,16 @@ namespace __debug _Base_iterator __victim(_Base::find(__key)); if (__victim != _Base::end()) { - this->_M_invalidate_if(_Equal(__victim)); + this->_M_invalidate_if( + [__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); + size_type __bucket_count = this->bucket_count(); _Base::erase(__victim); + _M_check_rehashed(__bucket_count); __ret = 1; } return __ret; @@ -268,8 +317,18 @@ namespace __debug erase(const_iterator __it) { __glibcxx_check_erase(__it); - this->_M_invalidate_if(_Equal(__it.base())); - return iterator(_Base::erase(__it.base()), this); + _Base_const_iterator __victim = __it.base(); + this->_M_invalidate_if( + [__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_const_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __next = _Base::erase(__it.base()); + _M_check_rehashed(__bucket_count); + return iterator(__next, this); } iterator @@ -283,10 +342,19 @@ namespace __debug _M_message(__gnu_debug::__msg_valid_range) ._M_iterator(__first, "first") ._M_iterator(__last, "last")); - this->_M_invalidate_if(_Equal(__tmp)); + this->_M_invalidate_if( + [__tmp](_Base_const_iterator __it) + { return __it == __tmp; }); + _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); + this->_M_invalidate_local_if( + [__local_tmp](_Base_const_local_iterator __it) + { return __it == __local_tmp; }); } - return iterator(_Base::erase(__first.base(), - __last.base()), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __next = _Base::erase(__first.base(), + __last.base()); + _M_check_rehashed(__bucket_count); + return iterator(__next, this); } _Base& @@ -297,11 +365,38 @@ namespace __debug private: void + _M_invalidate_locals() + { + _Base_local_iterator __local_end = _Base::end(0); + this->_M_invalidate_local_if( + [__local_end](_Base_const_local_iterator __it) + { return __it != __local_end; }); + } + + void _M_invalidate_all() { - typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; - this->_M_invalidate_if(_Not_equal(_Base::end())); + _Base_iterator __end = _Base::end(); + this->_M_invalidate_if( + [__end](_Base_const_iterator __it) + { return __it != __end; }); + _M_invalidate_locals(); + } + + void + _M_check_rehashed(size_type __prev_count) + { + if (__prev_count != this->bucket_count()) + _M_invalidate_locals(); } + + static _Base_local_iterator + _S_to_local(_Base_iterator __it) + { return _Base_local_iterator(__it._M_cur_node); } + + static _Base_const_local_iterator + _S_to_local(_Base_const_iterator __it) + { return _Base_const_local_iterator(__it._M_cur_node); } }; template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> @@ -330,15 +425,17 @@ namespace __debug typename _Alloc = std::allocator<_Value> > class unordered_multiset : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, - public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash, - _Pred, _Alloc> > + public __gnu_debug::_Safe_unordered_sequence< + unordered_multiset<_Value, _Hash, _Pred, _Alloc> > { typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base; - typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence<unordered_multiset> + _Safe_base; typedef typename _Base::const_iterator _Base_const_iterator; typedef typename _Base::iterator _Base_iterator; - typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; + typedef typename _Base::const_local_iterator _Base_const_local_iterator; + typedef typename _Base::local_iterator _Base_local_iterator; public: typedef typename _Base::size_type size_type; @@ -353,6 +450,10 @@ namespace __debug unordered_multiset> iterator; typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, unordered_multiset> const_iterator; + typedef __gnu_debug::_Safe_local_iterator< + _Base_local_iterator, unordered_multiset> local_iterator; + typedef __gnu_debug::_Safe_local_iterator< + _Base_const_local_iterator, unordered_multiset> const_local_iterator; explicit unordered_multiset(size_type __n = 10, @@ -457,44 +558,85 @@ namespace __debug { return const_iterator(_Base::end(), this); } // local versions - using _Base::begin; - using _Base::end; - using _Base::cbegin; - using _Base::cend; + local_iterator + begin(size_type __b) + { return local_iterator(_Base::begin(__b), __b, this); } + + local_iterator + end(size_type __b) + { return local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + begin(size_type __b) const + { return const_local_iterator(_Base::begin(__b), __b, this); } + + const_local_iterator + end(size_type __b) const + { return const_local_iterator(_Base::end(__b), __b, this); } + + const_local_iterator + cbegin(size_type __b) const + { return const_local_iterator(_Base::cbegin(__b), __b, this); } + + const_local_iterator + cend(size_type __b) const + { return const_local_iterator(_Base::cend(__b), __b, this); } iterator insert(const value_type& __obj) - { return iterator(_Base::insert(__obj), this); } + { + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__obj); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); + } iterator insert(const_iterator __hint, const value_type& __obj) { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), __obj), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__hint.base(), __obj); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } iterator insert(value_type&& __obj) - { return iterator(_Base::insert(std::move(__obj)), this); } + { + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(std::move(__obj)); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); + } iterator insert(const_iterator __hint, value_type&& __obj) { __glibcxx_check_insert(__hint); - return iterator(_Base::insert(__hint.base(), std::move(__obj)), this); + size_type __bucket_count = this->bucket_count(); + _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); + _M_check_rehashed(__bucket_count); + return iterator(__it, this); } void insert(std::initializer_list<value_type> __l) - { _Base::insert(__l); } + { + size_type __bucket_count = this->bucket_count(); + _Base::insert(__l); + _M_check_rehashed(__bucket_count); + } template<typename _InputIterator> - void - insert(_InputIterator __first, _InputIterator __last) - { + void + insert(_InputIterator __first, _InputIterator __last) + { __glibcxx_check_valid_range(__first, __last); + size_type __bucket_count = this->bucket_count(); _Base::insert(__gnu_debug::__base(__first), __gnu_debug::__base(__last)); + _M_check_rehashed(__bucket_count); } iterator @@ -531,7 +673,12 @@ namespace __debug _Base::equal_range(__key); for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) { - this->_M_invalidate_if(_Equal(__victim)); + this->_M_invalidate_if([__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); _Base::erase(__victim++); ++__ret; } @@ -542,7 +689,13 @@ namespace __debug erase(const_iterator __it) { __glibcxx_check_erase(__it); - this->_M_invalidate_if(_Equal(__it.base())); + _Base_const_iterator __victim = __it.base(); + this->_M_invalidate_if([__victim](_Base_const_iterator __it) + { return __it == __victim; }); + _Base_const_local_iterator __local_victim = _S_to_local(__victim); + this->_M_invalidate_local_if( + [__local_victim](_Base_const_local_iterator __it) + { return __it == __local_victim; }); return iterator(_Base::erase(__it.base()), this); } @@ -557,7 +710,12 @@ namespace __debug _M_message(__gnu_debug::__msg_valid_range) ._M_iterator(__first, "first") ._M_iterator(__last, "last")); - this->_M_invalidate_if(_Equal(__tmp)); + this->_M_invalidate_if([__tmp](_Base_const_iterator __it) + { return __it == __tmp; }); + _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); + this->_M_invalidate_local_if( + [__local_tmp](_Base_const_local_iterator __it) + { return __it == __local_tmp; }); } return iterator(_Base::erase(__first.base(), __last.base()), this); @@ -571,11 +729,37 @@ namespace __debug private: void + _M_invalidate_locals() + { + _Base_local_iterator __local_end = _Base::end(0); + this->_M_invalidate_local_if( + [__local_end](_Base_const_local_iterator __it) + { return __it != __local_end; }); + } + + void _M_invalidate_all() { - typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; - this->_M_invalidate_if(_Not_equal(_Base::end())); + _Base_iterator __end = _Base::end(); + this->_M_invalidate_if([__end](_Base_const_iterator __it) + { return __it != __end; }); + _M_invalidate_locals(); + } + + void + _M_check_rehashed(size_type __prev_count) + { + if (__prev_count != this->bucket_count()) + _M_invalidate_locals(); } + + static _Base_local_iterator + _S_to_local(_Base_iterator __it) + { return _Base_local_iterator(__it._M_cur_node); } + + static _Base_const_local_iterator + _S_to_local(_Base_const_iterator __it) + { return _Base_const_local_iterator(__it._M_cur_node); } }; template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> diff --git a/libstdc++-v3/include/precompiled/stdc++.h b/libstdc++-v3/include/precompiled/stdc++.h index 510a6552f52..b0c93cabe31 100644 --- a/libstdc++-v3/include/precompiled/stdc++.h +++ b/libstdc++-v3/include/precompiled/stdc++.h @@ -1,6 +1,6 @@ // C++ includes used for precompiling -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -106,6 +106,7 @@ #include <random> #include <ratio> #include <regex> +#include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> diff --git a/libstdc++-v3/include/std/array b/libstdc++-v3/include/std/array index 474b884ecb5..0abb628aded 100644 --- a/libstdc++-v3/include/std/array +++ b/libstdc++-v3/include/std/array @@ -35,6 +35,7 @@ # include <bits/c++0x_warning.h> #else +#include <stdexcept> #include <bits/stl_algobase.h> #include <bits/range_access.h> @@ -150,8 +151,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION operator[](size_type __n) { return _M_instance[__n]; } - const_reference - operator[](size_type __n) const + constexpr const_reference + operator[](size_type __n) const noexcept { return _M_instance[__n]; } reference @@ -162,12 +163,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _M_instance[__n]; } - const_reference + constexpr const_reference at(size_type __n) const { - if (__n >= _Nm) - std::__throw_out_of_range(__N("array::at")); - return _M_instance[__n]; + return __n < _Nm ? _M_instance[__n] : +#ifdef __EXCEPTIONS + throw out_of_range(__N("array::at")); +#else + _M_instance[0]; +#endif } reference diff --git a/libstdc++-v3/include/std/bitset b/libstdc++-v3/include/std/bitset index 6d23df2cba8..f880e72bd0d 100644 --- a/libstdc++-v3/include/std/bitset +++ b/libstdc++-v3/include/std/bitset @@ -111,7 +111,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT { return _M_w[_S_whichword(__pos)]; } - _WordT + _GLIBCXX_CONSTEXPR _WordT _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT { return _M_w[_S_whichword(__pos)]; } @@ -221,12 +221,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // find first "on" bit size_t - _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT; + _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT; // find the next "on" bit that follows "prev" size_t - _M_do_find_next(size_t __prev, size_t __not_found) const - _GLIBCXX_NOEXCEPT; + _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT; }; // Definitions of non-inline functions from _Base_bitset. @@ -405,7 +404,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_getword(size_t) _GLIBCXX_NOEXCEPT { return _M_w; } - _WordT + _GLIBCXX_CONSTEXPR _WordT _M_getword(size_t) const _GLIBCXX_NOEXCEPT { return _M_w; } @@ -557,7 +556,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER return *new _WordT; } - _WordT + _GLIBCXX_CONSTEXPR _WordT _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT { return 0; } @@ -1017,7 +1016,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER return *this; } - bool + _GLIBCXX_CONSTEXPR bool _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) != static_cast<_WordT>(0)); } @@ -1122,7 +1121,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER operator[](size_t __position) { return reference(*this, __position); } - bool + _GLIBCXX_CONSTEXPR bool operator[](size_t __position) const { return _Unchecked_test(__position); } //@} diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index ed8fc303306..f64fd6e1e7b 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -585,7 +585,7 @@ _GLIBCXX_END_NAMESPACE_VERSION template<typename _Clock, typename _Dur1, typename _Rep2, typename _Period2> - inline time_point<_Clock, + inline constexpr time_point<_Clock, typename common_type<_Dur1, duration<_Rep2, _Period2>>::type> operator+(const time_point<_Clock, _Dur1>& __lhs, const duration<_Rep2, _Period2>& __rhs) @@ -593,27 +593,37 @@ _GLIBCXX_END_NAMESPACE_VERSION typedef duration<_Rep2, _Period2> __dur2; typedef typename common_type<_Dur1,__dur2>::type __ct; typedef time_point<_Clock, __ct> __time_point; - return __time_point(__lhs) += __rhs; + return __time_point(__lhs.time_since_epoch() + __rhs); } template<typename _Rep1, typename _Period1, typename _Clock, typename _Dur2> - inline time_point<_Clock, + inline constexpr time_point<_Clock, typename common_type<duration<_Rep1, _Period1>, _Dur2>::type> operator+(const duration<_Rep1, _Period1>& __lhs, const time_point<_Clock, _Dur2>& __rhs) - { return __rhs + __lhs; } + { + typedef duration<_Rep1, _Period1> __dur1; + typedef typename common_type<__dur1,_Dur2>::type __ct; + typedef time_point<_Clock, __ct> __time_point; + return __time_point(__rhs.time_since_epoch() + __lhs); + } template<typename _Clock, typename _Dur1, typename _Rep2, typename _Period2> - inline time_point<_Clock, + inline constexpr time_point<_Clock, typename common_type<_Dur1, duration<_Rep2, _Period2>>::type> operator-(const time_point<_Clock, _Dur1>& __lhs, const duration<_Rep2, _Period2>& __rhs) - { return __lhs + (-__rhs); } + { + typedef duration<_Rep2, _Period2> __dur2; + typedef typename common_type<_Dur1,__dur2>::type __ct; + typedef time_point<_Clock, __ct> __time_point; + return __time_point(__lhs.time_since_epoch() -__rhs); + } template<typename _Clock, typename _Dur1, typename _Dur2> - inline typename common_type<_Dur1, _Dur2>::type + inline constexpr typename common_type<_Dur1, _Dur2>::type operator-(const time_point<_Clock, _Dur1>& __lhs, const time_point<_Clock, _Dur2>& __rhs) { return __lhs.time_since_epoch() - __rhs.time_since_epoch(); } @@ -673,7 +683,7 @@ _GLIBCXX_END_NAMESPACE_VERSION < system_clock::duration::zero(), "a clock's minimum duration cannot be less than its epoch"); - static constexpr bool is_monotonic = false; + static constexpr bool is_steady = false; static time_point now() throw (); @@ -696,21 +706,21 @@ _GLIBCXX_END_NAMESPACE_VERSION }; #ifdef _GLIBCXX_USE_CLOCK_MONOTONIC - /// monotonic_clock - struct monotonic_clock + /// steady_clock + struct steady_clock { typedef chrono::nanoseconds duration; typedef duration::rep rep; typedef duration::period period; - typedef chrono::time_point<monotonic_clock, duration> time_point; + typedef chrono::time_point<steady_clock, duration> time_point; - static constexpr bool is_monotonic = true; + static constexpr bool is_steady = true; static time_point now(); }; #else - typedef system_clock monotonic_clock; + typedef system_clock steady_clock; #endif typedef system_clock high_resolution_clock; diff --git a/libstdc++-v3/include/std/mutex b/libstdc++-v3/include/std/mutex index 1c66afc9e2c..184011715c7 100644 --- a/libstdc++-v3/include/std/mutex +++ b/libstdc++-v3/include/std/mutex @@ -212,7 +212,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef __gthread_mutex_t __native_type; #ifdef _GLIBCXX_USE_CLOCK_MONOTONIC - typedef chrono::monotonic_clock __clock_t; + typedef chrono::steady_clock __clock_t; #else typedef chrono::high_resolution_clock __clock_t; #endif @@ -317,7 +317,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef __gthread_recursive_mutex_t __native_type; #ifdef _GLIBCXX_USE_CLOCK_MONOTONIC - typedef chrono::monotonic_clock __clock_t; + typedef chrono::steady_clock __clock_t; #else typedef chrono::high_resolution_clock __clock_t; #endif diff --git a/libstdc++-v3/include/std/system_error b/libstdc++-v3/include/std/system_error index da09a758825..565261e709b 100644 --- a/libstdc++-v3/include/std/system_error +++ b/libstdc++-v3/include/std/system_error @@ -66,47 +66,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION class error_category { protected: - error_category(); + error_category() noexcept; public: - virtual ~error_category(); + virtual ~error_category() noexcept; error_category(const error_category&) = delete; error_category& operator=(const error_category&) = delete; virtual const char* - name() const = 0; + name() const noexcept = 0; virtual string message(int) const = 0; virtual error_condition - default_error_condition(int __i) const; + default_error_condition(int __i) const noexcept; virtual bool - equivalent(int __i, const error_condition& __cond) const; + equivalent(int __i, const error_condition& __cond) const noexcept; virtual bool - equivalent(const error_code& __code, int __i) const; + equivalent(const error_code& __code, int __i) const noexcept; bool - operator<(const error_category& __other) const + operator<(const error_category& __other) const noexcept { return less<const error_category*>()(this, &__other); } bool - operator==(const error_category& __other) const + operator==(const error_category& __other) const noexcept { return this == &__other; } bool - operator!=(const error_category& __other) const + operator!=(const error_category& __other) const noexcept { return this != &__other; } }; // DR 890. - _GLIBCXX_CONST const error_category& system_category() throw(); - _GLIBCXX_CONST const error_category& generic_category() throw(); + _GLIBCXX_CONST const error_category& system_category() noexcept; + _GLIBCXX_CONST const error_category& generic_category() noexcept; - error_code make_error_code(errc); + error_code make_error_code(errc) noexcept; template<typename _Tp> struct hash; @@ -115,49 +115,49 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Implementation-specific error identification struct error_code { - error_code() + error_code() noexcept : _M_value(0), _M_cat(&system_category()) { } - error_code(int __v, const error_category& __cat) + error_code(int __v, const error_category& __cat) noexcept : _M_value(__v), _M_cat(&__cat) { } - template<typename _ErrorCodeEnum> - error_code(_ErrorCodeEnum __e, - typename enable_if<is_error_code_enum<_ErrorCodeEnum>::value>::type* = 0) + template<typename _ErrorCodeEnum, typename = typename + enable_if<is_error_code_enum<_ErrorCodeEnum>::value>::type> + error_code(_ErrorCodeEnum __e) noexcept { *this = make_error_code(__e); } void - assign(int __v, const error_category& __cat) + assign(int __v, const error_category& __cat) noexcept { _M_value = __v; _M_cat = &__cat; } void - clear() + clear() noexcept { assign(0, system_category()); } // DR 804. template<typename _ErrorCodeEnum> typename enable_if<is_error_code_enum<_ErrorCodeEnum>::value, error_code&>::type - operator=(_ErrorCodeEnum __e) + operator=(_ErrorCodeEnum __e) noexcept { return *this = make_error_code(__e); } int - value() const { return _M_value; } + value() const noexcept { return _M_value; } const error_category& - category() const { return *_M_cat; } + category() const noexcept { return *_M_cat; } error_condition - default_error_condition() const; + default_error_condition() const noexcept; string message() const { return category().message(value()); } - explicit operator bool() const + explicit operator bool() const noexcept { return _M_value != 0 ? true : false; } // DR 804. @@ -170,11 +170,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // 19.4.2.6 non-member functions inline error_code - make_error_code(errc __e) + make_error_code(errc __e) noexcept { return error_code(static_cast<int>(__e), generic_category()); } inline bool - operator<(const error_code& __lhs, const error_code& __rhs) + operator<(const error_code& __lhs, const error_code& __rhs) noexcept { return (__lhs.category() < __rhs.category() || (__lhs.category() == __rhs.category() @@ -186,26 +186,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION operator<<(basic_ostream<_CharT, _Traits>& __os, const error_code& __e) { return (__os << __e.category().name() << ':' << __e.value()); } - error_condition make_error_condition(errc); + error_condition make_error_condition(errc) noexcept; /// error_condition // Portable error identification struct error_condition { - error_condition() + error_condition() noexcept : _M_value(0), _M_cat(&generic_category()) { } - error_condition(int __v, const error_category& __cat) + error_condition(int __v, const error_category& __cat) noexcept : _M_value(__v), _M_cat(&__cat) { } - template<typename _ErrorConditionEnum> - error_condition(_ErrorConditionEnum __e, - typename enable_if<is_error_condition_enum - <_ErrorConditionEnum>::value>::type* = 0) + template<typename _ErrorConditionEnum, typename = typename + enable_if<is_error_condition_enum<_ErrorConditionEnum>::value>::type> + error_condition(_ErrorConditionEnum __e) noexcept { *this = make_error_condition(__e); } void - assign(int __v, const error_category& __cat) + assign(int __v, const error_category& __cat) noexcept { _M_value = __v; _M_cat = &__cat; @@ -215,25 +214,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _ErrorConditionEnum> typename enable_if<is_error_condition_enum <_ErrorConditionEnum>::value, error_condition&>::type - operator=(_ErrorConditionEnum __e) + operator=(_ErrorConditionEnum __e) noexcept { return *this = make_error_condition(__e); } void - clear() + clear() noexcept { assign(0, generic_category()); } // 19.4.3.4 observers - int - value() const { return _M_value; } + int + value() const noexcept { return _M_value; } const error_category& - category() const { return *_M_cat; } + category() const noexcept { return *_M_cat; } string message() const { return category().message(value()); } - explicit operator bool() const + explicit operator bool() const noexcept { return _M_value != 0 ? true : false; } // DR 804. @@ -244,11 +243,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // 19.4.3.6 non-member functions inline error_condition - make_error_condition(errc __e) + make_error_condition(errc __e) noexcept { return error_condition(static_cast<int>(__e), generic_category()); } inline bool - operator<(const error_condition& __lhs, const error_condition& __rhs) + operator<(const error_condition& __lhs, + const error_condition& __rhs) noexcept { return (__lhs.category() < __rhs.category() || (__lhs.category() == __rhs.category() @@ -257,45 +257,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // 19.4.4 Comparison operators inline bool - operator==(const error_code& __lhs, const error_code& __rhs) + operator==(const error_code& __lhs, const error_code& __rhs) noexcept { return (__lhs.category() == __rhs.category() && __lhs.value() == __rhs.value()); } inline bool - operator==(const error_code& __lhs, const error_condition& __rhs) + operator==(const error_code& __lhs, const error_condition& __rhs) noexcept { return (__lhs.category().equivalent(__lhs.value(), __rhs) || __rhs.category().equivalent(__lhs, __rhs.value())); } inline bool - operator==(const error_condition& __lhs, const error_code& __rhs) + operator==(const error_condition& __lhs, const error_code& __rhs) noexcept { return (__rhs.category().equivalent(__rhs.value(), __lhs) || __lhs.category().equivalent(__rhs, __lhs.value())); } inline bool - operator==(const error_condition& __lhs, const error_condition& __rhs) + operator==(const error_condition& __lhs, + const error_condition& __rhs) noexcept { return (__lhs.category() == __rhs.category() && __lhs.value() == __rhs.value()); } inline bool - operator!=(const error_code& __lhs, const error_code& __rhs) + operator!=(const error_code& __lhs, const error_code& __rhs) noexcept { return !(__lhs == __rhs); } inline bool - operator!=(const error_code& __lhs, const error_condition& __rhs) + operator!=(const error_code& __lhs, const error_condition& __rhs) noexcept { return !(__lhs == __rhs); } inline bool - operator!=(const error_condition& __lhs, const error_code& __rhs) + operator!=(const error_condition& __lhs, const error_code& __rhs) noexcept { return !(__lhs == __rhs); } inline bool - operator!=(const error_condition& __lhs, const error_condition& __rhs) + operator!=(const error_condition& __lhs, + const error_condition& __rhs) noexcept { return !(__lhs == __rhs); } @@ -338,7 +340,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION virtual ~system_error() throw(); const error_code& - code() const throw() { return _M_code; } + code() const noexcept { return _M_code; } }; _GLIBCXX_END_NAMESPACE_VERSION |