[PATCH] Overload std::distance and std::advance for path::iterator

[Jonathan Wakely]

Although filesystem::path::iterator is only a bidirectional iterator,
the underlying sequence has random access iterators (specifically, raw
pointers). This means std::distance and std::advance can be implemented
more efficiently than the generic versions which apply ++ and --
repeatedly.

        PR libstdc++/71044 (partial)
        * include/bits/fs_path.h (__path_iter_distance, __path_iter_advance):
        New friend functions to implement std::distance and std::advance more
        efficiently.
        (distance, advance): Add overloads for path::iterator.
        * testsuite/27_io/filesystem/path/itr/components.cc: Test new
        overload.

Tested x86_64-linux, committed to trunk.


commit 994dfa1a5ca5ddd4e8d280873ef376ee6ab8352b
Author: Jonathan Wakely <jwak...@redhat.com>
Date:   Fri Nov 30 16:33:24 2018 +0000

    Overload std::distance and std::advance for path::iterator
    
    Although filesystem::path::iterator is only a bidirectional iterator,
    the underlying sequence has random access iterators (specifically, raw
    pointers). This means std::distance and std::advance can be implemented
    more efficiently than the generic versions which apply ++ and --
    repeatedly.
    
            PR libstdc++/71044 (partial)
            * include/bits/fs_path.h (__path_iter_distance, 
__path_iter_advance):
            New friend functions to implement std::distance and std::advance 
more
            efficiently.
            (distance, advance): Add overloads for path::iterator.
            * testsuite/27_io/filesystem/path/itr/components.cc: Test new
            overload.

diff --git a/libstdc++-v3/include/bits/fs_path.h 
b/libstdc++-v3/include/bits/fs_path.h
index cbaea7343a3..075b3ab5ef8 100644
--- a/libstdc++-v3/include/bits/fs_path.h
+++ b/libstdc++-v3/include/bits/fs_path.h
@@ -733,6 +733,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
   private:
     friend class path;
 
+    bool _M_is_multi() const { return _M_path->_M_type == _Type::_Multi; }
+
+    friend difference_type
+    __path_iter_distance(const iterator& __first, const iterator& __last)
+    {
+      __glibcxx_assert(__first._M_path != nullptr);
+      __glibcxx_assert(__first._M_path == __last._M_path);
+      if (__first._M_is_multi())
+       return std::distance(__first._M_cur, __last._M_cur);
+      else if (__first._M_at_end == __last._M_at_end)
+       return 0;
+      else
+       return __first._M_at_end ? -1 : 1;
+    }
+
+    friend void
+    __path_iter_advance(iterator& __i, difference_type __n)
+    {
+      if (__n == 1)
+       ++__i;
+      else if (__n == -1)
+       --__i;
+      else if (__n != 0)
+       {
+         __glibcxx_assert(__i._M_path != nullptr);
+         __glibcxx_assert(__i._M_is_multi());
+         // __glibcxx_assert(__i._M_path->_M_cmpts.end() - __i._M_cur >= __n);
+         __i._M_cur += __n;
+       }
+    }
+
     iterator(const path* __path, path::_List::const_iterator __iter)
     : _M_path(__path), _M_cur(__iter), _M_at_end()
     { }
@@ -1160,6 +1191,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 _GLIBCXX_END_NAMESPACE_CXX11
 } // namespace filesystem
 
+inline ptrdiff_t
+distance(filesystem::path::iterator __first, filesystem::path::iterator __last)
+{ return __path_iter_distance(__first, __last); }
+
+template<typename _InputIterator, typename _Distance>
+  void
+  advance(filesystem::path::iterator& __i, _Distance __n)
+  { __path_iter_advance(__i, static_cast<ptrdiff_t>(__n)); }
+
 extern template class __shared_ptr<const filesystem::filesystem_error::_Impl>;
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/testsuite/27_io/filesystem/path/itr/traversal.cc 
b/libstdc++-v3/testsuite/27_io/filesystem/path/itr/traversal.cc
index 4852c03c78e..55760e82a9a 100644
--- a/libstdc++-v3/testsuite/27_io/filesystem/path/itr/traversal.cc
+++ b/libstdc++-v3/testsuite/27_io/filesystem/path/itr/traversal.cc
@@ -136,10 +136,28 @@ test03()
     }
 }
 
+void
+test04()
+{
+  std::filesystem::path p = "/a/b/c/d/e/f/g";
+  VERIFY( std::distance(p.begin(), p.end()) == 8);
+  auto it = p.begin();
+  std::advance(it, 1);
+  VERIFY( std::distance(p.begin(), it) == 1 );
+  VERIFY( it->native() == "a" );
+  std::advance(it, 3);
+  VERIFY( std::distance(p.begin(), it) == 4 );
+  VERIFY( it->native() == "d" );
+  std::advance(it, -2);
+  VERIFY( std::distance(p.begin(), it) == 2 );
+  VERIFY( it->native() == "b" );
+}
+
 int
 main()
 {
   test01();
   test02();
   test03();
+  test04();
 }