Home | History | Annotate | Download | only in FuzzMutate 
      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
     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
     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:
     40   ReservoirSampler(GenT &RandGen) : RandGen(RandGen) {}
     41 
     42   uint64_t totalWeight() const { return TotalWeight; }
     43   bool isEmpty() const { return TotalWeight == 0; }
     44 
     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
     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.
     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>
     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>
     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>
     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