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> 17#include "llvm/Support/raw_ostream.h" 18namespace llvm { 19 20/// Return a uniformly distributed random value between \c Min and \c Max 21template <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 26template <typename T, typename GenT> T uniform(GenT &Gen) { 27 return uniform<T>(Gen, std::numeric_limits<T>::min(), 28 std::numeric_limits<T>::max()); 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. 33template <typename T, typename GenT> class ReservoirSampler { 34 GenT &RandGen; 35 typename std::remove_const<T>::type Selection = {}; 36 uint64_t TotalWeight = 0; 37 38public: 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 72template <typename GenT, typename RangeT, 73 typename ElT = typename std::remove_reference< 74 decltype(*std::begin(std::declval<RangeT>()))>::type> 75ReservoirSampler<ElT, GenT> makeSampler(GenT &RandGen, RangeT &&Items) { 76 ReservoirSampler<ElT, GenT> RS(RandGen); 77 RS.sample(Items); 78 return RS; 79} 80 81template <typename GenT, typename T> 82ReservoirSampler<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 89template <typename T, typename GenT> 90ReservoirSampler<T, GenT> makeSampler(GenT &RandGen) { 91 return ReservoirSampler<T, GenT>(RandGen); 92} 93 94} // End llvm namespace 95 96#endif // LLVM_FUZZMUTATE_RANDOM_H 97