168 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_SHUFFLE_H10#define _LIBCPP___ALGORITHM_SHUFFLE_H11 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_header24#endif25 26_LIBCPP_PUSH_MACROS27#include <__undef_macros>28 29_LIBCPP_BEGIN_NAMESPACE_STD30 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 _LIBCPP_CONSTEXPR result_type min() { return _Min; }50 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR 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_SEED57 return _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED;58#else59 static char __x;60 return reinterpret_cast<uintptr_t>(&__x);61#endif62 }63};64 65#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) || defined(_LIBCPP_BUILDING_LIBRARY)66class _LIBCPP_EXPORTED_FROM_ABI __rs_default;67 68_LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();69 70class _LIBCPP_EXPORTED_FROM_ABI __rs_default {71 static unsigned __c_;72 73 __rs_default();74 75public:76 typedef uint_fast32_t result_type;77 78 static const result_type _Min = 0;79 static const result_type _Max = 0xFFFFFFFF;80 81 __rs_default(const __rs_default&);82 ~__rs_default();83 84 result_type operator()();85 86 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }87 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; }88 89 friend _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();90};91 92_LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();93 94template <class _RandomAccessIterator>95_LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void96random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) {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 _Dp __uid;103 __rs_default __g = __rs_get();104 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {105 difference_type __i = __uid(__g, _Pp(0, __d));106 if (__i != difference_type(0))107 swap(*__first, *(__first + __i));108 }109 }110}111 112template <class _RandomAccessIterator, class _RandomNumberGenerator>113_LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void114random_shuffle(_RandomAccessIterator __first,115 _RandomAccessIterator __last,116# ifndef _LIBCPP_CXX03_LANG117 _RandomNumberGenerator&& __rand)118# else119 _RandomNumberGenerator& __rand)120# endif121{122 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;123 difference_type __d = __last - __first;124 if (__d > 1) {125 for (--__last; __first < __last; ++__first, (void)--__d) {126 difference_type __i = __rand(__d);127 if (__i != difference_type(0))128 swap(*__first, *(__first + __i));129 }130 }131}132#endif133 134template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>135_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator136__shuffle(_RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {137 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;138 typedef uniform_int_distribution<ptrdiff_t> _Dp;139 typedef typename _Dp::param_type _Pp;140 141 auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);142 auto __last = __original_last;143 difference_type __d = __last - __first;144 if (__d > 1) {145 _Dp __uid;146 for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {147 difference_type __i = __uid(__g, _Pp(0, __d));148 if (__i != difference_type(0))149 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);150 }151 }152 153 return __original_last;154}155 156template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>157_LIBCPP_HIDE_FROM_ABI void158shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {159 (void)std::__shuffle<_ClassicAlgPolicy>(160 std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));161}162 163_LIBCPP_END_NAMESPACE_STD164 165_LIBCPP_POP_MACROS166 167#endif // _LIBCPP___ALGORITHM_SHUFFLE_H168