absl/container/btree_test.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_CONTAINER_BTREE_TEST_H_
0016 #define ABSL_CONTAINER_BTREE_TEST_H_
0017
0018 #include <algorithm>
0019 #include <cassert>
0020 #include <random>
0021 #include <string>
0022 #include <utility>
0023 #include <vector>
0024
0025 #include "absl/container/btree_map.h"
0026 #include "absl/container/btree_set.h"
0027 #include "absl/container/flat_hash_set.h"
0028 #include "absl/strings/cord.h"
0029 #include "absl/time/time.h"
0030
0031 namespace absl {
0032 ABSL_NAMESPACE_BEGIN
0033 namespace container_internal {
0034
0035 // Like remove_const but propagates the removal through std::pair.
0036 template <typename T>
0037 struct remove_pair_const {
0038   using type = typename std::remove_const<T>::type;
0039 };
0040 template <typename T, typename U>
0041 struct remove_pair_const<std::pair<T, U> > {
0042   using type = std::pair<typename remove_pair_const<T>::type,
0043                          typename remove_pair_const<U>::type>;
0044 };
0045
0046 // Utility class to provide an accessor for a key given a value. The default
0047 // behavior is to treat the value as a pair and return the first element.
0048 template <typename K, typename V>
0049 struct KeyOfValue {
0050   struct type {
0051     const K& operator()(const V& p) const { return p.first; }
0052   };
0053 };
0054
0055 // Partial specialization of KeyOfValue class for when the key and value are
0056 // the same type such as in set<> and btree_set<>.
0057 template <typename K>
0058 struct KeyOfValue<K, K> {
0059   struct type {
0060     const K& operator()(const K& k) const { return k; }
0061   };
0062 };
0063
0064 inline char* GenerateDigits(char buf[16], unsigned val, unsigned maxval) {
0065   assert(val <= maxval);
0066   constexpr unsigned kBase = 64;  // avoid integer division.
0067   unsigned p = 15;
0068   buf[p--] = 0;
0069   while (maxval > 0) {
0070     buf[p--] = ' ' + (val % kBase);
0071     val /= kBase;
0072     maxval /= kBase;
0073   }
0074   return buf + p + 1;
0075 }
0076
0077 template <typename K>
0078 struct Generator {
0079   int maxval;
0080   explicit Generator(int m) : maxval(m) {}
0081   K operator()(int i) const {
0082     assert(i <= maxval);
0083     return K(i);
0084   }
0085 };
0086
0087 template <>
0088 struct Generator<absl::Time> {
0089   int maxval;
0090   explicit Generator(int m) : maxval(m) {}
0091   absl::Time operator()(int i) const { return absl::FromUnixMillis(i); }
0092 };
0093
0094 template <>
0095 struct Generator<std::string> {
0096   int maxval;
0097   explicit Generator(int m) : maxval(m) {}
0098   std::string operator()(int i) const {
0099     char buf[16];
0100     return GenerateDigits(buf, i, maxval);
0101   }
0102 };
0103
0104 template <>
0105 struct Generator<Cord> {
0106   int maxval;
0107   explicit Generator(int m) : maxval(m) {}
0108   Cord operator()(int i) const {
0109     char buf[16];
0110     return Cord(GenerateDigits(buf, i, maxval));
0111   }
0112 };
0113
0114 template <typename T, typename U>
0115 struct Generator<std::pair<T, U> > {
0116   Generator<typename remove_pair_const<T>::type> tgen;
0117   Generator<typename remove_pair_const<U>::type> ugen;
0118
0119   explicit Generator(int m) : tgen(m), ugen(m) {}
0120   std::pair<T, U> operator()(int i) const {
0121     return std::make_pair(tgen(i), ugen(i));
0122   }
0123 };
0124
0125 // Generate n values for our tests and benchmarks. Value range is [0, maxval].
0126 inline std::vector<int> GenerateNumbersWithSeed(int n, int maxval, int seed) {
0127   // NOTE: Some tests rely on generated numbers not changing between test runs.
0128   // We use std::minstd_rand0 because it is well-defined, but don't use
0129   // std::uniform_int_distribution because platforms use different algorithms.
0130   std::minstd_rand0 rng(seed);
0131
0132   std::vector<int> values;
0133   absl::flat_hash_set<int> unique_values;
0134   if (values.size() < n) {
0135     for (int i = values.size(); i < n; i++) {
0136       int value;
0137       do {
0138         value = static_cast<int>(rng()) % (maxval + 1);
0139       } while (!unique_values.insert(value).second);
0140
0141       values.push_back(value);
0142     }
0143   }
0144   return values;
0145 }
0146
0147 // Generates n values in the range [0, maxval].
0148 template <typename V>
0149 std::vector<V> GenerateValuesWithSeed(int n, int maxval, int seed) {
0150   const std::vector<int> nums = GenerateNumbersWithSeed(n, maxval, seed);
0151   Generator<V> gen(maxval);
0152   std::vector<V> vec;
0153
0154   vec.reserve(n);
0155   for (int i = 0; i < n; i++) {
0156     vec.push_back(gen(nums[i]));
0157   }
0158
0159   return vec;
0160 }
0161
0162 }  // namespace container_internal
0163 ABSL_NAMESPACE_END
0164 }  // namespace absl
0165
0166 #endif  // ABSL_CONTAINER_BTREE_TEST_H_