libcxx/include/__algorithm/shuffle.h

   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 <__iterator/iterator_traits.h>
  15 #include <__random/uniform_int_distribution.h>
  16 #include <__utility/forward.h>
  17 #include <__utility/move.h>
  18 #include <__utility/swap.h>
  19 #include <cstddef>
  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 class _LIBCPP_EXPORTED_FROM_ABI __libcpp_debug_randomizer {
  32 public:
  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
  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 };
  64
  65 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
  66   || defined(_LIBCPP_BUILDING_LIBRARY)
  67 class _LIBCPP_EXPORTED_FROM_ABI __rs_default;
  68
  69 _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
  70
  71 class _LIBCPP_EXPORTED_FROM_ABI __rs_default
  72 {
  73     static unsigned __c_;
  74
  75     __rs_default();
  76 public:
  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
  95 template <class _RandomAccessIterator>
  96 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
  97 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
  98 {
  99     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 100     typedef uniform_int_distribution<ptrdiff_t> _Dp;
 101     typedef typename _Dp::param_type _Pp;
 102     difference_type __d = __last - __first;
 103     if (__d > 1)
 104     {
 105         _Dp __uid;
 106         __rs_default __g = __rs_get();
 107         for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
 108         {
 109             difference_type __i = __uid(__g, _Pp(0, __d));
 110             if (__i != difference_type(0))
 111                 swap(*__first, *(__first + __i));
 112         }
 113     }
 114 }
 115
 116 template <class _RandomAccessIterator, class _RandomNumberGenerator>
 117 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
 118 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
 119 #ifndef _LIBCPP_CXX03_LANG
 120                _RandomNumberGenerator&& __rand)
 121 #else
 122                _RandomNumberGenerator& __rand)
 123 #endif
 124 {
 125     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 126     difference_type __d = __last - __first;
 127     if (__d > 1)
 128     {
 129         for (--__last; __first < __last; ++__first, (void) --__d)
 130         {
 131             difference_type __i = __rand(__d);
 132             if (__i != difference_type(0))
 133               swap(*__first, *(__first + __i));
 134         }
 135     }
 136 }
 137 #endif
 138
 139 template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
 140 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator __shuffle(
 141     _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
 142     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 143     typedef uniform_int_distribution<ptrdiff_t> _Dp;
 144     typedef typename _Dp::param_type _Pp;
 145
 146     auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
 147     auto __last = __original_last;
 148     difference_type __d = __last - __first;
 149     if (__d > 1)
 150     {
 151         _Dp __uid;
 152         for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
 153         {
 154             difference_type __i = __uid(__g, _Pp(0, __d));
 155             if (__i != difference_type(0))
 156                 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
 157         }
 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));
 168 }
 169
 170 _LIBCPP_END_NAMESPACE_STD
 171
 172 _LIBCPP_POP_MACROS
 173
 174 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H