1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK
10 #define _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK
11
12 #include <__config>
13
14 #include <__algorithm/comp_ref_type.h>
15 #include <__algorithm/is_sorted.h>
16 #include <__assert>
17 #include <__iterator/iterator_traits.h>
18 #include <__type_traits/is_constant_evaluated.h>
19
20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
21 # pragma GCC system_header
22 #endif
23
24 _LIBCPP_BEGIN_NAMESPACE_STD
25
26 template <class _RandomAccessIterator, class _Comp>
27 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
__check_strict_weak_ordering_sorted(_RandomAccessIterator __first,_RandomAccessIterator __last,_Comp & __comp)28 __check_strict_weak_ordering_sorted(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
29 #if _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG
30 using __diff_t = __iter_diff_t<_RandomAccessIterator>;
31 using _Comp_ref = __comp_ref_type<_Comp>;
32 if (!__libcpp_is_constant_evaluated()) {
33 // Check if the range is actually sorted.
34 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
35 (std::is_sorted<_RandomAccessIterator, _Comp_ref>(__first, __last, _Comp_ref(__comp))),
36 "The range is not sorted after the sort, your comparator is not a valid strict-weak ordering");
37 // Limit the number of elements we need to check.
38 __diff_t __size = __last - __first > __diff_t(100) ? __diff_t(100) : __last - __first;
39 __diff_t __p = 0;
40 while (__p < __size) {
41 __diff_t __q = __p + __diff_t(1);
42 // Find first element that is greater than *(__first+__p).
43 while (__q < __size && !__comp(*(__first + __p), *(__first + __q))) {
44 ++__q;
45 }
46 // Check that the elements from __p to __q are equal between each other.
47 for (__diff_t __b = __p; __b < __q; ++__b) {
48 for (__diff_t __a = __p; __a <= __b; ++__a) {
49 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
50 !__comp(*(__first + __a), *(__first + __b)), "Your comparator is not a valid strict-weak ordering");
51 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
52 !__comp(*(__first + __b), *(__first + __a)), "Your comparator is not a valid strict-weak ordering");
53 }
54 }
55 // Check that elements between __p and __q are less than between __q and __size.
56 for (__diff_t __a = __p; __a < __q; ++__a) {
57 for (__diff_t __b = __q; __b < __size; ++__b) {
58 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
59 __comp(*(__first + __a), *(__first + __b)), "Your comparator is not a valid strict-weak ordering");
60 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
61 !__comp(*(__first + __b), *(__first + __a)), "Your comparator is not a valid strict-weak ordering");
62 }
63 }
64 // Skip these equal elements.
65 __p = __q;
66 }
67 }
68 #else
69 (void)__first;
70 (void)__last;
71 (void)__comp;
72 #endif // _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG
73 }
74
75 _LIBCPP_END_NAMESPACE_STD
76
77 #endif // _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK
78