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 // <unordered_set>
10 
11 // template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
12 //           class Alloc = allocator<Value>>
13 // class unordered_set
14 
15 // void swap(unordered_set& u);
16 
17 #include <unordered_set>
18 #include <cassert>
19 #include <cstddef>
20 
21 #include "test_macros.h"
22 #include "../../test_compare.h"
23 #include "../../test_hash.h"
24 #include "test_allocator.h"
25 #include "min_allocator.h"
26 
27 int main(int, char**)
28 {
29     {
30         typedef test_hash<int> Hash;
31         typedef test_equal_to<int> Compare;
32         typedef test_allocator<int> Alloc;
33         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
34         C c1(0, Hash(1), Compare(1), Alloc(1, 1));
35         C c2(0, Hash(2), Compare(2), Alloc(1, 2));
36         c2.max_load_factor(2);
37         c1.swap(c2);
38 
39         LIBCPP_ASSERT(c1.bucket_count() == 0);
40         assert(c1.size() == 0);
41         assert(c1.hash_function() == Hash(2));
42         assert(c1.key_eq() == Compare(2));
43         assert(c1.get_allocator().get_id() == 1);
44         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
45         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
46         assert(c1.max_load_factor() == 2);
47 
48         LIBCPP_ASSERT(c2.bucket_count() == 0);
49         assert(c2.size() == 0);
50         assert(c2.hash_function() == Hash(1));
51         assert(c2.key_eq() == Compare(1));
52         assert(c2.get_allocator().get_id() == 2);
53         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
54         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
55         assert(c2.max_load_factor() == 1);
56     }
57     {
58         typedef test_hash<int> Hash;
59         typedef test_equal_to<int> Compare;
60         typedef test_allocator<int> Alloc;
61         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
62         typedef int P;
63         P a2[] =
64         {
65             P(10),
66             P(20),
67             P(30),
68             P(40),
69             P(50),
70             P(60),
71             P(70),
72             P(80)
73         };
74         C c1(0, Hash(1), Compare(1), Alloc(1, 1));
75         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
76         c2.max_load_factor(2);
77         c1.swap(c2);
78 
79         assert(c1.bucket_count() >= 8);
80         assert(c1.size() == 8);
81         assert(*c1.find(10) == 10);
exit_nicely(void)82         assert(*c1.find(20) == 20);
83         assert(*c1.find(30) == 30);
84         assert(*c1.find(40) == 40);
85         assert(*c1.find(50) == 50);
86         assert(*c1.find(60) == 60);
87         assert(*c1.find(70) == 70);
88         assert(*c1.find(80) == 80);
89         assert(c1.hash_function() == Hash(2));
90         assert(c1.key_eq() == Compare(2));
91         assert(c1.get_allocator().get_id() == 1);
92         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
main(int argc,char ** argv)93         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
94         assert(c1.max_load_factor() == 2);
95 
96         LIBCPP_ASSERT(c2.bucket_count() == 0);
97         assert(c2.size() == 0);
98         assert(c2.hash_function() == Hash(1));
99         assert(c2.key_eq() == Compare(1));
100         assert(c2.get_allocator().get_id() == 2);
101         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
102         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
103         assert(c2.max_load_factor() == 1);
104     }
105     {
106         typedef test_hash<int> Hash;
107         typedef test_equal_to<int> Compare;
108         typedef test_allocator<int> Alloc;
109         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
110         typedef int P;
111         P a1[] =
112         {
113             P(1),
114             P(2),
115             P(3),
116             P(4),
117             P(1),
118             P(2)
119         };
120         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
121         C c2(0, Hash(2), Compare(2), Alloc(1, 2));
122         c2.max_load_factor(2);
123         c1.swap(c2);
124 
125         LIBCPP_ASSERT(c1.bucket_count() == 0);
126         assert(c1.size() == 0);
127         assert(c1.hash_function() == Hash(2));
128         assert(c1.key_eq() == Compare(2));
129         assert(c1.get_allocator().get_id() == 1);
130         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
131         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
132         assert(c1.max_load_factor() == 2);
133 
134         assert(c2.bucket_count() >= 4);
135         assert(c2.size() == 4);
136         assert(c2.count(1) == 1);
137         assert(c2.count(2) == 1);
138         assert(c2.count(3) == 1);
139         assert(c2.count(4) == 1);
140         assert(c2.hash_function() == Hash(1));
141         assert(c2.key_eq() == Compare(1));
142         assert(c2.get_allocator().get_id() == 2);
143         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
144         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
145         assert(c2.max_load_factor() == 1);
146     }
147     {
148         typedef test_hash<int> Hash;
149         typedef test_equal_to<int> Compare;
150         typedef test_allocator<int> Alloc;
151         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
152         typedef int P;
153         P a1[] =
154         {
155             P(1),
156             P(2),
157             P(3),
158             P(4),
159             P(1),
160             P(2)
161         };
162         P a2[] =
163         {
164             P(10),
165             P(20),
166             P(30),
167             P(40),
168             P(50),
169             P(60),
170             P(70),
171             P(80)
172         };
173         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1, 1));
174         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(1, 2));
175         c2.max_load_factor(2);
176         c1.swap(c2);
177 
178         assert(c1.bucket_count() >= 8);
179         assert(c1.size() == 8);
180         assert(*c1.find(10) == 10);
181         assert(*c1.find(20) == 20);
182         assert(*c1.find(30) == 30);
183         assert(*c1.find(40) == 40);
184         assert(*c1.find(50) == 50);
185         assert(*c1.find(60) == 60);
186         assert(*c1.find(70) == 70);
187         assert(*c1.find(80) == 80);
188         assert(c1.hash_function() == Hash(2));
189         assert(c1.key_eq() == Compare(2));
190         assert(c1.get_allocator().get_id() == 1);
191         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
192         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
193         assert(c1.max_load_factor() == 2);
194 
195         assert(c2.bucket_count() >= 4);
196         assert(c2.size() == 4);
197         assert(c2.count(1) == 1);
198         assert(c2.count(2) == 1);
199         assert(c2.count(3) == 1);
200         assert(c2.count(4) == 1);
201         assert(c2.hash_function() == Hash(1));
202         assert(c2.key_eq() == Compare(1));
203         assert(c2.get_allocator().get_id() == 2);
204         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
205         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
206         assert(c2.max_load_factor() == 1);
207     }
208 
209     {
210         typedef test_hash<int> Hash;
211         typedef test_equal_to<int> Compare;
212         typedef other_allocator<int> Alloc;
213         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
214         C c1(0, Hash(1), Compare(1), Alloc(1));
215         C c2(0, Hash(2), Compare(2), Alloc(2));
216         c2.max_load_factor(2);
217         c1.swap(c2);
218 
219         LIBCPP_ASSERT(c1.bucket_count() == 0);
220         assert(c1.size() == 0);
221         assert(c1.hash_function() == Hash(2));
222         assert(c1.key_eq() == Compare(2));
223         assert(c1.get_allocator() == Alloc(2));
224         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
225         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
226         assert(c1.max_load_factor() == 2);
227 
228         LIBCPP_ASSERT(c2.bucket_count() == 0);
229         assert(c2.size() == 0);
230         assert(c2.hash_function() == Hash(1));
231         assert(c2.key_eq() == Compare(1));
232         assert(c2.get_allocator() == Alloc(1));
233         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
234         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
235         assert(c2.max_load_factor() == 1);
check_testspec(TestSpec * testspec)236     }
237     {
238         typedef test_hash<int> Hash;
239         typedef test_equal_to<int> Compare;
240         typedef other_allocator<int> Alloc;
241         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
242         typedef int P;
243         P a2[] =
244         {
245             P(10),
246             P(20),
247             P(30),
248             P(40),
249             P(50),
250             P(60),
251             P(70),
252             P(80)
253         };
254         C c1(0, Hash(1), Compare(1), Alloc(1));
255         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(2));
256         c2.max_load_factor(2);
257         c1.swap(c2);
258 
259         assert(c1.bucket_count() >= 8);
260         assert(c1.size() == 8);
261         assert(*c1.find(10) == 10);
262         assert(*c1.find(20) == 20);
263         assert(*c1.find(30) == 30);
264         assert(*c1.find(40) == 40);
265         assert(*c1.find(50) == 50);
266         assert(*c1.find(60) == 60);
267         assert(*c1.find(70) == 70);
268         assert(*c1.find(80) == 80);
269         assert(c1.hash_function() == Hash(2));
270         assert(c1.key_eq() == Compare(2));
271         assert(c1.get_allocator() == Alloc(2));
272         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
273         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
274         assert(c1.max_load_factor() == 2);
275 
276         LIBCPP_ASSERT(c2.bucket_count() == 0);
277         assert(c2.size() == 0);
278         assert(c2.hash_function() == Hash(1));
279         assert(c2.key_eq() == Compare(1));
280         assert(c2.get_allocator() == Alloc(1));
281         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
282         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
283         assert(c2.max_load_factor() == 1);
284     }
285     {
286         typedef test_hash<int> Hash;
287         typedef test_equal_to<int> Compare;
288         typedef other_allocator<int> Alloc;
289         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
290         typedef int P;
291         P a1[] =
292         {
293             P(1),
294             P(2),
295             P(3),
296             P(4),
297             P(1),
298             P(2)
299         };
300         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1));
301         C c2(0, Hash(2), Compare(2), Alloc(2));
302         c2.max_load_factor(2);
303         c1.swap(c2);
304 
305         LIBCPP_ASSERT(c1.bucket_count() == 0);
306         assert(c1.size() == 0);
307         assert(c1.hash_function() == Hash(2));
308         assert(c1.key_eq() == Compare(2));
309         assert(c1.get_allocator() == Alloc(2));
310         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
311         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
312         assert(c1.max_load_factor() == 2);
313 
314         assert(c2.bucket_count() >= 4);
315         assert(c2.size() == 4);
316         assert(c2.count(1) == 1);
317         assert(c2.count(2) == 1);
318         assert(c2.count(3) == 1);
319         assert(c2.count(4) == 1);
320         assert(c2.hash_function() == Hash(1));
321         assert(c2.key_eq() == Compare(1));
322         assert(c2.get_allocator() == Alloc(1));
323         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
324         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
325         assert(c2.max_load_factor() == 1);
326     }
327     {
328         typedef test_hash<int> Hash;
329         typedef test_equal_to<int> Compare;
330         typedef other_allocator<int> Alloc;
331         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
332         typedef int P;
333         P a1[] =
334         {
335             P(1),
336             P(2),
337             P(3),
338             P(4),
339             P(1),
340             P(2)
341         };
342         P a2[] =
343         {
344             P(10),
345             P(20),
346             P(30),
347             P(40),
348             P(50),
349             P(60),
350             P(70),
351             P(80)
352         };
353         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc(1));
354         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc(2));
355         c2.max_load_factor(2);
356         c1.swap(c2);
357 
358         assert(c1.bucket_count() >= 8);
359         assert(c1.size() == 8);
360         assert(*c1.find(10) == 10);
361         assert(*c1.find(20) == 20);
362         assert(*c1.find(30) == 30);
363         assert(*c1.find(40) == 40);
364         assert(*c1.find(50) == 50);
365         assert(*c1.find(60) == 60);
366         assert(*c1.find(70) == 70);
367         assert(*c1.find(80) == 80);
368         assert(c1.hash_function() == Hash(2));
369         assert(c1.key_eq() == Compare(2));
370         assert(c1.get_allocator() == Alloc(2));
371         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
372         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
373         assert(c1.max_load_factor() == 2);
374 
375         assert(c2.bucket_count() >= 4);
376         assert(c2.size() == 4);
377         assert(c2.count(1) == 1);
run_testspec(TestSpec * testspec)378         assert(c2.count(2) == 1);
379         assert(c2.count(3) == 1);
380         assert(c2.count(4) == 1);
381         assert(c2.hash_function() == Hash(1));
382         assert(c2.key_eq() == Compare(1));
383         assert(c2.get_allocator() == Alloc(1));
384         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
385         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
386         assert(c2.max_load_factor() == 1);
387     }
388 #if TEST_STD_VER >= 11
389     {
run_all_permutations(TestSpec * testspec)390         typedef test_hash<int> Hash;
391         typedef test_equal_to<int> Compare;
392         typedef min_allocator<int> Alloc;
393         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
394         C c1(0, Hash(1), Compare(1), Alloc());
395         C c2(0, Hash(2), Compare(2), Alloc());
396         c2.max_load_factor(2);
397         c1.swap(c2);
398 
399         LIBCPP_ASSERT(c1.bucket_count() == 0);
400         assert(c1.size() == 0);
401         assert(c1.hash_function() == Hash(2));
402         assert(c1.key_eq() == Compare(2));
403         assert(c1.get_allocator() == Alloc());
404         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
405         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
406         assert(c1.max_load_factor() == 2);
407 
408         LIBCPP_ASSERT(c2.bucket_count() == 0);
409         assert(c2.size() == 0);
410         assert(c2.hash_function() == Hash(1));
411         assert(c2.key_eq() == Compare(1));
412         assert(c2.get_allocator() == Alloc());
413         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
414         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
415         assert(c2.max_load_factor() == 1);
416     }
417     {
418         typedef test_hash<int> Hash;
419         typedef test_equal_to<int> Compare;
420         typedef min_allocator<int> Alloc;
421         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
422         typedef int P;
423         P a2[] =
424         {
425             P(10),
426             P(20),
427             P(30),
428             P(40),
429             P(50),
run_all_permutations_recurse(TestSpec * testspec,int * piles,int nsteps,PermutationStep ** steps)430             P(60),
431             P(70),
432             P(80)
433         };
434         C c1(0, Hash(1), Compare(1), Alloc());
435         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc());
436         c2.max_load_factor(2);
437         c1.swap(c2);
438 
439         assert(c1.bucket_count() >= 8);
440         assert(c1.size() == 8);
441         assert(*c1.find(10) == 10);
442         assert(*c1.find(20) == 20);
443         assert(*c1.find(30) == 30);
444         assert(*c1.find(40) == 40);
445         assert(*c1.find(50) == 50);
446         assert(*c1.find(60) == 60);
447         assert(*c1.find(70) == 70);
448         assert(*c1.find(80) == 80);
449         assert(c1.hash_function() == Hash(2));
450         assert(c1.key_eq() == Compare(2));
451         assert(c1.get_allocator() == Alloc());
452         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
453         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
454         assert(c1.max_load_factor() == 2);
455 
456         LIBCPP_ASSERT(c2.bucket_count() == 0);
457         assert(c2.size() == 0);
458         assert(c2.hash_function() == Hash(1));
459         assert(c2.key_eq() == Compare(1));
460         assert(c2.get_allocator() == Alloc());
461         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
462         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
463         assert(c2.max_load_factor() == 1);
464     }
465     {
466         typedef test_hash<int> Hash;
467         typedef test_equal_to<int> Compare;
468         typedef min_allocator<int> Alloc;
469         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
run_named_permutations(TestSpec * testspec)470         typedef int P;
471         P a1[] =
472         {
473             P(1),
474             P(2),
475             P(3),
476             P(4),
477             P(1),
478             P(2)
479         };
480         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc());
481         C c2(0, Hash(2), Compare(2), Alloc());
482         c2.max_load_factor(2);
step_qsort_cmp(const void * a,const void * b)483         c1.swap(c2);
484 
485         LIBCPP_ASSERT(c1.bucket_count() == 0);
486         assert(c1.size() == 0);
487         assert(c1.hash_function() == Hash(2));
488         assert(c1.key_eq() == Compare(2));
489         assert(c1.get_allocator() == Alloc());
490         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
491         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
step_bsearch_cmp(const void * a,const void * b)492         assert(c1.max_load_factor() == 2);
493 
494         assert(c2.bucket_count() >= 4);
495         assert(c2.size() == 4);
496         assert(c2.count(1) == 1);
497         assert(c2.count(2) == 1);
498         assert(c2.count(3) == 1);
499         assert(c2.count(4) == 1);
500         assert(c2.hash_function() == Hash(1));
501         assert(c2.key_eq() == Compare(1));
502         assert(c2.get_allocator() == Alloc());
503         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
run_permutation(TestSpec * testspec,int nsteps,PermutationStep ** steps)504         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
505         assert(c2.max_load_factor() == 1);
506     }
507     {
508         typedef test_hash<int> Hash;
509         typedef test_equal_to<int> Compare;
510         typedef min_allocator<int> Alloc;
511         typedef std::unordered_set<int, Hash, Compare, Alloc> C;
512         typedef int P;
513         P a1[] =
514         {
515             P(1),
516             P(2),
517             P(3),
518             P(4),
519             P(1),
520             P(2)
521         };
522         P a2[] =
523         {
524             P(10),
525             P(20),
526             P(30),
527             P(40),
528             P(50),
529             P(60),
530             P(70),
531             P(80)
532         };
533         C c1(std::begin(a1), std::end(a1), 0, Hash(1), Compare(1), Alloc());
534         C c2(std::begin(a2), std::end(a2), 0, Hash(2), Compare(2), Alloc());
535         c2.max_load_factor(2);
536         c1.swap(c2);
537 
538         assert(c1.bucket_count() >= 8);
539         assert(c1.size() == 8);
540         assert(*c1.find(10) == 10);
541         assert(*c1.find(20) == 20);
542         assert(*c1.find(30) == 30);
543         assert(*c1.find(40) == 40);
544         assert(*c1.find(50) == 50);
545         assert(*c1.find(60) == 60);
546         assert(*c1.find(70) == 70);
547         assert(*c1.find(80) == 80);
548         assert(c1.hash_function() == Hash(2));
549         assert(c1.key_eq() == Compare(2));
550         assert(c1.get_allocator() == Alloc());
551         assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
552         assert(static_cast<std::size_t>(std::distance(c1.cbegin(), c1.cend())) == c1.size());
553         assert(c1.max_load_factor() == 2);
554 
555         assert(c2.bucket_count() >= 4);
556         assert(c2.size() == 4);
557         assert(c2.count(1) == 1);
558         assert(c2.count(2) == 1);
559         assert(c2.count(3) == 1);
560         assert(c2.count(4) == 1);
561         assert(c2.hash_function() == Hash(1));
562         assert(c2.key_eq() == Compare(1));
563         assert(c2.get_allocator() == Alloc());
564         assert(static_cast<std::size_t>(std::distance(c2.begin(), c2.end())) == c2.size());
565         assert(static_cast<std::size_t>(std::distance(c2.cbegin(), c2.cend())) == c2.size());
566         assert(c2.max_load_factor() == 1);
567     }
568 #endif
569 
570   return 0;
571 }
572