1 | //===----------------------------------------------------------------------===// |
---|---|
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #ifndef SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H |
10 | #define SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H |
11 | |
12 | #include <algorithm> |
13 | #include <cassert> |
14 | #include <cmath> |
15 | #include <cstddef> |
16 | #include <limits> |
17 | #include <ranges> |
18 | #include <vector> |
19 | #include <utility> |
20 | |
21 | #include "../exception_safety_helpers.h" |
22 | #include "../from_range_helpers.h" |
23 | #include "../test_compare.h" |
24 | #include "../test_hash.h" |
25 | #include "MoveOnly.h" |
26 | #include "almost_satisfies_types.h" |
27 | #include "count_new.h" |
28 | #include "test_macros.h" |
29 | |
30 | // template<container-compatible-range<value_type> R> |
31 | // unordered-container(from_range_t, R&& rg, size_type n = see below, |
32 | // const hasher& hf = hasher(), const key_equal& eql = key_equal(), |
33 | // const allocator_type& a = allocator_type()); // C++23 |
34 | // |
35 | // template<container-compatible-range<value_type> R> |
36 | // unordered-container(from_range_t, R&& rg, size_type n, const allocator_type& a) |
37 | // : unordered-container(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 |
38 | // |
39 | // template<container-compatible-range<value_type> R> |
40 | // unordered-container(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) |
41 | // : unordered-container(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 |
42 | |
43 | template <class Container, class Range> |
44 | concept HasFromRangeCtr = requires(Range&& range) { |
45 | // (from_range, range) |
46 | Container(std::from_range, std::forward<Range>(range)); |
47 | // (from_range, range, n) |
48 | Container(std::from_range, std::forward<Range>(range), 0); |
49 | // (from_range, range, n, hash) |
50 | Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>()); |
51 | // (from_range, range, n, hash, equal) |
52 | Container(std::from_range, |
53 | std::forward<Range>(range), |
54 | 0, |
55 | std::hash<typename Container::key_type>(), |
56 | std::equal_to<typename Container::key_type>()); |
57 | // (from_range, range, n, hash, equal, alloc) |
58 | Container(std::from_range, |
59 | std::forward<Range>(range), |
60 | 0, |
61 | std::hash<typename Container::key_type>(), |
62 | std::equal_to<typename Container::key_type>(), |
63 | std::allocator<typename Container::value_type>()); |
64 | // (from_range, range, n, alloc) |
65 | Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>()); |
66 | // (from_range, range, n, hash, alloc) |
67 | Container(std::from_range, |
68 | std::forward<Range>(range), |
69 | 0, |
70 | std::hash<typename Container::key_type>(), |
71 | std::allocator<typename Container::value_type>()); |
72 | }; |
73 | |
74 | template <template <class...> class Container, class K, class V, class K2, class V2> |
75 | constexpr bool test_map_constraints() { |
76 | using ValueType = std::pair<const K, V>; |
77 | |
78 | // Input range with the same value type. |
79 | static_assert(HasFromRangeCtr<Container<K, V>, InputRange<ValueType>>); |
80 | // Input range with a convertible value type. |
81 | static_assert(HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K2, V2>>>); |
82 | // Input range with a non-convertible value type. |
83 | static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const Empty, V>>>); |
84 | static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K, Empty>>>); |
85 | // Not an input range. |
86 | static_assert(!HasFromRangeCtr<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>); |
87 | |
88 | return true; |
89 | } |
90 | |
91 | template <template <class...> class Container, |
92 | class K, |
93 | class V, |
94 | class Iter, |
95 | class Sent, |
96 | class Hash, |
97 | class Equal, |
98 | class Alloc, |
99 | class ValueType = std::pair<const K, V>> |
100 | void test_unordered_map_with_input(std::vector<ValueType>&& input) { |
101 | using DefaultHash = std::hash<int>; |
102 | using DefaultEqual = std::equal_to<int>; |
103 | |
104 | auto validate = [](auto&& c) { |
105 | if (!c.empty()) { |
106 | auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count()); |
107 | assert(std::fabs(diff) < std::numeric_limits<float>::epsilon()); |
108 | } |
109 | assert(c.max_load_factor() == 1); |
110 | }; |
111 | |
112 | { // (range) |
113 | auto in = wrap_input<Iter, Sent>(input); |
114 | Container<K, V> c(std::from_range, in); |
115 | |
116 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
117 | assert(std::ranges::is_permutation(input, c)); |
118 | validate(c); |
119 | } |
120 | |
121 | { // (range, n) |
122 | auto in = wrap_input<Iter, Sent>(input); |
123 | Container<K, V> c(std::from_range, in, 123); |
124 | |
125 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
126 | assert(std::ranges::is_permutation(input, c)); |
127 | validate(c); |
128 | } |
129 | |
130 | { // (range, n, hasher) |
131 | auto in = wrap_input<Iter, Sent>(input); |
132 | Container<K, V, Hash> c(std::from_range, in, 123, Hash()); |
133 | |
134 | assert(c.hash_function() == Hash()); |
135 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
136 | assert(std::ranges::is_permutation(input, c)); |
137 | validate(c); |
138 | } |
139 | |
140 | { // (range, n, hasher, key_equal) |
141 | auto in = wrap_input<Iter, Sent>(input); |
142 | Container<K, V, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal()); |
143 | |
144 | assert(c.hash_function() == Hash()); |
145 | assert(c.key_eq() == Equal()); |
146 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
147 | assert(std::ranges::is_permutation(input, c)); |
148 | validate(c); |
149 | } |
150 | |
151 | { // (range, n, hasher, key_equal, allocator) |
152 | auto in = wrap_input<Iter, Sent>(input); |
153 | Alloc alloc; |
154 | Container<K, V, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc); |
155 | |
156 | assert(c.hash_function() == Hash()); |
157 | assert(c.key_eq() == Equal()); |
158 | assert(c.get_allocator() == alloc); |
159 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
160 | assert(std::ranges::is_permutation(input, c)); |
161 | validate(c); |
162 | } |
163 | |
164 | { // (range, n, allocator) |
165 | auto in = wrap_input<Iter, Sent>(input); |
166 | Alloc alloc; |
167 | Container<K, V, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc); |
168 | |
169 | assert(c.get_allocator() == alloc); |
170 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
171 | assert(std::ranges::is_permutation(input, c)); |
172 | validate(c); |
173 | } |
174 | |
175 | { // (range, n, hasher, allocator) |
176 | auto in = wrap_input<Iter, Sent>(input); |
177 | Alloc alloc; |
178 | Container<K, V, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc); |
179 | |
180 | assert(c.hash_function() == Hash()); |
181 | assert(c.get_allocator() == alloc); |
182 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
183 | assert(std::ranges::is_permutation(input, c)); |
184 | validate(c); |
185 | } |
186 | } |
187 | |
188 | template <template <class...> class Container, |
189 | class K, |
190 | class V, |
191 | class Iter, |
192 | class Sent, |
193 | class Hash, |
194 | class Equal, |
195 | class Alloc> |
196 | void test_unordered_map() { |
197 | auto test_with_input = &test_unordered_map_with_input<Container, K, V, Iter, Sent, Hash, Equal, Alloc>; |
198 | |
199 | // Normal input. |
200 | test_with_input({{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}); |
201 | // Empty input. |
202 | test_with_input({}); |
203 | // Single-element input. |
204 | test_with_input({{1, 2}}); |
205 | } |
206 | |
207 | template <template <class...> class Container> |
208 | void test_unordered_map_move_only() { |
209 | std::pair<const int, MoveOnly> input[5]; |
210 | std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); |
211 | |
212 | [[maybe_unused]] Container<int, MoveOnly> c(std::from_range, in); |
213 | } |
214 | |
215 | template <template <class...> class Container> |
216 | void test_map_exception_safety_throwing_copy() { |
217 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
218 | using K = int; |
219 | using V = ThrowingCopy<3>; |
220 | |
221 | V::throwing_enabled = false; |
222 | std::pair<const K, V> in[5] = {{1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}}}; |
223 | V::throwing_enabled = true; |
224 | V::reset(); |
225 | |
226 | try { |
227 | Container<K, V> c(std::from_range, in); |
228 | assert(false); // The constructor call above should throw. |
229 | |
230 | } catch (int) { |
231 | assert(V::created_by_copying == 3); |
232 | assert(V::destroyed == 2); // No destructor call for the partially-constructed element. |
233 | } |
234 | #endif |
235 | } |
236 | |
237 | template <template <class...> class Container, class K, class V> |
238 | void test_map_exception_safety_throwing_allocator() { |
239 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
240 | using ValueType = std::pair<const K, V>; |
241 | ValueType in[] = {ValueType{K{1}, V{1}}}; |
242 | |
243 | try { |
244 | ThrowingAllocator<ValueType> alloc; |
245 | |
246 | globalMemCounter.reset(); |
247 | Container<K, V, test_hash<K>, test_equal_to<K>, ThrowingAllocator<ValueType>> c( |
248 | std::from_range, in, /*n=*/0, alloc); |
249 | assert(false); // The constructor call should throw. |
250 | |
251 | } catch (int) { |
252 | assert(globalMemCounter.new_called == globalMemCounter.delete_called); |
253 | } |
254 | #endif |
255 | } |
256 | |
257 | template <class Container, class Range> |
258 | concept SetHasFromRangeCtr = requires(Range&& range) { |
259 | // (from_range, range) |
260 | Container(std::from_range, std::forward<Range>(range)); |
261 | // (from_range, range, n) |
262 | Container(std::from_range, std::forward<Range>(range), 0); |
263 | // (from_range, range, n, hash) |
264 | Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>()); |
265 | // (from_range, range, n, hash, equal) |
266 | Container(std::from_range, |
267 | std::forward<Range>(range), |
268 | 0, |
269 | std::hash<typename Container::value_type>(), |
270 | std::equal_to<typename Container::value_type>()); |
271 | // (from_range, range, n, hash, equal, alloc) |
272 | Container(std::from_range, |
273 | std::forward<Range>(range), |
274 | 0, |
275 | std::hash<typename Container::value_type>(), |
276 | std::equal_to<typename Container::value_type>(), |
277 | std::allocator<typename Container::value_type>()); |
278 | // (from_range, range, n, alloc) |
279 | Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>()); |
280 | // (from_range, range, n, hash, alloc) |
281 | Container(std::from_range, |
282 | std::forward<Range>(range), |
283 | 0, |
284 | std::hash<typename Container::value_type>(), |
285 | std::allocator<typename Container::value_type>()); |
286 | }; |
287 | |
288 | template <template <class...> class Container, class T, class U> |
289 | constexpr bool test_set_constraints() { |
290 | // Input range with the same value type. |
291 | static_assert(HasFromRangeCtr<Container<T>, InputRange<T>>); |
292 | // Input range with a convertible value type. |
293 | static_assert(HasFromRangeCtr<Container<T>, InputRange<U>>); |
294 | // Input range with a non-convertible value type. |
295 | static_assert(!HasFromRangeCtr<Container<T>, InputRange<Empty>>); |
296 | // Not an input range. |
297 | static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotDerivedFromGeneric<T>>); |
298 | |
299 | return true; |
300 | } |
301 | |
302 | template <template <class...> class Container, class T, class Iter, class Sent, class Hash, class Equal, class Alloc> |
303 | void test_unordered_set_with_input(std::vector<T>&& input) { |
304 | using DefaultHash = std::hash<int>; |
305 | using DefaultEqual = std::equal_to<int>; |
306 | |
307 | auto validate = [](auto&& c) { |
308 | if (!c.empty()) { |
309 | auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count()); |
310 | assert(std::fabs(diff) < std::numeric_limits<float>::epsilon()); |
311 | } |
312 | assert(c.max_load_factor() == 1); |
313 | }; |
314 | |
315 | { // (range) |
316 | std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); |
317 | Container<T> c(std::from_range, in); |
318 | |
319 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
320 | assert(std::ranges::is_permutation(input, c)); |
321 | validate(c); |
322 | } |
323 | |
324 | { // (range, n) |
325 | std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); |
326 | Container<T> c(std::from_range, in, 123); |
327 | |
328 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
329 | assert(std::ranges::is_permutation(input, c)); |
330 | validate(c); |
331 | } |
332 | |
333 | { // (range, n, hasher) |
334 | std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); |
335 | Container<T, Hash> c(std::from_range, in, 123, Hash()); |
336 | |
337 | assert(c.hash_function() == Hash()); |
338 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
339 | assert(std::ranges::is_permutation(input, c)); |
340 | validate(c); |
341 | } |
342 | |
343 | { // (range, n, hasher, key_equal) |
344 | std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); |
345 | Container<T, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal()); |
346 | |
347 | assert(c.hash_function() == Hash()); |
348 | assert(c.key_eq() == Equal()); |
349 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
350 | assert(std::ranges::is_permutation(input, c)); |
351 | validate(c); |
352 | } |
353 | |
354 | { // (range, n, hasher, key_equal, allocator) |
355 | std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); |
356 | Alloc alloc; |
357 | Container<T, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc); |
358 | |
359 | assert(c.hash_function() == Hash()); |
360 | assert(c.key_eq() == Equal()); |
361 | assert(c.get_allocator() == alloc); |
362 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
363 | assert(std::ranges::is_permutation(input, c)); |
364 | validate(c); |
365 | } |
366 | |
367 | { // (range, n, allocator) |
368 | std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); |
369 | Alloc alloc; |
370 | Container<T, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc); |
371 | |
372 | assert(c.get_allocator() == alloc); |
373 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
374 | assert(std::ranges::is_permutation(input, c)); |
375 | validate(c); |
376 | } |
377 | |
378 | { // (range, n, hasher, allocator) |
379 | std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); |
380 | Alloc alloc; |
381 | Container<T, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc); |
382 | |
383 | assert(c.hash_function() == Hash()); |
384 | assert(c.get_allocator() == alloc); |
385 | assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); |
386 | assert(std::ranges::is_permutation(input, c)); |
387 | validate(c); |
388 | } |
389 | } |
390 | |
391 | template <template <class...> class Container, class T, class Iter, class Sent, class Hash, class Equal, class Alloc> |
392 | void test_unordered_set() { |
393 | auto test_with_input = &test_unordered_set_with_input<Container, T, Iter, Sent, Hash, Equal, Alloc>; |
394 | |
395 | // Normal input. |
396 | test_with_input({0, 5, 12, 7, -1, 8, 26}); |
397 | // Empty input. |
398 | test_with_input({}); |
399 | // Single-element input. |
400 | test_with_input({5}); |
401 | } |
402 | |
403 | template <template <class...> class Container> |
404 | void test_unordered_set_move_only() { |
405 | MoveOnly input[5]; |
406 | std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); |
407 | |
408 | [[maybe_unused]] Container<MoveOnly> c(std::from_range, in); |
409 | } |
410 | |
411 | template <template <class...> class Container> |
412 | void test_set_exception_safety_throwing_copy() { |
413 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
414 | using T = ThrowingCopy<3>; |
415 | T::reset(); |
416 | T in[5] = {{1}, {2}, {3}, {4}, {5}}; |
417 | |
418 | try { |
419 | Container<T, test_hash<T>> c(std::from_range, in); |
420 | assert(false); // The constructor call above should throw. |
421 | |
422 | } catch (int) { |
423 | assert(T::created_by_copying == 3); |
424 | assert(T::destroyed == 2); // No destructor call for the partially-constructed element. |
425 | } |
426 | #endif |
427 | } |
428 | |
429 | template <template <class...> class Container, class T> |
430 | void test_set_exception_safety_throwing_allocator() { |
431 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
432 | T in[] = {1, 2, 3}; |
433 | |
434 | try { |
435 | ThrowingAllocator<T> alloc; |
436 | |
437 | globalMemCounter.reset(); |
438 | Container<T, test_hash<T>, test_equal_to<T>, ThrowingAllocator<T>> c(std::from_range, in, /*n=*/0, alloc); |
439 | assert(false); // The constructor call should throw. |
440 | |
441 | } catch (int) { |
442 | assert(globalMemCounter.new_called == globalMemCounter.delete_called); |
443 | } |
444 | #endif |
445 | } |
446 | |
447 | #endif // SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H |
448 |
Definitions
- HasFromRangeCtr
- test_map_constraints
- test_unordered_map_with_input
- test_unordered_map
- test_unordered_map_move_only
- test_map_exception_safety_throwing_copy
- test_map_exception_safety_throwing_allocator
- SetHasFromRangeCtr
- test_set_constraints
- test_unordered_set_with_input
- test_unordered_set
- test_unordered_set_move_only
- test_set_exception_safety_throwing_copy
Improve your Profiling and Debugging skills
Find out more