Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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 |