From 5aa5d282eac56a21e74611c1cdbaa97bb5db2dca Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Tue, 8 Feb 2022 02:05:36 +0300 Subject: chore(3p/abseil_cpp): unvendor abseil_cpp we weren't actually using these sources anymore, okay? Change-Id: If701571d9716de308d3512e1eb22c35db0877a66 Reviewed-on: https://cl.tvl.fyi/c/depot/+/5248 Tested-by: BuildkiteCI Reviewed-by: grfn Autosubmit: tazjin --- .../absl/random/log_uniform_int_distribution.h | 254 --------------------- 1 file changed, 254 deletions(-) delete mode 100644 third_party/abseil_cpp/absl/random/log_uniform_int_distribution.h (limited to 'third_party/abseil_cpp/absl/random/log_uniform_int_distribution.h') diff --git a/third_party/abseil_cpp/absl/random/log_uniform_int_distribution.h b/third_party/abseil_cpp/absl/random/log_uniform_int_distribution.h deleted file mode 100644 index 960816e2f8ff..000000000000 --- a/third_party/abseil_cpp/absl/random/log_uniform_int_distribution.h +++ /dev/null @@ -1,254 +0,0 @@ -// Copyright 2017 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#ifndef ABSL_RANDOM_LOG_UNIFORM_INT_DISTRIBUTION_H_ -#define ABSL_RANDOM_LOG_UNIFORM_INT_DISTRIBUTION_H_ - -#include -#include -#include -#include -#include -#include -#include - -#include "absl/random/internal/fastmath.h" -#include "absl/random/internal/generate_real.h" -#include "absl/random/internal/iostream_state_saver.h" -#include "absl/random/internal/traits.h" -#include "absl/random/uniform_int_distribution.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN - -// log_uniform_int_distribution: -// -// Returns a random variate R in range [min, max] such that -// floor(log(R-min, base)) is uniformly distributed. -// We ensure uniformity by discretization using the -// boundary sets [0, 1, base, base * base, ... min(base*n, max)] -// -template -class log_uniform_int_distribution { - private: - using unsigned_type = - typename random_internal::make_unsigned_bits::type; - - public: - using result_type = IntType; - - class param_type { - public: - using distribution_type = log_uniform_int_distribution; - - explicit param_type( - result_type min = 0, - result_type max = (std::numeric_limits::max)(), - result_type base = 2) - : min_(min), - max_(max), - base_(base), - range_(static_cast(max_) - - static_cast(min_)), - log_range_(0) { - assert(max_ >= min_); - assert(base_ > 1); - - if (base_ == 2) { - // Determine where the first set bit is on range(), giving a log2(range) - // value which can be used to construct bounds. - log_range_ = (std::min)(random_internal::LeadingSetBit(range()), - std::numeric_limits::digits); - } else { - // NOTE: Computing the logN(x) introduces error from 2 sources: - // 1. Conversion of int to double loses precision for values >= - // 2^53, which may cause some log() computations to operate on - // different values. - // 2. The error introduced by the division will cause the result - // to differ from the expected value. - // - // Thus a result which should equal K may equal K +/- epsilon, - // which can eliminate some values depending on where the bounds fall. - const double inv_log_base = 1.0 / std::log(base_); - const double log_range = std::log(static_cast(range()) + 0.5); - log_range_ = static_cast(std::ceil(inv_log_base * log_range)); - } - } - - result_type(min)() const { return min_; } - result_type(max)() const { return max_; } - result_type base() const { return base_; } - - friend bool operator==(const param_type& a, const param_type& b) { - return a.min_ == b.min_ && a.max_ == b.max_ && a.base_ == b.base_; - } - - friend bool operator!=(const param_type& a, const param_type& b) { - return !(a == b); - } - - private: - friend class log_uniform_int_distribution; - - int log_range() const { return log_range_; } - unsigned_type range() const { return range_; } - - result_type min_; - result_type max_; - result_type base_; - unsigned_type range_; // max - min - int log_range_; // ceil(logN(range_)) - - static_assert(std::is_integral::value, - "Class-template absl::log_uniform_int_distribution<> must be " - "parameterized using an integral type."); - }; - - log_uniform_int_distribution() : log_uniform_int_distribution(0) {} - - explicit log_uniform_int_distribution( - result_type min, - result_type max = (std::numeric_limits::max)(), - result_type base = 2) - : param_(min, max, base) {} - - explicit log_uniform_int_distribution(const param_type& p) : param_(p) {} - - void reset() {} - - // generating functions - template - result_type operator()(URBG& g) { // NOLINT(runtime/references) - return (*this)(g, param_); - } - - template - result_type operator()(URBG& g, // NOLINT(runtime/references) - const param_type& p) { - return (p.min)() + Generate(g, p); - } - - result_type(min)() const { return (param_.min)(); } - result_type(max)() const { return (param_.max)(); } - result_type base() const { return param_.base(); } - - param_type param() const { return param_; } - void param(const param_type& p) { param_ = p; } - - friend bool operator==(const log_uniform_int_distribution& a, - const log_uniform_int_distribution& b) { - return a.param_ == b.param_; - } - friend bool operator!=(const log_uniform_int_distribution& a, - const log_uniform_int_distribution& b) { - return a.param_ != b.param_; - } - - private: - // Returns a log-uniform variate in the range [0, p.range()]. The caller - // should add min() to shift the result to the correct range. - template - unsigned_type Generate(URNG& g, // NOLINT(runtime/references) - const param_type& p); - - param_type param_; -}; - -template -template -typename log_uniform_int_distribution::unsigned_type -log_uniform_int_distribution::Generate( - URBG& g, // NOLINT(runtime/references) - const param_type& p) { - // sample e over [0, log_range]. Map the results of e to this: - // 0 => 0 - // 1 => [1, b-1] - // 2 => [b, (b^2)-1] - // n => [b^(n-1)..(b^n)-1] - const int e = absl::uniform_int_distribution(0, p.log_range())(g); - if (e == 0) { - return 0; - } - const int d = e - 1; - - unsigned_type base_e, top_e; - if (p.base() == 2) { - base_e = static_cast(1) << d; - - top_e = (e >= std::numeric_limits::digits) - ? (std::numeric_limits::max)() - : (static_cast(1) << e) - 1; - } else { - const double r = std::pow(p.base(), d); - const double s = (r * p.base()) - 1.0; - - base_e = - (r > static_cast((std::numeric_limits::max)())) - ? (std::numeric_limits::max)() - : static_cast(r); - - top_e = - (s > static_cast((std::numeric_limits::max)())) - ? (std::numeric_limits::max)() - : static_cast(s); - } - - const unsigned_type lo = (base_e >= p.range()) ? p.range() : base_e; - const unsigned_type hi = (top_e >= p.range()) ? p.range() : top_e; - - // choose uniformly over [lo, hi] - return absl::uniform_int_distribution(lo, hi)(g); -} - -template -std::basic_ostream& operator<<( - std::basic_ostream& os, // NOLINT(runtime/references) - const log_uniform_int_distribution& x) { - using stream_type = - typename random_internal::stream_format_type::type; - auto saver = random_internal::make_ostream_state_saver(os); - os << static_cast((x.min)()) << os.fill() - << static_cast((x.max)()) << os.fill() - << static_cast(x.base()); - return os; -} - -template -std::basic_istream& operator>>( - std::basic_istream& is, // NOLINT(runtime/references) - log_uniform_int_distribution& x) { // NOLINT(runtime/references) - using param_type = typename log_uniform_int_distribution::param_type; - using result_type = - typename log_uniform_int_distribution::result_type; - using stream_type = - typename random_internal::stream_format_type::type; - - stream_type min; - stream_type max; - stream_type base; - - auto saver = random_internal::make_istream_state_saver(is); - is >> min >> max >> base; - if (!is.fail()) { - x.param(param_type(static_cast(min), - static_cast(max), - static_cast(base))); - } - return is; -} - -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_RANDOM_LOG_UNIFORM_INT_DISTRIBUTION_H_ -- cgit 1.4.1