From 194571f10e354ff084afd84518f85d3326d118e9 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Tue, 14 Apr 2015 13:02:48 +0200 Subject: [PATCH] re PR libstdc++/61347 (std::distance(list.first(),list.end()) in O(1)) 2015-04-14 Marc Glisse PR libstdc++/61347 * include/bits/stl_iterator_base_funcs.h (_List_iterator, _List_const_iterator): Declare. (__distance): Declare new overloads for _List_iterator and _List_const_iterator. * include/bits/stl_list.h (__distance): New overloads for _List_iterator and _List_const_iterator. * testsuite/23_containers/list/61347.cc: New testcase. From-SVN: r222082 --- libstdc++-v3/ChangeLog | 11 +++++ .../include/bits/stl_iterator_base_funcs.h | 21 ++++++++ libstdc++-v3/include/bits/stl_list.h | 39 +++++++++++++++ .../testsuite/23_containers/list/61347.cc | 49 +++++++++++++++++++ 4 files changed, 120 insertions(+) create mode 100644 libstdc++-v3/testsuite/23_containers/list/61347.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 7c8ec63f51c..22b434ea5be 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,14 @@ +2015-04-14 Marc Glisse + + PR libstdc++/61347 + * include/bits/stl_iterator_base_funcs.h (_List_iterator, + _List_const_iterator): Declare. + (__distance): Declare new overloads for _List_iterator and + _List_const_iterator. + * include/bits/stl_list.h (__distance): New overloads for + _List_iterator and _List_const_iterator. + * testsuite/23_containers/list/61347.cc: New testcase. + 2015-04-14 Jonathan Wakely * doc/xml/manual/evolution.xml: Fix typos. diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h index a146611b25f..6ee2ffbc5f2 100644 --- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h +++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h @@ -66,6 +66,12 @@ namespace std _GLIBCXX_VISIBILITY(default) { +_GLIBCXX_BEGIN_NAMESPACE_CONTAINER + // Forward declaration for the overloads of __distance. + template struct _List_iterator; + template struct _List_const_iterator; +_GLIBCXX_END_NAMESPACE_CONTAINER + _GLIBCXX_BEGIN_NAMESPACE_VERSION template @@ -96,6 +102,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __last - __first; } +#if _GLIBCXX_USE_CXX11_ABI + // Forward declaration because of the qualified call in distance. + template + ptrdiff_t + __distance(_GLIBCXX_STD_C::_List_iterator<_Tp>, + _GLIBCXX_STD_C::_List_iterator<_Tp>, + input_iterator_tag); + + template + ptrdiff_t + __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp>, + _GLIBCXX_STD_C::_List_const_iterator<_Tp>, + input_iterator_tag); +#endif + /** * @brief A generalization of pointer arithmetic. * @param __first An input iterator. diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index f8bfff18b19..3401e5b4d25 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -1868,6 +1868,45 @@ _GLIBCXX_END_NAMESPACE_CXX11 { __x.swap(__y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if _GLIBCXX_USE_CXX11_ABI +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // Detect when distance is used to compute the size of the whole list. + template + inline ptrdiff_t + __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first, + _GLIBCXX_STD_C::_List_iterator<_Tp> __last, + input_iterator_tag __tag) + { + typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter; + return std::__distance(_CIter(__first), _CIter(__last), __tag); + } + + template + inline ptrdiff_t + __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first, + _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last, + input_iterator_tag) + { + typedef _GLIBCXX_STD_C::_List_node _Sentinel; + _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last; + ++__beyond; + bool __whole = __first == __beyond; + if (__builtin_constant_p (__whole) && __whole) + return static_cast(__last._M_node)->_M_data; + + ptrdiff_t __n = 0; + while (__first != __last) + { + ++__first; + ++__n; + } + return __n; + } + +_GLIBCXX_END_NAMESPACE_VERSION +#endif } // namespace std #endif /* _STL_LIST_H */ diff --git a/libstdc++-v3/testsuite/23_containers/list/61347.cc b/libstdc++-v3/testsuite/23_containers/list/61347.cc new file mode 100644 index 00000000000..653591228ef --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/61347.cc @@ -0,0 +1,49 @@ +// { dg-options "-std=gnu++11 -O2 -D_GLIBCXX_USE_CXX11_ABI" } + +// Copyright (C) 2015 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 +#include +#include + +__attribute__((__noinline__, __noclone__)) +void testm(std::list& l) +{ + bool b = std::distance(l.begin(), l.end()) == l.size(); + VERIFY( __builtin_constant_p(b) ); + VERIFY( b ); +} + +__attribute__((__noinline__, __noclone__)) +void testc(const std::list& l) +{ + bool b = std::distance(l.begin(), l.end()) == l.size(); + VERIFY( __builtin_constant_p(b) ); + VERIFY( b ); +} + +int main() +{ + bool test __attribute__((unused)) = true; + +#if _GLIBCXX_USE_DUAL_ABI + std::list l; + testm(l); + testc(l); +#endif +} -- 2.30.2