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 // <map>
10 
11 // class map
12 
13 // map& operator=(const map& m);
14 
15 // XFAIL: libcpp-has-debug-mode
16 
17 #include <map>
18 #include <algorithm>
19 #include <cassert>
20 #include <cstdio>
21 #include <iterator>
22 #include <vector>
23 
24 #include "test_macros.h"
25 #include "../../../test_compare.h"
26 #include "test_allocator.h"
27 #include "min_allocator.h"
28 
29 #if TEST_STD_VER >= 11
30 std::vector<int> ca_allocs;
31 std::vector<int> ca_deallocs;
32 
33 template <class T>
34 class counting_allocatorT {
35 public:
36     typedef T value_type;
37     int foo{0};
38     counting_allocatorT(int f) noexcept : foo(f) {}
39 
40     using propagate_on_container_copy_assignment = std::true_type;
41     template <class U> counting_allocatorT(const counting_allocatorT<U>& other) noexcept {foo = other.foo;}
42     template <class U> bool operator==(const counting_allocatorT<U>& other) const noexcept { return foo == other.foo; }
43     template <class U> bool operator!=(const counting_allocatorT<U>& other) const noexcept { return foo != other.foo; }
44 
45     T* allocate(size_t n) const {
46         ca_allocs.push_back(foo);
47         void * const pv = ::malloc(n * sizeof(T));
48         return static_cast<T *>(pv);
49     }
50     void deallocate(T* p, size_t) const noexcept {
51         ca_deallocs.push_back(foo);
52         free(p);
53     }
54 };
55 
56 template <class T>
57 class counting_allocatorF {
58 public:
59     typedef T value_type;
60     int foo{0};
61     counting_allocatorF(int f) noexcept : foo(f) {}
62 
63     using propagate_on_container_copy_assignment = std::false_type;
64     template <class U> counting_allocatorF(const counting_allocatorF<U>& other) noexcept {foo = other.foo;}
65     template <class U> bool operator==(const counting_allocatorF<U>& other) const noexcept { return foo == other.foo; }
66     template <class U> bool operator!=(const counting_allocatorF<U>& other) const noexcept { return foo != other.foo; }
67 
68     T* allocate(size_t n) const {
69         ca_allocs.push_back(foo);
70         void * const pv = ::malloc(n * sizeof(T));
71         return static_cast<T *>(pv);
72     }
73     void deallocate(T* p, size_t) const noexcept {
74         ca_deallocs.push_back(foo);
75         free(p);
76     }
77 };
78 
79 bool balanced_allocs() {
80     std::vector<int> temp1, temp2;
81 
82     std::printf("Allocations = %zu, deallocations = %zu\n", ca_allocs.size(),
83                 ca_deallocs.size());
84     if (ca_allocs.size() != ca_deallocs.size())
85         return false;
86 
87     temp1 = ca_allocs;
88     std::sort(temp1.begin(), temp1.end());
89     temp2.clear();
90     std::unique_copy(temp1.begin(), temp1.end(), std::back_inserter<std::vector<int>>(temp2));
91     std::printf("There were %zu different allocators\n", temp2.size());
92 
93     for (std::vector<int>::const_iterator it = temp2.begin(); it != temp2.end(); ++it ) {
94         std::ptrdiff_t const allocs = std::count(ca_allocs.begin(), ca_allocs.end(), *it);
95         std::ptrdiff_t const deallocs = std::count(ca_deallocs.begin(), ca_deallocs.end(), *it);
96         std::printf("%d: %td vs %td\n", *it, allocs, deallocs);
97         if (allocs != deallocs)
98             return false;
99     }
100 
101     temp1 = ca_allocs;
102     std::sort(temp1.begin(), temp1.end());
103     temp2.clear();
104     std::unique_copy(temp1.begin(), temp1.end(), std::back_inserter<std::vector<int>>(temp2));
105     std::printf("There were %zu different (de)allocators\n", temp2.size());
106 
107     for (std::vector<int>::const_iterator it = ca_deallocs.begin(); it != ca_deallocs.end(); ++it ) {
108         std::ptrdiff_t const allocs = std::count(ca_allocs.begin(), ca_allocs.end(), *it);
109         std::ptrdiff_t const deallocs = std::count(ca_deallocs.begin(), ca_deallocs.end(), *it);
110         std::printf("%d: %td vs %td\n", *it, allocs, deallocs);
111         if (allocs != deallocs)
112             return false;
113     }
114 
115     return true;
116 }
117 #endif
118 
119 int main(int, char**)
120 {
121     {
122         typedef std::pair<const int, double> V;
123         V ar[] =
124         {
125             V(1, 1),
126             V(1, 1.5),
127             V(1, 2),
128             V(2, 1),
129             V(2, 1.5),
130             V(2, 2),
131             V(3, 1),
132             V(3, 1.5),
133             V(3, 2)
134         };
135         typedef test_less<int> C;
136         typedef test_allocator<V> A;
137         std::map<int, double, C, A> mo(ar, ar+sizeof(ar)/sizeof(ar[0]), C(5), A(2));
138         std::map<int, double, C, A> m(ar, ar+sizeof(ar)/sizeof(ar[0])/2, C(3), A(7));
139         m = mo;
140         assert(m.get_allocator() == A(7));
141         assert(m.key_comp() == C(5));
142         assert(m.size() == 3);
143         assert(std::distance(m.begin(), m.end()) == 3);
144         assert(*m.begin() == V(1, 1));
145         assert(*std::next(m.begin()) == V(2, 1));
146         assert(*std::next(m.begin(), 2) == V(3, 1));
147 
148         assert(mo.get_allocator() == A(2));
149         assert(mo.key_comp() == C(5));
150         assert(mo.size() == 3);
151         assert(std::distance(mo.begin(), mo.end()) == 3);
152         assert(*mo.begin() == V(1, 1));
153         assert(*std::next(mo.begin()) == V(2, 1));
154         assert(*std::next(mo.begin(), 2) == V(3, 1));
155     }
156     {
157         typedef std::pair<const int, double> V;
158         const V ar[] =
159         {
160             V(1, 1),
161             V(2, 1),
162             V(3, 1),
163         };
164         std::map<int, double> m(ar, ar+sizeof(ar)/sizeof(ar[0]));
165         std::map<int, double> *p = &m;
166         m = *p;
167 
168         assert(m.size() == 3);
169         assert(std::equal(m.begin(), m.end(), ar));
170     }
171     {
172         typedef std::pair<const int, double> V;
173         V ar[] =
174         {
175             V(1, 1),
176             V(1, 1.5),
177             V(1, 2),
178             V(2, 1),
179             V(2, 1.5),
180             V(2, 2),
181             V(3, 1),
182             V(3, 1.5),
183             V(3, 2)
184         };
185         typedef test_less<int> C;
186         typedef other_allocator<V> A;
187         std::map<int, double, C, A> mo(ar, ar+sizeof(ar)/sizeof(ar[0]), C(5), A(2));
188         std::map<int, double, C, A> m(ar, ar+sizeof(ar)/sizeof(ar[0])/2, C(3), A(7));
189         m = mo;
190         assert(m.get_allocator() == A(2));
191         assert(m.key_comp() == C(5));
192         assert(m.size() == 3);
193         assert(std::distance(m.begin(), m.end()) == 3);
194         assert(*m.begin() == V(1, 1));
195         assert(*std::next(m.begin()) == V(2, 1));
196         assert(*std::next(m.begin(), 2) == V(3, 1));
197 
198         assert(mo.get_allocator() == A(2));
199         assert(mo.key_comp() == C(5));
200         assert(mo.size() == 3);
201         assert(std::distance(mo.begin(), mo.end()) == 3);
202         assert(*mo.begin() == V(1, 1));
203         assert(*std::next(mo.begin()) == V(2, 1));
204         assert(*std::next(mo.begin(), 2) == V(3, 1));
205     }
206 #if TEST_STD_VER >= 11
207     {
208         typedef std::pair<const int, double> V;
209         V ar[] =
210         {
211             V(1, 1),
212             V(1, 1.5),
213             V(1, 2),
214             V(2, 1),
215             V(2, 1.5),
216             V(2, 2),
217             V(3, 1),
218             V(3, 1.5),
219             V(3, 2)
220         };
221         typedef test_less<int> C;
222         typedef min_allocator<V> A;
223         std::map<int, double, C, A> mo(ar, ar+sizeof(ar)/sizeof(ar[0]), C(5), A());
224         std::map<int, double, C, A> m(ar, ar+sizeof(ar)/sizeof(ar[0])/2, C(3), A());
225         m = mo;
226         assert(m.get_allocator() == A());
227         assert(m.key_comp() == C(5));
228         assert(m.size() == 3);
229         assert(std::distance(m.begin(), m.end()) == 3);
230         assert(*m.begin() == V(1, 1));
231         assert(*std::next(m.begin()) == V(2, 1));
232         assert(*std::next(m.begin(), 2) == V(3, 1));
233 
234         assert(mo.get_allocator() == A());
235         assert(mo.key_comp() == C(5));
236         assert(mo.size() == 3);
237         assert(std::distance(mo.begin(), mo.end()) == 3);
238         assert(*mo.begin() == V(1, 1));
239         assert(*std::next(mo.begin()) == V(2, 1));
240         assert(*std::next(mo.begin(), 2) == V(3, 1));
241     }
242     {
243         typedef std::pair<const int, double> V;
244         V ar[] =
245         {
246             V(1, 1),
247             V(1, 1.5),
248             V(1, 2),
249             V(2, 1),
250             V(2, 1.5),
251             V(2, 2),
252             V(3, 1),
253             V(3, 1.5),
254             V(3, 2)
255         };
256         typedef test_less<int> C;
257         typedef min_allocator<V> A;
258         std::map<int, double, C, A> mo(ar, ar+sizeof(ar)/sizeof(ar[0]), C(5), A());
259         std::map<int, double, C, A> m(ar, ar+sizeof(ar)/sizeof(ar[0])/2, C(3), A());
260         m = mo;
261         assert(m.get_allocator() == A());
262         assert(m.key_comp() == C(5));
263         assert(m.size() == 3);
264         assert(std::distance(m.begin(), m.end()) == 3);
265         assert(*m.begin() == V(1, 1));
266         assert(*std::next(m.begin()) == V(2, 1));
267         assert(*std::next(m.begin(), 2) == V(3, 1));
268 
269         assert(mo.get_allocator() == A());
270         assert(mo.key_comp() == C(5));
271         assert(mo.size() == 3);
272         assert(std::distance(mo.begin(), mo.end()) == 3);
273         assert(*mo.begin() == V(1, 1));
274         assert(*std::next(mo.begin()) == V(2, 1));
275         assert(*std::next(mo.begin(), 2) == V(3, 1));
276     }
277 
278     assert(balanced_allocs());
279     {
280         typedef std::pair<const int, double> V;
281         V ar[] =
282         {
283             V(1, 1),
284             V(1, 1.5),
285             V(1, 2),
286             V(2, 1),
287             V(2, 1.5),
288             V(2, 2),
289             V(3, 1),
290             V(3, 1.5),
291             V(3, 2)
292         };
293         typedef test_less<int> C;
294         typedef counting_allocatorT<V> A;
295         std::map<int, double, C, A> mo(ar, ar+sizeof(ar)/sizeof(ar[0]), C(5), A(1));
296         std::map<int, double, C, A> m(ar, ar+sizeof(ar)/sizeof(ar[0])/2, C(3), A(2));
297         m = mo;
298         assert(m.key_comp() == C(5));
299         assert(m.size() == 3);
300         assert(std::distance(m.begin(), m.end()) == 3);
301         assert(*m.begin() == V(1, 1));
302         assert(*std::next(m.begin()) == V(2, 1));
303         assert(*std::next(m.begin(), 2) == V(3, 1));
304 
305         assert(mo.key_comp() == C(5));
306         assert(mo.size() == 3);
307         assert(std::distance(mo.begin(), mo.end()) == 3);
308         assert(*mo.begin() == V(1, 1));
309         assert(*std::next(mo.begin()) == V(2, 1));
310         assert(*std::next(mo.begin(), 2) == V(3, 1));
311     }
312     assert(balanced_allocs());
313     {
314         typedef std::pair<const int, double> V;
315         V ar[] =
316         {
317             V(1, 1),
318             V(1, 1.5),
319             V(1, 2),
320             V(2, 1),
321             V(2, 1.5),
322             V(2, 2),
323             V(3, 1),
324             V(3, 1.5),
325             V(3, 2)
326         };
327         typedef test_less<int> C;
328         typedef counting_allocatorF<V> A;
329         std::map<int, double, C, A> mo(ar, ar+sizeof(ar)/sizeof(ar[0]), C(5), A(100));
330         std::map<int, double, C, A> m(ar, ar+sizeof(ar)/sizeof(ar[0])/2, C(3), A(200));
331         m = mo;
332         assert(m.key_comp() == C(5));
333         assert(m.size() == 3);
334         assert(std::distance(m.begin(), m.end()) == 3);
335         assert(*m.begin() == V(1, 1));
336         assert(*std::next(m.begin()) == V(2, 1));
337         assert(*std::next(m.begin(), 2) == V(3, 1));
338 
339         assert(mo.key_comp() == C(5));
340         assert(mo.size() == 3);
341         assert(std::distance(mo.begin(), mo.end()) == 3);
342         assert(*mo.begin() == V(1, 1));
343         assert(*std::next(mo.begin()) == V(2, 1));
344         assert(*std::next(mo.begin(), 2) == V(3, 1));
345     }
346     assert(balanced_allocs());
347 #endif
348 
349   return 0;
350 }
351