This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: niter_base simplification


On 27/04/2015 13:55, Jonathan Wakely wrote:
On 22/04/15 22:10 +0200, François Dumont wrote:
Hello

I don't know if I am missing something but I think __niter_base could be simplified to remove usage of _Iter_base. Additionally I overload it to also remove __normal_iterator layer even if behind a reverse_iterator or move_iterator, might help compiler to optimize code, no ? If not, might allow other algo optimization in the future...

I prefered to provide a __make_reverse_iterator to allow the latter in C++11 and not only in C++14. Is it fine to do it this way or do you prefer to simply get rid of all this part ?

It's fine to add __make_reverse_iterator but see my comment below.

* include/bits/cpp_type_traits.h (__gnu_cxx::__normal_iterator): Delete.

You're removing __is_normal_iterator not __normal_iterator.

   * include/bits/stl_algobase.h (std::__niter_base): Adapt.
* include/bits/stl_iterator.h (__make_reverse_iterator): New in C++11.
   (std::__niter_base): Overloads for std::reverse_iterator,
   __gnu_cxx::__normal_iterator and std::move_iterator.

Tested under Linux x86_64. I checked that std::copy still ends up calling __builtin_memmove when used on vector iterators.

François


diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 0bcb133..73eea6b 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -270,17 +270,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      return __a;
    }

- // If _Iterator is a __normal_iterator return its base (a plain pointer, - // normally) otherwise return it untouched. See copy, fill, ... + // Fallback implementation of the function used to remove the
+  // __normal_iterator wrapper. See copy, fill, ...

It's a bit strange to have a function with no other overloads visible
described as a fallback. It would be good to say that the other
definition is in bits/stl_iterator.h

  template<typename _Iterator>
-    struct _Niter_base
-    : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>
-    { };
-
-  template<typename _Iterator>
-    inline typename _Niter_base<_Iterator>::iterator_type
+    inline _Iterator
    __niter_base(_Iterator __it)
-    { return std::_Niter_base<_Iterator>::_S_base(__it); }
+    { return __it; }

  // Likewise, for move_iterator.

This comment no longer makes sense, because you've removed the comment
on _Niter_base that it referred to. Please restore the original text
of the _Niter_base comment for _Miter_base.

(Alternatively, could the same simplification be made for
__miter_base? Do we need _Miter_base<> or just two overloads of
__miter_base()?)

Definitely, I already have a patch for that.



  template<typename _Iterator>
diff --git a/libstdc++-v3/include/bits/stl_iterator.h b/libstdc++-v3/include/bits/stl_iterator.h
index 4a9189e..3aad9f3 100644
--- a/libstdc++-v3/include/bits/stl_iterator.h
+++ b/libstdc++-v3/include/bits/stl_iterator.h
@@ -390,7 +390,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    { return __y.base() - __x.base(); }
  //@}

-#if __cplusplus > 201103L
+#if __cplusplus == 201103L
+  template<typename _Iterator>
+    inline reverse_iterator<_Iterator>
+    __make_reverse_iterator(_Iterator __i)
+    { return reverse_iterator<_Iterator>(__i); }
+
+# define _GLIBCXX_MAKE_REVERSE_ITERATOR(_Iter) \
+  std::__make_reverse_iterator(_Iter)
+#elif __cplusplus > 201103L
#define __cpp_lib_make_reverse_iterator 201402

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -400,6 +408,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    inline reverse_iterator<_Iterator>
    make_reverse_iterator(_Iterator __i)
    { return reverse_iterator<_Iterator>(__i); }
+
+# define _GLIBCXX_MAKE_REVERSE_ITERATOR(_Iter) \
+  std::make_reverse_iterator(_Iter)
+#endif
+
+#if __cplusplus >= 201103L
+  template<typename _Iterator>
+    auto
+    __niter_base(reverse_iterator<_Iterator> __it)
+ -> decltype(_GLIBCXX_MAKE_REVERSE_ITERATOR(__niter_base(__it.base()))) + { return _GLIBCXX_MAKE_REVERSE_ITERATOR(__niter_base(__it.base())); }
#endif


It might be simpler to just add __make_reverse_iterator for >= 201103L
and then always use std::__make_reverse_iterator instead of a macro.

That's similar to what we do for std:__addressof and std:addressof.

Ok, attached is the patch I have plan to commit then that I am testing at the moment.

François

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 222611)
+++ ChangeLog	(working copy)
@@ -1,5 +1,14 @@
 2015-04-30  François Dumont  <fdumont@gcc.gnu.org>
 
