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

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