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 #ifndef MAP_ALLOCATOR_REQUIREMENT_TEST_TEMPLATES_H
9 #define MAP_ALLOCATOR_REQUIREMENT_TEST_TEMPLATES_H
10 
11 // <map>
12 // <unordered_map>
13 
14 // class map
15 // class unordered_map
16 
17 // insert(...);
18 // emplace(...);
19 // emplace_hint(...);
20 
21 // UNSUPPORTED: c++03
22 
23 #include <cassert>
24 #include <iterator>
25 
26 #include "test_macros.h"
27 #include "count_new.h"
28 #include "container_test_types.h"
29 
30 
31 template <class Container>
32 void testMapInsert()
33 {
34   typedef typename Container::value_type ValueTp;
35   ConstructController* cc = getConstructController();
36   cc->reset();
37   {
38     // Testing C::insert(const value_type&)
39     Container c;
40     const ValueTp v(42, 1);
41     cc->expect<const ValueTp&>();
42     assert(c.insert(v).second);
43     assert(!cc->unchecked());
44     {
45       DisableAllocationGuard g;
46       const ValueTp v2(42, 1);
47       assert(c.insert(v2).second == false);
48     }
49   }
50   {
51     // Testing C::insert(value_type&)
52     Container c;
53     ValueTp v(42, 1);
54     cc->expect<const ValueTp&>();
55     assert(c.insert(v).second);
56     assert(!cc->unchecked());
57     {
58       DisableAllocationGuard g;
59       ValueTp v2(42, 1);
60       assert(c.insert(v2).second == false);
61     }
62   }
63   {
64     // Testing C::insert(value_type&&)
65     Container c;
66     ValueTp v(42, 1);
67     cc->expect<ValueTp&&>();
68     assert(c.insert(std::move(v)).second);
69     assert(!cc->unchecked());
70     {
71       DisableAllocationGuard g;
72       ValueTp v2(42, 1);
73       assert(c.insert(std::move(v2)).second == false);
74     }
75   }
76   {
77     // Testing C::insert(const value_type&&)
78     Container c;
79     const ValueTp v(42, 1);
80     cc->expect<const ValueTp&>();
81     assert(c.insert(std::move(v)).second);
82     assert(!cc->unchecked());
83     {
84       DisableAllocationGuard g;
85       const ValueTp v2(42, 1);
86       assert(c.insert(std::move(v2)).second == false);
87     }
88   }
89   {
90     // Testing C::insert({key, value})
91     Container c;
92     cc->expect<ValueTp&&>();
93     assert(c.insert({42, 1}).second);
94     assert(!cc->unchecked());
95     {
96       DisableAllocationGuard g;
97       const ValueTp v2(42, 1);
98       assert(c.insert(std::move(v2)).second == false);
99     }
100   }
101   {
102     // Testing C::insert(std::initializer_list<ValueTp>)
103     Container c;
104     std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
105     cc->expect<ValueTp const&>(2);
106     c.insert(il);
107     assert(!cc->unchecked());
108     {
109       DisableAllocationGuard g;
110       c.insert(il);
111     }
112   }
113   {
114     // Testing C::insert(Iter, Iter) for *Iter = value_type const&
115     Container c;
116     const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
117     cc->expect<ValueTp const&>(3);
118     c.insert(std::begin(ValueList), std::end(ValueList));
119     assert(!cc->unchecked());
120     {
121       DisableAllocationGuard g;
122       c.insert(std::begin(ValueList), std::end(ValueList));
123     }
124   }
125   {
126     // Testing C::insert(Iter, Iter) for *Iter = value_type&&
127     Container c;
128     ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
129     cc->expect<ValueTp&&>(3);
130     c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
131              std::move_iterator<ValueTp*>(std::end(ValueList)));
132     assert(!cc->unchecked());
133     {
134       DisableAllocationGuard g;
135       ValueTp ValueList2[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
136       c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
137                std::move_iterator<ValueTp*>(std::end(ValueList2)));
138     }
139   }
140   {
141     // Testing C::insert(Iter, Iter) for *Iter = value_type&
142     Container c;
143     ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
144     cc->expect<ValueTp const&>(3);
145     c.insert(std::begin(ValueList), std::end(ValueList));
146     assert(!cc->unchecked());
147     {
148       DisableAllocationGuard g;
149       c.insert(std::begin(ValueList), std::end(ValueList));
150     }
151   }
152 }
153 
154 
155 template <class Container>
156 void testMapInsertHint()
157 {
158   typedef typename Container::value_type ValueTp;
159   typedef typename Container::key_type Key;
160   typedef typename Container::mapped_type Mapped;
161   typedef typename std::pair<Key, Mapped> NonConstKeyPair;
162   typedef Container C;
163   typedef typename C::iterator It;
164   ConstructController* cc = getConstructController();
165   cc->reset();
166   {
167     // Testing C::insert(p, const value_type&)
168     Container c;
169     const ValueTp v(42, 1);
170     cc->expect<const ValueTp&>();
171     It ret = c.insert(c.end(), v);
172     assert(ret != c.end());
173     assert(c.size() == 1);
174     assert(!cc->unchecked());
175     {
176       DisableAllocationGuard g;
177       const ValueTp v2(42, 1);
178       It ret2 = c.insert(c.begin(), v2);
179       assert(&(*ret2) == &(*ret));
180       assert(c.size() == 1);
181     }
182   }
183   {
184     // Testing C::insert(p, value_type&)
185     Container c;
186     ValueTp v(42, 1);
187     cc->expect<ValueTp const&>();
188     It ret = c.insert(c.end(), v);
189     assert(ret != c.end());
190     assert(c.size() == 1);
191     assert(!cc->unchecked());
192     {
193       DisableAllocationGuard g;
194       ValueTp v2(42, 1);
195       It ret2 = c.insert(c.begin(), v2);
196       assert(&(*ret2) == &(*ret));
197       assert(c.size() == 1);
198     }
199   }
200   {
201     // Testing C::insert(p, value_type&&)
202     Container c;
203     ValueTp v(42, 1);
204     cc->expect<ValueTp&&>();
205     It ret = c.insert(c.end(), std::move(v));
206     assert(ret != c.end());
207     assert(c.size() == 1);
208     assert(!cc->unchecked());
209     {
210       DisableAllocationGuard g;
211       ValueTp v2(42, 1);
212       It ret2 = c.insert(c.begin(), std::move(v2));
213       assert(&(*ret2) == &(*ret));
214       assert(c.size() == 1);
215     }
216   }
217   {
218     // Testing C::insert(p, {key, value})
219     Container c;
220     cc->expect<ValueTp&&>();
221     It ret = c.insert(c.end(), {42, 1});
222     assert(ret != c.end());
223     assert(c.size() == 1);
224     assert(!cc->unchecked());
225     {
226       DisableAllocationGuard g;
227       It ret2 = c.insert(c.begin(), {42, 1});
228       assert(&(*ret2) == &(*ret));
229       assert(c.size() == 1);
230     }
231   }
232   {
233     // Testing C::insert(p, const value_type&&)
234     Container c;
235     const ValueTp v(42, 1);
236     cc->expect<const ValueTp&>();
237     It ret = c.insert(c.end(), std::move(v));
238     assert(ret != c.end());
239     assert(c.size() == 1);
240     assert(!cc->unchecked());
241     {
242       DisableAllocationGuard g;
243       const ValueTp v2(42, 1);
244       It ret2 = c.insert(c.begin(), std::move(v2));
245       assert(&(*ret2) == &(*ret));
246       assert(c.size() == 1);
247     }
248   }
249   {
250     // Testing C::insert(p, pair<Key, Mapped> const&)
251     Container c;
252     const NonConstKeyPair v(42, 1);
253     cc->expect<const NonConstKeyPair&>();
254     It ret = c.insert(c.end(), v);
255     assert(ret != c.end());
256     assert(c.size() == 1);
257     assert(!cc->unchecked());
258     {
259       DisableAllocationGuard g;
260       const NonConstKeyPair v2(42, 1);
261       It ret2 = c.insert(c.begin(), v2);
262       assert(&(*ret2) == &(*ret));
263       assert(c.size() == 1);
264     }
265   }
266   {
267     // Testing C::insert(p, pair<Key, Mapped>&&)
268     Container c;
269     NonConstKeyPair v(42, 1);
270     cc->expect<NonConstKeyPair&&>();
271     It ret = c.insert(c.end(), std::move(v));
272     assert(ret != c.end());
273     assert(c.size() == 1);
274     assert(!cc->unchecked());
275     {
276       DisableAllocationGuard g;
277       NonConstKeyPair v2(42, 1);
278       It ret2 = c.insert(c.begin(), std::move(v2));
279       assert(&(*ret2) == &(*ret));
280       assert(c.size() == 1);
281     }
282   }
283 
284 
285 }
286 
287 
288 template <class Container>
289 void testMapEmplace()
290 {
291   typedef typename Container::value_type ValueTp;
292   typedef typename Container::key_type Key;
293   typedef typename Container::mapped_type Mapped;
294   typedef typename std::pair<Key, Mapped> NonConstKeyPair;
295   ConstructController* cc = getConstructController();
296   cc->reset();
297   {
298     // Testing C::emplace(const value_type&)
299     Container c;
300     const ValueTp v(42, 1);
301     cc->expect<const ValueTp&>();
302     assert(c.emplace(v).second);
303     assert(!cc->unchecked());
304     {
305       DisableAllocationGuard g;
306       const ValueTp v2(42, 1);
307       assert(c.emplace(v2).second == false);
308     }
309   }
310   {
311     // Testing C::emplace(value_type&)
312     Container c;
313     ValueTp v(42, 1);
314     cc->expect<ValueTp&>();
315     assert(c.emplace(v).second);
316     assert(!cc->unchecked());
317     {
318       DisableAllocationGuard g;
319       ValueTp v2(42, 1);
320       assert(c.emplace(v2).second == false);
321     }
322   }
323   {
324     // Testing C::emplace(value_type&&)
325     Container c;
326     ValueTp v(42, 1);
327     cc->expect<ValueTp&&>();
328     assert(c.emplace(std::move(v)).second);
329     assert(!cc->unchecked());
330     {
331       DisableAllocationGuard g;
332       ValueTp v2(42, 1);
333       assert(c.emplace(std::move(v2)).second == false);
334     }
335   }
336   {
337     // Testing C::emplace(const value_type&&)
338     Container c;
339     const ValueTp v(42, 1);
340     cc->expect<const ValueTp&&>();
341     assert(c.emplace(std::move(v)).second);
342     assert(!cc->unchecked());
343     {
344       DisableAllocationGuard g;
345       const ValueTp v2(42, 1);
346       assert(c.emplace(std::move(v2)).second == false);
347     }
348   }
349   {
350     // Testing C::emplace(pair<Key, Mapped> const&)
351     Container c;
352     const NonConstKeyPair v(42, 1);
353     cc->expect<const NonConstKeyPair&>();
354     assert(c.emplace(v).second);
355     assert(!cc->unchecked());
356     {
357       DisableAllocationGuard g;
358       const NonConstKeyPair v2(42, 1);
359       assert(c.emplace(v2).second == false);
360     }
361   }
362   {
363     // Testing C::emplace(pair<Key, Mapped> &&)
364     Container c;
365     NonConstKeyPair v(42, 1);
366     cc->expect<NonConstKeyPair&&>();
367     assert(c.emplace(std::move(v)).second);
368     assert(!cc->unchecked());
369     {
370       DisableAllocationGuard g;
371       NonConstKeyPair v2(42, 1);
372       assert(c.emplace(std::move(v2)).second == false);
373     }
374   }
375   {
376     // Testing C::emplace(const Key&, ConvertibleToMapped&&)
377     Container c;
378     const Key k(42);
379     cc->expect<Key const&, int&&>();
380     assert(c.emplace(k, 1).second);
381     assert(!cc->unchecked());
382     {
383       DisableAllocationGuard g;
384       const Key k2(42);
385       assert(c.emplace(k2, 2).second == false);
386     }
387   }
388   {
389     // Testing C::emplace(Key&, Mapped&)
390     Container c;
391     Key k(42);
392     Mapped m(1);
393     cc->expect<Key&, Mapped&>();
394     assert(c.emplace(k, m).second);
395     assert(!cc->unchecked());
396     {
397       DisableAllocationGuard g;
398       Key k2(42);
399       assert(c.emplace(k2, m).second == false);
400     }
401   }
402   {
403     // Testing C::emplace(Key&&, Mapped&&)
404     Container c;
405     Key k(42);
406     Mapped m(1);
407     cc->expect<Key&&, Mapped&&>();
408     assert(c.emplace(std::move(k), std::move(m)).second);
409     assert(!cc->unchecked());
410     {
411       DisableAllocationGuard g;
412       Key k2(42);
413       Mapped m2(2);
414       assert(c.emplace(std::move(k2), std::move(m2)).second == false);
415     }
416   }
417   {
418     // Testing C::emplace(ConvertibleToKey&&, ConvertibleToMapped&&)
419     Container c;
420     cc->expect<int&&, int&&>();
421     assert(c.emplace(42, 1).second);
422     assert(!cc->unchecked());
423     {
424       // test that emplacing a duplicate item allocates. We cannot optimize
425       // this case because int&& does not match the type of key exactly.
426       cc->expect<int&&, int&&>();
427       assert(c.emplace(42, 1).second == false);
428       assert(!cc->unchecked());
429     }
430   }
431 }
432 
433 
434 template <class Container>
435 void testMapEmplaceHint()
436 {
437   typedef typename Container::value_type ValueTp;
438   typedef typename Container::key_type Key;
439   typedef typename Container::mapped_type Mapped;
440   typedef typename std::pair<Key, Mapped> NonConstKeyPair;
441   typedef Container C;
442   typedef typename C::iterator It;
443   ConstructController* cc = getConstructController();
444   cc->reset();
445   {
446     // Testing C::emplace_hint(p, const value_type&)
447     Container c;
448     const ValueTp v(42, 1);
449     cc->expect<const ValueTp&>();
450     It ret = c.emplace_hint(c.end(), v);
451     assert(ret != c.end());
452     assert(c.size() == 1);
453     assert(!cc->unchecked());
454     {
455       DisableAllocationGuard g;
456       const ValueTp v2(42, 1);
457       It ret2 = c.emplace_hint(c.begin(), v2);
458       assert(&(*ret2) == &(*ret));
459       assert(c.size() == 1);
460     }
461   }
462   {
463     // Testing C::emplace_hint(p, value_type&)
464     Container c;
465     ValueTp v(42, 1);
466     cc->expect<ValueTp&>();
467     It ret = c.emplace_hint(c.end(), v);
468     assert(ret != c.end());
469     assert(c.size() == 1);
470     assert(!cc->unchecked());
471     {
472       DisableAllocationGuard g;
473       ValueTp v2(42, 1);
474       It ret2 = c.emplace_hint(c.begin(), v2);
475       assert(&(*ret2) == &(*ret));
476       assert(c.size() == 1);
477     }
478   }
479   {
480     // Testing C::emplace_hint(p, value_type&&)
481     Container c;
482     ValueTp v(42, 1);
483     cc->expect<ValueTp&&>();
484     It ret = c.emplace_hint(c.end(), std::move(v));
485     assert(ret != c.end());
486     assert(c.size() == 1);
487     assert(!cc->unchecked());
488     {
489       DisableAllocationGuard g;
490       ValueTp v2(42, 1);
491       It ret2 = c.emplace_hint(c.begin(), std::move(v2));
492       assert(&(*ret2) == &(*ret));
493       assert(c.size() == 1);
494     }
495   }
496   {
497     // Testing C::emplace_hint(p, const value_type&&)
498     Container c;
499     const ValueTp v(42, 1);
500     cc->expect<const ValueTp&&>();
501     It ret = c.emplace_hint(c.end(), std::move(v));
502     assert(ret != c.end());
503     assert(c.size() == 1);
504     assert(!cc->unchecked());
505     {
506       DisableAllocationGuard g;
507       const ValueTp v2(42, 1);
508       It ret2 = c.emplace_hint(c.begin(), std::move(v2));
509       assert(&(*ret2) == &(*ret));
510       assert(c.size() == 1);
511     }
512   }
513   {
514     // Testing C::emplace_hint(p, pair<Key, Mapped> const&)
515     Container c;
516     const NonConstKeyPair v(42, 1);
517     cc->expect<const NonConstKeyPair&>();
518     It ret = c.emplace_hint(c.end(), v);
519     assert(ret != c.end());
520     assert(c.size() == 1);
521     assert(!cc->unchecked());
522     {
523       DisableAllocationGuard g;
524       const NonConstKeyPair v2(42, 1);
525       It ret2 = c.emplace_hint(c.begin(), v2);
526       assert(&(*ret2) == &(*ret));
527       assert(c.size() == 1);
528     }
529   }
530   {
531     // Testing C::emplace_hint(p, pair<Key, Mapped>&&)
532     Container c;
533     NonConstKeyPair v(42, 1);
534     cc->expect<NonConstKeyPair&&>();
535     It ret = c.emplace_hint(c.end(), std::move(v));
536     assert(ret != c.end());
537     assert(c.size() == 1);
538     assert(!cc->unchecked());
539     {
540       DisableAllocationGuard g;
541       NonConstKeyPair v2(42, 1);
542       It ret2 = c.emplace_hint(c.begin(), std::move(v2));
543       assert(&(*ret2) == &(*ret));
544       assert(c.size() == 1);
545     }
546   }
547   {
548     // Testing C::emplace_hint(p, const Key&, ConvertibleToMapped&&)
549     Container c;
550     const Key k(42);
551     cc->expect<Key const&, int&&>();
552     It ret = c.emplace_hint(c.end(), k, 42);
553     assert(ret != c.end());
554     assert(c.size() == 1);
555     assert(!cc->unchecked());
556     {
557       DisableAllocationGuard g;
558       const Key k2(42);
559       It ret2 = c.emplace_hint(c.begin(), k2, 1);
560       assert(&(*ret2) == &(*ret));
561       assert(c.size() == 1);
562     }
563   }
564   {
565     // Testing C::emplace_hint(p, Key&, Mapped&)
566     Container c;
567     Key k(42);
568     Mapped m(1);
569     cc->expect<Key&, Mapped&>();
570     It ret = c.emplace_hint(c.end(), k, m);
571     assert(ret != c.end());
572     assert(c.size() == 1);
573     assert(!cc->unchecked());
574     {
575       DisableAllocationGuard g;
576       Key k2(42);
577       Mapped m2(2);
578       It ret2 = c.emplace_hint(c.begin(), k2, m2);
579       assert(&(*ret2) == &(*ret));
580       assert(c.size() == 1);
581     }
582   }
583   {
584     // Testing C::emplace_hint(p, Key&&, Mapped&&)
585     Container c;
586     Key k(42);
587     Mapped m(1);
588     cc->expect<Key&&, Mapped&&>();
589     It ret = c.emplace_hint(c.end(), std::move(k), std::move(m));
590     assert(ret != c.end());
591     assert(c.size() == 1);
592     assert(!cc->unchecked());
593     {
594       DisableAllocationGuard g;
595       Key k2(42);
596       Mapped m2(2);
597       It ret2 = c.emplace_hint(c.begin(), std::move(k2), std::move(m2));
598       assert(&(*ret2) == &(*ret));
599       assert(c.size() == 1);
600     }
601   }
602   {
603     // Testing C::emplace_hint(p, ConvertibleToKey&&, ConvertibleToMapped&&)
604     Container c;
605     cc->expect<int&&, int&&>();
606     It ret = c.emplace_hint(c.end(), 42, 1);
607     assert(ret != c.end());
608     assert(c.size() == 1);
609     assert(!cc->unchecked());
610     {
611       cc->expect<int&&, int&&>();
612       It ret2 = c.emplace_hint(c.begin(), 42, 2);
613       assert(&(*ret2) == &(*ret));
614       assert(c.size() == 1);
615       assert(!cc->unchecked());
616     }
617   }
618 
619 }
620 
621 
622 template <class Container>
623 void testMultimapInsert()
624 {
625   typedef typename Container::value_type ValueTp;
626   ConstructController* cc = getConstructController();
627   cc->reset();
628   {
629     // Testing C::insert(const value_type&)
630     Container c;
631     const ValueTp v(42, 1);
632     cc->expect<const ValueTp&>();
633     c.insert(v);
634     assert(!cc->unchecked());
635   }
636   {
637     // Testing C::insert(value_type&)
638     Container c;
639     ValueTp v(42, 1);
640     cc->expect<ValueTp&>();
641     c.insert(v);
642     assert(!cc->unchecked());
643   }
644   {
645     // Testing C::insert(value_type&&)
646     Container c;
647     ValueTp v(42, 1);
648     cc->expect<ValueTp&&>();
649     c.insert(std::move(v));
650     assert(!cc->unchecked());
651   }
652   {
653     // Testing C::insert({key, value})
654     Container c;
655     cc->expect<ValueTp&&>();
656     c.insert({42, 1});
657     assert(!cc->unchecked());
658   }
659   {
660     // Testing C::insert(std::initializer_list<ValueTp>)
661     Container c;
662     std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
663     cc->expect<ValueTp const&>(2);
664     c.insert(il);
665     assert(!cc->unchecked());
666   }
667   {
668     // Testing C::insert(Iter, Iter) for *Iter = value_type const&
669     Container c;
670     const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
671     cc->expect<ValueTp const&>(3);
672     c.insert(std::begin(ValueList), std::end(ValueList));
673     assert(!cc->unchecked());
674   }
675   {
676     // Testing C::insert(Iter, Iter) for *Iter = value_type&&
677     Container c;
678     ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
679     cc->expect<ValueTp&&>(3);
680     c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
681              std::move_iterator<ValueTp*>(std::end(ValueList)));
682     assert(!cc->unchecked());
683   }
684   {
685     // Testing C::insert(Iter, Iter) for *Iter = value_type&
686     Container c;
687     ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
688     cc->expect<ValueTp&>(3);
689     c.insert(std::begin(ValueList), std::end(ValueList));
690     assert(!cc->unchecked());
691   }
692 }
693 
694 
695 template <class Container>
696 void testMultimapInsertHint()
697 {
698   typedef typename Container::value_type ValueTp;
699   ConstructController* cc = getConstructController();
700   cc->reset();
701   {
702     // Testing C::insert(p, const value_type&)
703     Container c;
704     const ValueTp v(42, 1);
705     cc->expect<const ValueTp&>();
706     c.insert(c.begin(), v);
707     assert(!cc->unchecked());
708   }
709   {
710     // Testing C::insert(p, value_type&)
711     Container c;
712     ValueTp v(42, 1);
713     cc->expect<ValueTp&>();
714     c.insert(c.begin(), v);
715     assert(!cc->unchecked());
716   }
717   {
718     // Testing C::insert(p, value_type&&)
719     Container c;
720     ValueTp v(42, 1);
721     cc->expect<ValueTp&&>();
722     c.insert(c.begin(), std::move(v));
723     assert(!cc->unchecked());
724   }
725   {
726     // Testing C::insert(p, {key, value})
727     Container c;
728     cc->expect<ValueTp&&>();
729     c.insert(c.begin(), {42, 1});
730     assert(!cc->unchecked());
731   }
732 }
733 
734 #endif
735