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:
__libcpp_debug_randomizer()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
operator()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
min()49 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }
max()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_;
__seed()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
min()87 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() {return _Min;}
max()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
random_shuffle(_RandomAccessIterator __first,_RandomAccessIterator __last)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
random_shuffle(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomNumberGenerator && __rand)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>
__shuffle(_RandomAccessIterator __first,_Sentinel __last_sentinel,_UniformRandomNumberGenerator && __g)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
shuffle(_RandomAccessIterator __first,_RandomAccessIterator __last,_UniformRandomNumberGenerator && __g)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