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) || defined(_LIBCPP_BUILDING_LIBRARY) 66 class _LIBCPP_EXPORTED_FROM_ABI __rs_default; 67 68 _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get(); 69 70 class _LIBCPP_EXPORTED_FROM_ABI __rs_default { 71 static unsigned __c_; 72 73 __rs_default(); 74 75 public: 76 typedef uint_fast32_t result_type; 77 78 static const result_type _Min = 0; 79 static const result_type _Max = 0xFFFFFFFF; 80 81 __rs_default(const __rs_default&); 82 ~__rs_default(); 83 84 result_type operator()(); 85 86 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; } 87 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; } 88 89 friend _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get(); 90 }; 91 92 _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get(); 93 94 template <class _RandomAccessIterator> 95 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void 96 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) { 97 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 98 typedef uniform_int_distribution<ptrdiff_t> _Dp; 99 typedef typename _Dp::param_type _Pp; 100 difference_type __d = __last - __first; 101 if (__d > 1) { 102 _Dp __uid; 103 __rs_default __g = __rs_get(); 104 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) { 105 difference_type __i = __uid(__g, _Pp(0, __d)); 106 if (__i != difference_type(0)) 107 swap(*__first, *(__first + __i)); 108 } 109 } 110 } 111 112 template <class _RandomAccessIterator, class _RandomNumberGenerator> 113 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void 114 random_shuffle(_RandomAccessIterator __first, 115 _RandomAccessIterator __last, 116 # ifndef _LIBCPP_CXX03_LANG 117 _RandomNumberGenerator&& __rand) 118 # else 119 _RandomNumberGenerator& __rand) 120 # endif 121 { 122 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 123 difference_type __d = __last - __first; 124 if (__d > 1) { 125 for (--__last; __first < __last; ++__first, (void)--__d) { 126 difference_type __i = __rand(__d); 127 if (__i != difference_type(0)) 128 swap(*__first, *(__first + __i)); 129 } 130 } 131 } 132 #endif 133 134 template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator> 135 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator 136 __shuffle(_RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) { 137 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 138 typedef uniform_int_distribution<ptrdiff_t> _Dp; 139 typedef typename _Dp::param_type _Pp; 140 141 auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel); 142 auto __last = __original_last; 143 difference_type __d = __last - __first; 144 if (__d > 1) { 145 _Dp __uid; 146 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) { 147 difference_type __i = __uid(__g, _Pp(0, __d)); 148 if (__i != difference_type(0)) 149 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i); 150 } 151 } 152 153 return __original_last; 154 } 155 156 template <class _RandomAccessIterator, class _UniformRandomNumberGenerator> 157 _LIBCPP_HIDE_FROM_ABI void 158 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) { 159 (void)std::__shuffle<_ClassicAlgPolicy>( 160 std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g)); 161 } 162 163 _LIBCPP_END_NAMESPACE_STD 164 165 _LIBCPP_POP_MACROS 166 167 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H 168