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___ALGORITHM_SHUFFLE_H 10 #define _LIBCPP___ALGORITHM_SHUFFLE_H 11 12 #include <__algorithm/iterator_operations.h> 13 #include <__config> 14 #include <__debug> 15 #include <__iterator/iterator_traits.h> 16 #include <__random/uniform_int_distribution.h> 17 #include <__utility/forward.h> 18 #include <__utility/move.h> 19 #include <__utility/swap.h> 20 #include <cstddef> 21 #include <cstdint> 22 23 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 24 # pragma GCC system_header 25 #endif 26 27 _LIBCPP_PUSH_MACROS 28 #include <__undef_macros> 29 30 _LIBCPP_BEGIN_NAMESPACE_STD 31 32 class _LIBCPP_TYPE_VIS __libcpp_debug_randomizer { 33 public: 34 __libcpp_debug_randomizer() { 35 __state_ = __seed(); 36 __inc_ = __state_ + 0xda3e39cb94b95bdbULL; 37 __inc_ = (__inc_ << 1) | 1; 38 } 39 typedef uint_fast32_t result_type; 40 41 static const result_type _Min = 0; 42 static const result_type _Max = 0xFFFFFFFF; 43 44 _LIBCPP_HIDE_FROM_ABI result_type operator()() { 45 uint_fast64_t __oldstate = __state_; 46 __state_ = __oldstate * 6364136223846793005ULL + __inc_; 47 return __oldstate >> 32; 48 } 49 50 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; } 51 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; } 52 53 private: 54 uint_fast64_t __state_; 55 uint_fast64_t __inc_; 56 _LIBCPP_HIDE_FROM_ABI static uint_fast64_t __seed() { 57 #ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED 58 return _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED; 59 #else 60 static char __x; 61 return reinterpret_cast<uintptr_t>(&__x); 62 #endif 63 } 64 }; 65 66 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \ 67 || defined(_LIBCPP_BUILDING_LIBRARY) 68 class _LIBCPP_TYPE_VIS __rs_default; 69 70 _LIBCPP_FUNC_VIS __rs_default __rs_get(); 71 72 class _LIBCPP_TYPE_VIS __rs_default 73 { 74 static unsigned __c_; 75 76 __rs_default(); 77 public: 78 typedef uint_fast32_t result_type; 79 80 static const result_type _Min = 0; 81 static const result_type _Max = 0xFFFFFFFF; 82 83 __rs_default(const __rs_default&); 84 ~__rs_default(); 85 86 result_type operator()(); 87 88 static _LIBCPP_CONSTEXPR result_type min() {return _Min;} 89 static _LIBCPP_CONSTEXPR result_type max() {return _Max;} 90 91 friend _LIBCPP_FUNC_VIS __rs_default __rs_get(); 92 }; 93 94 _LIBCPP_FUNC_VIS __rs_default __rs_get(); 95 96 template <class _RandomAccessIterator> 97 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void 98 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 99 { 100 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 101 typedef uniform_int_distribution<ptrdiff_t> _Dp; 102 typedef typename _Dp::param_type _Pp; 103 difference_type __d = __last - __first; 104 if (__d > 1) 105 { 106 _Dp __uid; 107 __rs_default __g = __rs_get(); 108 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 109 { 110 difference_type __i = __uid(__g, _Pp(0, __d)); 111 if (__i != difference_type(0)) 112 swap(*__first, *(__first + __i)); 113 } 114 } 115 } 116 117 template <class _RandomAccessIterator, class _RandomNumberGenerator> 118 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void 119 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 120 #ifndef _LIBCPP_CXX03_LANG 121 _RandomNumberGenerator&& __rand) 122 #else 123 _RandomNumberGenerator& __rand) 124 #endif 125 { 126 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 127 difference_type __d = __last - __first; 128 if (__d > 1) 129 { 130 for (--__last; __first < __last; ++__first, (void) --__d) 131 { 132 difference_type __i = __rand(__d); 133 if (__i != difference_type(0)) 134 swap(*__first, *(__first + __i)); 135 } 136 } 137 } 138 #endif 139 140 template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator> 141 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator __shuffle( 142 _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) { 143 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 144 typedef uniform_int_distribution<ptrdiff_t> _Dp; 145 typedef typename _Dp::param_type _Pp; 146 147 auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel); 148 auto __last = __original_last; 149 difference_type __d = __last - __first; 150 if (__d > 1) 151 { 152 _Dp __uid; 153 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 154 { 155 difference_type __i = __uid(__g, _Pp(0, __d)); 156 if (__i != difference_type(0)) 157 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i); 158 } 159 } 160 161 return __original_last; 162 } 163 164 template <class _RandomAccessIterator, class _UniformRandomNumberGenerator> 165 _LIBCPP_HIDE_FROM_ABI void 166 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) { 167 (void)std::__shuffle<_ClassicAlgPolicy>( 168 std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g)); 169 } 170 171 _LIBCPP_END_NAMESPACE_STD 172 173 _LIBCPP_POP_MACROS 174 175 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H 176