llvm-project

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(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
    }
48
    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};
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(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
    }
71
    void deallocate(T* p, std::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(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