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