1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
// 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 <algorithm>
#include <cassert>
#include <random>
#include <string>
#include <utility>
#include <vector>
#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 {
ABSL_NAMESPACE_BEGIN
namespace container_internal {
// Like remove_const but propagates the removal through std::pair.
template <typename T>
struct remove_pair_const {
using type = typename std::remove_const<T>::type;
};
template <typename T, typename U>
struct remove_pair_const<std::pair<T, U> > {
using type = std::pair<typename remove_pair_const<T>::type,
typename remove_pair_const<U>::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 <typename K, typename V>
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 <typename K>
struct KeyOfValue<K, K> {
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 <typename K>
struct Generator {
int maxval;
explicit Generator(int m) : maxval(m) {}
K operator()(int i) const {
assert(i <= maxval);
return K(i);
}
};
template <>
struct Generator<absl::Time> {
int maxval;
explicit Generator(int m) : maxval(m) {}
absl::Time operator()(int i) const { return absl::FromUnixMillis(i); }
};
template <>
struct Generator<std::string> {
int maxval;
explicit Generator(int m) : maxval(m) {}
std::string operator()(int i) const {
char buf[16];
return GenerateDigits(buf, i, maxval);
}
};
template <typename T, typename U>
struct Generator<std::pair<T, U> > {
Generator<typename remove_pair_const<T>::type> tgen;
Generator<typename remove_pair_const<U>::type> ugen;
explicit Generator(int m) : tgen(m), ugen(m) {}
std::pair<T, U> 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<int> 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<int> values;
absl::flat_hash_set<int> unique_values;
if (values.size() < n) {
for (int i = values.size(); i < n; i++) {
int value;
do {
value = static_cast<int>(rng()) % (maxval + 1);
} while (!unique_values.insert(value).second);
values.push_back(value);
}
}
return values;
}
// Generates n values in the range [0, maxval].
template <typename V>
std::vector<V> GenerateValuesWithSeed(int n, int maxval, int seed) {
const std::vector<int> nums = GenerateNumbersWithSeed(n, maxval, seed);
Generator<V> gen(maxval);
std::vector<V> vec;
vec.reserve(n);
for (int i = 0; i < n; i++) {
vec.push_back(gen(nums[i]));
}
return vec;
}
} // namespace container_internal
ABSL_NAMESPACE_END
} // namespace absl
#endif // ABSL_CONTAINER_BTREE_TEST_H_
|
