1 //===--- Random.h - Utilities for random sampling -------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Utilities for random sampling.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_FUZZMUTATE_RANDOM_H
15 #define LLVM_FUZZMUTATE_RANDOM_H
16
17 #include <random>
18 #include "llvm/Support/raw_ostream.h"
19 namespace llvm {
20
21 /// Return a uniformly distributed random value between \c Min and \c Max
uniform(GenT & Gen,T Min,T Max)22 template <typename T, typename GenT> T uniform(GenT &Gen, T Min, T Max) {
23 return std::uniform_int_distribution<T>(Min, Max)(Gen);
24 }
25
26 /// Return a uniformly distributed random value of type \c T
uniform(GenT & Gen)27 template <typename T, typename GenT> T uniform(GenT &Gen) {
28 return uniform<T>(Gen, std::numeric_limits<T>::min(),
29 std::numeric_limits<T>::max());
30 }
31
32 /// Randomly selects an item by sampling into a set with an unknown number of
33 /// elements, which may each be weighted to be more likely choices.
34 template <typename T, typename GenT> class ReservoirSampler {
35 GenT &RandGen;
36 typename std::remove_const<T>::type Selection = {};
37 uint64_t TotalWeight = 0;
38
39 public:
ReservoirSampler(GenT & RandGen)40 ReservoirSampler(GenT &RandGen) : RandGen(RandGen) {}
41
totalWeight()42 uint64_t totalWeight() const { return TotalWeight; }
isEmpty()43 bool isEmpty() const { return TotalWeight == 0; }
44
getSelection()45 const T &getSelection() const {
46 assert(!isEmpty() && "Nothing selected");
47 return Selection;
48 }
49
50 explicit operator bool() const { return !isEmpty();}
51 const T &operator*() const { return getSelection(); }
52
53 /// Sample each item in \c Items with unit weight
sample(RangeT && Items)54 template <typename RangeT> ReservoirSampler &sample(RangeT &&Items) {
55 for (auto &I : Items)
56 sample(I, 1);
57 return *this;
58 }
59
60 /// Sample a single item with the given weight.
sample(const T & Item,uint64_t Weight)61 ReservoirSampler &sample(const T &Item, uint64_t Weight) {
62 if (!Weight)
63 // If the weight is zero, do nothing.
64 return *this;
65 TotalWeight += Weight;
66 // Consider switching from the current element to this one.
67 if (uniform<uint64_t>(RandGen, 1, TotalWeight) <= Weight)
68 Selection = Item;
69 return *this;
70 }
71 };
72
73 template <typename GenT, typename RangeT,
74 typename ElT = typename std::remove_reference<
75 decltype(*std::begin(std::declval<RangeT>()))>::type>
makeSampler(GenT & RandGen,RangeT && Items)76 ReservoirSampler<ElT, GenT> makeSampler(GenT &RandGen, RangeT &&Items) {
77 ReservoirSampler<ElT, GenT> RS(RandGen);
78 RS.sample(Items);
79 return RS;
80 }
81
82 template <typename GenT, typename T>
makeSampler(GenT & RandGen,const T & Item,uint64_t Weight)83 ReservoirSampler<T, GenT> makeSampler(GenT &RandGen, const T &Item,
84 uint64_t Weight) {
85 ReservoirSampler<T, GenT> RS(RandGen);
86 RS.sample(Item, Weight);
87 return RS;
88 }
89
90 template <typename T, typename GenT>
makeSampler(GenT & RandGen)91 ReservoirSampler<T, GenT> makeSampler(GenT &RandGen) {
92 return ReservoirSampler<T, GenT>(RandGen);
93 }
94
95 } // End llvm namespace
96
97 #endif // LLVM_FUZZMUTATE_RANDOM_H
98