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> 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> 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 44 OrderChecker(typename Container::value_compare& v_comp, typename Container::key_compare& k_comp) 45 : val_comp(v_comp), key_comp(k_comp) {} 46 47 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> 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> 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> 128 void test_basic() { 129 test_basic_common<Container, CheckElementState>(); 130 test_ordered_methods<Container>(); 131 } 132 133 template <typename Container> 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> 166 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> 175 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> 184 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