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};
counting_allocatorT(int f)36 counting_allocatorT(int f) noexcept : foo(f) {}
37
38 using propagate_on_container_copy_assignment = std::true_type;
counting_allocatorT(const counting_allocatorT<U> & other)39 template <class U> counting_allocatorT(const counting_allocatorT<U>& other) noexcept {foo = other.foo;}
operator ==(const counting_allocatorT<U> & other) const40 template <class U> bool operator==(const counting_allocatorT<U>& other) const noexcept { return foo == other.foo; }
operator !=(const counting_allocatorT<U> & other) const41 template <class U> bool operator!=(const counting_allocatorT<U>& other) const noexcept { return foo != other.foo; }
42
allocate(std::size_t n) const43 T* allocate(std::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 }
deallocate(T * p,std::size_t) const48 void deallocate(T* p, std::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};
counting_allocatorF(int f)59 counting_allocatorF(int f) noexcept : foo(f) {}
60
61 using propagate_on_container_copy_assignment = std::false_type;
counting_allocatorF(const counting_allocatorF<U> & other)62 template <class U> counting_allocatorF(const counting_allocatorF<U>& other) noexcept {foo = other.foo;}
operator ==(const counting_allocatorF<U> & other) const63 template <class U> bool operator==(const counting_allocatorF<U>& other) const noexcept { return foo == other.foo; }
operator !=(const counting_allocatorF<U> & other) const64 template <class U> bool operator!=(const counting_allocatorF<U>& other) const noexcept { return foo != other.foo; }
65
allocate(std::size_t n) const66 T* allocate(std::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 }
deallocate(T * p,std::size_t) const71 void deallocate(T* p, std::size_t) const noexcept {
72 ca_deallocs.push_back(foo);
73 free(p);
74 }
75 };
76
balanced_allocs()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
main(int,char **)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(std::distance(m.begin(), m.end()) == 3);
142 assert(*m.begin() == V(1, 1));
143 assert(*std::next(m.begin()) == V(2, 1));
144 assert(*std::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(std::distance(mo.begin(), mo.end()) == 3);
150 assert(*mo.begin() == V(1, 1));
151 assert(*std::next(mo.begin()) == V(2, 1));
152 assert(*std::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(std::distance(m.begin(), m.end()) == 3);
192 assert(*m.begin() == V(1, 1));
193 assert(*std::next(m.begin()) == V(2, 1));
194 assert(*std::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(std::distance(mo.begin(), mo.end()) == 3);
200 assert(*mo.begin() == V(1, 1));
201 assert(*std::next(mo.begin()) == V(2, 1));
202 assert(*std::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(std::distance(m.begin(), m.end()) == 3);
228 assert(*m.begin() == V(1, 1));
229 assert(*std::next(m.begin()) == V(2, 1));
230 assert(*std::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(std::distance(mo.begin(), mo.end()) == 3);
236 assert(*mo.begin() == V(1, 1));
237 assert(*std::next(mo.begin()) == V(2, 1));
238 assert(*std::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(std::distance(m.begin(), m.end()) == 3);
263 assert(*m.begin() == V(1, 1));
264 assert(*std::next(m.begin()) == V(2, 1));
265 assert(*std::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(std::distance(mo.begin(), mo.end()) == 3);
271 assert(*mo.begin() == V(1, 1));
272 assert(*std::next(mo.begin()) == V(2, 1));
273 assert(*std::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(std::distance(m.begin(), m.end()) == 3);
299 assert(*m.begin() == V(1, 1));
300 assert(*std::next(m.begin()) == V(2, 1));
301 assert(*std::next(m.begin(), 2) == V(3, 1));
302
303 assert(mo.key_comp() == C(5));
304 assert(mo.size() == 3);
305 assert(std::distance(mo.begin(), mo.end()) == 3);
306 assert(*mo.begin() == V(1, 1));
307 assert(*std::next(mo.begin()) == V(2, 1));
308 assert(*std::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(std::distance(m.begin(), m.end()) == 3);
333 assert(*m.begin() == V(1, 1));
334 assert(*std::next(m.begin()) == V(2, 1));
335 assert(*std::next(m.begin(), 2) == V(3, 1));
336
337 assert(mo.key_comp() == C(5));
338 assert(mo.size() == 3);
339 assert(std::distance(mo.begin(), mo.end()) == 3);
340 assert(*mo.begin() == V(1, 1));
341 assert(*std::next(mo.begin()) == V(2, 1));
342 assert(*std::next(mo.begin(), 2) == V(3, 1));
343 }
344 assert(balanced_allocs());
345 #endif
346
347 return 0;
348 }
349