1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
/*
* Copyright (c) 2017 The WebRTC project authors. All Rights Reserved.
*
* Use of this source code is governed by a BSD-style license
* that can be found in the LICENSE file in the root of the source
* tree. An additional intellectual property rights grant can be found
* in the file PATENTS. All contributing project authors may
* be found in the AUTHORS file in the root of the source tree.
*/
#include "rtc_base/numerics/histogram_percentile_counter.h"
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <optional>
#include "rtc_base/checks.h"
namespace webrtc {
HistogramPercentileCounter::HistogramPercentileCounter(
uint32_t long_tail_boundary)
: histogram_low_(size_t{long_tail_boundary}),
long_tail_boundary_(long_tail_boundary),
total_elements_(0),
total_elements_low_(0) {}
HistogramPercentileCounter::~HistogramPercentileCounter() = default;
void HistogramPercentileCounter::Add(const HistogramPercentileCounter& other) {
for (uint32_t value = 0; value < other.long_tail_boundary_; ++value) {
Add(value, other.histogram_low_[value]);
}
for (const auto& it : histogram_high_) {
Add(it.first, it.second);
}
}
void HistogramPercentileCounter::Add(uint32_t value, size_t count) {
if (value < long_tail_boundary_) {
histogram_low_[value] += count;
total_elements_low_ += count;
} else {
histogram_high_[value] += count;
}
total_elements_ += count;
}
void HistogramPercentileCounter::Add(uint32_t value) {
Add(value, 1);
}
std::optional<uint32_t> HistogramPercentileCounter::GetPercentile(
float fraction) {
RTC_CHECK_LE(fraction, 1.0);
RTC_CHECK_GE(fraction, 0.0);
if (total_elements_ == 0)
return std::nullopt;
size_t elements_to_skip = static_cast<size_t>(
std::max(0.0f, std::ceil(total_elements_ * fraction) - 1));
if (elements_to_skip >= total_elements_)
elements_to_skip = total_elements_ - 1;
if (elements_to_skip < total_elements_low_) {
for (uint32_t value = 0; value < long_tail_boundary_; ++value) {
if (elements_to_skip < histogram_low_[value])
return value;
elements_to_skip -= histogram_low_[value];
}
} else {
elements_to_skip -= total_elements_low_;
for (const auto& it : histogram_high_) {
if (elements_to_skip < it.second)
return it.first;
elements_to_skip -= it.second;
}
}
RTC_DCHECK_NOTREACHED();
return std::nullopt;
}
} // namespace webrtc
|
