Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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 "llvm/Support/raw_ostream.h"
  17. #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(),
  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.
  33. template <typename T, typename GenT> class ReservoirSampler {
  34.   GenT &RandGen;
  35.   std::remove_const_t<T> 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 = std::remove_reference_t<
  74.               decltype(*std::begin(std::declval<RangeT>()))>>
  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>
  90. ReservoirSampler<T, GenT> makeSampler(GenT &RandGen) {
  91.   return ReservoirSampler<T, GenT>(RandGen);
  92. }
  93.  
  94. } // namespace llvm
  95.  
  96. #endif // LLVM_FUZZMUTATE_RANDOM_H
  97.