283 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// <set>10 11// class multiset12 13// multiset& operator=(const multiset& s);14 15#include <algorithm>16#include <cassert>17#include <iterator>18#include <set>19#include <vector>20 21#include "../../../test_compare.h"22#include "min_allocator.h"23#include "test_macros.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 multiset combinations72 { // assign from a non-empty container into an empty one73 using Set = std::multiset<int, std::less<int>, Alloc>;74 75 int arr[] = {1, 2, 2};76 const Set orig(std::begin(arr), std::end(arr), std::less<int>(), rhs_alloc);77 Set copy(lhs_alloc);78 copy = orig;79 assert(copy.size() == 3);80 assert(*std::next(copy.begin(), 0) == 1);81 assert(*std::next(copy.begin(), 1) == 2);82 assert(*std::next(copy.begin(), 2) == 2);83 assert(std::next(copy.begin(), 3) == copy.end());84 85 // Check that orig is still what is expected86 assert(orig.size() == 3);87 assert(*std::next(orig.begin(), 0) == 1);88 assert(*std::next(orig.begin(), 1) == 2);89 assert(*std::next(orig.begin(), 2) == 2);90 assert(std::next(orig.begin(), 3) == orig.end());91 }92 check_alloc_invariant();93 { // assign from an empty container into an empty one94 using Set = std::multiset<int, std::less<int>, Alloc>;95 96 const Set orig(rhs_alloc);97 Set copy(lhs_alloc);98 copy = orig;99 assert(copy.size() == 0);100 assert(copy.begin() == copy.end());101 102 // Check that orig is still what is expected103 assert(orig.size() == 0);104 assert(orig.begin() == orig.end());105 }106 check_alloc_invariant();107 { // assign from an empty container into a non-empty one108 using Set = std::multiset<int, std::less<int>, Alloc>;109 110 int arr[] = {1, 2, 2};111 const Set orig(rhs_alloc);112 Set copy(std::begin(arr), std::end(arr), std::less<int>(), rhs_alloc);113 copy = orig;114 assert(copy.size() == 0);115 assert(copy.begin() == copy.end());116 117 // Check that orig is still what is expected118 assert(orig.size() == 0);119 assert(orig.begin() == orig.end());120 }121 }122 123 { // Ensure that self-assignment works correctly124 { // with a non-empty multiset125 using Set = std::multiset<int, std::less<int>, Alloc>;126 127 int arr[] = {1, 2, 2};128 Set orig(std::begin(arr), std::end(arr), std::less<int>(), rhs_alloc);129 orig = static_cast<const Set&>(orig);130 131 assert(orig.size() == 3);132 assert(*std::next(orig.begin(), 0) == 1);133 assert(*std::next(orig.begin(), 1) == 2);134 assert(*std::next(orig.begin(), 2) == 2);135 assert(std::next(orig.begin(), 3) == orig.end());136 }137 { // with an empty multiset138 using Set = std::multiset<int, std::less<int>, Alloc>;139 140 Set orig(rhs_alloc);141 orig = static_cast<const Set&>(orig);142 143 assert(orig.size() == 0);144 assert(orig.begin() == orig.end());145 }146 }147 148 { // check assignment into a non-empty multiset149 check_alloc_invariant();150 { // LHS already contains elements, but fewer than the RHS151 using Set = std::multiset<int, std::less<int>, Alloc>;152 153 int lhs_arr[] = {1, 2, 2};154 const Set orig(std::begin(lhs_arr), std::end(lhs_arr), std::less<int>(), rhs_alloc);155 156 int rhs_arr[] = {4, 5};157 Set copy(std::begin(rhs_arr), std::end(rhs_arr), std::less<int>(), lhs_alloc);158 copy = orig;159 assert(copy.size() == 3);160 assert(*std::next(copy.begin(), 0) == 1);161 assert(*std::next(copy.begin(), 1) == 2);162 assert(*std::next(copy.begin(), 2) == 2);163 assert(std::next(copy.begin(), 3) == copy.end());164 165 // Check that orig is still what is expected166 assert(orig.size() == 3);167 assert(*std::next(orig.begin(), 0) == 1);168 assert(*std::next(orig.begin(), 1) == 2);169 assert(*std::next(orig.begin(), 2) == 2);170 assert(std::next(orig.begin(), 3) == orig.end());171 }172 check_alloc_invariant();173 { // LHS contains the same number of elements as the RHS174 using Set = std::multiset<int, std::less<int>, Alloc>;175 176 int lhs_arr[] = {1, 2, 2};177 const Set orig(std::begin(lhs_arr), std::end(lhs_arr), std::less<int>(), rhs_alloc);178 179 int rhs_arr[] = {4, 5, 6};180 Set copy(std::begin(rhs_arr), std::end(rhs_arr), std::less<int>(), lhs_alloc);181 copy = orig;182 assert(copy.size() == 3);183 assert(*std::next(copy.begin(), 0) == 1);184 assert(*std::next(copy.begin(), 1) == 2);185 assert(*std::next(copy.begin(), 2) == 2);186 assert(std::next(copy.begin(), 3) == copy.end());187 188 // Check that orig is still what is expected189 assert(orig.size() == 3);190 assert(*std::next(orig.begin(), 0) == 1);191 assert(*std::next(orig.begin(), 1) == 2);192 assert(*std::next(orig.begin(), 2) == 2);193 assert(std::next(orig.begin(), 3) == orig.end());194 }195 check_alloc_invariant();196 { // LHS already contains more elements than the RHS197 using Set = std::multiset<int, std::less<int>, Alloc>;198 199 int lhs_arr[] = {1, 2, 2};200 const Set orig(std::begin(lhs_arr), std::end(lhs_arr), std::less<int>(), rhs_alloc);201 202 int rhs_arr[] = {4, 5, 6};203 Set copy(std::begin(rhs_arr), std::end(rhs_arr), std::less<int>(), lhs_alloc);204 copy = orig;205 assert(copy.size() == 3);206 assert(*std::next(copy.begin(), 0) == 1);207 assert(*std::next(copy.begin(), 1) == 2);208 assert(*std::next(copy.begin(), 2) == 2);209 assert(std::next(copy.begin(), 3) == copy.end());210 211 // Check that orig is still what is expected212 assert(orig.size() == 3);213 assert(*std::next(orig.begin(), 0) == 1);214 assert(*std::next(orig.begin(), 1) == 2);215 assert(*std::next(orig.begin(), 2) == 2);216 assert(std::next(orig.begin(), 3) == orig.end());217 }218 check_alloc_invariant();219 { // Make a somewhat larger multiset to exercise the algorithm a bit220 using Set = std::multiset<int, std::less<int>, Alloc>;221 222 Set orig(rhs_alloc);223 for (int i = 0; i != 50; ++i)224 orig.insert(i);225 226 Set copy(lhs_alloc);227 copy = orig;228 int i = 0;229 for (auto v : copy) {230 assert(v == i++);231 }232 }233 check_alloc_invariant();234 }235}236 237void test() {238 test_alloc<std::allocator<int> >();239#if TEST_STD_VER >= 11240 test_alloc<min_allocator<int> >();241 242 { // Make sure we're allocating/deallocating nodes with the correct allocator243 // See https://llvm.org/PR29001244 class AssertEmpty {245 std::vector<void*>* lhs_allocs_;246 std::vector<void*>* rhs_allocs_;247 248 public:249 AssertEmpty(std::vector<void*>& lhs_allocs, std::vector<void*>& rhs_allocs)250 : lhs_allocs_(&lhs_allocs), rhs_allocs_(&rhs_allocs) {}251 252 void operator()() {253 assert(lhs_allocs_->empty());254 assert(rhs_allocs_->empty());255 }256 };257 258 std::vector<void*> lhs_allocs;259 std::vector<void*> rhs_allocs;260 test_alloc<tracking_allocator<int> >(lhs_allocs, rhs_allocs, AssertEmpty(lhs_allocs, rhs_allocs));261 }262#endif263 264 { // Ensure that the comparator is copied265 int arr[] = {1, 2, 2};266 const std::multiset<int, test_less<int> > orig(std::begin(arr), std::end(arr), test_less<int>(3));267 std::multiset<int, test_less<int> > copy;268 copy = orig;269 assert(copy.size() == 3);270 assert(copy.key_comp() == test_less<int>(3));271 272 // Check that orig is still what is expected273 assert(orig.size() == 3);274 assert(orig.key_comp() == test_less<int>(3));275 }276}277 278int main(int, char**) {279 test();280 281 return 0;282}283