+	* include/bits/cpp_type_traits.h
+	(__gnu_cxx::__is_normal_iterator): Delete.
+	* include/bits/stl_algobase.h (std::__niter_base): Adapt.
+	* include/bits/stl_iterator.h (__make_reverse_iterator): New in C++11.
+	(std::__niter_base): Overloads for std::reverse_iterator,
+	__gnu_cxx::__normal_iterator and std::move_iterator.
+
+2015-04-30  François Dumont  <fdumont@gcc.gnu.org>
+
 	* include/bits/hashtable_policy.h (_Prime_rehash_policy::_S_n_primes):
 	Delete.
 	* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
Index: include/bits/cpp_type_traits.h
===================================================================
--- include/bits/cpp_type_traits.h	(revision 222610)
+++ include/bits/cpp_type_traits.h	(working copy)
@@ -64,17 +64,6 @@
 // removed.
 //
 
-// Forward declaration hack, should really include this from somewhere.
-namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
-{
-_GLIBCXX_BEGIN_NAMESPACE_VERSION
-
-  template<typename _Iterator, typename _Container>
-    class __normal_iterator;
-
-_GLIBCXX_END_NAMESPACE_VERSION
-} // namespace
-
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -331,24 +320,6 @@
     };
 
   //
-  // Normal iterator type
-  //
-  template<typename _Tp>
-    struct __is_normal_iterator
-    {
-      enum { __value = 0 };
-      typedef __false_type __type;
-    };
-
-  template<typename _Iterator, typename _Container>
-    struct __is_normal_iterator< __gnu_cxx::__normal_iterator<_Iterator,
-							      _Container> >
-    {
-      enum { __value = 1 };
-      typedef __true_type __type;
-    };
-
-  //
   // An arithmetic type is an integer type or a floating point type
   //
   template<typename _Tp>
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h	(revision 222610)
+++ include/bits/stl_algobase.h	(working copy)
@@ -270,19 +270,15 @@
       return __a;
     }
 
-  // If _Iterator is a __normal_iterator return its base (a plain pointer,
-  // normally) otherwise return it untouched.  See copy, fill, ... 
+  // Fallback implementation of the function in bits/stl_iterator.h used to
+  // remove the __normal_iterator wrapper. See copy, fill, ...
   template<typename _Iterator>
-    struct _Niter_base
-    : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>
-    { };
-
-  template<typename _Iterator>
-    inline typename _Niter_base<_Iterator>::iterator_type
+    inline _Iterator
     __niter_base(_Iterator __it)
-    { return std::_Niter_base<_Iterator>::_S_base(__it); }
+    { return __it; }
 
-  // Likewise, for move_iterator.
+  // If _Iterator is a move_iterator return its base otherwise return it
+  // untouched.  See copy, fill, ...
   template<typename _Iterator>
     struct _Miter_base
     : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value>
Index: include/bits/stl_iterator.h
===================================================================
--- include/bits/stl_iterator.h	(revision 222610)
+++ include/bits/stl_iterator.h	(working copy)
@@ -388,9 +388,16 @@
     { return __y.base() - __x.base(); }
   //@}
 
-#if __cplusplus > 201103L
-#define __cpp_lib_make_reverse_iterator 201402
+#if __cplusplus >= 201103L
+  // Same as C++14 make_reverse_iterator but used in C++03 mode too.
+  template<typename _Iterator>
+    inline reverse_iterator<_Iterator>
+    __make_reverse_iterator(_Iterator __i)
+    { return reverse_iterator<_Iterator>(__i); }
 
+# if __cplusplus > 201103L
+#  define __cpp_lib_make_reverse_iterator 201402
+
   // _GLIBCXX_RESOLVE_LIB_DEFECTS
   // DR 2285. make_reverse_iterator
   /// Generator function for reverse_iterator.
@@ -398,8 +405,17 @@
     inline reverse_iterator<_Iterator>
     make_reverse_iterator(_Iterator __i)
     { return reverse_iterator<_Iterator>(__i); }
+# endif
 #endif
 
+#if __cplusplus >= 201103L
+  template<typename _Iterator>
+    auto
+    __niter_base(reverse_iterator<_Iterator> __it)
+    -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
+    { return __make_reverse_iterator(__niter_base(__it.base())); }
+#endif
+
   // 24.4.2.2.1 back_insert_iterator
   /**
    *  @brief  Turns assignment into insertion.
@@ -935,6 +951,18 @@
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  template<typename _Iterator, typename _Container>
+    _Iterator
+    __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
+    { return __it.base(); }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace
+
 #if __cplusplus >= 201103L
 
 namespace std _GLIBCXX_VISIBILITY(default)
@@ -1168,6 +1196,12 @@
 
   // @} group iterators
 
+  template<typename _Iterator>
+    auto
+    __niter_base(move_iterator<_Iterator> __it)
+    -> decltype(make_move_iterator(__niter_base(__it.base())))
+    { return make_move_iterator(__niter_base(__it.base())); }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]