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