Ilya Nikolaevskiy | ed23be9 | 2017-10-12 12:38:01 +0200 | [diff] [blame] | 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/histogram_percentile_counter.h" |
| 12 | |
| 13 | #include <algorithm> |
| 14 | #include <cmath> |
| 15 | |
| 16 | #include "rtc_base/checks.h" |
| 17 | |
| 18 | namespace rtc { |
| 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 | |
| 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 | |
| 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 | |
| 47 | void HistogramPercentileCounter::Add(uint32_t value) { |
| 48 | Add(value, 1); |
| 49 | } |
| 50 | |
| 51 | rtc::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 rtc::Optional<uint32_t>(); |
| 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 rtc::Optional<uint32_t>(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 rtc::Optional<uint32_t>(it.first); |
| 72 | elements_to_skip -= it.second; |
| 73 | } |
| 74 | } |
| 75 | RTC_NOTREACHED(); |
| 76 | return rtc::Optional<uint32_t>(); |
| 77 | } |
| 78 | |
| 79 | } // namespace rtc |