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