1 /*
2 Copyright (c) 2019-2021 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #ifndef __TBB_test_common_concurrent_ordered_common_H
18 #define __TBB_test_common_concurrent_ordered_common_H
19
20 #define __TBB_TEST_CPP20_COMPARISONS __TBB_CPP20_COMPARISONS_PRESENT && __TBB_CPP20_CONCEPTS_PRESENT
21
22 #include "config.h"
23
24 #include "common/concurrent_associative_common.h"
25 #include "test_comparisons.h"
26
27 template<typename MyTable>
CheckContainerAllocator(MyTable & table,size_t expected_allocs,size_t expected_frees,bool exact)28 inline void CheckContainerAllocator(MyTable &table, size_t expected_allocs, size_t expected_frees, bool exact) {
29 typename MyTable::allocator_type a = table.get_allocator();
30 CheckAllocator<MyTable>(a, expected_allocs, expected_frees, exact);
31 }
32
33 template<typename Container>
CheckNoAllocations(Container &)34 inline void CheckNoAllocations(Container&) {
35 // TODO: enable
36 // CheckContainerAllocator(cont, 0, 0, false);
37 }
38
39 template <typename Container>
40 struct OrderChecker {
41 typename Container::value_compare& val_comp;
42 typename Container::key_compare& key_comp;
43
OrderCheckerOrderChecker44 OrderChecker(typename Container::value_compare& v_comp, typename Container::key_compare& k_comp)
45 : val_comp(v_comp), key_comp(k_comp) {}
46
operatorOrderChecker47 bool operator()(const typename Container::value_type& lhs, const typename Container::value_type& rhs) {
48 if (AllowMultimapping<Container>::value)
49 // We need to use not greater comparator for multicontainer
50 return !val_comp(rhs, lhs) && !key_comp(Value<Container>::key(rhs), Value<Container>::key(lhs));
51 return val_comp(lhs, rhs) && key_comp(Value<Container>::key(lhs), Value<Container>::key(rhs));
52 }
53 }; // struct OrderChecker
54
55 template <typename Container>
check_container_order(const Container & cont)56 void check_container_order( const Container& cont ) {
57 if (!cont.empty()) {
58 typename Container::key_compare key_comp = cont.key_comp();
59 typename Container::value_compare value_comp = cont.value_comp();
60 OrderChecker<Container> check_order(value_comp, key_comp);
61
62 for (auto it = cont.begin(); std::next(it) != cont.end();) {
63 auto pr_it = it++;
64 REQUIRE_MESSAGE(check_order(*pr_it, *it), "The order of the elements is broken");
65 }
66 }
67 }
68
69 template <typename Container>
test_ordered_methods()70 void test_ordered_methods() {
71 Container cont;
72 const Container& ccont = cont;
73
74 int r, random_threshold = 10, uncontained_key = random_threshold / 2;
75 for (int i = 0; i < 100; ++i) {
76 r = std::rand() % random_threshold;
77 if (r != uncontained_key) {
78 cont.insert(Value<Container>::make(r));
79 }
80 }
81
82 check_container_order(cont);
83
84 typename Container::value_compare val_comp = cont.value_comp();
85 typename Container::iterator l_bound_check, u_bound_check;
86 for (int key = -1; key < random_threshold + 1; ++key) {
87 auto eq_range = cont.equal_range(key);
88 // Check equal_range content
89 for (auto it = eq_range.first; it != eq_range.second; ++it)
90 REQUIRE_MESSAGE(*it == Value<Container>::make(key), "equal_range contains wrong value");
91
92 // Manual search of upper and lower bounds
93 l_bound_check = cont.end();
94 u_bound_check = cont.end();
95 for (auto it = cont.begin(); it != cont.end(); ++it){
96 if (!val_comp(*it, Value<Container>::make(key)) && l_bound_check == cont.end()) {
97 l_bound_check = it;
98 }
99 if (val_comp(Value<Container>::make(key), *it) && u_bound_check == cont.end()) {
100 u_bound_check = it;
101 break;
102 }
103 }
104
105 typename Container::range_type cont_range = cont.range();
106 typename Container::const_range_type ccont_range = ccont.range();
107 REQUIRE_MESSAGE(cont_range.size() == ccont_range.size(), "Incorrect ordered container range size");
108 REQUIRE_MESSAGE(cont_range.size() == cont.size(), "Incorrect ordered container range size");
109
110 typename Container::iterator l_bound = cont.lower_bound(key);
111 typename Container::iterator u_bound = cont.upper_bound(key);
112
113 REQUIRE_MESSAGE(l_bound == l_bound_check, "lower_bound() returned wrong iterator");
114 REQUIRE_MESSAGE(u_bound == u_bound_check, "upper_bound() returned wrong iterator");
115
116 using const_iterator = typename Container::const_iterator;
117 const_iterator cl_bound = ccont.lower_bound(key);
118 const_iterator cu_bound = ccont.upper_bound(key);
119
120 REQUIRE_MESSAGE(cl_bound == const_iterator(l_bound), "lower_bound() const returned wrong iterator");
121 REQUIRE_MESSAGE(cu_bound == const_iterator(u_bound), "upper_bound() const returned wrong iterator");
122
123 REQUIRE((l_bound == eq_range.first && u_bound == eq_range.second));
124 }
125 }
126
127 template <typename Container, typename CheckElementState = std::false_type>
test_basic()128 void test_basic() {
129 test_basic_common<Container, CheckElementState>();
130 test_ordered_methods<Container>();
131 }
132
133 template <typename Container>
test_concurrent_order()134 void test_concurrent_order() {
135 // TODO: MinThread - MaxThread loop
136 auto num_threads = utils::get_platform_max_threads();
137 Container cont;
138 int items = 1000;
139 utils::NativeParallelFor(num_threads, [&](std::size_t index) {
140 int step = index % 4 + 1;
141 bool reverse = (step % 2 == 0);
142 if (reverse) {
143 for (int i = 0; i < items; i += step) {
144 cont.insert(Value<Container>::make(i));
145 }
146 } else {
147 for (int i = items; i > 0; i -= step) {
148 cont.insert(Value<Container>::make(i));
149 }
150 }
151 });
152
153 check_container_order(cont);
154 }
155
156 template <typename Container>
157 void test_concurrent(bool asymptotic = false) {
158 test_concurrent_common<Container>(asymptotic);
159 test_concurrent_order<Container>();
160 }
161
162 struct OrderedMoveTraitsBase {
163 static constexpr std::size_t expected_number_of_items_to_allocate_for_steal_move = 584; // TODO: remove allocation of dummy_node
164
165 template <typename OrderedType, typename Iterator>
construct_containerOrderedMoveTraitsBase166 static OrderedType& construct_container( typename std::aligned_storage<sizeof(OrderedType)>::type& storage,
167 Iterator begin, Iterator end )
168 {
169 OrderedType* ptr = reinterpret_cast<OrderedType*>(&storage);
170 new (ptr) OrderedType(begin, end);
171 return *ptr;
172 }
173
174 template <typename OrderedType, typename Iterator, typename Allocator>
construct_containerOrderedMoveTraitsBase175 static OrderedType& construct_container( typename std::aligned_storage<sizeof(OrderedType)>::type& storage,
176 Iterator begin, Iterator end, const Allocator& alloc )
177 {
178 OrderedType* ptr = reinterpret_cast<OrderedType*>(&storage);
179 new (ptr) OrderedType(begin, end, typename OrderedType::key_compare(), alloc);
180 return *ptr;
181 }
182
183 template <typename OrderedType, typename Iterator>
equalOrderedMoveTraitsBase184 static bool equal( const OrderedType& c, Iterator begin, Iterator end ) {
185 bool equal_sizes = std::size_t(std::distance(begin, end)) == c.size();
186 if (!equal_sizes) return false;
187 for (Iterator it = begin; it != end; ++it) {
188 if (!c.contains(Value<OrderedType>::key((*it)))) return false;
189 }
190 return true;
191 }
192 };
193
194 namespace std {
195 template <>
196 struct less<std::weak_ptr<int>> {
197 bool operator()( const std::weak_ptr<int>& lhs, const std::weak_ptr<int>& rhs ) const {
198 return *lhs.lock() < *rhs.lock();
199 }
200 };
201
202 template <>
203 struct less<const std::weak_ptr<int>> : less<std::weak_ptr<int>> {};
204 }
205
206 template <bool DefCtorPresent, typename Table>
207 void Examine(Table c, const std::list<typename Table::value_type>& lst) {
208 CommonExamine<DefCtorPresent>(c, lst);
209 }
210
211 template <bool DefCtorPresent, typename Table>
212 void TypeTester( const std::list<typename Table::value_type>& lst ) {
213 REQUIRE_MESSAGE(lst.size() >= 5, "Array should have at least 5 elements");
214 REQUIRE_MESSAGE(lst.size() <= 100, "The test has O(n^2) complexity so a big number of elements can lead long execution time");
215
216 // Construct an empty table
217 Table c1;
218 c1.insert(lst.begin(), lst.end());
219 Examine<DefCtorPresent>(c1, lst);
220
221 typename Table::key_compare compare;
222 typename Table::allocator_type allocator;
223
224 auto it = lst.begin();
225 auto init = {*it++, *it++, *it++};
226
227 // Constructor from an std::initializer_list
228 Table c2(init);
229 c2.insert(it, lst.end());
230 Examine<DefCtorPresent>(c2, lst);
231
232 // Constructor from an std::initializer_list, default comparator and non-default allocator
233 Table c2_alloc(init, allocator);
234 c2_alloc.insert(it, lst.end());
235 Examine<DefCtorPresent>(c2_alloc, lst);
236
237 // Constructor from an std::initializer_list, non-default comparator and allocator
238 Table c2_comp_alloc(init, compare, allocator);
239 c2_comp_alloc.insert(it, lst.end());
240 Examine<DefCtorPresent>(c2_comp_alloc, lst);
241
242 // Copying constructor
243 Table c3(c1);
244 Examine<DefCtorPresent>(c3, lst);
245
246 // Copying constructor with the allocator
247 Table c3_alloc(c1, allocator);
248 Examine<DefCtorPresent>(c3_alloc, lst);
249
250 // Constructor with non-default compare
251 Table c4(compare);
252 c4.insert(lst.begin(), lst.end());
253 Examine<DefCtorPresent>(c4, lst);
254
255 // Constructor with non-default allocator
256 Table c5(allocator);
257 c5.insert(lst.begin(), lst.end());
258 Examine<DefCtorPresent>(c5, lst);
259
260 // Constructor with non-default compare and non-default allocator
261 Table c6(compare, allocator);
262 c6.insert(lst.begin(), lst.end());
263 Examine<DefCtorPresent>(c6, lst);
264
265 // Constructor from an iteration range
266 Table c7(c1.begin(), c1.end());
267 Examine<DefCtorPresent>(c7, lst);
268
269 // Constructor from an iteration range, default compare and non-default allocator
270 Table c8(c1.begin(), c1.end(), allocator);
271 Examine<DefCtorPresent>(c8, lst);
272
273 // Constructor from an iteration range, non-default compare and non-default allocator
274 Table c9(c1.begin(), c1.end(), compare, allocator);
275 Examine<DefCtorPresent>(c9, lst);
276 }
277
278 struct TransparentLess {
279 template <typename T, typename U>
280 auto operator()( T&& lhs, U&& rhs ) const
281 -> decltype(std::forward<T>(lhs) < std::forward<U>(rhs)) {
282 return lhs < rhs;
283 }
284
285 using is_transparent = void;
286 };
287
288 template <template <typename...> class Container, typename... Args>
289 void check_heterogeneous_functions_key_int() {
290 check_heterogeneous_functions_key_int_impl<Container<Args..., TransparentLess>>();
291 }
292
293 template <template <typename...> class Container, typename... Args>
294 void check_heterogeneous_functions_key_string() {
295 check_heterogeneous_functions_key_string_impl<Container<Args..., TransparentLess>>();
296 }
297
298 template <typename Container>
299 void check_heterogeneous_bound_functions() {
300 static_assert(std::is_same<typename Container::key_type, int>::value,
301 "incorrect key_type for heterogeneous bounds test");
302 // Initialization
303 Container c;
304 const Container& cc = c;
305
306 int size = 10;
307 for (int i = 0; i < size; ++i) {
308 c.insert(Value<Container>::make(i));
309 }
310 // Insert first duplicated element for multicontainers
311 if (AllowMultimapping<Container>::value) {
312 c.insert(Value<Container>::make(0));
313 }
314
315 // Upper and lower bound testing
316 for (int i = 0; i < size; ++i) {
317 int_key k(i);
318 int key = i;
319
320 REQUIRE_MESSAGE(c.lower_bound(k) == c.lower_bound(key), "Incorrect heterogeneous lower_bound return value");
321 REQUIRE_MESSAGE(c.upper_bound(k) == c.upper_bound(key), "Incorrect heterogeneous upper_bound return value");
322 REQUIRE_MESSAGE(cc.lower_bound(k) == cc.lower_bound(key), "Incorrect const heterogeneous lower_bound return value");
323 REQUIRE_MESSAGE(cc.upper_bound(k) == cc.upper_bound(key), "Incorrect const heterogeneous upper_bound return value");
324 }
325 }
326
327 template <typename Container>
328 void test_comparisons_basic() {
329 using comparisons_testing::testEqualityAndLessComparisons;
330 Container c1, c2;
331 testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(c1, c2);
332
333 c1.insert(Value<Container>::make(1));
334 testEqualityAndLessComparisons</*ExpectEqual = */false, /*ExpectLess = */false>(c1, c2);
335
336 c2.insert(Value<Container>::make(1));
337 testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(c1, c2);
338
339 c2.insert(Value<Container>::make(2));
340 testEqualityAndLessComparisons</*ExpectEqual = */false, /*ExpectLess = */true>(c1, c2);
341
342 c1.clear();
343 c2.clear();
344
345 testEqualityAndLessComparisons</*ExpectEqual = */true, /*ExpectLess = */false>(c1, c2);
346 }
347
348 template <typename TwoWayComparableContainerType>
349 void test_two_way_comparable_container() {
350 TwoWayComparableContainerType c1, c2;
351 c1.insert(Value<TwoWayComparableContainerType>::make(1));
352 c2.insert(Value<TwoWayComparableContainerType>::make(1));
353 comparisons_testing::TwoWayComparable::reset();
354 REQUIRE_MESSAGE(!(c1 < c2), "Incorrect operator < result");
355 comparisons_testing::check_two_way_comparison();
356 REQUIRE_MESSAGE(!(c1 > c2), "Incorrect operator > result");
357 comparisons_testing::check_two_way_comparison();
358 REQUIRE_MESSAGE(c1 <= c2, "Incorrect operator <= result");
359 comparisons_testing::check_two_way_comparison();
360 REQUIRE_MESSAGE(c1 >= c2, "Incorrect operator >= result");
361 comparisons_testing::check_two_way_comparison();
362 }
363
364 #if __TBB_TEST_CPP20_COMPARISONS
365 template <typename ThreeWayComparableContainerType>
366 void test_three_way_comparable_container() {
367 ThreeWayComparableContainerType c1, c2;
368 c1.insert(Value<ThreeWayComparableContainerType>::make(1));
369 c2.insert(Value<ThreeWayComparableContainerType>::make(1));
370 comparisons_testing::ThreeWayComparable::reset();
371 REQUIRE_MESSAGE(!(c1 <=> c2 < 0), "Incorrect operator<=> result");
372 comparisons_testing::check_three_way_comparison();
373
374 REQUIRE_MESSAGE(!(c1 < c2), "Incorrect operator< result");
375 comparisons_testing::check_three_way_comparison();
376
377 REQUIRE_MESSAGE(!(c1 > c2), "Incorrect operator> result");
378 comparisons_testing::check_three_way_comparison();
379
380 REQUIRE_MESSAGE(c1 <= c2, "Incorrect operator>= result");
381 comparisons_testing::check_three_way_comparison();
382
383 REQUIRE_MESSAGE(c1 >= c2, "Incorrect operator>= result");
384 comparisons_testing::check_three_way_comparison();
385 }
386 #endif
387
388 template <template <typename...> class ContainerType>
389 void test_map_comparisons() {
390 using integral_container = ContainerType<int, int>;
391 using two_way_comparable_container = ContainerType<comparisons_testing::TwoWayComparable,
392 comparisons_testing::TwoWayComparable>;
393 test_comparisons_basic<integral_container>();
394 test_comparisons_basic<two_way_comparable_container>();
395 test_two_way_comparable_container<two_way_comparable_container>();
396
397 #if __TBB_TEST_CPP20_COMPARISONS
398 using two_way_less_only_container = ContainerType<comparisons_testing::LessComparableOnly,
399 comparisons_testing::LessComparableOnly>;
400
401 using three_way_only_container = ContainerType<comparisons_testing::ThreeWayComparableOnly,
402 comparisons_testing::ThreeWayComparableOnly>;
403
404 using three_way_comparable_container = ContainerType<comparisons_testing::ThreeWayComparable,
405 comparisons_testing::ThreeWayComparable>;
406
407 test_comparisons_basic<two_way_less_only_container>();
408 test_comparisons_basic<three_way_only_container>();
409 test_comparisons_basic<three_way_comparable_container>();
410 test_three_way_comparable_container<three_way_comparable_container>();
411 #endif // __TBB_TEST_CPP20_COMPARISONS
412 }
413
414 template <template <typename...> class ContainerType>
415 void test_set_comparisons() {
416 using integral_container = ContainerType<int>;
417 using two_way_comparable_container = ContainerType<comparisons_testing::TwoWayComparable>;
418
419 test_comparisons_basic<integral_container>();
420 test_comparisons_basic<two_way_comparable_container>();
421 test_two_way_comparable_container<two_way_comparable_container>();
422
423 #if __TBB_TEST_CPP20_COMPARISONS
424 using two_way_less_only_container = ContainerType<comparisons_testing::LessComparableOnly>;
425 using three_way_only_container = ContainerType<comparisons_testing::ThreeWayComparableOnly>;
426 using three_way_comparable_container = ContainerType<comparisons_testing::ThreeWayComparable>;
427
428 test_comparisons_basic<two_way_less_only_container>();
429 test_comparisons_basic<three_way_only_container>();
430 test_comparisons_basic<three_way_comparable_container>();
431 test_three_way_comparable_container<three_way_comparable_container>();
432 #endif // __TBB_TEST_CPP20_COMPARISONS
433 }
434
435 #endif // __TBB_test_common_concurrent_ordered_common_H
436