Warning: This file is not a C or C++ file. It does not have highlighting.

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___CXX03___ALGORITHM_SHUFFLE_H
10#define _LIBCPP___CXX03___ALGORITHM_SHUFFLE_H
11
12#include <__cxx03/__algorithm/iterator_operations.h>
13#include <__cxx03/__config>
14#include <__cxx03/__iterator/iterator_traits.h>
15#include <__cxx03/__random/uniform_int_distribution.h>
16#include <__cxx03/__utility/forward.h>
17#include <__cxx03/__utility/move.h>
18#include <__cxx03/__utility/swap.h>
19#include <__cxx03/cstddef>
20#include <__cxx03/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 <__cxx03/__undef_macros>
28
29_LIBCPP_BEGIN_NAMESPACE_STD
30
31class _LIBCPP_EXPORTED_FROM_ABI __libcpp_debug_randomizer {
32public:
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
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 result_type min() { return _Min; }
50 static _LIBCPP_HIDE_FROM_ABI result_type max() { return _Max; }
51
52private:
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
65class _LIBCPP_EXPORTED_FROM_ABI __rs_default;
66
67_LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
68
69class _LIBCPP_EXPORTED_FROM_ABI __rs_default {
70 static unsigned __c_;
71
72 __rs_default();
73
74public:
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_HIDE_FROM_ABI result_type min() { return _Min; }
86 static _LIBCPP_HIDE_FROM_ABI result_type max() { return _Max; }
87
88 friend _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
89};
90
91_LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
92
93template <class _RandomAccessIterator>
94_LIBCPP_HIDE_FROM_ABI void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) {
95 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
96 typedef uniform_int_distribution<ptrdiff_t> _Dp;
97 typedef typename _Dp::param_type _Pp;
98 difference_type __d = __last - __first;
99 if (__d > 1) {
100 _Dp __uid;
101 __rs_default __g = __rs_get();
102 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {
103 difference_type __i = __uid(__g, _Pp(0, __d));
104 if (__i != difference_type(0))
105 swap(*__first, *(__first + __i));
106 }
107 }
108}
109
110template <class _RandomAccessIterator, class _RandomNumberGenerator>
111_LIBCPP_HIDE_FROM_ABI void
112random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomNumberGenerator&& __rand) {
113 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
114 difference_type __d = __last - __first;
115 if (__d > 1) {
116 for (--__last; __first < __last; ++__first, (void)--__d) {
117 difference_type __i = __rand(__d);
118 if (__i != difference_type(0))
119 swap(*__first, *(__first + __i));
120 }
121 }
122}
123
124template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
125_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
126__shuffle(_RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
127 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
128 typedef uniform_int_distribution<ptrdiff_t> _Dp;
129 typedef typename _Dp::param_type _Pp;
130
131 auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
132 auto __last = __original_last;
133 difference_type __d = __last - __first;
134 if (__d > 1) {
135 _Dp __uid;
136 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {
137 difference_type __i = __uid(__g, _Pp(0, __d));
138 if (__i != difference_type(0))
139 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
140 }
141 }
142
143 return __original_last;
144}
145
146template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
147_LIBCPP_HIDE_FROM_ABI void
148shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
149 (void)std::__shuffle<_ClassicAlgPolicy>(
150 std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
151}
152
153_LIBCPP_END_NAMESPACE_STD
154
155_LIBCPP_POP_MACROS
156
157#endif // _LIBCPP___CXX03___ALGORITHM_SHUFFLE_H
158

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__cxx03/__algorithm/shuffle.h