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
43template <class Container, class Range>
44concept 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
74template <template <class...> class Container, class K, class V, class K2, class V2>
75constexpr 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
91template <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>>
100void 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
188template <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>
196void 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
207template <template <class...> class Container>
208void 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
215template <template <class...> class Container>
216void 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
237template <template <class...> class Container, class K, class V>
238void 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
257template <class Container, class Range>
258concept 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
288template <template <class...> class Container, class T, class U>
289constexpr 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
302template <template <class...> class Container, class T, class Iter, class Sent, class Hash, class Equal, class Alloc>
303void 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
391template <template <class...> class Container, class T, class Iter, class Sent, class Hash, class Equal, class Alloc>
392void 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
403template <template <class...> class Container>
404void 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
411template <template <class...> class Container>
412void 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
429template <template <class...> class Container, class T>
430void 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

source code of libcxx/test/std/containers/unord/from_range_unordered_containers.h