From patchwork Tue Jul 19 19:43:23 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 105510 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 0DF7DB6F64 for ; Wed, 20 Jul 2011 05:44:56 +1000 (EST) Received: (qmail 14433 invoked by alias); 19 Jul 2011 19:44:52 -0000 Received: (qmail 14316 invoked by uid 22791); 19 Jul 2011 19:44:30 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, T_FILL_THIS_FORM_SHORT X-Spam-Check-By: sourceware.org Received: from smtp6-g21.free.fr (HELO smtp6-g21.free.fr) (212.27.42.6) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 19 Jul 2011 19:43:35 +0000 Received: from localhost.localdomain (unknown [82.237.250.248]) by smtp6-g21.free.fr (Postfix) with ESMTP id D4BD2822A4; Tue, 19 Jul 2011 21:43:24 +0200 (CEST) Message-ID: <4E25DE5B.1080300@free.fr> Date: Tue, 19 Jul 2011 21:43:23 +0200 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.18) Gecko/20110621 Mandriva/3.1.11-0.1mdv2010.2 (2010.2) Thunderbird/3.1.11 MIME-Version: 1.0 To: Paolo Carlini CC: "libstdc++@gcc.gnu.org" , gcc-patches@gcc.gnu.org Subject: Re: safe unordered local iterators References: <4E10CE8A.1040300@free.fr> <4E176C37.7010809@free.fr> <4E1ACCE2.1000407@oracle.com> <4E1B524B.3050805@free.fr> <4E1F5D10.7060207@free.fr> <4E23FEA9.9070308@oracle.com> In-Reply-To: <4E23FEA9.9070308@oracle.com> Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Attached patch applied: 2011-07-19 François Dumont * include/debug/safe_unordered_base.h, safe_unordered_sequence.h, safe_unordered_sequence.tcc, safe_local_iterator.h, safe_local_iterator.tcc: New, support for unordered sequence safe local iterators. * include/Makefile.am: Add previous files. * include/Makefile.in: Regenerate. * include/debug/unordered_map, unordered_set: Implement _Safe_unordered_sequence and expose _Safe_local_iterator. * include/debug/safe_iterator.h, safe_iterator.tcc: Refactor _Safe_iterator::_M_get_distance static method to expose it as __get_distance function and use it in _Safe_local_iterator type. * include/debug/formatter.h: Add __msg_local_iter_compare_bad _Debug_msg_id enum entry to notify invalid comparison between local iterators from different buckets. Add _Parameter constructor from _Safe_local_iterator. * include/debug/functions.h: Add __valid_range overload for _Safe_local_iterator. * src/debug.cc: Add _Safe_unordered_sequence_base and _Safe_local_iterator_base methods implementations. * config/abi/pre/gnu.ver: Add export of some _Safe_unordered_sequence_base and _Safe_local_iterator_base methods. * testsuite/util/debug/checks.h: Add use_invalid_iterator function to simulate use of a singular iterator. * testsuite/util/debug/unordered_checks.h: New, several functions to simulate classic invalid usage of unordered sequence local iterators. * testsuite/23_containers/unordered_map/debug/ use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc, use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc, invalid_local_iterator_compare_neg.cc: New. * testsuite/23_containers/unordered_multimap/debug/ use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc, use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc, invalid_local_iterator_compare_neg.cc: New. * testsuite/23_containers/unordered_set/debug/ use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc, use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc, invalid_local_iterator_compare_neg.cc: New. * testsuite/23_containers/unordered_multiset/debug/ use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc, use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc, invalid_local_iterator_compare_neg.cc: New. Tested on x86_64 linux. I have integrated all your remarks Paolo. Regards On 07/18/2011 11:36 AM, Paolo Carlini wrote: > Hi, >> Ok to apply ? > I think the patch can go in, but before that, please fix some coding > convention issues: > 1- I spotted quite a few overlong lines. > 2- In simple conditionals avoid redundant curly brackets, eg > > + if (_M_sequence) > + { > + _M_get_sequence()->_M_detach_local(this); > + } > > or > > + if (!__victim->_M_singular()&& __pred(__victim->base())) > + { > + __victim->_M_invalidate(); > + } > > Many of those. > 3- I also see a misplaced bracket: > > + switch (__dist.second) { > > 4- Finally, not a big deal, but I think you want the __get_distance > inline, are all very simple (on the other hand, at some point we > should go through the entire debug/ directory and move out of line > many large member functions currently inline). > > Thanks! > Paolo. > Index: src/debug.cc =================================================================== --- src/debug.cc (revision 176486) +++ src/debug.cc (working copy) @@ -1,7 +1,7 @@ // Debugging mode support code -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 -// Free Software Foundation, Inc. +// 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 // software; you can redistribute it and/or modify it under the @@ -25,7 +25,9 @@ #include #include +#include #include +#include #include #include #include @@ -51,28 +53,58 @@ } void - swap_seq(__gnu_debug::_Safe_sequence_base& __lhs, - __gnu_debug::_Safe_sequence_base& __rhs) + swap_its(__gnu_debug::_Safe_sequence_base& __lhs, + __gnu_debug::_Safe_iterator_base*& __lhs_its, + __gnu_debug::_Safe_sequence_base& __rhs, + __gnu_debug::_Safe_iterator_base*& __rhs_its) { - swap(__lhs._M_iterators, __rhs._M_iterators); - swap(__lhs._M_const_iterators, __rhs._M_const_iterators); - swap(__lhs._M_version, __rhs._M_version); + swap(__lhs_its, __rhs_its); __gnu_debug::_Safe_iterator_base* __iter; - for (__iter = __rhs._M_iterators; __iter; __iter = __iter->_M_next) + for (__iter = __rhs_its; __iter; __iter = __iter->_M_next) __iter->_M_sequence = &__rhs; - for (__iter = __lhs._M_iterators; __iter; __iter = __iter->_M_next) + for (__iter = __lhs_its; __iter; __iter = __iter->_M_next) __iter->_M_sequence = &__lhs; - for (__iter = __rhs._M_const_iterators; __iter; __iter = __iter->_M_next) - __iter->_M_sequence = &__rhs; - for (__iter = __lhs._M_const_iterators; __iter; __iter = __iter->_M_next) - __iter->_M_sequence = &__lhs; } + + void + swap_seq(__gnu_debug::_Safe_sequence_base& __lhs, + __gnu_debug::_Safe_sequence_base& __rhs) + { + swap(__lhs._M_version, __rhs._M_version); + swap_its(__lhs, __lhs._M_iterators, + __rhs, __rhs._M_iterators); + swap_its(__lhs, __lhs._M_const_iterators, + __rhs, __rhs._M_const_iterators); + } + + void + swap_useq(__gnu_debug::_Safe_unordered_sequence_base& __lhs, + __gnu_debug::_Safe_unordered_sequence_base& __rhs) + { + swap_seq(__lhs, __rhs); + swap_its(__lhs, __lhs._M_local_iterators, + __rhs, __rhs._M_local_iterators); + swap_its(__lhs, __lhs._M_const_local_iterators, + __rhs, __rhs._M_const_local_iterators); + } + + void + detach_all(__gnu_debug::_Safe_iterator_base* __iter) + { + for (; __iter;) + { + __gnu_debug::_Safe_iterator_base* __old = __iter; + __iter = __iter->_M_next; + __old->_M_reset(); + } + } } // anonymous namespace namespace __gnu_debug { const char* _S_debug_messages[] = { + // General Checks "function requires a valid iterator range [%1.name;, %2.name;)", "attempt to insert into container with a singular iterator", "attempt to insert into container with an iterator" @@ -93,15 +125,18 @@ "elements in iterator range [%1.name;, %2.name;) do not form a heap", "elements in iterator range [%1.name;, %2.name;)" " do not form a heap with respect to the predicate %3;", + // std::bitset checks "attempt to write through a singular bitset reference", "attempt to read from a singular bitset reference", "attempt to flip a singular bitset reference", + // std::list checks "attempt to splice a list into itself", "attempt to splice lists with inequal allocators", "attempt to splice elements referenced by a %1.state; iterator", "attempt to splice an iterator from a different container", "splice destination %1.name;" " occurs within source range [%2.name;, %3.name;)", + // iterator checks "attempt to initialize an iterator that will immediately become singular", "attempt to copy-construct an iterator from a singular iterator", "attempt to construct a constant iterator" @@ -124,17 +159,24 @@ " iterator to a %2.state; iterator", "attempt to compute the different between two iterators" " from different sequences", + // istream_iterator "attempt to dereference an end-of-stream istream_iterator", "attempt to increment an end-of-stream istream_iterator", + // ostream_iterator "attempt to output via an ostream_iterator with no associated stream", + // istreambuf_iterator "attempt to dereference an end-of-stream istreambuf_iterator" " (this is a GNU extension)", "attempt to increment an end-of-stream istreambuf_iterator", + // std::forward_list "attempt to insert into container after an end iterator", "attempt to erase from container after a %2.state; iterator not followed" " by a dereferenceable one", "function requires a valid iterator range (%2.name;, %3.name;)" - ", \"%2.name;\" shall be before and not equal to \"%3.name;\"" + ", \"%2.name;\" shall be before and not equal to \"%3.name;\"", + // std::unordered_sequence::local_iterator + "attempt to compare local iterators from different unordered sequence" + " buckets" }; void @@ -142,20 +184,10 @@ _M_detach_all() { __gnu_cxx::__scoped_lock sentry(_M_get_mutex()); - for (_Safe_iterator_base* __iter = _M_iterators; __iter;) - { - _Safe_iterator_base* __old = __iter; - __iter = __iter->_M_next; - __old->_M_reset(); - } + detach_all(_M_iterators); _M_iterators = 0; - for (_Safe_iterator_base* __iter2 = _M_const_iterators; __iter2;) - { - _Safe_iterator_base* __old = __iter2; - __iter2 = __iter2->_M_next; - __old->_M_reset(); - } + detach_all(_M_const_iterators); _M_const_iterators = 0; } @@ -299,9 +331,7 @@ _M_detach() { if (_M_sequence) - { - _M_sequence->_M_detach(this); - } + _M_sequence->_M_detach(this); _M_reset(); } @@ -311,9 +341,7 @@ _M_detach_single() throw () { if (_M_sequence) - { - _M_sequence->_M_detach_single(this); - } + _M_sequence->_M_detach_single(this); _M_reset(); } @@ -346,7 +374,144 @@ _M_get_mutex() throw () { return get_safe_base_mutex(_M_sequence); } + _Safe_unordered_sequence_base* + _Safe_local_iterator_base:: + _M_get_sequence() const _GLIBCXX_NOEXCEPT + { return static_cast<_Safe_unordered_sequence_base*>(_M_sequence); } + void + _Safe_local_iterator_base:: + _M_attach(_Safe_sequence_base* __seq, bool __constant) + { + _M_detach(); + + // Attach to the new sequence (if there is one) + if (__seq) + { + _M_sequence = __seq; + _M_version = _M_sequence->_M_version; + _M_get_sequence()->_M_attach_local(this, __constant); + } + } + + void + _Safe_local_iterator_base:: + _M_attach_single(_Safe_sequence_base* __seq, bool __constant) throw () + { + _M_detach_single(); + + // Attach to the new sequence (if there is one) + if (__seq) + { + _M_sequence = __seq; + _M_version = _M_sequence->_M_version; + _M_get_sequence()->_M_attach_local_single(this, __constant); + } + } + + void + _Safe_local_iterator_base:: + _M_detach() + { + if (_M_sequence) + _M_get_sequence()->_M_detach_local(this); + + _M_reset(); + } + + void + _Safe_local_iterator_base:: + _M_detach_single() throw () + { + if (_M_sequence) + _M_get_sequence()->_M_detach_local_single(this); + + _M_reset(); + } + + void + _Safe_unordered_sequence_base:: + _M_detach_all() + { + __gnu_cxx::__scoped_lock sentry(_M_get_mutex()); + detach_all(_M_iterators); + _M_iterators = 0; + + detach_all(_M_const_iterators); + _M_const_iterators = 0; + + detach_all(_M_local_iterators); + _M_local_iterators = 0; + + detach_all(_M_const_local_iterators); + _M_const_local_iterators = 0; + } + + void + _Safe_unordered_sequence_base:: + _M_swap(_Safe_unordered_sequence_base& __x) + { + // We need to lock both sequences to swap + using namespace __gnu_cxx; + __mutex *__this_mutex = &_M_get_mutex(); + __mutex *__x_mutex = &__x._M_get_mutex(); + if (__this_mutex == __x_mutex) + { + __scoped_lock __lock(*__this_mutex); + swap_useq(*this, __x); + } + else + { + __scoped_lock __l1(__this_mutex < __x_mutex + ? *__this_mutex : *__x_mutex); + __scoped_lock __l2(__this_mutex < __x_mutex + ? *__x_mutex : *__this_mutex); + swap_useq(*this, __x); + } + } + + void + _Safe_unordered_sequence_base:: + _M_attach_local(_Safe_iterator_base* __it, bool __constant) + { + __gnu_cxx::__scoped_lock sentry(_M_get_mutex()); + _M_attach_local_single(__it, __constant); + } + + void + _Safe_unordered_sequence_base:: + _M_attach_local_single(_Safe_iterator_base* __it, bool __constant) throw () + { + _Safe_iterator_base*& __its = + __constant ? _M_const_local_iterators : _M_local_iterators; + __it->_M_next = __its; + if (__it->_M_next) + __it->_M_next->_M_prior = __it; + __its = __it; + } + + void + _Safe_unordered_sequence_base:: + _M_detach_local(_Safe_iterator_base* __it) + { + // Remove __it from this sequence's list + __gnu_cxx::__scoped_lock sentry(_M_get_mutex()); + _M_detach_local_single(__it); + } + + void + _Safe_unordered_sequence_base:: + _M_detach_local_single(_Safe_iterator_base* __it) throw () + { + // Remove __it from this sequence's list + __it->_M_unlink(); + if (_M_const_local_iterators == __it) + _M_const_local_iterators = __it->_M_next; + if (_M_local_iterators == __it) + _M_local_iterators = __it->_M_next; + } + + void _Error_formatter::_Parameter:: _M_print_field(const _Error_formatter* __formatter, const char* __name) const { Index: include/Makefile.in =================================================================== --- include/Makefile.in (revision 176486) +++ include/Makefile.in (working copy) @@ -946,8 +946,13 @@ ${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 \ Index: include/debug/unordered_map =================================================================== --- include/debug/unordered_map (revision 176486) +++ include/debug/unordered_map (working copy) @@ -35,8 +35,9 @@ #else # include -#include +#include #include +#include namespace std _GLIBCXX_VISIBILITY(default) { @@ -49,15 +50,16 @@ typename _Alloc = std::allocator<_Key> > class unordered_map : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, - public __gnu_debug::_Safe_sequence > + public __gnu_debug::_Safe_unordered_sequence > { typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; - typedef __gnu_debug::_Safe_sequence _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence _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 @@ 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 @@ : _Base(__n, __hf, __eql, __a) { } template - 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 @@ { 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 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 @@ 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::value>::type> - std::pair - insert(_Pair&& __obj) - { + std::pair + 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::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 __l) - { _Base::insert(__l); } + { + size_type __bucket_count = this->bucket_count(); + _Base::insert(__l); + _M_check_rehashed(__bucket_count); + } template - 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 @@ _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 @@ 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 @@ _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 @@ 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, - public __gnu_debug::_Safe_sequence > + public __gnu_debug::_Safe_unordered_sequence > { typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; - typedef __gnu_debug::_Safe_sequence _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence + _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 @@ 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 @@ : _Base(__n, __hf, __eql, __a) { } template - 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 @@ { 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::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(__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 @@ { _Base::insert(__l); } template - 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 @@ 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 @@ 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 @@ _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 @@ 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. + +/** @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 + template + 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(__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(__iter2); + __iter2 = __iter2->_M_next; + if (!__victim->_M_singular() && __pred(__victim->base())) + { + __victim->_M_invalidate(); + } + } + } + + + template + template + 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(__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(__iter2); + __iter2 = __iter2->_M_next; + if (!__victim->_M_singular() && __pred(__victim->base())) + { + __victim->_M_invalidate(); + } + } + } + +} // namespace __gnu_debug + +#endif Index: include/debug/safe_local_iterator.h =================================================================== --- include/debug/safe_local_iterator.h (revision 0) +++ include/debug/safe_local_iterator.h (revision 0) @@ -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 +// . + +/** @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 +#include +#include +#include +#include + +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 + 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::__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_t __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 > 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 + _Safe_local_iterator( + const _Safe_local_iterator<_MutableIterator, + typename __gnu_cxx::__enable_if::__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 > 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 > 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 + 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(_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 + bool _M_in_same_bucket(const _Safe_local_iterator<_Other, + _Sequence>& __other) const + { return _M_bucket == __other.bucket(); } + }; + + template + 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 + 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 + 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 + 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 + +#endif Property changes on: include/debug/safe_local_iterator.h ___________________________________________________________________ Added: svn:eol-style + native Index: include/debug/formatter.h =================================================================== --- include/debug/formatter.h (revision 176486) +++ include/debug/formatter.h (working copy) @@ -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 @@ template class _Safe_iterator; + template + class _Safe_local_iterator; + template class _Safe_sequence; @@ -103,7 +106,9 @@ // 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 @@ } } + template + _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 _Parameter(const _Type*& __it, const char* __name, _Is_iterator) : _M_kind(__iterator), _M_variant() Index: include/debug/functions.h =================================================================== --- include/debug/functions.h (revision 176486) +++ include/debug/functions.h (working copy) @@ -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 @@ 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 + 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. Index: include/debug/safe_iterator.tcc =================================================================== --- include/debug/safe_iterator.tcc (revision 176486) +++ include/debug/safe_iterator.tcc (working copy) @@ -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 @@ { const_iterator __begin = _M_get_sequence()->_M_base().begin(); std::pair __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 @@ { const_iterator __end = _M_get_sequence()->_M_base().end(); std::pair __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 @@ /* Determine if we can order the iterators without the help of the container */ std::pair __dist = - this->_M_get_distance(base(), __rhs.base()); + __get_distance(base(), __rhs.base()); switch (__dist.second) { case __dp_equality: if (__dist.first == 0) Index: include/debug/unordered_set =================================================================== --- include/debug/unordered_set (revision 176486) +++ include/debug/unordered_set (working copy) @@ -35,8 +35,9 @@ #else # include -#include +#include #include +#include namespace std _GLIBCXX_VISIBILITY(default) { @@ -49,15 +50,16 @@ typename _Alloc = std::allocator<_Value> > class unordered_set : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>, - public __gnu_debug::_Safe_sequence > { typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; - typedef __gnu_debug::_Safe_sequence _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence _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 @@ 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 @@ { 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 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 @@ 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 insert(value_type&& __obj) { + size_type __bucket_count = this->bucket_count(); typedef std::pair __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 @@ 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 __l) - { _Base::insert(__l); } + { + size_type __bucket_count = this->bucket_count(); + _Base::insert(__l); + _M_check_rehashed(__bucket_count); + } template - 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 @@ _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 @@ 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 @@ _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 @@ 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 @@ -330,15 +425,17 @@ typename _Alloc = std::allocator<_Value> > class unordered_multiset : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, - public __gnu_debug::_Safe_sequence > + 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 _Safe_base; + typedef __gnu_debug::_Safe_unordered_sequence + _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 @@ 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 @@ { 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 __l) - { _Base::insert(__l); } + { + size_type __bucket_count = this->bucket_count(); + _Base::insert(__l); + _M_check_rehashed(__bucket_count); + } template - 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 @@ _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 @@ 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 @@ _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 @@ 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 Index: include/debug/safe_unordered_sequence.h =================================================================== --- include/debug/safe_unordered_sequence.h (revision 0) +++ include/debug/safe_unordered_sequence.h (revision 0) @@ -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 +// . + +/** @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 +#include +#include +#include + +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 + 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 + void + _M_invalidate_if(_Predicate __pred); + + template + void + _M_invalidate_local_if(_Predicate __pred); + }; +} // namespace __gnu_debug + +#include + +#endif Property changes on: include/debug/safe_unordered_sequence.h ___________________________________________________________________ Added: svn:eol-style + native Index: include/debug/safe_unordered_base.h =================================================================== --- include/debug/safe_unordered_base.h (revision 0) +++ include/debug/safe_unordered_base.h (revision 0) @@ -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 +// . + +/** @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 + +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 Property changes on: include/debug/safe_unordered_base.h ___________________________________________________________________ Added: svn:eol-style + native Index: include/debug/safe_local_iterator.tcc =================================================================== --- include/debug/safe_local_iterator.tcc (revision 0) +++ include/debug/safe_local_iterator.tcc (revision 0) @@ -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 +// . + +/** @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 + template + 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 __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 Index: include/debug/safe_iterator.h =================================================================== --- include/debug/safe_iterator.h (revision 176486) +++ include/debug/safe_iterator.h (working copy) @@ -62,6 +62,43 @@ __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 + inline std::pair::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 + inline std::pair::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 + inline std::pair::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 @@ { 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 @@ _M_get_sequence() const { return static_cast(_M_sequence); } - /** Determine the distance between two iterators with some known - * precision. - */ - template - static std::pair - _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 - static std::pair - _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, - std::random_access_iterator_tag) - { return std::make_pair(__rhs - __lhs, __dp_exact); } - - template - static std::pair - _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(); } Index: include/Makefile.am =================================================================== --- include/Makefile.am (revision 176486) +++ include/Makefile.am (working copy) @@ -701,8 +701,13 @@ ${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 \ Index: testsuite/23_containers/unordered_map/debug/use_erased_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_map/debug/use_erased_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_map/debug/use_erased_local_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_erased_local_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_map/debug/invalid_local_iterator_range_neg.cc =================================================================== --- testsuite/23_containers/unordered_map/debug/invalid_local_iterator_range_neg.cc (revision 0) +++ testsuite/23_containers/unordered_map/debug/invalid_local_iterator_range_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::invalid_local_iterator_range>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_map/debug/use_invalid_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_map/debug/use_invalid_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_map/debug/use_invalid_local_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_invalid_local_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_map/debug/use_invalid_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_map/debug/use_invalid_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_map/debug/use_invalid_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_invalid_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_map/debug/invalid_local_iterator_compare_neg.cc =================================================================== --- testsuite/23_containers/unordered_map/debug/invalid_local_iterator_compare_neg.cc (revision 0) +++ testsuite/23_containers/unordered_map/debug/invalid_local_iterator_compare_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::invalid_local_iterator_compare>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multimap/debug/use_erased_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_multimap/debug/use_erased_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/debug/use_erased_local_iterator_neg.cc (revision 0) @@ -0,0 +1,35 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + typedef std::unordered_multimap cont_type; + __gnu_test::use_erased_local_iterator(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multimap/debug/invalid_local_iterator_range_neg.cc =================================================================== --- testsuite/23_containers/unordered_multimap/debug/invalid_local_iterator_range_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/debug/invalid_local_iterator_range_neg.cc (revision 0) @@ -0,0 +1,35 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + typedef std::unordered_multimap cont_type; + __gnu_test::invalid_local_iterator_range(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multimap/debug/use_invalid_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_multimap/debug/use_invalid_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/debug/use_invalid_local_iterator_neg.cc (revision 0) @@ -0,0 +1,35 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + typedef std::unordered_multimap cont_type; + __gnu_test::use_invalid_local_iterator(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multimap/debug/use_invalid_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_multimap/debug/use_invalid_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/debug/use_invalid_iterator_neg.cc (revision 0) @@ -0,0 +1,35 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + typedef std::unordered_multimap cont_type; + __gnu_test::use_invalid_iterator(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multimap/debug/invalid_local_iterator_compare_neg.cc =================================================================== --- testsuite/23_containers/unordered_multimap/debug/invalid_local_iterator_compare_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/debug/invalid_local_iterator_compare_neg.cc (revision 0) @@ -0,0 +1,35 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + typedef std::unordered_multimap cont_type; + __gnu_test::invalid_local_iterator_compare(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_set/debug/use_erased_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_set/debug/use_erased_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_set/debug/use_erased_local_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_erased_local_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_set/debug/invalid_local_iterator_range_neg.cc =================================================================== --- testsuite/23_containers/unordered_set/debug/invalid_local_iterator_range_neg.cc (revision 0) +++ testsuite/23_containers/unordered_set/debug/invalid_local_iterator_range_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::invalid_local_iterator_range>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_set/debug/use_invalid_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_set/debug/use_invalid_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_set/debug/use_invalid_local_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_invalid_local_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_set/debug/use_invalid_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_set/debug/use_invalid_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_set/debug/use_invalid_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_invalid_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_set/debug/invalid_local_iterator_compare_neg.cc =================================================================== --- testsuite/23_containers/unordered_set/debug/invalid_local_iterator_compare_neg.cc (revision 0) +++ testsuite/23_containers/unordered_set/debug/invalid_local_iterator_compare_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::invalid_local_iterator_compare>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multiset/debug/use_erased_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_multiset/debug/use_erased_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multiset/debug/use_erased_local_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_erased_local_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multiset/debug/invalid_local_iterator_range_neg.cc =================================================================== --- testsuite/23_containers/unordered_multiset/debug/invalid_local_iterator_range_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multiset/debug/invalid_local_iterator_range_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::invalid_local_iterator_range>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multiset/debug/use_invalid_local_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_multiset/debug/use_invalid_local_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multiset/debug/use_invalid_local_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_invalid_local_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multiset/debug/use_invalid_iterator_neg.cc =================================================================== --- testsuite/23_containers/unordered_multiset/debug/use_invalid_iterator_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multiset/debug/use_invalid_iterator_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::use_invalid_iterator>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multiset/debug/invalid_local_iterator_compare_neg.cc =================================================================== --- testsuite/23_containers/unordered_multiset/debug/invalid_local_iterator_compare_neg.cc (revision 0) +++ testsuite/23_containers/unordered_multiset/debug/invalid_local_iterator_compare_neg.cc (revision 0) @@ -0,0 +1,34 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// +// { dg-require-debug-mode "" } +// { dg-options "-std=gnu++0x" } +// { dg-do run { xfail *-*-* } } + +#include +#include + +void test01() +{ + __gnu_test::invalid_local_iterator_compare>(); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/util/debug/checks.h =================================================================== --- testsuite/util/debug/checks.h (revision 176486) +++ testsuite/util/debug/checks.h (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2010 Free Software Foundation, Inc. +// Copyright (C) 2010, 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 @@ -45,7 +45,7 @@ { typedef _Tp value_type; - operator value_type() + value_type build() { static value_type _S_; ++_S_; @@ -60,7 +60,7 @@ typedef _Tp2 second_type; typedef std::pair<_Tp1, _Tp2> pair_type; - operator pair_type() + pair_type build() { static first_type _S_1; static second_type _S_2; @@ -86,7 +86,7 @@ vector_type v; for (int i = 0; i != 5; ++i) - v.push_back(gu); + v.push_back(gu.build()); VERIFY(v.size() == 5); const val_type* first = &v.front() + 1; @@ -116,7 +116,7 @@ vector_type v; for (int i = 0; i != 5; ++i) - v.push_back(gu); + v.push_back(gu.build()); VERIFY(v.size() == 5); typename vector_type::iterator first = v.begin() + 1; @@ -145,7 +145,7 @@ list_type l; for (int i = 0; i != 5; ++i) - l.push_back(gu); + l.push_back(gu.build()); VERIFY(l.size() == 5); typename list_type::iterator first = l.begin(); ++first; @@ -174,7 +174,7 @@ vector_type v; for (int i = 0; i != 5; ++i) - v.push_back(gu); + v.push_back(gu.build()); VERIFY(v.size() == 5); val_type *first = &v.front() + 1; @@ -201,7 +201,7 @@ vector_type v; for (int i = 0; i != 5; ++i) - v.push_back(gu); + v.push_back(gu.build()); VERIFY(v.size() == 5); typename vector_type::iterator first = v.begin() + 1; @@ -228,7 +228,7 @@ list_type l; for (int i = 0; i != 5; ++i) - l.push_back(gu); + l.push_back(gu.build()); VERIFY(l.size() == 5); typename list_type::iterator first = l.begin(); ++first; @@ -304,7 +304,7 @@ vector_type v; for (int i = 0; i != 5; ++i) - v.push_back(gu); + v.push_back(gu.build()); VERIFY(v.size() == 5); const val_type* first = &v.front() + 1; @@ -333,7 +333,7 @@ vector_type v; for (int i = 0; i != 5; ++i) - v.push_back(gu); + v.push_back(gu.build()); VERIFY(v.size() == 5); typename vector_type::iterator first = v.begin() + 1; @@ -362,7 +362,7 @@ list_type l; for (int i = 0; i != 5; ++i) - l.push_back(gu); + l.push_back(gu.build()); VERIFY(l.size() == 5); typename list_type::iterator first = l.begin(); ++first; @@ -375,5 +375,25 @@ cont_type c2; InsertRangeHelper::Insert(c2, last, first); // Expected failure } + + template + void use_invalid_iterator() + { + bool test __attribute__((unused)) = true; + + typedef _Tp cont_type; + typedef typename cont_type::value_type cont_val_type; + typedef typename CopyableValueType::value_type val_type; + generate_unique gu; + + cont_type c; + for (size_t i = 0; i != 5; ++i) + c.insert(gu.build()); + + typename cont_type::iterator it = c.begin(); + cont_val_type val = *it; + c.clear(); + VERIFY( *it == val ); + } } Index: testsuite/util/debug/unordered_checks.h =================================================================== --- testsuite/util/debug/unordered_checks.h (revision 0) +++ testsuite/util/debug/unordered_checks.h (revision 0) @@ -0,0 +1,190 @@ +// 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . +// + +#include + +namespace __gnu_test +{ + template + struct CopyableValueType + { + typedef _Tp value_type; + }; + + template + struct CopyableValueType > + { + typedef std::pair<_Tp1, _Tp2> value_type; + }; + + template + struct generate_unique + { + typedef _Tp value_type; + + value_type build() + { + static value_type _S_; + ++_S_; + return _S_; + } + }; + + template + struct generate_unique > + { + typedef _Tp1 first_type; + typedef _Tp2 second_type; + typedef std::pair<_Tp1, _Tp2> pair_type; + + pair_type build() + { + static first_type _S_1; + static second_type _S_2; + ++_S_1; + ++_S_2; + return pair_type(_S_1, _S_2); + } + }; + + template + struct KeyExtractor + { + static _Tp get_key(const _Tp& val) + { return val; } + }; + + template + struct KeyExtractor> + { + static _Tp1 get_key(const std::pair& val) + { return val.first; } + }; + + template + void use_erased_local_iterator() + { + bool test __attribute__((unused)) = true; + + typedef _Tp cont_type; + typedef typename cont_type::value_type cont_val_type; + typedef typename CopyableValueType::value_type val_type; + generate_unique gu; + + cont_type c; + for (size_t i = 0; i != 5; ++i) + c.insert(gu.build()); + + typename cont_type::local_iterator it, end; + for (size_t i = 0; i != c.bucket_count(); ++i) + { + it = c.begin(i); + end = c.end(i); + if (it != end) + break; + } + typename cont_type::key_type key = KeyExtractor::get_key(*it); + c.erase(key); + VERIFY( it != end ); + } + + template + void use_invalid_local_iterator() + { + bool test __attribute__((unused)) = true; + + typedef _Tp cont_type; + typedef typename cont_type::value_type cont_val_type; + typedef typename CopyableValueType::value_type val_type; + generate_unique gu; + + cont_type c; + for (size_t i = 0; i != 5; ++i) + c.insert(gu.build()); + + typename cont_type::local_iterator it; + for (size_t i = 0; i != c.bucket_count(); ++i) + { + it = c.begin(i); + if (it != c.end(i)) + break; + } + cont_val_type val = *it; + c.clear(); + VERIFY( *it == val ); + } + + template + void invalid_local_iterator_compare() + { + bool test __attribute__((unused)) = true; + + typedef _Tp cont_type; + typedef typename cont_type::value_type cont_val_type; + typedef typename CopyableValueType::value_type val_type; + generate_unique gu; + + cont_type c; + for (size_t i = 0; i != 5; ++i) + c.insert(gu.build()); + + typename cont_type::local_iterator it1, it2; + size_t i; + for (i = 0; i != c.bucket_count(); ++i) + { + it1 = c.begin(i); + if (it1 != c.end(i)) + break; + } + VERIFY( i != c.bucket_count() ); + for (++i; i != c.bucket_count(); ++i) + { + it2 = c.begin(i); + if (it2 != c.end(i)) + break; + } + + VERIFY( it1 != it2 ); + } + + template + void invalid_local_iterator_range() + { + bool test __attribute__((unused)) = true; + + typedef _Tp cont_type; + typedef typename cont_type::value_type cont_val_type; + typedef typename CopyableValueType::value_type val_type; + generate_unique gu; + + cont_type c; + for (size_t i = 0; i != 5; ++i) + c.insert(gu.build()); + + typename cont_type::local_iterator it, end; + for (size_t i = 0; i != c.bucket_count(); ++i) + { + it = c.begin(i); + end = c.end(i); + if (it != end) + break; + } + c.insert(end, it); + } +} + Property changes on: testsuite/util/debug/unordered_checks.h ___________________________________________________________________ Added: svn:eol-style + native Index: config/abi/pre/gnu.ver =================================================================== --- config/abi/pre/gnu.ver (revision 176486) +++ config/abi/pre/gnu.ver (working copy) @@ -1284,6 +1284,11 @@ # std::thread::hardware_concurrency _ZNSt6thread20hardware_concurrencyEv; + # __gnu_debug::_Safe_unordered_sequence_base and _Safe_local_iterator_base + _ZN11__gnu_debug29_Safe_unordered_sequence_base7_M_swapERS0_; + _ZN11__gnu_debug29_Safe_unordered_sequence_base13_M_detach_allEv; + _ZN11__gnu_debug25_Safe_local_iterator_base9_M_attachEPNS_19_Safe_sequence_baseEb; + _ZN11__gnu_debug25_Safe_local_iterator_base9_M_detachEv; } GLIBCXX_3.4.16; # Symbols in the support library (libsupc++) have their own tag.