From 9e160526440decfabecbe06e7ed22ee828d93010 Mon Sep 17 00:00:00 2001
From: Jonathan Wakely <jwakely@redhat.com>
Date: Wed, 12 Dec 2018 16:13:49 +0000
Subject: [PATCH] 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.

From-SVN: r267057
---
 libstdc++-v3/ChangeLog                        |  8 ++++
 libstdc++-v3/include/bits/fs_path.h           | 40 +++++++++++++++++++
 .../27_io/filesystem/path/itr/traversal.cc    | 18 +++++++++
 3 files changed, 66 insertions(+)

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 886253db410..cd7c7ee65bf 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,13 @@
 2018-12-12  Jonathan Wakely  <jwakely@redhat.com>
 
+	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.
+
 	PR libstdc++/80762
 	* include/bits/fs_path.h (path::_Path): Use remove_cv_t and is_void.
 	* include/experimental/bits/fs_path.h (path::_Path): Likewise.
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();
 }
-- 
2.30.2