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