LLVM  10.0.0svn
Random.h
Go to the documentation of this file.
1 //===--- Random.h - Utilities for random sampling -------------------------===//
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 // Utilities for random sampling.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_FUZZMUTATE_RANDOM_H
14 #define LLVM_FUZZMUTATE_RANDOM_H
15 
16 #include <random>
18 namespace llvm {
19 
20 /// Return a uniformly distributed random value between \c Min and \c Max
21 template <typename T, typename GenT> T uniform(GenT &Gen, T Min, T Max) {
22  return std::uniform_int_distribution<T>(Min, Max)(Gen);
23 }
24 
25 /// Return a uniformly distributed random value of type \c T
26 template <typename T, typename GenT> T uniform(GenT &Gen) {
27  return uniform<T>(Gen, std::numeric_limits<T>::min(),
29 }
30 
31 /// Randomly selects an item by sampling into a set with an unknown number of
32 /// elements, which may each be weighted to be more likely choices.
33 template <typename T, typename GenT> class ReservoirSampler {
34  GenT &RandGen;
35  typename std::remove_const<T>::type Selection = {};
36  uint64_t TotalWeight = 0;
37 
38 public:
39  ReservoirSampler(GenT &RandGen) : RandGen(RandGen) {}
40 
41  uint64_t totalWeight() const { return TotalWeight; }
42  bool isEmpty() const { return TotalWeight == 0; }
43 
44  const T &getSelection() const {
45  assert(!isEmpty() && "Nothing selected");
46  return Selection;
47  }
48 
49  explicit operator bool() const { return !isEmpty();}
50  const T &operator*() const { return getSelection(); }
51 
52  /// Sample each item in \c Items with unit weight
53  template <typename RangeT> ReservoirSampler &sample(RangeT &&Items) {
54  for (auto &I : Items)
55  sample(I, 1);
56  return *this;
57  }
58 
59  /// Sample a single item with the given weight.
60  ReservoirSampler &sample(const T &Item, uint64_t Weight) {
61  if (!Weight)
62  // If the weight is zero, do nothing.
63  return *this;
64  TotalWeight += Weight;
65  // Consider switching from the current element to this one.
66  if (uniform<uint64_t>(RandGen, 1, TotalWeight) <= Weight)
67  Selection = Item;
68  return *this;
69  }
70 };
71 
72 template <typename GenT, typename RangeT,
73  typename ElT = typename std::remove_reference<
74  decltype(*std::begin(std::declval<RangeT>()))>::type>
75 ReservoirSampler<ElT, GenT> makeSampler(GenT &RandGen, RangeT &&Items) {
76  ReservoirSampler<ElT, GenT> RS(RandGen);
77  RS.sample(Items);
78  return RS;
79 }
80 
81 template <typename GenT, typename T>
82 ReservoirSampler<T, GenT> makeSampler(GenT &RandGen, const T &Item,
83  uint64_t Weight) {
84  ReservoirSampler<T, GenT> RS(RandGen);
85  RS.sample(Item, Weight);
86  return RS;
87 }
88 
89 template <typename T, typename GenT>
91  return ReservoirSampler<T, GenT>(RandGen);
92 }
93 
94 } // End llvm namespace
95 
96 #endif // LLVM_FUZZMUTATE_RANDOM_H
ReservoirSampler & sample(const T &Item, uint64_t Weight)
Sample a single item with the given weight.
Definition: Random.h:60
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
This class represents lattice values for constants.
Definition: AllocatorList.h:23
uint64_t totalWeight() const
Definition: Random.h:41
T uniform(GenT &Gen, T Min, T Max)
Return a uniformly distributed random value between Min and Max.
Definition: Random.h:21
ReservoirSampler & sample(RangeT &&Items)
Sample each item in Items with unit weight.
Definition: Random.h:53
ReservoirSampler< ElT, GenT > makeSampler(GenT &RandGen, RangeT &&Items)
Definition: Random.h:75
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
const T & operator*() const
Definition: Random.h:50
Randomly selects an item by sampling into a set with an unknown number of elements, which may each be weighted to be more likely choices.
Definition: Random.h:33
bool isEmpty() const
Definition: Random.h:42
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ReservoirSampler(GenT &RandGen)
Definition: Random.h:39
const T & getSelection() const
Definition: Random.h:44