Debian Codegraph @

tests/btree_test.h

raw
1 // ---------------------------------------------------------------------------
2 // Copyright (c) 2019, Gregory Popovitch - [email protected]
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // https://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16 // Includes work from abseil-cpp (https://github.com/abseil/abseil-cpp)
17 // with modifications.
18 //
19 // Copyright 2018 The Abseil Authors.
20 //
21 // Licensed under the Apache License, Version 2.0 (the "License");
22 // you may not use this file except in compliance with the License.
23 // You may obtain a copy of the License at
24 //
25 // https://www.apache.org/licenses/LICENSE-2.0
26 //
27 // Unless required by applicable law or agreed to in writing, software
28 // distributed under the License is distributed on an "AS IS" BASIS,
29 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
30 // See the License for the specific language governing permissions and
31 // limitations under the License.
32 // ---------------------------------------------------------------------------
33
34 #ifndef PHMAP_CONTAINER_BTREE_TEST_H_
35 #define PHMAP_CONTAINER_BTREE_TEST_H_
36
37 #include <algorithm>
38 #include <cassert>
39 #include <random>
40 #include <string>
41 #include <utility>
42 #include <vector>
43 #include <cstdint>
44 #include <map>
45 #include <memory>
46 #include <stdexcept>
47 #include <string>
48 #include <type_traits>
49 #include <utility>
50 #include <cstdlib>
51 #include <ostream>
52
53 #include "gmock/gmock.h"
54 #include "gtest/gtest.h"
55
56 #include "parallel_hashmap/btree.h"
57 #include "parallel_hashmap/phmap.h"
58
59 namespace phmap {
60
61 namespace test_internal {
62
63 // A type that counts number of occurrences of the type, the live occurrences of
64 // the type, as well as the number of copies, moves, swaps, and comparisons that
65 // have occurred on the type. This is used as a base class for the copyable,
66 // copyable+movable, and movable types below that are used in actual tests. Use
67 // InstanceTracker in tests to track the number of instances.
68 class BaseCountedInstance {
69 public:
70 explicit BaseCountedInstance(size_t x) : value_(x) {
71 ++num_instances_;
72 ++num_live_instances_;
73 }
74 BaseCountedInstance(const BaseCountedInstance& x)
75 : value_(x.value_), is_live_(x.is_live_) {
76 ++num_instances_;
77 if (is_live_) ++num_live_instances_;
78 ++num_copies_;
79 }
80 BaseCountedInstance(BaseCountedInstance&& x)
81 : value_(x.value_), is_live_(x.is_live_) {
82 x.is_live_ = false;
83 ++num_instances_;
84 ++num_moves_;
85 }
86 ~BaseCountedInstance() {
87 --num_instances_;
88 if (is_live_) --num_live_instances_;
89 }
90
91 BaseCountedInstance& operator=(const BaseCountedInstance& x) {
92 value_ = x.value_;
93 if (is_live_) --num_live_instances_;
94 is_live_ = x.is_live_;
95 if (is_live_) ++num_live_instances_;
96 ++num_copies_;
97 return *this;
98 }
99 BaseCountedInstance& operator=(BaseCountedInstance&& x) {
100 value_ = x.value_;
101 if (is_live_) --num_live_instances_;
102 is_live_ = x.is_live_;
103 x.is_live_ = false;
104 ++num_moves_;
105 return *this;
106 }
107
108 bool operator==(const BaseCountedInstance& x) const {
109 ++num_comparisons_;
110 return value_ == x.value_;
111 }
112
113 bool operator!=(const BaseCountedInstance& x) const {
114 ++num_comparisons_;
115 return value_ != x.value_;
116 }
117
118 bool operator<(const BaseCountedInstance& x) const {
119 ++num_comparisons_;
120 return value_ < x.value_;
121 }
122
123 bool operator>(const BaseCountedInstance& x) const {
124 ++num_comparisons_;
125 return value_ > x.value_;
126 }
127
128 bool operator<=(const BaseCountedInstance& x) const {
129 ++num_comparisons_;
130 return value_ <= x.value_;
131 }
132
133 bool operator>=(const BaseCountedInstance& x) const {
134 ++num_comparisons_;
135 return value_ >= x.value_;
136 }
137
138 phmap::weak_ordering compare(const BaseCountedInstance& x) const {
139 ++num_comparisons_;
140 return value_ < x.value_
141 ? phmap::weak_ordering::less
142 : value_ == x.value_ ? phmap::weak_ordering::equivalent
143 : phmap::weak_ordering::greater;
144 }
145
146 size_t value() const {
147 if (!is_live_) std::abort();
148 return value_;
149 }
150
151 friend std::ostream& operator<<(std::ostream& o,
152 const BaseCountedInstance& v) {
153 return o << "[value:" << v.value() << "]";
154 }
155
156 // Implementation of efficient swap() that counts swaps.
157 static void SwapImpl(
158 BaseCountedInstance& lhs, // NOLINT(runtime/references)
159 BaseCountedInstance& rhs) { // NOLINT(runtime/references)
160 using std::swap;
161 swap(lhs.value_, rhs.value_);
162 swap(lhs.is_live_, rhs.is_live_);
163 ++BaseCountedInstance::num_swaps_;
164 }
165
166 private:
167 friend class InstanceTracker;
168
169 size_t value_;
170
171 // Indicates if the value is live, ie it hasn't been moved away from.
172 bool is_live_ = true;
173
174 // Number of instances.
175 static size_t num_instances_;
176
177 // Number of live instances (those that have not been moved away from.)
178 static size_t num_live_instances_;
179
180 // Number of times that BaseCountedInstance objects were moved.
181 static size_t num_moves_;
182
183 // Number of times that BaseCountedInstance objects were copied.
184 static size_t num_copies_;
185
186 // Number of times that BaseCountedInstance objects were swapped.
187 static size_t num_swaps_;
188
189 // Number of times that BaseCountedInstance objects were compared.
190 static size_t num_comparisons_;
191 };
192
193 // Helper to track the BaseCountedInstance instance counters. Expects that the
194 // number of instances and live_instances are the same when it is constructed
195 // and when it is destructed.
196 class InstanceTracker {
197 public:
198 InstanceTracker()
199 : start_instances_(BaseCountedInstance::num_instances_),
200 start_live_instances_(BaseCountedInstance::num_live_instances_) {
201 ResetCopiesMovesSwaps();
202 }
203 ~InstanceTracker() {
204 if (instances() != 0) std::abort();
205 if (live_instances() != 0) std::abort();
206 }
207
208 // Returns the number of BaseCountedInstance instances both containing valid
209 // values and those moved away from compared to when the InstanceTracker was
210 // constructed
211 size_t instances() const {
212 return BaseCountedInstance::num_instances_ - start_instances_;
213 }
214
215 // Returns the number of live BaseCountedInstance instances compared to when
216 // the InstanceTracker was constructed
217 size_t live_instances() const {
218 return BaseCountedInstance::num_live_instances_ - start_live_instances_;
219 }
220
221 // Returns the number of moves on BaseCountedInstance objects since
222 // construction or since the last call to ResetCopiesMovesSwaps().
223 size_t moves() const { return BaseCountedInstance::num_moves_ - start_moves_; }
224
225 // Returns the number of copies on BaseCountedInstance objects since
226 // construction or the last call to ResetCopiesMovesSwaps().
227 size_t copies() const {
228 return BaseCountedInstance::num_copies_ - start_copies_;
229 }
230
231 // Returns the number of swaps on BaseCountedInstance objects since
232 // construction or the last call to ResetCopiesMovesSwaps().
233 size_t swaps() const { return BaseCountedInstance::num_swaps_ - start_swaps_; }
234
235 // Returns the number of comparisons on BaseCountedInstance objects since
236 // construction or the last call to ResetCopiesMovesSwaps().
237 size_t comparisons() const {
238 return BaseCountedInstance::num_comparisons_ - start_comparisons_;
239 }
240
241 // Resets the base values for moves, copies, comparisons, and swaps to the
242 // current values, so that subsequent Get*() calls for moves, copies,
243 // comparisons, and swaps will compare to the situation at the point of this
244 // call.
245 void ResetCopiesMovesSwaps() {
246 start_moves_ = BaseCountedInstance::num_moves_;
247 start_copies_ = BaseCountedInstance::num_copies_;
248 start_swaps_ = BaseCountedInstance::num_swaps_;
249 start_comparisons_ = BaseCountedInstance::num_comparisons_;
250 }
251
252 private:
253 size_t start_instances_;
254 size_t start_live_instances_;
255 size_t start_moves_;
256 size_t start_copies_;
257 size_t start_swaps_;
258 size_t start_comparisons_;
259 };
260
261 // Copyable, not movable.
262 class CopyableOnlyInstance : public BaseCountedInstance {
263 public:
264 explicit CopyableOnlyInstance(size_t x) : BaseCountedInstance(x) {}
265 CopyableOnlyInstance(const CopyableOnlyInstance& rhs) = default;
266 CopyableOnlyInstance& operator=(const CopyableOnlyInstance& rhs) = default;
267
268 friend void swap(CopyableOnlyInstance& lhs, CopyableOnlyInstance& rhs) {
269 BaseCountedInstance::SwapImpl(lhs, rhs);
270 }
271
272 static bool supports_move() { return false; }
273 };
274
275 // Copyable and movable.
276 class CopyableMovableInstance : public BaseCountedInstance {
277 public:
278 explicit CopyableMovableInstance(size_t x) : BaseCountedInstance(x) {}
279 CopyableMovableInstance(const CopyableMovableInstance& rhs) = default;
280 CopyableMovableInstance(CopyableMovableInstance&& rhs) = default;
281 CopyableMovableInstance& operator=(const CopyableMovableInstance& rhs) =
282 default;
283 CopyableMovableInstance& operator=(CopyableMovableInstance&& rhs) = default;
284
285 friend void swap(CopyableMovableInstance& lhs, CopyableMovableInstance& rhs) {
286 BaseCountedInstance::SwapImpl(lhs, rhs);
287 }
288
289 static bool supports_move() { return true; }
290 };
291
292 // Only movable, not default-constructible.
293 class MovableOnlyInstance : public BaseCountedInstance {
294 public:
295 explicit MovableOnlyInstance(size_t x) : BaseCountedInstance(x) {}
296 MovableOnlyInstance(MovableOnlyInstance&& other) = default;
297 MovableOnlyInstance& operator=(MovableOnlyInstance&& other) = default;
298
299 friend void swap(MovableOnlyInstance& lhs, MovableOnlyInstance& rhs) {
300 BaseCountedInstance::SwapImpl(lhs, rhs);
301 }
302
303 static bool supports_move() { return true; }
304 };
305
306 } // namespace test_internal
307
308
309 namespace priv {
310
311 // Like remove_const but propagates the removal through std::pair.
312 template <typename T>
313 struct remove_pair_const {
314 using type = typename std::remove_const<T>::type;
315 };
316 template <typename T, typename U>
317 struct remove_pair_const<std::pair<T, U> > {
318 using type = std::pair<typename remove_pair_const<T>::type,
319 typename remove_pair_const<U>::type>;
320 };
321
322 // Utility class to provide an accessor for a key given a value. The default
323 // behavior is to treat the value as a pair and return the first element.
324 template <typename K, typename V>
325 struct KeyOfValue {
326 struct type {
327 const K& operator()(const V& p) const { return p.first; }
328 };
329 };
330
331 // Partial specialization of KeyOfValue class for when the key and value are
332 // the same type such as in set<> and btree_set<>.
333 template <typename K>
334 struct KeyOfValue<K, K> {
335 struct type {
336 const K& operator()(const K& k) const { return k; }
337 };
338 };
339
340 inline char* GenerateDigits(char buf[16], unsigned val, unsigned maxval) {
341 assert(val <= maxval);
342 constexpr unsigned kBase = 64; // avoid integer division.
343 unsigned p = 15;
344 buf[p--] = 0;
345 while (maxval > 0) {
346 buf[p--] = ' ' + (val % kBase);
347 val /= kBase;
348 maxval /= kBase;
349 }
350 return buf + p + 1;
351 }
352
353 template <typename K>
354 struct Generator {
355 int maxval;
356 explicit Generator(int m) : maxval(m) {}
357 K operator()(int i) const {
358 assert(i <= maxval);
359 return K(i);
360 }
361 };
362
363 #if 0
364 template <>
365 struct Generator<phmap::Time> {
366 int maxval;
367 explicit Generator(int m) : maxval(m) {}
368 phmap::Time operator()(int i) const { return phmap::FromUnixMillis(i); }
369 };
370 #endif
371
372 template <>
373 struct Generator<std::string> {
374 int maxval;
375 explicit Generator(int m) : maxval(m) {}
376 std::string operator()(int i) const {
377 char buf[16];
378 return GenerateDigits(buf, i, maxval);
379 }
380 };
381
382 template <typename T, typename U>
383 struct Generator<std::pair<T, U> > {
384 Generator<typename remove_pair_const<T>::type> tgen;
385 Generator<typename remove_pair_const<U>::type> ugen;
386
387 explicit Generator(int m) : tgen(m), ugen(m) {}
388 std::pair<T, U> operator()(int i) const {
389 return std::make_pair(tgen(i), ugen(i));
390 }
391 };
392
393 // Generate n values for our tests and benchmarks. Value range is [0, maxval].
394 inline std::vector<int> GenerateNumbersWithSeed(size_t n, int maxval, int seed) {
395 // NOTE: Some tests rely on generated numbers not changing between test runs.
396 // We use std::minstd_rand0 because it is well-defined, but don't use
397 // std::uniform_int_distribution because platforms use different algorithms.
398 std::minstd_rand0 rng(seed);
399
400 std::vector<int> values;
401 phmap::flat_hash_set<int> unique_values;
402 if (values.size() < n) {
403 for (size_t i = values.size(); i < n; i++) {
404 int value;
405 do {
406 value = static_cast<int>(rng()) % (maxval + 1);
407 } while (!unique_values.insert(value).second);
408
409 values.push_back(value);
410 }
411 }
412 return values;
413 }
414
415 // Generates n values in the range [0, maxval].
416 template <typename V>
417 std::vector<V> GenerateValuesWithSeed(size_t n, int maxval, int seed) {
418 const std::vector<int> nums = GenerateNumbersWithSeed(n, maxval, seed);
419 Generator<V> gen(maxval);
420 std::vector<V> vec;
421
422 vec.reserve(n);
423 for (size_t i = 0; i < n; i++) {
424 vec.push_back(gen(nums[i]));
425 }
426
427 return vec;
428 }
429
430 } // namespace priv
431
432 namespace priv {
433
434 // This is a stateful allocator, but the state lives outside of the
435 // allocator (in whatever test is using the allocator). This is odd
436 // but helps in tests where the allocator is propagated into nested
437 // containers - that chain of allocators uses the same state and is
438 // thus easier to query for aggregate allocation information.
439 template <typename T>
440 class CountingAllocator : public std::allocator<T> {
441 public:
442 using Alloc = std::allocator<T>;
443 using AllocTraits = typename std::allocator_traits<Alloc>;
444 using pointer = typename AllocTraits::pointer;
445 using size_type = typename AllocTraits::size_type;
446
447 CountingAllocator() : bytes_used_(nullptr) {}
448 explicit CountingAllocator(int64_t* b) : bytes_used_(b) {}
449
450 template <typename U>
451 CountingAllocator(const CountingAllocator<U>& x)
452 : Alloc(x), bytes_used_(x.bytes_used_) {}
453
454 pointer allocate(size_type n,
455 std::allocator_traits<std::allocator<void>>::const_pointer hint = nullptr) {
456 assert(bytes_used_ != nullptr);
457 *bytes_used_ += n * sizeof(T);
458 return AllocTraits::allocate(*this, n, hint);
459 }
460
461 void deallocate(pointer p, size_type n) {
462 AllocTraits::deallocate(*this, p, n);
463 assert(bytes_used_ != nullptr);
464 *bytes_used_ -= n * sizeof(T);
465 }
466
467 template<typename U>
468 class rebind {
469 public:
470 using other = CountingAllocator<U>;
471 };
472
473 friend bool operator==(const CountingAllocator& a,
474 const CountingAllocator& b) {
475 return a.bytes_used_ == b.bytes_used_;
476 }
477
478 friend bool operator!=(const CountingAllocator& a,
479 const CountingAllocator& b) {
480 return !(a == b);
481 }
482
483 int64_t* bytes_used_;
484 };
485
486 } // namespace priv
487
488 } // namespace phmap
489
490 #endif // PHMAP_CONTAINER_BTREE_TEST_H_