158 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___CXX03___ALGORITHM_SHUFFLE_H10#define _LIBCPP___CXX03___ALGORITHM_SHUFFLE_H11 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_header24#endif25 26_LIBCPP_PUSH_MACROS27#include <__cxx03/__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 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_SEED57 return _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED;58#else59 static char __x;60 return reinterpret_cast<uintptr_t>(&__x);61#endif62 }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 void112random_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 _RandomAccessIterator126__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 void148shuffle(_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_STD154 155_LIBCPP_POP_MACROS156 157#endif // _LIBCPP___CXX03___ALGORITHM_SHUFFLE_H158