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