diff options
Diffstat (limited to 'libcxx/include/__algorithm/sort.h')
| -rw-r--r-- | libcxx/include/__algorithm/sort.h | 73 |
1 files changed, 49 insertions, 24 deletions
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index f8706129082a..3583c4499cc2 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -279,12 +279,13 @@ void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __l // element in the input range is greater or equal to the element at __first - 1. template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> _LIBCPP_HIDE_FROM_ABI void -__insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { +__insertion_sort_unguarded(_RandomAccessIterator const __first, _RandomAccessIterator __last, _Compare __comp) { using _Ops = _IterOps<_AlgPolicy>; typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; if (__first == __last) return; + const _RandomAccessIterator __leftmost = __first - difference_type(1); (void)__leftmost; // can be unused when assertions are disabled for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) { _RandomAccessIterator __j = __i - difference_type(1); if (__comp(*__i, *__j)) { @@ -294,6 +295,7 @@ __insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator do { *__j = _Ops::__iter_move(__k); __j = __k; + _LIBCPP_ASSERT(__k != __leftmost, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above. *__j = std::move(__t); } @@ -496,14 +498,17 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type; _LIBCPP_ASSERT(__last - __first >= difference_type(3), ""); + const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around + const _RandomAccessIterator __end = __last; (void)__end; // - _RandomAccessIterator __begin = __first; value_type __pivot(_Ops::__iter_move(__first)); // Find the first element greater than the pivot. if (__comp(__pivot, *(__last - difference_type(1)))) { // Not guarded since we know the last element is greater than the pivot. - while (!__comp(__pivot, *++__first)) { - } + do { + ++__first; + _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + } while (!__comp(__pivot, *__first)); } else { while (++__first < __last && !__comp(__pivot, *__first)) { } @@ -512,8 +517,10 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, if (__first < __last) { // It will be always guarded because __introsort will do the median-of-three // before calling this. - while (__comp(__pivot, *--__last)) { - } + do { + _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + --__last; + } while (__comp(__pivot, *__last)); } // If the first element greater than the pivot is at or after the // last element less than or equal to the pivot, then we have covered the @@ -578,13 +585,16 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; _LIBCPP_ASSERT(__last - __first >= difference_type(3), ""); - _RandomAccessIterator __begin = __first; + const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around + const _RandomAccessIterator __end = __last; (void)__end; // value_type __pivot(_Ops::__iter_move(__first)); // Find the first element greater or equal to the pivot. It will be always // guarded because __introsort will do the median-of-three before calling // this. - while (__comp(*++__first, __pivot)) - ; + do { + ++__first; + _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + } while (__comp(*__first, __pivot)); // Find the last element less than the pivot. if (__begin == __first - difference_type(1)) { @@ -592,8 +602,10 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte ; } else { // Guarded. - while (!__comp(*--__last, __pivot)) - ; + do { + _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + --__last; + } while (!__comp(*__last, __pivot)); } // If the first element greater than or equal to the pivot is at or after the @@ -605,10 +617,14 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte // correct side of the pivot. while (__first < __last) { _Ops::iter_swap(__first, __last); - while (__comp(*++__first, __pivot)) - ; - while (!__comp(*--__last, __pivot)) - ; + do { + ++__first; + _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + } while (__comp(*__first, __pivot)); + do { + _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + --__last; + } while (!__comp(*__last, __pivot)); } // Move the pivot to its correct position. _RandomAccessIterator __pivot_pos = __first - difference_type(1); @@ -627,12 +643,15 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter using _Ops = _IterOps<_AlgPolicy>; typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; - _RandomAccessIterator __begin = __first; + const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around + const _RandomAccessIterator __end = __last; (void)__end; // value_type __pivot(_Ops::__iter_move(__first)); if (__comp(__pivot, *(__last - difference_type(1)))) { // Guarded. - while (!__comp(__pivot, *++__first)) { - } + do { + ++__first; + _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + } while (!__comp(__pivot, *__first)); } else { while (++__first < __last && !__comp(__pivot, *__first)) { } @@ -641,15 +660,21 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter if (__first < __last) { // It will be always guarded because __introsort will do the // median-of-three before calling this. - while (__comp(__pivot, *--__last)) { - } + do { + _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + --__last; + } while (__comp(__pivot, *__last)); } while (__first < __last) { _Ops::iter_swap(__first, __last); - while (!__comp(__pivot, *++__first)) - ; - while (__comp(__pivot, *--__last)) - ; + do { + ++__first; + _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + } while (!__comp(__pivot, *__first)); + do { + _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?"); + --__last; + } while (__comp(__pivot, *__last)); } _RandomAccessIterator __pivot_pos = __first - difference_type(1); if (__begin != __pivot_pos) { |