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

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