310 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// <map>10 11// class map12 13// map& operator=(const map& m);14 15#include <algorithm>16#include <cassert>17#include <cstdio>18#include <iterator>19#include <map>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 27template <class T>28class tracking_allocator {29 std::vector<void*>* allocs_;30 31 template <class U>32 friend class tracking_allocator;33 34public:35 using value_type = T;36 using propagate_on_container_copy_assignment = std::true_type;37 38 tracking_allocator(std::vector<void*>& allocs) : allocs_(&allocs) {}39 40 template <class U>41 tracking_allocator(const tracking_allocator<U>& other) : allocs_(other.allocs_) {}42 43 T* allocate(std::size_t n) {44 T* allocation = std::allocator<T>().allocate(n);45 allocs_->push_back(allocation);46 return allocation;47 }48 49 void deallocate(T* ptr, std::size_t n) TEST_NOEXCEPT {50 auto res = std::remove(allocs_->begin(), allocs_->end(), ptr);51 assert(res != allocs_->end() && "Trying to deallocate memory from different allocator?");52 allocs_->erase(res);53 std::allocator<T>().deallocate(ptr, n);54 }55 56 friend bool operator==(const tracking_allocator& lhs, const tracking_allocator& rhs) {57 return lhs.allocs_ == rhs.allocs_;58 }59 60 friend bool operator!=(const tracking_allocator& lhs, const tracking_allocator& rhs) {61 return lhs.allocs_ != rhs.allocs_;62 }63};64 65struct NoOp {66 void operator()() {}67};68 69template <class Alloc, class AllocatorInvariant = NoOp>70void test_alloc(const Alloc& lhs_alloc = Alloc(),71 const Alloc& rhs_alloc = Alloc(),72 AllocatorInvariant check_alloc_invariant = NoOp()) {73 { // Test empty/non-empty map combinations74 { // assign from a non-empty container into an empty one75 using V = std::pair<const int, int>;76 using Map = std::map<int, int, std::less<int>, Alloc>;77 78 V arr[] = {V(1, 1), V(2, 3), V(3, 6)};79 const Map orig(begin(arr), end(arr), std::less<int>(), rhs_alloc);80 Map copy(lhs_alloc);81 copy = orig;82 assert(copy.size() == 3);83 assert(*std::next(copy.begin(), 0) == V(1, 1));84 assert(*std::next(copy.begin(), 1) == V(2, 3));85 assert(*std::next(copy.begin(), 2) == V(3, 6));86 assert(std::next(copy.begin(), 3) == copy.end());87 88 // Check that orig is still what is expected89 assert(orig.size() == 3);90 assert(*std::next(orig.begin(), 0) == V(1, 1));91 assert(*std::next(orig.begin(), 1) == V(2, 3));92 assert(*std::next(orig.begin(), 2) == V(3, 6));93 assert(std::next(orig.begin(), 3) == orig.end());94 }95 check_alloc_invariant();96 { // assign from an empty container into an empty one97 using Map = std::map<int, int, std::less<int>, Alloc>;98 99 const Map orig(rhs_alloc);100 Map copy(lhs_alloc);101 copy = orig;102 assert(copy.size() == 0);103 assert(copy.begin() == copy.end());104 105 // Check that orig is still what is expected106 assert(orig.size() == 0);107 assert(orig.begin() == orig.end());108 }109 check_alloc_invariant();110 { // assign from an empty container into a non-empty one111 using V = std::pair<const int, int>;112 using Map = std::map<int, int, std::less<int>, Alloc>;113 114 V arr[] = {V(1, 1), V(2, 3), V(3, 6)};115 const Map orig(rhs_alloc);116 Map copy(begin(arr), end(arr), std::less<int>(), rhs_alloc);117 copy = orig;118 assert(copy.size() == 0);119 assert(copy.begin() == copy.end());120 121 // Check that orig is still what is expected122 assert(orig.size() == 0);123 assert(orig.begin() == orig.end());124 }125 }126 127 { // Ensure that self-assignment works correctly128 { // with a non-empty map129 using V = std::pair<const int, int>;130 using Map = std::map<int, int, std::less<int>, Alloc>;131 132 V arr[] = {V(1, 1), V(2, 3), V(3, 6)};133 Map orig(begin(arr), end(arr), std::less<int>(), rhs_alloc);134 orig = static_cast<const Map&>(orig);135 136 assert(orig.size() == 3);137 assert(*std::next(orig.begin(), 0) == V(1, 1));138 assert(*std::next(orig.begin(), 1) == V(2, 3));139 assert(*std::next(orig.begin(), 2) == V(3, 6));140 assert(std::next(orig.begin(), 3) == orig.end());141 }142 { // with an empty map143 using Map = std::map<int, int, std::less<int>, Alloc>;144 145 Map orig(rhs_alloc);146 orig = static_cast<const Map&>(orig);147 148 assert(orig.size() == 0);149 assert(orig.begin() == orig.end());150 }151 }152 153 { // check assignment into a non-empty map154 check_alloc_invariant();155 { // LHS already contains elements, but fewer than the RHS156 using V = std::pair<const int, int>;157 using Map = std::map<int, int, std::less<int>, Alloc>;158 159 V lhs_arr[] = {V(1, 1), V(2, 3), V(3, 6)};160 const Map orig(begin(lhs_arr), end(lhs_arr), std::less<int>(), rhs_alloc);161 162 V rhs_arr[] = {V(4, 2), V(5, 1)};163 Map copy(begin(rhs_arr), end(rhs_arr), std::less<int>(), lhs_alloc);164 copy = orig;165 assert(copy.size() == 3);166 assert(*std::next(copy.begin(), 0) == V(1, 1));167 assert(*std::next(copy.begin(), 1) == V(2, 3));168 assert(*std::next(copy.begin(), 2) == V(3, 6));169 assert(std::next(copy.begin(), 3) == copy.end());170 171 // Check that orig is still what is expected172 assert(orig.size() == 3);173 assert(*std::next(orig.begin(), 0) == V(1, 1));174 assert(*std::next(orig.begin(), 1) == V(2, 3));175 assert(*std::next(orig.begin(), 2) == V(3, 6));176 assert(std::next(orig.begin(), 3) == orig.end());177 }178 check_alloc_invariant();179 { // LHS contains the same number of elements as the RHS180 using V = std::pair<const int, int>;181 using Map = std::map<int, int, std::less<int>, Alloc>;182 183 V lhs_arr[] = {V(1, 1), V(2, 3), V(3, 6)};184 const Map orig(begin(lhs_arr), end(lhs_arr), std::less<int>(), rhs_alloc);185 186 V rhs_arr[] = {V(4, 2), V(5, 1), V(6, 0)};187 Map copy(begin(rhs_arr), end(rhs_arr), std::less<int>(), lhs_alloc);188 copy = orig;189 assert(copy.size() == 3);190 assert(*std::next(copy.begin(), 0) == V(1, 1));191 assert(*std::next(copy.begin(), 1) == V(2, 3));192 assert(*std::next(copy.begin(), 2) == V(3, 6));193 assert(std::next(copy.begin(), 3) == copy.end());194 195 // Check that orig is still what is expected196 assert(orig.size() == 3);197 assert(*std::next(orig.begin(), 0) == V(1, 1));198 assert(*std::next(orig.begin(), 1) == V(2, 3));199 assert(*std::next(orig.begin(), 2) == V(3, 6));200 assert(std::next(orig.begin(), 3) == orig.end());201 }202 check_alloc_invariant();203 { // LHS already contains more elements than the RHS204 using V = std::pair<const int, int>;205 using Map = std::map<int, int, std::less<int>, Alloc>;206 207 V lhs_arr[] = {V(1, 1), V(2, 3), V(3, 6)};208 const Map orig(begin(lhs_arr), end(lhs_arr), std::less<int>(), rhs_alloc);209 210 V rhs_arr[] = {V(4, 2), V(5, 1), V(6, 0), V(7, 9)};211 Map copy(begin(rhs_arr), end(rhs_arr), std::less<int>(), lhs_alloc);212 copy = orig;213 assert(copy.size() == 3);214 assert(*std::next(copy.begin(), 0) == V(1, 1));215 assert(*std::next(copy.begin(), 1) == V(2, 3));216 assert(*std::next(copy.begin(), 2) == V(3, 6));217 assert(std::next(copy.begin(), 3) == copy.end());218 219 // Check that orig is still what is expected220 assert(orig.size() == 3);221 assert(*std::next(orig.begin(), 0) == V(1, 1));222 assert(*std::next(orig.begin(), 1) == V(2, 3));223 assert(*std::next(orig.begin(), 2) == V(3, 6));224 assert(std::next(orig.begin(), 3) == orig.end());225 }226 check_alloc_invariant();227 }228 { // Make a somewhat larger set to exercise the algorithm a bit229 using V = std::pair<const int, int>;230 using Map = std::map<int, int, std::less<int>, Alloc>;231 232 Map orig(rhs_alloc);233 for (int i = 0; i != 50; ++i)234 orig[i] = i + 3;235 236 Map copy(lhs_alloc);237 copy = orig;238 int i = 0;239 for (auto v : copy) {240 assert(v == V(i, i + 3));241 ++i;242 }243 }244 check_alloc_invariant();245}246 247void test() {248 test_alloc<std::allocator<std::pair<const int, int> > >();249#if TEST_STD_VER >= 11250 test_alloc<min_allocator<std::pair<const int, int> > >();251 252 { // Make sure we're allocating/deallocating nodes with the correct allocator253 // See https://llvm.org/PR29001254 class AssertEmpty {255 std::vector<void*>* lhs_allocs_;256 std::vector<void*>* rhs_allocs_;257 258 public:259 AssertEmpty(std::vector<void*>& lhs_allocs, std::vector<void*>& rhs_allocs)260 : lhs_allocs_(&lhs_allocs), rhs_allocs_(&rhs_allocs) {}261 262 void operator()() {263 assert(lhs_allocs_->empty());264 assert(rhs_allocs_->empty());265 }266 };267 268 std::vector<void*> lhs_allocs;269 std::vector<void*> rhs_allocs;270 test_alloc<tracking_allocator<std::pair<const int, int> > >(271 lhs_allocs, rhs_allocs, AssertEmpty(lhs_allocs, rhs_allocs));272 }273#endif274 275 { // Ensure that the comparator is copied276 using V = std::pair<const int, int>;277 using Map = std::map<int, int, test_less<int> >;278 279 V arr[] = {V(1, 1), V(2, 3), V(3, 6)};280 const Map orig(begin(arr), end(arr), test_less<int>(3));281 Map copy;282 copy = orig;283 assert(copy.size() == 3);284 assert(copy.key_comp() == test_less<int>(3));285 286 // Check that orig is still what is expected287 assert(orig.size() == 3);288 assert(orig.key_comp() == test_less<int>(3));289 }290 291 { // Make sure the color is copied as well292 std::map<int, int> in;293 294 for (int i = 0; i != 32; ++i)295 in[i] = i;296 297 std::map<int, int> out = in;298 299 out.erase(std::next(out.begin(), 10), out.end());300 out = in;301 out.erase(std::next(out.begin(), 17), out.end());302 }303}304 305int main(int, char**) {306 test();307 308 return 0;309}310