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#ifndef SUPPORT_FLAT_MULTIMAP_HELPERS_H
10#define SUPPORT_FLAT_MULTIMAP_HELPERS_H
11
12#include <algorithm>
13#include <cassert>
14#include <string>
15#include <vector>
16#include <flat_map>
17
18#include "../flat_helpers.h"
19#include "test_allocator.h"
20#include "test_macros.h"
21
22template <class... Args>
23void check_invariant(const std::flat_multimap<Args...>& m) {
24 assert(m.keys().size() == m.values().size());
25 const auto& keys = m.keys();
26 assert(std::is_sorted(keys.begin(), keys.end(), m.key_comp()));
27}
28
29template <class F>
30void test_emplace_exception_guarantee([[maybe_unused]] F&& emplace_function) {
31#ifndef TEST_HAS_NO_EXCEPTIONS
32 using C = TransparentComparator;
33 {
34 // Throw on emplace the key, and underlying has strong exception guarantee
35 using KeyContainer = std::vector<int, test_allocator<int>>;
36 using M = std::flat_multimap<int, int, C, KeyContainer>;
37
38 LIBCPP_STATIC_ASSERT(std::__container_traits<KeyContainer>::__emplacement_has_strong_exception_safety_guarantee);
39
40 test_allocator_statistics stats;
41
42 KeyContainer a({1, 1, 2, 4}, test_allocator<int>{&stats});
43 std::vector<int> b = {5, 6, 7, 8};
44 [[maybe_unused]] auto expected_keys = a;
45 [[maybe_unused]] auto expected_values = b;
46 M m(std::sorted_equivalent, std::move(a), std::move(b));
47
48 stats.throw_after = 1;
49 try {
50 emplace_function(m, 1, 1);
51 assert(false);
52 } catch (const std::bad_alloc&) {
53 check_invariant(m);
54 // In libc++, the flat_multimap is unchanged
55 LIBCPP_ASSERT(m.size() == 4);
56 LIBCPP_ASSERT(m.keys() == expected_keys);
57 LIBCPP_ASSERT(m.values() == expected_values);
58 }
59 }
60 {
61 // Throw on emplace the key, and underlying has no strong exception guarantee
62 using KeyContainer = EmplaceUnsafeContainer<int>;
63 using M = std::flat_multimap<int, int, C, KeyContainer>;
64
65 LIBCPP_STATIC_ASSERT(!std::__container_traits<KeyContainer>::__emplacement_has_strong_exception_safety_guarantee);
66 KeyContainer a = {1, 2, 2, 4};
67 std::vector<int> b = {5, 6, 7, 8};
68 M m(std::sorted_equivalent, std::move(a), std::move(b));
69 try {
70 emplace_function(m, 1, 1);
71 assert(false);
72 } catch (int) {
73 check_invariant(m);
74 // In libc++, the flat_multimap is cleared
75 LIBCPP_ASSERT(m.size() == 0);
76 }
77 }
78 {
79 // Throw on emplace the value, and underlying has strong exception guarantee
80 using ValueContainer = std::vector<int, test_allocator<int>>;
81 ;
82 using M = std::flat_multimap<int, int, C, std::vector<int>, ValueContainer>;
83
84 LIBCPP_STATIC_ASSERT(std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);
85
86 std::vector<int> a = {1, 3, 3, 4};
87 test_allocator_statistics stats;
88 ValueContainer b({1, 2, 3, 4}, test_allocator<int>{&stats});
89
90 [[maybe_unused]] auto expected_keys = a;
91 [[maybe_unused]] auto expected_values = b;
92 M m(std::sorted_equivalent, std::move(a), std::move(b));
93
94 stats.throw_after = 1;
95 try {
96 emplace_function(m, 3, 3);
97 assert(false);
98 } catch (const std::bad_alloc&) {
99 check_invariant(m);
100 // In libc++, the emplaced key is erased and the flat_multimap is unchanged
101 LIBCPP_ASSERT(m.size() == 4);
102 LIBCPP_ASSERT(m.keys() == expected_keys);
103 LIBCPP_ASSERT(m.values() == expected_values);
104 }
105 }
106 {
107 // Throw on emplace the value, and underlying has no strong exception guarantee
108 using ValueContainer = EmplaceUnsafeContainer<int>;
109 using M = std::flat_multimap<int, int, C, std::vector<int>, ValueContainer>;
110
111 LIBCPP_STATIC_ASSERT(!std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);
112 std::vector<int> a = {1, 1, 1, 1};
113 ValueContainer b = {1, 2, 3, 4};
114
115 M m(std::sorted_equivalent, std::move(a), std::move(b));
116
117 try {
118 emplace_function(m, 1, 5);
119 assert(false);
120 } catch (int) {
121 check_invariant(m);
122 // In libc++, the flat_multimap is cleared
123 LIBCPP_ASSERT(m.size() == 0);
124 }
125 }
126 {
127 // Throw on emplace the value, then throw again on erasing the key
128 using KeyContainer = ThrowOnEraseContainer<int>;
129 using ValueContainer = std::vector<int, test_allocator<int>>;
130 using M = std::flat_multimap<int, int, C, KeyContainer, ValueContainer>;
131
132 LIBCPP_STATIC_ASSERT(std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);
133
134 KeyContainer a = {4, 4, 4, 4};
135 test_allocator_statistics stats;
136 ValueContainer b({1, 2, 3, 4}, test_allocator<int>{&stats});
137
138 M m(std::sorted_equivalent, std::move(a), std::move(b));
139 stats.throw_after = 1;
140 try {
141 emplace_function(m, 0, 0);
142 assert(false);
143 } catch (const std::bad_alloc&) {
144 check_invariant(m);
145 // In libc++, we try to erase the key after value emplacement failure.
146 // and after erasure failure, we clear the flat_multimap
147 LIBCPP_ASSERT(m.size() == 0);
148 }
149 }
150#endif
151}
152
153template <class F>
154void test_insert_range_exception_guarantee([[maybe_unused]] F&& insert_function) {
155#ifndef TEST_HAS_NO_EXCEPTIONS
156 using KeyContainer = EmplaceUnsafeContainer<int>;
157 using ValueContainer = std::vector<int>;
158 using M = std::flat_multimap<int, int, std::ranges::less, KeyContainer, ValueContainer>;
159 test_allocator_statistics stats;
160 KeyContainer a{1, 2, 3, 4};
161 ValueContainer b{1, 2, 3, 4};
162 M m(std::sorted_equivalent, std::move(a), std::move(b));
163
164 std::vector<std::pair<int, int>> newValues = {{0, 0}, {1, 1}, {5, 5}, {6, 6}, {7, 7}, {8, 8}};
165 stats.throw_after = 1;
166 try {
167 insert_function(m, newValues);
168 assert(false);
169 } catch (int) {
170 check_invariant(m);
171 // In libc++, we clear if anything goes wrong when inserting a range
172 LIBCPP_ASSERT(m.size() == 0);
173 }
174#endif
175}
176
177template <class F>
178void test_erase_exception_guarantee([[maybe_unused]] F&& erase_function) {
179#ifndef TEST_HAS_NO_EXCEPTIONS
180 {
181 // key erase throws
182 using KeyContainer = ThrowOnEraseContainer<int>;
183 using ValueContainer = std::vector<int>;
184 using M = std::flat_multimap<int, int, TransparentComparator, KeyContainer, ValueContainer>;
185
186 KeyContainer a{1, 3, 3, 4};
187 ValueContainer b{1, 3, 3, 4};
188 M m(std::sorted_equivalent, std::move(a), std::move(b));
189 try {
190 erase_function(m, 3);
191 assert(false);
192 } catch (int) {
193 check_invariant(m);
194 // In libc++, we clear if anything goes wrong when erasing
195 LIBCPP_ASSERT(m.size() == 0);
196 }
197 }
198 {
199 // key erase throws
200 using KeyContainer = std::vector<int>;
201 using ValueContainer = ThrowOnEraseContainer<int>;
202 using M = std::flat_multimap<int, int, TransparentComparator, KeyContainer, ValueContainer>;
203
204 KeyContainer a{1, 3, 3, 4};
205 ValueContainer b{1, 3, 3, 4};
206 M m(std::sorted_equivalent, std::move(a), std::move(b));
207 try {
208 erase_function(m, 3);
209 assert(false);
210 } catch (int) {
211 check_invariant(m);
212 // In libc++, we clear if anything goes wrong when erasing
213 LIBCPP_ASSERT(m.size() == 0);
214 }
215 }
216#endif
217}
218
219#endif // SUPPORT_FLAT_MULTIMAP_HELPERS_H
220

source code of libcxx/test/std/containers/container.adaptors/flat.multimap/helpers.h