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_INSERT_RANGE_MAPS_SETS_H |
10 | #define SUPPORT_INSERT_RANGE_MAPS_SETS_H |
11 | |
12 | #include <algorithm> |
13 | #include <array> |
14 | #include <cassert> |
15 | #include <concepts> |
16 | #include <ranges> |
17 | #include <type_traits> |
18 | #include <vector> |
19 | |
20 | #include "MoveOnly.h" |
21 | #include "almost_satisfies_types.h" |
22 | #include "count_new.h" |
23 | #include "exception_safety_helpers.h" |
24 | #include "insert_range_helpers.h" |
25 | #include "min_allocator.h" |
26 | #include "test_allocator.h" |
27 | #include "test_compare.h" |
28 | #include "test_hash.h" |
29 | #include "test_iterators.h" |
30 | #include "test_macros.h" |
31 | #include "type_algorithms.h" |
32 | |
33 | template <class Container, class Range> |
34 | concept HasInsertRange = requires(Container& c, Range&& range) { c.insert_range(range); }; |
35 | |
36 | template <template <class...> class Container, class T, class U> |
37 | constexpr bool test_set_constraints_insert_range() { |
38 | // Input range with the same value type. |
39 | static_assert(HasInsertRange<Container<T>, InputRange<T>>); |
40 | // Input range with a convertible value type. |
41 | static_assert(HasInsertRange<Container<T>, InputRange<U>>); |
42 | // Input range with a non-convertible value type. |
43 | static_assert(!HasInsertRange<Container<T>, InputRange<Empty>>); |
44 | // Not an input range. |
45 | static_assert(!HasInsertRange<Container<T>, InputRangeNotDerivedFrom>); |
46 | static_assert(!HasInsertRange<Container<T>, InputRangeNotIndirectlyReadable>); |
47 | static_assert(!HasInsertRange<Container<T>, InputRangeNotInputOrOutputIterator>); |
48 | |
49 | return true; |
50 | } |
51 | |
52 | template <template <class...> class Container, class K, class V, class K2, class V2> |
53 | constexpr bool test_map_constraints_insert_range() { |
54 | using ValueType = std::pair<const K, V>; |
55 | |
56 | // Input range with the same value type. |
57 | static_assert(HasInsertRange<Container<K, V>, InputRange<ValueType>>); |
58 | // Input range with a convertible value type. |
59 | static_assert(HasInsertRange<Container<K, V>, InputRange<std::pair<const K2, V2>>>); |
60 | // Input range with a non-convertible value type. |
61 | static_assert(!HasInsertRange<Container<K, V>, InputRange<std::pair<const K, Empty>>>); |
62 | static_assert(!HasInsertRange<Container<K, V>, InputRange<std::pair<const Empty, V>>>); |
63 | // Not an input range. |
64 | static_assert(!HasInsertRange<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>); |
65 | |
66 | return true; |
67 | } |
68 | |
69 | template <class T> |
70 | struct TestCaseMapSet { |
71 | Buffer<T> initial; |
72 | Buffer<T> input; |
73 | Buffer<T> expected; |
74 | Buffer<T> expected_multi; |
75 | }; |
76 | |
77 | // Empty container. |
78 | |
79 | template <class T> |
80 | TestCaseMapSet<T> constexpr EmptyContainer_EmptyRange{.initial = {}, .input = {}, .expected = {}}; |
81 | |
82 | template <class T> |
83 | TestCaseMapSet<T> constexpr EmptyContainer_OneElementRange{.initial = {}, .input = {1}, .expected = {1}}; |
84 | template <class K, class V> |
85 | TestCaseMapSet<std::pair<K, V>> constexpr EmptyContainer_OneElementRange<std::pair<K, V>>{ |
86 | .initial = {}, .input = {{1, 'a'}}, .expected = {{1, 'a'}}}; |
87 | |
88 | template <class T> |
89 | TestCaseMapSet<T> constexpr EmptyContainer_RangeNoDuplicates{ |
90 | .initial = {}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6}}; |
91 | template <class K, class V> |
92 | TestCaseMapSet<std::pair<K, V>> constexpr EmptyContainer_RangeNoDuplicates<std::pair<K, V>>{ |
93 | .initial = {}, |
94 | .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}}, |
95 | .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}}}; |
96 | |
97 | template <class T> |
98 | TestCaseMapSet<T> constexpr EmptyContainer_RangeWithDuplicates{ |
99 | .initial = {}, |
100 | .input = {5, 1, 1, 3, 5, 8, 5, 6, 10}, |
101 | .expected = {5, 1, 3, 8, 6, 10}, |
102 | .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10}}; |
103 | template <class K, class V> |
104 | TestCaseMapSet<std::pair<K, V>> constexpr EmptyContainer_RangeWithDuplicates<std::pair<K, V>>{ |
105 | .initial = {}, |
106 | .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}}, |
107 | .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'b'}}, |
108 | .expected_multi = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}}}; |
109 | |
110 | // One-element container. |
111 | |
112 | template <class T> |
113 | TestCaseMapSet<T> constexpr OneElementContainer_EmptyRange{.initial = {10}, .input = {}, .expected = {10}}; |
114 | template <class K, class V> |
115 | TestCaseMapSet<std::pair<K, V>> constexpr OneElementContainer_EmptyRange<std::pair<K, V>>{ |
116 | .initial = {{10, 'A'}}, .input = {}, .expected = {{10, 'A'}}}; |
117 | |
118 | template <class T> |
119 | TestCaseMapSet<T> constexpr OneElementContainer_OneElementRange{.initial = {10}, .input = {1}, .expected = {1, 10}}; |
120 | template <class K, class V> |
121 | TestCaseMapSet<std::pair<K, V>> constexpr OneElementContainer_OneElementRange<std::pair<K, V>>{ |
122 | .initial = {{10, 'A'}}, .input = {{1, 'a'}}, .expected = {{1, 'a'}, {10, 'A'}}}; |
123 | |
124 | template <class T> |
125 | TestCaseMapSet<T> constexpr OneElementContainer_RangeNoDuplicates{ |
126 | .initial = {10}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6, 10}}; |
127 | template <class K, class V> |
128 | TestCaseMapSet<std::pair<K, V>> constexpr OneElementContainer_RangeNoDuplicates<std::pair<K, V>>{ |
129 | .initial = {{10, 'A'}}, |
130 | .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}}, |
131 | .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}, {10, 'A'}}}; |
132 | |
133 | template <class T> |
134 | TestCaseMapSet<T> constexpr OneElementContainer_RangeWithDuplicates{ |
135 | .initial = {10}, |
136 | .input = {5, 1, 1, 3, 5, 8, 5, 6, 10}, |
137 | .expected = {5, 1, 3, 8, 6, 10}, |
138 | .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10, 10}}; |
139 | template <class K, class V> |
140 | TestCaseMapSet<std::pair<K, V>> constexpr OneElementContainer_RangeWithDuplicates<std::pair<K, V>>{ |
141 | .initial = {{10, 'A'}}, |
142 | .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}}, |
143 | .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'A'}}, |
144 | .expected_multi = { |
145 | {5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'A'}, {10, 'b'}}}; |
146 | |
147 | // N-elements container. |
148 | |
149 | template <class T> |
150 | TestCaseMapSet<T> constexpr NElementsContainer_EmptyRange{ |
151 | .initial = {10, 15, 19, 16}, .input = {}, .expected = {10, 15, 19, 16}}; |
152 | template <class K, class V> |
153 | TestCaseMapSet<std::pair<K, V>> constexpr NElementsContainer_EmptyRange<std::pair<K, V>>{ |
154 | .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, |
155 | .input = {}, |
156 | .expected = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}}; |
157 | |
158 | template <class T> |
159 | TestCaseMapSet<T> constexpr NElementsContainer_OneElementRange{ |
160 | .initial = {10, 15, 19, 16}, .input = {1}, .expected = {1, 10, 15, 19, 16}}; |
161 | template <class K, class V> |
162 | TestCaseMapSet<std::pair<K, V>> constexpr NElementsContainer_OneElementRange<std::pair<K, V>>{ |
163 | .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, |
164 | .input = {{1, 'a'}}, |
165 | .expected = {{1, 'a'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}}; |
166 | |
167 | template <class T> |
168 | TestCaseMapSet<T> constexpr NElementsContainer_RangeNoDuplicates{ |
169 | .initial = {10, 15, 19, 16}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6, 10, 15, 19, 16}}; |
170 | template <class K, class V> |
171 | TestCaseMapSet<std::pair<K, V>> constexpr NElementsContainer_RangeNoDuplicates<std::pair<K, V>>{ |
172 | .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, |
173 | .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}}, |
174 | .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}}; |
175 | |
176 | template <class T> |
177 | TestCaseMapSet<T> constexpr NElementsContainer_RangeWithDuplicates{ |
178 | .initial = {10, 15, 19, 16}, |
179 | .input = {5, 1, 1, 3, 5, 8, 5, 6, 10}, |
180 | .expected = {5, 1, 3, 8, 6, 10, 15, 19, 16}, |
181 | .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10, 10, 15, 19, 16}}; |
182 | template <class K, class V> |
183 | TestCaseMapSet<std::pair<K, V>> constexpr NElementsContainer_RangeWithDuplicates<std::pair<K, V>>{ |
184 | .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, |
185 | .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}}, |
186 | .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, |
187 | .expected_multi = { |
188 | {5, 'a'}, |
189 | {1, 'a'}, |
190 | {1, 'b'}, |
191 | {3, 'a'}, |
192 | {5, 'b'}, |
193 | {8, 'a'}, |
194 | {5, 'c'}, |
195 | {6, 'a'}, |
196 | {10, 'b'}, |
197 | {10, 'A'}, |
198 | {15, 'B'}, |
199 | {19, 'C'}, |
200 | {16, 'D'}}}; |
201 | |
202 | template <class Container, class T, class Iter, class Sent> |
203 | void test_map_set_insert_range(bool allow_duplicates = false) { |
204 | auto test = [&](const TestCaseMapSet<T>& test_case, bool check_multi = false) { |
205 | Container c(test_case.initial.begin(), test_case.initial.end()); |
206 | auto in = wrap_input<Iter, Sent>(test_case.input); |
207 | |
208 | c.insert_range(in); |
209 | if (check_multi) { |
210 | return std::ranges::is_permutation(c, test_case.expected_multi); |
211 | } else { |
212 | return std::ranges::is_permutation(c, test_case.expected); |
213 | } |
214 | }; |
215 | |
216 | { // Empty container. |
217 | // empty_c.insert_range(empty_range) |
218 | assert(test(EmptyContainer_EmptyRange<T>)); |
219 | // empty_c.insert_range(one_element_range) |
220 | assert(test(EmptyContainer_OneElementRange<T>)); |
221 | // empty_c.insert_range(range_no_duplicates) |
222 | assert(test(EmptyContainer_RangeNoDuplicates<T>)); |
223 | // empty_c.insert_range(range_with_duplicates) |
224 | assert(test(EmptyContainer_RangeWithDuplicates<T>, allow_duplicates)); |
225 | } |
226 | |
227 | { // One-element container. |
228 | // one_element_c.insert_range(empty_range) |
229 | assert(test(OneElementContainer_EmptyRange<T>)); |
230 | // one_element_c.insert_range(one_element_range) |
231 | assert(test(OneElementContainer_OneElementRange<T>)); |
232 | // one_element_c.insert_range(range_no_duplicates) |
233 | assert(test(OneElementContainer_RangeNoDuplicates<T>)); |
234 | // one_element_c.insert_range(range_with_duplicates) |
235 | assert(test(OneElementContainer_RangeWithDuplicates<T>, allow_duplicates)); |
236 | } |
237 | |
238 | { // N-elements container. |
239 | // n_elements_c.insert_range(empty_range) |
240 | assert(test(NElementsContainer_EmptyRange<T>)); |
241 | // n_elements_c.insert_range(one_element_range) |
242 | assert(test(NElementsContainer_OneElementRange<T>)); |
243 | // n_elements_c.insert_range(range_no_duplicates) |
244 | assert(test(NElementsContainer_RangeNoDuplicates<T>)); |
245 | // n_elements_c.insert_range(range_with_duplicates) |
246 | assert(test(NElementsContainer_RangeWithDuplicates<T>, allow_duplicates)); |
247 | } |
248 | } |
249 | |
250 | // Move-only types. |
251 | |
252 | template <template <class...> class Container> |
253 | void test_set_insert_range_move_only() { |
254 | MoveOnly input[5]; |
255 | std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); |
256 | |
257 | Container<MoveOnly> c; |
258 | c.insert_range(in); |
259 | } |
260 | |
261 | template <template <class...> class Container> |
262 | void test_map_insert_range_move_only() { |
263 | using Value = std::pair<const int, MoveOnly>; |
264 | Value input[5]; |
265 | std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); |
266 | |
267 | Container<int, MoveOnly> c; |
268 | c.insert_range(in); |
269 | } |
270 | |
271 | // Exception safety. |
272 | |
273 | template <template <class...> class Container> |
274 | void test_set_insert_range_exception_safety_throwing_copy() { |
275 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
276 | using T = ThrowingCopy<3>; |
277 | T::reset(); |
278 | T in[5] = {{1}, {2}, {3}, {4}, {5}}; |
279 | |
280 | try { |
281 | Container<T> c; |
282 | c.insert_range(in); |
283 | assert(false); // The constructor call above should throw. |
284 | |
285 | } catch (int) { |
286 | assert(T::created_by_copying == 3); |
287 | assert(T::destroyed == 2); // No destructor call for the partially-constructed element. |
288 | } |
289 | #endif |
290 | } |
291 | |
292 | template <template <class...> class Container> |
293 | void test_map_insert_range_exception_safety_throwing_copy() { |
294 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
295 | using K = int; |
296 | using V = ThrowingCopy<3>; |
297 | |
298 | V::throwing_enabled = false; |
299 | std::pair<const K, V> in[5] = {{1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}}}; |
300 | V::throwing_enabled = true; |
301 | V::reset(); |
302 | |
303 | try { |
304 | Container<K, V> c; |
305 | c.insert_range(in); |
306 | assert(false); // The function call above should throw. |
307 | |
308 | } catch (int) { |
309 | assert(V::created_by_copying == 3); |
310 | assert(V::destroyed == 2); // No destructor call for the partially-constructed element. |
311 | } |
312 | #endif |
313 | } |
314 | |
315 | template <template <class...> class Container, class T> |
316 | void test_assoc_set_insert_range_exception_safety_throwing_allocator() { |
317 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
318 | T in[] = {1, 2}; |
319 | |
320 | try { |
321 | ThrowingAllocator<T> alloc; |
322 | |
323 | globalMemCounter.reset(); |
324 | Container<T, test_less<T>, ThrowingAllocator<T>> c(alloc); |
325 | c.insert_range(in); |
326 | assert(false); // The function call above should throw. |
327 | |
328 | } catch (int) { |
329 | assert(globalMemCounter.new_called == globalMemCounter.delete_called); |
330 | } |
331 | #endif |
332 | } |
333 | |
334 | template <template <class...> class Container, class T> |
335 | void test_unord_set_insert_range_exception_safety_throwing_allocator() { |
336 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
337 | T in[] = {1, 2}; |
338 | |
339 | try { |
340 | ThrowingAllocator<T> alloc; |
341 | |
342 | globalMemCounter.reset(); |
343 | Container<T, test_hash<T>, test_equal_to<T>, ThrowingAllocator<T>> c(alloc); |
344 | c.insert_range(in); |
345 | assert(false); // The function call above should throw. |
346 | |
347 | } catch (int) { |
348 | assert(globalMemCounter.new_called == globalMemCounter.delete_called); |
349 | } |
350 | #endif |
351 | } |
352 | |
353 | template <template <class...> class Container, class K, class V> |
354 | void test_assoc_map_insert_range_exception_safety_throwing_allocator() { |
355 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
356 | using ValueType = std::pair<const K, V>; |
357 | ValueType in[] = {ValueType{K{1}, V{1}}}; |
358 | |
359 | try { |
360 | ThrowingAllocator<ValueType> alloc; |
361 | |
362 | globalMemCounter.reset(); |
363 | Container<K, V, test_less<K>, ThrowingAllocator<ValueType>> c(alloc); |
364 | c.insert_range(in); |
365 | assert(false); // The function call above should throw. |
366 | |
367 | } catch (int) { |
368 | assert(globalMemCounter.new_called == globalMemCounter.delete_called); |
369 | } |
370 | #endif |
371 | } |
372 | |
373 | template <template <class...> class Container, class K, class V> |
374 | void test_unord_map_insert_range_exception_safety_throwing_allocator() { |
375 | #if !defined(TEST_HAS_NO_EXCEPTIONS) |
376 | using ValueType = std::pair<const K, V>; |
377 | ValueType in[] = {ValueType{K{1}, V{1}}}; |
378 | |
379 | try { |
380 | ThrowingAllocator<ValueType> alloc; |
381 | |
382 | globalMemCounter.reset(); |
383 | Container<K, V, test_hash<K>, test_equal_to<K>, ThrowingAllocator<ValueType>> c(alloc); |
384 | c.insert_range(in); |
385 | assert(false); // The function call above should throw. |
386 | |
387 | } catch (int) { |
388 | assert(globalMemCounter.new_called == globalMemCounter.delete_called); |
389 | } |
390 | #endif |
391 | } |
392 | |
393 | #endif // SUPPORT_INSERT_RANGE_MAPS_SETS_H |
394 |
Definitions
- HasInsertRange
- test_set_constraints_insert_range
- test_map_constraints_insert_range
- TestCaseMapSet
- EmptyContainer_EmptyRange
- EmptyContainer_OneElementRange
- EmptyContainer_OneElementRange
- EmptyContainer_RangeNoDuplicates
- EmptyContainer_RangeNoDuplicates
- EmptyContainer_RangeWithDuplicates
- EmptyContainer_RangeWithDuplicates
- OneElementContainer_EmptyRange
- OneElementContainer_EmptyRange
- OneElementContainer_OneElementRange
- OneElementContainer_OneElementRange
- OneElementContainer_RangeNoDuplicates
- OneElementContainer_RangeNoDuplicates
- OneElementContainer_RangeWithDuplicates
- OneElementContainer_RangeWithDuplicates
- NElementsContainer_EmptyRange
- NElementsContainer_EmptyRange
- NElementsContainer_OneElementRange
- NElementsContainer_OneElementRange
- NElementsContainer_RangeNoDuplicates
- NElementsContainer_RangeNoDuplicates
- NElementsContainer_RangeWithDuplicates
- NElementsContainer_RangeWithDuplicates
- test_map_set_insert_range
- test_set_insert_range_move_only
- test_map_insert_range_move_only
- test_set_insert_range_exception_safety_throwing_copy
- test_map_insert_range_exception_safety_throwing_copy
- test_assoc_set_insert_range_exception_safety_throwing_allocator
- test_unord_set_insert_range_exception_safety_throwing_allocator
- test_assoc_map_insert_range_exception_safety_throwing_allocator
Improve your Profiling and Debugging skills
Find out more