298 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 multimap12 13// multimap& operator=(const multimap& m);14 15#include <algorithm>16#include <cassert>17#include <map>18#include <vector>19 20#include "test_macros.h"21#include "../../../test_compare.h"22#include "test_allocator.h"23#include "min_allocator.h"24 25template <class T>26class tracking_allocator {27 std::vector<void*>* allocs_;28 29 template <class U>30 friend class tracking_allocator;31 32public:33 using value_type = T;34 using propagate_on_container_copy_assignment = std::true_type;35 36 tracking_allocator(std::vector<void*>& allocs) : allocs_(&allocs) {}37 38 template <class U>39 tracking_allocator(const tracking_allocator<U>& other) : allocs_(other.allocs_) {}40 41 T* allocate(std::size_t n) {42 T* allocation = std::allocator<T>().allocate(n);43 allocs_->push_back(allocation);44 return allocation;45 }46 47 void deallocate(T* ptr, std::size_t n) TEST_NOEXCEPT {48 auto res = std::remove(allocs_->begin(), allocs_->end(), ptr);49 assert(res != allocs_->end() && "Trying to deallocate memory from different allocator?");50 allocs_->erase(res);51 std::allocator<T>().deallocate(ptr, n);52 }53 54 friend bool operator==(const tracking_allocator& lhs, const tracking_allocator& rhs) {55 return lhs.allocs_ == rhs.allocs_;56 }57 58 friend bool operator!=(const tracking_allocator& lhs, const tracking_allocator& rhs) {59 return lhs.allocs_ != rhs.allocs_;60 }61};62 63struct NoOp {64 void operator()() {}65};66 67template <class Alloc, class AllocatorInvariant = NoOp>68void test_alloc(const Alloc& lhs_alloc = Alloc(),69 const Alloc& rhs_alloc = Alloc(),70 AllocatorInvariant check_alloc_invariant = NoOp()) {71 { // Test empty/non-empty multimap combinations72 { // assign from a non-empty container into an empty one73 using V = std::pair<const int, int>;74 using Map = std::multimap<int, int, std::less<int>, Alloc>;75 76 V arr[] = {V(1, 1), V(2, 3), V(2, 6)};77 const Map orig(begin(arr), end(arr), std::less<int>(), rhs_alloc);78 Map copy(lhs_alloc);79 copy = orig;80 assert(copy.size() == 3);81 assert(*std::next(copy.begin(), 0) == V(1, 1));82 assert(*std::next(copy.begin(), 1) == V(2, 3));83 assert(*std::next(copy.begin(), 2) == V(2, 6));84 assert(std::next(copy.begin(), 3) == copy.end());85 86 // Check that orig is still what is expected87 assert(orig.size() == 3);88 assert(*std::next(orig.begin(), 0) == V(1, 1));89 assert(*std::next(orig.begin(), 1) == V(2, 3));90 assert(*std::next(orig.begin(), 2) == V(2, 6));91 assert(std::next(orig.begin(), 3) == orig.end());92 }93 check_alloc_invariant();94 { // assign from an empty container into an empty one95 using Map = std::multimap<int, int, std::less<int>, Alloc>;96 97 const Map orig(rhs_alloc);98 Map copy(lhs_alloc);99 copy = orig;100 assert(copy.size() == 0);101 assert(copy.begin() == copy.end());102 103 // Check that orig is still what is expected104 assert(orig.size() == 0);105 assert(orig.begin() == orig.end());106 }107 check_alloc_invariant();108 { // assign from an empty container into a non-empty one109 using V = std::pair<const int, int>;110 using Map = std::multimap<int, int, std::less<int>, Alloc>;111 112 V arr[] = {V(1, 1), V(2, 3), V(2, 6)};113 const Map orig(rhs_alloc);114 Map copy(begin(arr), end(arr), std::less<int>(), rhs_alloc);115 copy = orig;116 assert(copy.size() == 0);117 assert(copy.begin() == copy.end());118 119 // Check that orig is still what is expected120 assert(orig.size() == 0);121 assert(orig.begin() == orig.end());122 }123 }124 125 { // Ensure that self-assignment works correctly126 { // with a non-empty multimap127 using V = std::pair<const int, int>;128 using Map = std::multimap<int, int, std::less<int>, Alloc>;129 130 V arr[] = {V(1, 1), V(2, 3), V(2, 6)};131 Map orig(begin(arr), end(arr), std::less<int>(), rhs_alloc);132 orig = static_cast<const Map&>(orig);133 134 assert(orig.size() == 3);135 assert(*std::next(orig.begin(), 0) == V(1, 1));136 assert(*std::next(orig.begin(), 1) == V(2, 3));137 assert(*std::next(orig.begin(), 2) == V(2, 6));138 assert(std::next(orig.begin(), 3) == orig.end());139 }140 { // with an empty multimap141 using Map = std::multimap<int, int, std::less<int>, Alloc>;142 143 Map orig(rhs_alloc);144 orig = static_cast<const Map&>(orig);145 146 assert(orig.size() == 0);147 assert(orig.begin() == orig.end());148 }149 }150 151 { // check assignment into a non-empty multimap152 check_alloc_invariant();153 { // LHS already contains elements, but fewer than the RHS154 using V = std::pair<const int, int>;155 using Map = std::multimap<int, int, std::less<int>, Alloc>;156 157 V lhs_arr[] = {V(1, 1), V(2, 3), V(2, 6)};158 const Map orig(begin(lhs_arr), end(lhs_arr), std::less<int>(), rhs_alloc);159 160 V rhs_arr[] = {V(4, 2), V(5, 1)};161 Map copy(begin(rhs_arr), end(rhs_arr), std::less<int>(), lhs_alloc);162 copy = orig;163 assert(copy.size() == 3);164 assert(*std::next(copy.begin(), 0) == V(1, 1));165 assert(*std::next(copy.begin(), 1) == V(2, 3));166 assert(*std::next(copy.begin(), 2) == V(2, 6));167 assert(std::next(copy.begin(), 3) == copy.end());168 169 // Check that orig is still what is expected170 assert(orig.size() == 3);171 assert(*std::next(orig.begin(), 0) == V(1, 1));172 assert(*std::next(orig.begin(), 1) == V(2, 3));173 assert(*std::next(orig.begin(), 2) == V(2, 6));174 assert(std::next(orig.begin(), 3) == orig.end());175 }176 check_alloc_invariant();177 { // LHS contains the same number of elements as the RHS178 using V = std::pair<const int, int>;179 using Map = std::multimap<int, int, std::less<int>, Alloc>;180 181 V lhs_arr[] = {V(1, 1), V(2, 3), V(2, 6)};182 const Map orig(begin(lhs_arr), end(lhs_arr), std::less<int>(), rhs_alloc);183 184 V rhs_arr[] = {V(4, 2), V(5, 1), V(6, 0)};185 Map copy(begin(rhs_arr), end(rhs_arr), std::less<int>(), lhs_alloc);186 copy = orig;187 assert(copy.size() == 3);188 assert(*std::next(copy.begin(), 0) == V(1, 1));189 assert(*std::next(copy.begin(), 1) == V(2, 3));190 assert(*std::next(copy.begin(), 2) == V(2, 6));191 assert(std::next(copy.begin(), 3) == copy.end());192 193 // Check that orig is still what is expected194 assert(orig.size() == 3);195 assert(*std::next(orig.begin(), 0) == V(1, 1));196 assert(*std::next(orig.begin(), 1) == V(2, 3));197 assert(*std::next(orig.begin(), 2) == V(2, 6));198 assert(std::next(orig.begin(), 3) == orig.end());199 }200 check_alloc_invariant();201 { // LHS already contains more elements than the RHS202 using V = std::pair<const int, int>;203 using Map = std::multimap<int, int, std::less<int>, Alloc>;204 205 V lhs_arr[] = {V(1, 1), V(2, 3), V(2, 6)};206 const Map orig(begin(lhs_arr), end(lhs_arr), std::less<int>(), rhs_alloc);207 208 V rhs_arr[] = {V(4, 2), V(5, 1), V(6, 0), V(7, 9)};209 Map copy(begin(rhs_arr), end(rhs_arr), std::less<int>(), lhs_alloc);210 copy = orig;211 assert(copy.size() == 3);212 assert(*std::next(copy.begin(), 0) == V(1, 1));213 assert(*std::next(copy.begin(), 1) == V(2, 3));214 assert(*std::next(copy.begin(), 2) == V(2, 6));215 assert(std::next(copy.begin(), 3) == copy.end());216 217 // Check that orig is still what is expected218 assert(orig.size() == 3);219 assert(*std::next(orig.begin(), 0) == V(1, 1));220 assert(*std::next(orig.begin(), 1) == V(2, 3));221 assert(*std::next(orig.begin(), 2) == V(2, 6));222 assert(std::next(orig.begin(), 3) == orig.end());223 }224 check_alloc_invariant();225 }226 { // Make a somewhat larger set to exercise the algorithm a bit227 using V = std::pair<const int, int>;228 using Map = std::multimap<int, int, std::less<int>, Alloc>;229 230 Map orig(rhs_alloc);231 for (int i = 0; i != 50; ++i) {232 orig.insert(V(i, i + 3));233 orig.insert(V(i, i + 5));234 }235 236 Map copy(lhs_alloc);237 copy = orig;238 int i = 0;239 for (auto iter = copy.begin(); iter != copy.end();) {240 assert(*iter++ == V(i, i + 3));241 assert(*iter++ == V(i, i + 5));242 ++i;243 }244 }245 check_alloc_invariant();246}247 248void test() {249 test_alloc<std::allocator<std::pair<const int, int> > >();250#if TEST_STD_VER >= 11251 test_alloc<min_allocator<std::pair<const int, int> > >();252 253 { // Make sure we're allocating/deallocating nodes with the correct allocator254 // See https://llvm.org/PR29001255 class AssertEmpty {256 std::vector<void*>* lhs_allocs_;257 std::vector<void*>* rhs_allocs_;258 259 public:260 AssertEmpty(std::vector<void*>& lhs_allocs, std::vector<void*>& rhs_allocs)261 : lhs_allocs_(&lhs_allocs), rhs_allocs_(&rhs_allocs) {}262 263 void operator()() {264 assert(lhs_allocs_->empty());265 assert(rhs_allocs_->empty());266 }267 };268 269 std::vector<void*> lhs_allocs;270 std::vector<void*> rhs_allocs;271 test_alloc<tracking_allocator<std::pair<const int, int> > >(272 lhs_allocs, rhs_allocs, AssertEmpty(lhs_allocs, rhs_allocs));273 }274#endif275 276 { // Ensure that the comparator is copied277 using V = std::pair<const int, int>;278 using Map = std::multimap<int, int, test_less<int> >;279 280 V arr[] = {V(1, 1), V(2, 3), V(2, 6)};281 const Map orig(begin(arr), end(arr), test_less<int>(3));282 Map copy;283 copy = orig;284 assert(copy.size() == 3);285 assert(copy.key_comp() == test_less<int>(3));286 287 // Check that orig is still what is expected288 assert(orig.size() == 3);289 assert(orig.key_comp() == test_less<int>(3));290 }291}292 293int main(int, char**) {294 test();295 296 return 0;297}298