From 4ef574064e75b86f115549e9eb4c7e806781b3ab Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 9 Aug 2019 11:54:24 -0700 Subject: Export of internal Abseil changes -- 3dbb096e4662311f81df1017a8e0975e903936cf by Derek Mauro : Document and workaround a known MSVC bug doing constexpr pointer arithmetic PiperOrigin-RevId: 262604652 -- b5fa7f1a0c776f6ba20d52772a1679ec42ad21fd by Derek Mauro : Fix typo in macos_xcode_bazel.sh PiperOrigin-RevId: 262591285 -- 89dd77ab5bb44d76b6cb6b2f288e21536e16a85a by Derek Mauro : Internal change PiperOrigin-RevId: 262582747 -- 32295ed9a0c6c8ab143a912194040eede05d3ea3 by Abseil Team : Internal change PiperOrigin-RevId: 262569140 -- 7f0f5b94197369228024529022d727439d2c894f by Abseil Team : Internal change PiperOrigin-RevId: 262563554 -- 314aed043639abbd221074125c57b7c68616de7e by Derek Mauro : Release absl::btree PiperOrigin-RevId: 262553526 -- 72b44056c6ce9000c4a6cd9aec58b82067c82a13 by CJ Johnson : Internal change PiperOrigin-RevId: 262421185 -- 4e2c12151edf534f929e8e810f1334073f90489a by Abseil Team : Update documentation to make it less likely for users to write `Hours(24)` without considering using civil dates instead. PiperOrigin-RevId: 262420758 -- 92b85b9573e800bd96b019408eefbc5ce4f68780 by Derek Mauro : Add the ability to override the bazel version in the macos_xcode_bazel.sh test script. PiperOrigin-RevId: 262412063 GitOrigin-RevId: 3dbb096e4662311f81df1017a8e0975e903936cf Change-Id: I423b2b829dc0c5f814e37bec4d68c7470f43f041 --- absl/container/btree_test.h | 153 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+) create mode 100644 absl/container/btree_test.h (limited to 'absl/container/btree_test.h') diff --git a/absl/container/btree_test.h b/absl/container/btree_test.h new file mode 100644 index 0000000..5ecf43c --- /dev/null +++ b/absl/container/btree_test.h @@ -0,0 +1,153 @@ +// Copyright 2018 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_CONTAINER_BTREE_TEST_H_ +#define ABSL_CONTAINER_BTREE_TEST_H_ + +#include +#include +#include +#include +#include +#include + +#include "absl/container/btree_map.h" +#include "absl/container/btree_set.h" +#include "absl/container/flat_hash_set.h" +#include "absl/time/time.h" + +namespace absl { +namespace container_internal { + +// Like remove_const but propagates the removal through std::pair. +template +struct remove_pair_const { + using type = typename std::remove_const::type; +}; +template +struct remove_pair_const > { + using type = std::pair::type, + typename remove_pair_const::type>; +}; + +// Utility class to provide an accessor for a key given a value. The default +// behavior is to treat the value as a pair and return the first element. +template +struct KeyOfValue { + struct type { + const K& operator()(const V& p) const { return p.first; } + }; +}; + +// Partial specialization of KeyOfValue class for when the key and value are +// the same type such as in set<> and btree_set<>. +template +struct KeyOfValue { + struct type { + const K& operator()(const K& k) const { return k; } + }; +}; + +inline char* GenerateDigits(char buf[16], unsigned val, unsigned maxval) { + assert(val <= maxval); + constexpr unsigned kBase = 64; // avoid integer division. + unsigned p = 15; + buf[p--] = 0; + while (maxval > 0) { + buf[p--] = ' ' + (val % kBase); + val /= kBase; + maxval /= kBase; + } + return buf + p + 1; +} + +template +struct Generator { + int maxval; + explicit Generator(int m) : maxval(m) {} + K operator()(int i) const { + assert(i <= maxval); + return K(i); + } +}; + +template <> +struct Generator { + int maxval; + explicit Generator(int m) : maxval(m) {} + absl::Time operator()(int i) const { return absl::FromUnixMillis(i); } +}; + +template <> +struct Generator { + int maxval; + explicit Generator(int m) : maxval(m) {} + std::string operator()(int i) const { + char buf[16]; + return GenerateDigits(buf, i, maxval); + } +}; + +template +struct Generator > { + Generator::type> tgen; + Generator::type> ugen; + + explicit Generator(int m) : tgen(m), ugen(m) {} + std::pair operator()(int i) const { + return std::make_pair(tgen(i), ugen(i)); + } +}; + +// Generate n values for our tests and benchmarks. Value range is [0, maxval]. +inline std::vector GenerateNumbersWithSeed(int n, int maxval, int seed) { + // NOTE: Some tests rely on generated numbers not changing between test runs. + // We use std::minstd_rand0 because it is well-defined, but don't use + // std::uniform_int_distribution because platforms use different algorithms. + std::minstd_rand0 rng(seed); + + std::vector values; + absl::flat_hash_set unique_values; + if (values.size() < n) { + for (int i = values.size(); i < n; i++) { + int value; + do { + value = static_cast(rng()) % (maxval + 1); + } while (!unique_values.insert(value).second); + + values.push_back(value); + } + } + return values; +} + +// Generates n values in the range [0, maxval]. +template +std::vector GenerateValuesWithSeed(int n, int maxval, int seed) { + const std::vector nums = GenerateNumbersWithSeed(n, maxval, seed); + Generator gen(maxval); + std::vector vec; + + vec.reserve(n); + for (int i = 0; i < n; i++) { + vec.push_back(gen(nums[i])); + } + + return vec; +} + +} // namespace container_internal +} // namespace absl + +#endif // ABSL_CONTAINER_BTREE_TEST_H_ -- cgit v1.2.3