From patchwork Thu Nov 7 21:00:57 2013 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: 289481 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 690A32C0079 for ; Fri, 8 Nov 2013 08:03:43 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=mrZXv2jxbG8KZhXhwYUT6XWvkW2O0S8e+edW8Eozp8uV2L ngIK+IEBDuJhsHrxq0RIqyn/9QqOO699Dix7sf2cel7iDLp+igvoYDw65GSJPAD/ kRtw2O3PQCovL22/FVdO/40dbJiwSsVPeb/DqQIBZpjVn7y0Qk+sgly/0Fri0= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=xLQ8xGDC0MSKS9lKcbQKF8i2YZ4=; b=bS060+LZWQJGZhto3OJj olT0XWpZdgedCw0CzD6sO0PZ1LG1Zbs7smeqyqyeWzxtcCbZy9Rl0RCfav0VZLvG B+wEIGotBqSnUDNXV/42XdVVzp+N6ddh8p/7vyqS4iF1YmCdZ9x6ONaZZAMMiyUP cnIy+BrS26sCbTmHBJJAPHE= Received: (qmail 31953 invoked by alias); 7 Nov 2013 21:02:58 -0000 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 Received: (qmail 31857 invoked by uid 89); 7 Nov 2013 21:02:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=2.1 required=5.0 tests=AWL, BAYES_50, FREEMAIL_FROM, RDNS_NONE, SPAM_SUBJECT, SPF_PASS, URIBL_BLOCKED autolearn=no version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-we0-f169.google.com Received: from Unknown (HELO mail-we0-f169.google.com) (74.125.82.169) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 07 Nov 2013 21:01:09 +0000 Received: by mail-we0-f169.google.com with SMTP id q58so1129295wes.28 for ; Thu, 07 Nov 2013 13:01:00 -0800 (PST) X-Received: by 10.194.173.163 with SMTP id bl3mr9374152wjc.10.1383858060311; Thu, 07 Nov 2013 13:01:00 -0800 (PST) Received: from localhost.localdomain (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPSA id ev4sm24445006wib.7.2013.11.07.13.00.57 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 07 Nov 2013 13:00:59 -0800 (PST) Message-ID: <527BFF89.2020406@gmail.com> Date: Thu, 07 Nov 2013 22:00:57 +0100 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120829 Thunderbird/15.0 MIME-Version: 1.0 To: "libstdc++@gcc.gnu.org" , gcc-patches Subject: [patch] safe iterator simplification Hi Here is a patch to simplify a little safe iterator implementation. Returning a sequence pointer from a safe iterator and a const sequence pointer from a const safe iterator allows to avoid inconsistent usages of iterator like comparing iterator with a const_iterator. This way __get_distance can be simplified to only take one type of iterator, _M_valid_range is not a template method anymore. I also modified _BeforeBeginHelper so that it also generates consistent comparisons of iterators. 2013-11-08 François Dumont * include/debug/safe_iterator.h (_BeforeBeginHelper<>::_S_Is): Take only a const safe iterator reference. (_BeforeBeingHelper<>::_S_Is_beginnest): Likewise. (__get_distance): Take only one type of iterator. (_Safe_iterator<>::_M_valid_range<>): Not template anymore. (_Safe_iterator<>::_M_get_sequence()): Return pointer to const sequence from a const_iterator and a pointer to sequence from an iterator. * include/debug/safe_iterator.tcc: Adapt. * include/debug/safe_local_iterator.h (_Safe_local_iterator<>::_M_valid_range<>): Not template anymore. (_Safe_local_iterator<>::_M_get_sequence()): Return pointer to const sequence from a const_iterator and a pointer to sequence from an iterator. * include/debug/safe_local_iterator.tcc: Adapt. * include/debug/forward_list (_BeforeBeginHelpers>): Adapt. Tested undex Linux x86_64 debug mode. Ok to commit ? François Index: include/debug/safe_iterator.tcc =================================================================== --- include/debug/safe_iterator.tcc (revision 204419) +++ include/debug/safe_iterator.tcc (working copy) @@ -36,27 +36,22 @@ _Safe_iterator<_Iterator, _Sequence>:: _M_can_advance(const difference_type& __n) const { - typedef typename _Sequence::const_iterator const_debug_iterator; - typedef typename const_debug_iterator::iterator_type const_iterator; - if (this->_M_singular()) return false; if (__n == 0) return true; if (__n < 0) { - const_iterator __begin = _M_get_sequence()->_M_base().begin(); std::pair __dist = - __get_distance(__begin, base()); + __get_distance(_M_get_sequence()->_M_base().begin(), base()); bool __ok = ((__dist.second == __dp_exact && __dist.first >= -__n) || (__dist.second != __dp_exact && __dist.first > 0)); return __ok; } else { - const_iterator __end = _M_get_sequence()->_M_base().end(); std::pair __dist = - __get_distance(base(), __end); + __get_distance(base(), _M_get_sequence()->_M_base().end()); bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n) || (__dist.second != __dp_exact && __dist.first > 0)); return __ok; @@ -64,42 +59,41 @@ } template - template - bool - _Safe_iterator<_Iterator, _Sequence>:: - _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const - { - if (!_M_can_compare(__rhs)) - return false; + bool + _Safe_iterator<_Iterator, _Sequence>:: + _M_valid_range(const _Safe_iterator& __rhs) const + { + if (!_M_can_compare(__rhs)) + 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. Note, for the special case of forward_list, - * before_begin replaces the role of begin. */ - if (_M_is_beginnest() || __rhs._M_is_end()) + /* 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; - if (_M_is_end() || __rhs._M_is_beginnest()) - return false; + break; - // Assume that this is a valid range; we can't check anything else - return true; + 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. Note, for the special case of forward_list, + * before_begin replaces the role of begin. */ + if (_M_is_beginnest() || __rhs._M_is_end()) + return true; + if (_M_is_end() || __rhs._M_is_beginnest()) + return false; + + // Assume that this is a valid range; we can't check anything else + return true; + } } // namespace __gnu_debug #endif Index: include/debug/forward_list =================================================================== --- include/debug/forward_list (revision 204419) +++ include/debug/forward_list (working copy) @@ -785,16 +785,19 @@ struct _BeforeBeginHelper > { typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence; - typedef typename _Sequence::const_iterator _It; - typedef typename _It::iterator_type _BaseIt; - static bool - _S_Is(_BaseIt __it, const _Sequence* __seq) - { return __it == __seq->_M_base().cbefore_begin(); } + template + static bool + _S_Is(const _Safe_iterator<_Iterator, _Sequence>& __it) + { + return + __it.base() == __it._M_get_sequence()->_M_base().before_begin(); + } - static bool - _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq) - { return _S_Is(__it, __seq); } + template + static bool + _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it) + { return _S_Is(__it); } }; #ifndef _GLIBCXX_DEBUG_PEDANTIC Index: include/debug/safe_local_iterator.tcc =================================================================== --- include/debug/safe_local_iterator.tcc (revision 204419) +++ include/debug/safe_local_iterator.tcc (working copy) @@ -32,21 +32,20 @@ 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; + bool + _Safe_local_iterator<_Iterator, _Sequence>:: + _M_valid_range(const _Safe_local_iterator& __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) + /* 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) @@ -58,18 +57,18 @@ 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 + /* 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 204419) +++ include/debug/safe_iterator.h (working copy) @@ -44,16 +44,15 @@ template struct _BeforeBeginHelper { - typedef typename _Sequence::const_iterator _It; - typedef typename _It::iterator_type _BaseIt; + template + static bool + _S_Is(const _Safe_iterator<_Iterator, _Sequence>&) + { return false; } - static bool - _S_Is(_BaseIt, const _Sequence*) - { return false; } - - static bool - _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq) - { return __it == __seq->_M_base().begin(); } + template + static bool + _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it) + { return __it.base() == __it._M_get_sequence()->_M_base().begin(); } }; /** Iterators that derive from _Safe_iterator_base can be determined singular @@ -76,26 +75,26 @@ /** Determine the distance between two iterators with some known * precision. */ - template - inline std::pair::difference_type, + template + inline std::pair::difference_type, _Distance_precision> - __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, + __get_distance(const _Iterator& __lhs, const _Iterator& __rhs, std::random_access_iterator_tag) { return std::make_pair(__rhs - __lhs, __dp_exact); } - template - inline std::pair::difference_type, + template + inline std::pair::difference_type, _Distance_precision> - __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, + __get_distance(const _Iterator& __lhs, const _Iterator& __rhs, std::forward_iterator_tag) { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); } - template - inline std::pair::difference_type, + template + inline std::pair::difference_type, _Distance_precision> - __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs) + __get_distance(const _Iterator& __lhs, const _Iterator& __rhs) { - typedef typename std::iterator_traits<_Iterator1>::iterator_category + typedef typename std::iterator_traits<_Iterator>::iterator_category _Category; return __get_distance(__lhs, __rhs, _Category()); } @@ -115,6 +114,7 @@ class _Safe_iterator : public _Safe_iterator_base { typedef _Safe_iterator _Self; + typedef typename _Sequence::const_iterator _Const_iterator; /// The underlying iterator _Iterator _M_current; @@ -122,10 +122,7 @@ /// Determine if this is a constant iterator. bool _M_constant() const - { - typedef typename _Sequence::const_iterator const_iterator; - return std::__are_same::__value; - } + { return std::__are_same<_Const_iterator, _Safe_iterator>::__value; } typedef std::iterator_traits<_Iterator> _Traits; @@ -445,37 +442,39 @@ _M_can_advance(const difference_type& __n) const; // Is the iterator range [*this, __rhs) valid? - template - bool - _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const; + bool + _M_valid_range(const _Safe_iterator& __rhs) const; // The sequence this iterator references. - const _Sequence* + typename + __gnu_cxx::__conditional_type::__value, + const _Sequence*, + _Sequence*>::__type _M_get_sequence() const - { return static_cast(_M_sequence); } + { return static_cast<_Sequence*>(_M_sequence); } /// Is this iterator equal to the sequence's begin() iterator? - bool _M_is_begin() const + bool + _M_is_begin() const { return base() == _M_get_sequence()->_M_base().begin(); } /// Is this iterator equal to the sequence's end() iterator? - bool _M_is_end() const + bool + _M_is_end() const { return base() == _M_get_sequence()->_M_base().end(); } /// Is this iterator equal to the sequence's before_begin() iterator if /// any? - bool _M_is_before_begin() const - { - return _BeforeBeginHelper<_Sequence>::_S_Is(base(), _M_get_sequence()); - } + bool + _M_is_before_begin() const + { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); } /// Is this iterator equal to the sequence's before_begin() iterator if /// any or begin() otherwise? - bool _M_is_beginnest() const - { - return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(base(), - _M_get_sequence()); - } + bool + _M_is_beginnest() const + { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); } }; template Index: include/debug/safe_local_iterator.h =================================================================== --- include/debug/safe_local_iterator.h (revision 204419) +++ include/debug/safe_local_iterator.h (working copy) @@ -52,6 +52,7 @@ class _Safe_local_iterator : public _Safe_local_iterator_base { typedef _Safe_local_iterator _Self; + typedef typename _Sequence::const_local_iterator _Const_local_iterator; typedef typename _Sequence::size_type size_type; /// The underlying iterator @@ -64,8 +65,8 @@ bool _M_constant() const { - typedef typename _Sequence::const_local_iterator const_iterator; - return std::__are_same::__value; + return std::__are_same<_Const_local_iterator, + _Safe_local_iterator>::__value; } typedef std::iterator_traits<_Iterator> _Traits; @@ -253,15 +254,17 @@ { 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; + bool + _M_valid_range(const _Safe_local_iterator& __rhs) const; // The sequence this iterator references. - const _Sequence* + typename + __gnu_cxx::__conditional_type::__value, + const _Sequence*, + _Sequence*>::__type _M_get_sequence() const - { return static_cast(_M_sequence); } + { return static_cast<_Sequence*>(_M_sequence); } /// Is this iterator equal to the sequence's begin() iterator? bool _M_is_begin() const