1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #ifndef ABSL_CONTAINER_BTREE_TEST_H_
16 #define ABSL_CONTAINER_BTREE_TEST_H_
17 
18 #include <algorithm>
19 #include <cassert>
20 #include <random>
21 #include <string>
22 #include <utility>
23 #include <vector>
24 
25 #include "absl/container/btree_map.h"
26 #include "absl/container/btree_set.h"
27 #include "absl/container/flat_hash_set.h"
28 #include "absl/strings/cord.h"
29 #include "absl/time/time.h"
30 
31 namespace absl {
32 ABSL_NAMESPACE_BEGIN
33 namespace container_internal {
34 
35 // Like remove_const but propagates the removal through std::pair.
36 template <typename T>
37 struct remove_pair_const {
38   using type = typename std::remove_const<T>::type;
39 };
40 template <typename T, typename U>
41 struct remove_pair_const<std::pair<T, U> > {
42   using type = std::pair<typename remove_pair_const<T>::type,
43                          typename remove_pair_const<U>::type>;
44 };
45 
46 // Utility class to provide an accessor for a key given a value. The default
47 // behavior is to treat the value as a pair and return the first element.
48 template <typename K, typename V>
49 struct KeyOfValue {
50   struct type {
51     const K& operator()(const V& p) const { return p.first; }
52   };
53 };
54 
55 // Partial specialization of KeyOfValue class for when the key and value are
56 // the same type such as in set<> and btree_set<>.
57 template <typename K>
58 struct KeyOfValue<K, K> {
59   struct type {
60     const K& operator()(const K& k) const { return k; }
61   };
62 };
63 
64 inline char* GenerateDigits(char buf[16], unsigned val, unsigned maxval) {
65   assert(val <= maxval);
66   constexpr unsigned kBase = 64;  // avoid integer division.
67   unsigned p = 15;
68   buf[p--] = 0;
69   while (maxval > 0) {
70     buf[p--] = ' ' + (val % kBase);
71     val /= kBase;
72     maxval /= kBase;
73   }
74   return buf + p + 1;
75 }
76 
77 template <typename K>
78 struct Generator {
79   int maxval;
80   explicit Generator(int m) : maxval(m) {}
81   K operator()(int i) const {
82     assert(i <= maxval);
83     return K(i);
84   }
85 };
86 
87 template <>
88 struct Generator<absl::Time> {
89   int maxval;
90   explicit Generator(int m) : maxval(m) {}
91   absl::Time operator()(int i) const { return absl::FromUnixMillis(i); }
92 };
93 
94 template <>
95 struct Generator<std::string> {
96   int maxval;
97   explicit Generator(int m) : maxval(m) {}
98   std::string operator()(int i) const {
99     char buf[16];
100     return GenerateDigits(buf, i, maxval);
101   }
102 };
103 
104 template <>
105 struct Generator<Cord> {
106   int maxval;
107   explicit Generator(int m) : maxval(m) {}
108   Cord operator()(int i) const {
109     char buf[16];
110     return Cord(GenerateDigits(buf, i, maxval));
111   }
112 };
113 
114 template <typename T, typename U>
115 struct Generator<std::pair<T, U> > {
116   Generator<typename remove_pair_const<T>::type> tgen;
117   Generator<typename remove_pair_const<U>::type> ugen;
118 
119   explicit Generator(int m) : tgen(m), ugen(m) {}
120   std::pair<T, U> operator()(int i) const {
121     return std::make_pair(tgen(i), ugen(i));
122   }
123 };
124 
125 // Generate n values for our tests and benchmarks. Value range is [0, maxval].
126 inline std::vector<int> GenerateNumbersWithSeed(int n, int maxval, int seed) {
127   // NOTE: Some tests rely on generated numbers not changing between test runs.
128   // We use std::minstd_rand0 because it is well-defined, but don't use
129   // std::uniform_int_distribution because platforms use different algorithms.
130   std::minstd_rand0 rng(seed);
131 
132   std::vector<int> values;
133   absl::flat_hash_set<int> unique_values;
134   if (values.size() < n) {
135     for (int i = values.size(); i < n; i++) {
136       int value;
137       do {
138         value = static_cast<int>(rng()) % (maxval + 1);
139       } while (!unique_values.insert(value).second);
140 
141       values.push_back(value);
142     }
143   }
144   return values;
145 }
146 
147 // Generates n values in the range [0, maxval].
148 template <typename V>
149 std::vector<V> GenerateValuesWithSeed(int n, int maxval, int seed) {
150   const std::vector<int> nums = GenerateNumbersWithSeed(n, maxval, seed);
151   Generator<V> gen(maxval);
152   std::vector<V> vec;
153 
154   vec.reserve(n);
155   for (int i = 0; i < n; i++) {
156     vec.push_back(gen(nums[i]));
157   }
158 
159   return vec;
160 }
161 
162 }  // namespace container_internal
163 ABSL_NAMESPACE_END
164 }  // namespace absl
165 
166 #endif  // ABSL_CONTAINER_BTREE_TEST_H_
167