v1/__debug_utils/strict_weak_ordering_check.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK
0010 #define _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK
0011
0012 #include <__config>
0013
0014 #include <__algorithm/comp_ref_type.h>
0015 #include <__algorithm/is_sorted.h>
0016 #include <__assert>
0017 #include <__iterator/iterator_traits.h>
0018 #include <__type_traits/is_constant_evaluated.h>
0019
0020 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0021 #  pragma GCC system_header
0022 #endif
0023
0024 _LIBCPP_BEGIN_NAMESPACE_STD
0025
0026 template <class _RandomAccessIterator, class _Comp>
0027 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
0028 __check_strict_weak_ordering_sorted(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
0029 #if _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG
0030   using __diff_t  = __iter_diff_t<_RandomAccessIterator>;
0031   using _Comp_ref = __comp_ref_type<_Comp>;
0032   if (!__libcpp_is_constant_evaluated()) {
0033     // Check if the range is actually sorted.
0034     _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0035         (std::is_sorted<_RandomAccessIterator, _Comp_ref>(__first, __last, _Comp_ref(__comp))),
0036         "The range is not sorted after the sort, your comparator is not a valid strict-weak ordering");
0037     // Limit the number of elements we need to check.
0038     __diff_t __size = __last - __first > __diff_t(100) ? __diff_t(100) : __last - __first;
0039     __diff_t __p    = 0;
0040     while (__p < __size) {
0041       __diff_t __q = __p + __diff_t(1);
0042       // Find first element that is greater than *(__first+__p).
0043       while (__q < __size && !__comp(*(__first + __p), *(__first + __q))) {
0044         ++__q;
0045       }
0046       // Check that the elements from __p to __q are equal between each other.
0047       for (__diff_t __b = __p; __b < __q; ++__b) {
0048         for (__diff_t __a = __p; __a <= __b; ++__a) {
0049           _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0050               !__comp(*(__first + __a), *(__first + __b)), "Your comparator is not a valid strict-weak ordering");
0051           _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0052               !__comp(*(__first + __b), *(__first + __a)), "Your comparator is not a valid strict-weak ordering");
0053         }
0054       }
0055       // Check that elements between __p and __q are less than between __q and __size.
0056       for (__diff_t __a = __p; __a < __q; ++__a) {
0057         for (__diff_t __b = __q; __b < __size; ++__b) {
0058           _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0059               __comp(*(__first + __a), *(__first + __b)), "Your comparator is not a valid strict-weak ordering");
0060           _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(
0061               !__comp(*(__first + __b), *(__first + __a)), "Your comparator is not a valid strict-weak ordering");
0062         }
0063       }
0064       // Skip these equal elements.
0065       __p = __q;
0066     }
0067   }
0068 #else
0069   (void)__first;
0070   (void)__last;
0071   (void)__comp;
0072 #endif // _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG
0073 }
0074
0075 _LIBCPP_END_NAMESPACE_STD
0076
0077 #endif // _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK