285 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 set12 13// set& operator=(const set& s);14 15#include <algorithm>16#include <cassert>17#include <cstdio>18#include <iterator>19#include <set>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 set combinations74 { // assign from a non-empty container into an empty one75 using Set = std::set<int, std::less<int>, Alloc>;76 77 int arr[] = {1, 2, 3};78 const Set orig(std::begin(arr), std::end(arr), std::less<int>(), rhs_alloc);79 Set copy(lhs_alloc);80 copy = orig;81 assert(copy.size() == 3);82 assert(*std::next(copy.begin(), 0) == 1);83 assert(*std::next(copy.begin(), 1) == 2);84 assert(*std::next(copy.begin(), 2) == 3);85 assert(std::next(copy.begin(), 3) == copy.end());86 87 // Check that orig is still what is expected88 assert(orig.size() == 3);89 assert(*std::next(orig.begin(), 0) == 1);90 assert(*std::next(orig.begin(), 1) == 2);91 assert(*std::next(orig.begin(), 2) == 3);92 assert(std::next(orig.begin(), 3) == orig.end());93 }94 check_alloc_invariant();95 { // assign from an empty container into an empty one96 using Set = std::set<int, std::less<int>, Alloc>;97 98 const Set orig(rhs_alloc);99 Set copy(lhs_alloc);100 copy = orig;101 assert(copy.size() == 0);102 assert(copy.begin() == copy.end());103 104 // Check that orig is still what is expected105 assert(orig.size() == 0);106 assert(orig.begin() == orig.end());107 }108 check_alloc_invariant();109 { // assign from an empty container into a non-empty one110 using Set = std::set<int, std::less<int>, Alloc>;111 112 int arr[] = {1, 2, 3};113 const Set orig(rhs_alloc);114 Set copy(std::begin(arr), std::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 set127 using Set = std::set<int, std::less<int>, Alloc>;128 129 int arr[] = {1, 2, 3};130 Set orig(std::begin(arr), std::end(arr), std::less<int>(), rhs_alloc);131 orig = static_cast<const Set&>(orig);132 133 assert(orig.size() == 3);134 assert(*std::next(orig.begin(), 0) == 1);135 assert(*std::next(orig.begin(), 1) == 2);136 assert(*std::next(orig.begin(), 2) == 3);137 assert(std::next(orig.begin(), 3) == orig.end());138 }139 { // with an empty set140 using Set = std::set<int, std::less<int>, Alloc>;141 142 Set orig(rhs_alloc);143 orig = static_cast<const Set&>(orig);144 145 assert(orig.size() == 0);146 assert(orig.begin() == orig.end());147 }148 }149 150 { // check assignment into a non-empty set151 check_alloc_invariant();152 { // LHS already contains elements, but fewer than the RHS153 using Set = std::set<int, std::less<int>, Alloc>;154 155 int lhs_arr[] = {1, 2, 3};156 const Set orig(std::begin(lhs_arr), std::end(lhs_arr), std::less<int>(), rhs_alloc);157 158 int rhs_arr[] = {4, 5};159 Set copy(std::begin(rhs_arr), std::end(rhs_arr), std::less<int>(), lhs_alloc);160 copy = orig;161 assert(copy.size() == 3);162 assert(*std::next(copy.begin(), 0) == 1);163 assert(*std::next(copy.begin(), 1) == 2);164 assert(*std::next(copy.begin(), 2) == 3);165 assert(std::next(copy.begin(), 3) == copy.end());166 167 // Check that orig is still what is expected168 assert(orig.size() == 3);169 assert(*std::next(orig.begin(), 0) == 1);170 assert(*std::next(orig.begin(), 1) == 2);171 assert(*std::next(orig.begin(), 2) == 3);172 assert(std::next(orig.begin(), 3) == orig.end());173 }174 check_alloc_invariant();175 { // LHS contains the same number of elements as the RHS176 using Set = std::set<int, std::less<int>, Alloc>;177 178 int lhs_arr[] = {1, 2, 3};179 const Set orig(std::begin(lhs_arr), std::end(lhs_arr), std::less<int>(), rhs_alloc);180 181 int rhs_arr[] = {4, 5, 6};182 Set copy(std::begin(rhs_arr), std::end(rhs_arr), std::less<int>(), lhs_alloc);183 copy = orig;184 assert(copy.size() == 3);185 assert(*std::next(copy.begin(), 0) == 1);186 assert(*std::next(copy.begin(), 1) == 2);187 assert(*std::next(copy.begin(), 2) == 3);188 assert(std::next(copy.begin(), 3) == copy.end());189 190 // Check that orig is still what is expected191 assert(orig.size() == 3);192 assert(*std::next(orig.begin(), 0) == 1);193 assert(*std::next(orig.begin(), 1) == 2);194 assert(*std::next(orig.begin(), 2) == 3);195 assert(std::next(orig.begin(), 3) == orig.end());196 }197 check_alloc_invariant();198 { // LHS already contains more elements than the RHS199 using Set = std::set<int, std::less<int>, Alloc>;200 201 int lhs_arr[] = {1, 2, 3};202 const Set orig(std::begin(lhs_arr), std::end(lhs_arr), std::less<int>(), rhs_alloc);203 204 int rhs_arr[] = {4, 5, 6};205 Set copy(std::begin(rhs_arr), std::end(rhs_arr), std::less<int>(), lhs_alloc);206 copy = orig;207 assert(copy.size() == 3);208 assert(*std::next(copy.begin(), 0) == 1);209 assert(*std::next(copy.begin(), 1) == 2);210 assert(*std::next(copy.begin(), 2) == 3);211 assert(std::next(copy.begin(), 3) == copy.end());212 213 // Check that orig is still what is expected214 assert(orig.size() == 3);215 assert(*std::next(orig.begin(), 0) == 1);216 assert(*std::next(orig.begin(), 1) == 2);217 assert(*std::next(orig.begin(), 2) == 3);218 assert(std::next(orig.begin(), 3) == orig.end());219 }220 check_alloc_invariant();221 { // Make a somewhat larger set to exercise the algorithm a bit222 using Set = std::set<int, std::less<int>, Alloc>;223 224 Set orig(rhs_alloc);225 for (int i = 0; i != 50; ++i)226 orig.insert(i);227 228 Set copy(lhs_alloc);229 copy = orig;230 int i = 0;231 for (auto v : copy) {232 assert(v == i++);233 }234 }235 check_alloc_invariant();236 }237}238 239void test() {240 test_alloc<std::allocator<int> >();241#if TEST_STD_VER >= 11242 test_alloc<min_allocator<int> >();243 244 { // Make sure we're allocating/deallocating nodes with the correct allocator245 // See https://llvm.org/PR29001246 class AssertEmpty {247 std::vector<void*>* lhs_allocs_;248 std::vector<void*>* rhs_allocs_;249 250 public:251 AssertEmpty(std::vector<void*>& lhs_allocs, std::vector<void*>& rhs_allocs)252 : lhs_allocs_(&lhs_allocs), rhs_allocs_(&rhs_allocs) {}253 254 void operator()() {255 assert(lhs_allocs_->empty());256 assert(rhs_allocs_->empty());257 }258 };259 260 std::vector<void*> lhs_allocs;261 std::vector<void*> rhs_allocs;262 test_alloc<tracking_allocator<int> >(lhs_allocs, rhs_allocs, AssertEmpty(lhs_allocs, rhs_allocs));263 }264#endif265 266 { // Ensure that the comparator is copied267 int arr[] = {1, 2, 3};268 const std::set<int, test_less<int> > orig(std::begin(arr), std::end(arr), test_less<int>(3));269 std::set<int, test_less<int> > copy;270 copy = orig;271 assert(copy.size() == 3);272 assert(copy.key_comp() == test_less<int>(3));273 274 // Check that orig is still what is expected275 assert(orig.size() == 3);276 assert(orig.key_comp() == test_less<int>(3));277 }278}279 280int main(int, char**) {281 test();282 283 return 0;284}285