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