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 <__cstddef/ptrdiff_t.h>
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 <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_LIBCPP_BEGIN_EXPLICIT_ABI_ANNOTATIONS
32class _LIBCPP_EXPORTED_FROM_ABI __libcpp_debug_randomizer {
33public:
34 _LIBCPP_HIDE_FROM_ABI __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
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
50 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }
51 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; }
52
53private:
54 uint_fast64_t __state_;
55 uint_fast64_t __inc_;
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) || defined(_LIBCPP_BUILDING_LIBRARY)
67class _LIBCPP_EXPORTED_FROM_ABI __rs_default;
68
69_LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
70
71class _LIBCPP_EXPORTED_FROM_ABI __rs_default {
72 static unsigned __c_;
73
74 __rs_default();
75
76public:
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_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }
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
95template <class _RandomAccessIterator>
96_LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
97random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) {
98 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
99 typedef uniform_int_distribution<ptrdiff_t> _Dp;
100 typedef typename _Dp::param_type _Pp;
101 difference_type __d = __last - __first;
102 if (__d > 1) {
103 _Dp __uid;
104 __rs_default __g = __rs_get();
105 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {
106 difference_type __i = __uid(__g, _Pp(0, __d));
107 if (__i != difference_type(0))
108 swap(*__first, *(__first + __i));
109 }
110 }
111}
112
113template <class _RandomAccessIterator, class _RandomNumberGenerator>
114_LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
115random_shuffle(_RandomAccessIterator __first,
116 _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 for (--__last; __first < __last; ++__first, (void)--__d) {
127 difference_type __i = __rand(__d);
128 if (__i != difference_type(0))
129 swap(*__first, *(__first + __i));
130 }
131 }
132}
133#endif
134
135template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
136_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
137__shuffle(_RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
138 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
139 typedef uniform_int_distribution<ptrdiff_t> _Dp;
140 typedef typename _Dp::param_type _Pp;
141
142 auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
143 auto __last = __original_last;
144 difference_type __d = __last - __first;
145 if (__d > 1) {
146 _Dp __uid;
147 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {
148 difference_type __i = __uid(__g, _Pp(0, __d));
149 if (__i != difference_type(0))
150 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
151 }
152 }
153
154 return __original_last;
155}
156
157template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
158_LIBCPP_HIDE_FROM_ABI void
159shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
160 (void)std::__shuffle<_ClassicAlgPolicy>(
161 std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
162}
163
164_LIBCPP_END_EXPLICIT_ABI_ANNOTATIONS
165_LIBCPP_END_NAMESPACE_STD
166
167_LIBCPP_POP_MACROS
168
169#endif // _LIBCPP___ALGORITHM_SHUFFLE_H
170