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