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 <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_TYPE_VIS __libcpp_debug_randomizer {
32 public:
33   __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) \
66   || defined(_LIBCPP_BUILDING_LIBRARY)
67 class _LIBCPP_TYPE_VIS __rs_default;
68 
69 _LIBCPP_FUNC_VIS __rs_default __rs_get();
70 
71 class _LIBCPP_TYPE_VIS __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 
87     static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
88     static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
89 
90     friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
91 };
92 
93 _LIBCPP_FUNC_VIS __rs_default __rs_get();
94 
95 template <class _RandomAccessIterator>
96 _LIBCPP_DEPRECATED_IN_CXX14 void
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_DEPRECATED_IN_CXX14 void
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 _UniformRandomNumberGenerator>
140 void __shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
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                 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
153         }
154     }
155 }
156 
157 template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
158 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
159              _UniformRandomNumberGenerator&& __g) {
160   std::__shuffle<_ClassicAlgPolicy>(
161       std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
162 }
163 
164 _LIBCPP_END_NAMESPACE_STD
165 
166 _LIBCPP_POP_MACROS
167 
168 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H
169