Mercurial > hg > CbC > CbC_llvm

comparison libcxx/include/__algorithm/shuffle.h @ 236:c4bab56944e8 llvm-original

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 16
author kono
date Wed, 09 Nov 2022 17:45:10 +0900
parents 5f17cb93ff66
children 1f2b6ac9f198
comparison
equal deleted inserted replaced
232:70dce7da266c 236:c4bab56944e8
7 //===----------------------------------------------------------------------===// 7 //===----------------------------------------------------------------------===//
8 8
9 #ifndef _LIBCPP___ALGORITHM_SHUFFLE_H 9 #ifndef _LIBCPP___ALGORITHM_SHUFFLE_H
10 #define _LIBCPP___ALGORITHM_SHUFFLE_H 10 #define _LIBCPP___ALGORITHM_SHUFFLE_H
11 11
12 #include <__algorithm/iterator_operations.h>
12 #include <__config> 13 #include <__config>
14 #include <__debug>
13 #include <__iterator/iterator_traits.h> 15 #include <__iterator/iterator_traits.h>
14 #include <__random/uniform_int_distribution.h> 16 #include <__random/uniform_int_distribution.h>
15 #include <__utility/swap.h> 17 #include <__utility/forward.h>
18 #include <__utility/move.h>
16 #include <cstddef> 19 #include <cstddef>
17 #include <cstdint> 20 #include <cstdint>
18 21
19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
20 #pragma GCC system_header 23 # pragma GCC system_header
21 #endif 24 #endif
22 25
23 _LIBCPP_PUSH_MACROS 26 _LIBCPP_PUSH_MACROS
24 #include <__undef_macros> 27 #include <__undef_macros>
25 28
26 _LIBCPP_BEGIN_NAMESPACE_STD 29 _LIBCPP_BEGIN_NAMESPACE_STD
27 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 };
28 64
29 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \ 65 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
30 || defined(_LIBCPP_BUILDING_LIBRARY) 66 || defined(_LIBCPP_BUILDING_LIBRARY)
31 class _LIBCPP_TYPE_VIS __rs_default; 67 class _LIBCPP_TYPE_VIS __rs_default;
32 68
55 }; 91 };
56 92
57 _LIBCPP_FUNC_VIS __rs_default __rs_get(); 93 _LIBCPP_FUNC_VIS __rs_default __rs_get();
58 94
59 template <class _RandomAccessIterator> 95 template <class _RandomAccessIterator>
60 _LIBCPP_DEPRECATED_IN_CXX14 void 96 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
61 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 97 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
62 { 98 {
63 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 99 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
64 typedef uniform_int_distribution<ptrdiff_t> _Dp; 100 typedef uniform_int_distribution<ptrdiff_t> _Dp;
65 typedef typename _Dp::param_type _Pp; 101 typedef typename _Dp::param_type _Pp;
76 } 112 }
77 } 113 }
78 } 114 }
79 115
80 template <class _RandomAccessIterator, class _RandomNumberGenerator> 116 template <class _RandomAccessIterator, class _RandomNumberGenerator>
81 _LIBCPP_DEPRECATED_IN_CXX14 void 117 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
82 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 118 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
83 #ifndef _LIBCPP_CXX03_LANG 119 #ifndef _LIBCPP_CXX03_LANG
84 _RandomNumberGenerator&& __rand) 120 _RandomNumberGenerator&& __rand)
85 #else 121 #else
86 _RandomNumberGenerator& __rand) 122 _RandomNumberGenerator& __rand)
98 } 134 }
99 } 135 }
100 } 136 }
101 #endif 137 #endif
102 138
103 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> 139 template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
104 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 140 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator __shuffle(
105 _UniformRandomNumberGenerator&& __g) 141 _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
106 {
107 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 142 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
108 typedef uniform_int_distribution<ptrdiff_t> _Dp; 143 typedef uniform_int_distribution<ptrdiff_t> _Dp;
109 typedef typename _Dp::param_type _Pp; 144 typedef typename _Dp::param_type _Pp;
145
146 auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
147 auto __last = __original_last;
110 difference_type __d = __last - __first; 148 difference_type __d = __last - __first;
111 if (__d > 1) 149 if (__d > 1)
112 { 150 {
113 _Dp __uid; 151 _Dp __uid;
114 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 152 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
115 { 153 {
116 difference_type __i = __uid(__g, _Pp(0, __d)); 154 difference_type __i = __uid(__g, _Pp(0, __d));
117 if (__i != difference_type(0)) 155 if (__i != difference_type(0))
118 swap(*__first, *(__first + __i)); 156 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
119 } 157 }
120 } 158 }
159
160 return __original_last;
161 }
162
163 template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
164 _LIBCPP_HIDE_FROM_ABI void
165 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
166 (void)std::__shuffle<_ClassicAlgPolicy>(
167 std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
121 } 168 }
122 169
123 _LIBCPP_END_NAMESPACE_STD 170 _LIBCPP_END_NAMESPACE_STD
124 171
125 _LIBCPP_POP_MACROS 172 _LIBCPP_POP_MACROS