Upd libc++ to d0af4276d62418ba9e54fec99b293d2fd7c92213 (14 Mar 2022)

1 files changed, 33 insertions, 0 deletions

diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sift_down.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sift_down.h
index b636da78b0..0351a1c578 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sift_down.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sift_down.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H
 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
 
+#include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
@@ -73,6 +74,38 @@ __sift_down(_RandomAccessIterator __first, _Compare __comp,
     *__start = _VSTD::move(__top);
 }
 
+template <class _Compare, class _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
+__floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
+                  typename iterator_traits<_RandomAccessIterator>::difference_type __len)
+{
+    using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+    _LIBCPP_ASSERT(__len >= 2, "shouldn't be called unless __len >= 2");
+
+    _RandomAccessIterator __hole = __first;
+    _RandomAccessIterator __child_i = __first;
+    difference_type __child = 0;
+
+    while (true) {
+        __child_i += difference_type(__child + 1);
+        __child = 2 * __child + 1;
+
+        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
+            // right-child exists and is greater than left-child
+            ++__child_i;
+            ++__child;
+        }
+
+        // swap __hole with its largest child
+        *__hole = std::move(*__child_i);
+        __hole = __child_i;
+
+        // if __hole is now a leaf, we're done
+        if (__child > (__len - 2) / 2)
+            return __hole;
+    }
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H