Coverage Report

Created: 2023-11-12 09:30

/proc/self/cwd/external/com_github_google_libprotobuf_mutator/src/weighted_reservoir_sampler.h
Line
Count
Source (jump to first uncovered line)
1
// Copyright 2016 Google Inc. All rights reserved.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14
15
#ifndef SRC_WEIGHTED_RESERVOIR_SAMPLER_H_
16
#define SRC_WEIGHTED_RESERVOIR_SAMPLER_H_
17
18
#include <cassert>
19
#include <random>
20
21
namespace protobuf_mutator {
22
23
// Algorithm pick one item from the sequence of weighted items.
24
// https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao
25
//
26
// Example:
27
//   WeightedReservoirSampler<int> sampler;
28
//   for(int i = 0; i < size; ++i)
29
//     sampler.Pick(weight[i], i);
30
//   return sampler.GetSelected();
31
template <class T, class RandomEngine = std::default_random_engine>
32
class WeightedReservoirSampler {
33
 public:
34
0
  explicit WeightedReservoirSampler(RandomEngine* random) : random_(random) {}
Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::WeightedReservoirSampler(std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul>*)
Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::WeightedReservoirSampler(std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul>*)
35
36
0
  void Try(uint64_t weight, const T& item) {
37
0
    if (Pick(weight)) selected_ = item;
38
0
  }
Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Try(unsigned long, protobuf_mutator::(anonymous namespace)::MutationSampler::Result const&)
Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Try(unsigned long, protobuf_mutator::ConstFieldInstance const&)
39
40
0
  const T& selected() const { return selected_; }
Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::selected() const
Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::selected() const
41
42
0
  bool IsEmpty() const { return total_weight_ == 0; }
43
44
 private:
45
0
  bool Pick(uint64_t weight) {
46
0
    if (weight == 0) return false;
47
0
    total_weight_ += weight;
48
0
    return weight == total_weight_ || std::uniform_int_distribution<uint64_t>(
49
0
                                          1, total_weight_)(*random_) <= weight;
50
0
  }
Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Pick(unsigned long)
Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Pick(unsigned long)
51
52
  T selected_ = {};
53
  uint64_t total_weight_ = 0;
54
  RandomEngine* random_;
55
};
56
57
}  // namespace protobuf_mutator
58
59
#endif  // SRC_WEIGHTED_RESERVOIR_SAMPLER_H_