LCOV - code coverage report
Current view: top level - include/llvm/FuzzMutate - Random.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 14 20 70.0 %
Date: 2017-09-14 15:23:50 Functions: 1 14 7.1 %
Legend: Lines: hit not hit

          Line data    Source code
       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      300002 :   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           0 : 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       15002 :   ReservoirSampler(GenT &RandGen) : RandGen(RandGen) {}
      41             : 
      42             :   uint64_t totalWeight() const { return TotalWeight; }
      43           1 :   bool isEmpty() const { return TotalWeight == 0; }
      44             : 
      45             :   const T &getSelection() const {
      46             :     assert(!isEmpty() && "Nothing selected");
      47             :     return Selection;
      48             :   }
      49             : 
      50           0 :   explicit operator bool() const { return !isEmpty();}
      51           0 :   const T &operator*() const { return getSelection(); }
      52             : 
      53             :   /// Sample each item in \c Items with unit weight
      54           0 :   template <typename RangeT> ReservoirSampler &sample(RangeT &&Items) {
      55      210000 :     for (auto &I : Items)
      56      150000 :       sample(I, 1);
      57           0 :     return *this;
      58             :   }
      59             : 
      60             :   /// Sample a single item with the given weight.
      61      150002 :   ReservoirSampler &sample(const T &Item, uint64_t Weight) {
      62      150002 :     if (!Weight)
      63             :       // If the weight is zero, do nothing.
      64             :       return *this;
      65      150001 :     TotalWeight += Weight;
      66             :     // Consider switching from the current element to this one.
      67      300002 :     if (uniform<uint64_t>(RandGen, 1, TotalWeight) <= Weight)
      68       44054 :       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       15000 :   ReservoirSampler<ElT, GenT> RS(RandGen);
      78       15000 :   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           2 :   ReservoirSampler<T, GenT> RS(RandGen);
      86           2 :   RS.sample(Item, Weight);
      87             :   return RS;
      88             : }
      89             : 
      90             : template <typename T, typename GenT>
      91             : ReservoirSampler<T, GenT> makeSampler(GenT &RandGen) {
      92           0 :   return ReservoirSampler<T, GenT>(RandGen);
      93             : }
      94             : 
      95             : } // End llvm namespace
      96             : 
      97             : #endif // LLVM_FUZZMUTATE_RANDOM_H

Generated by: LCOV version 1.13