1 /* 2 Copyright (c) 2005-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 #ifndef NOMINMAX 17 #define NOMINMAX 18 #endif 19 #include <tbb/concurrent_map.h> 20 #include "common/concurrent_ordered_common.h" 21 22 //! \file test_concurrent_map.cpp 23 //! \brief Test for [containers.concurrent_map containers.concurrent_multimap] specifications 24 25 template <typename... Args> 26 struct AllowMultimapping<tbb::concurrent_multimap<Args...>> : std::true_type {}; 27 28 template <typename Key, typename Mapped> 29 using MyAllocator = LocalCountingAllocator<std::allocator<std::pair<const Key, Mapped>>>; 30 31 using move_support_tests::FooWithAssign; 32 33 using map_type = tbb::concurrent_map<int, int, std::less<int>, MyAllocator<int, int>>; 34 using multimap_type = tbb::concurrent_multimap<int, int, std::less<int>, MyAllocator<int, int>>; 35 using checked_map_type = tbb::concurrent_map<int, CheckType<int>, std::less<int>, MyAllocator<int, CheckType<int>>>; 36 using checked_multimap_type = tbb::concurrent_multimap<int, CheckType<int>, std::less<int>, MyAllocator<int, CheckType<int>>>; 37 using greater_map_type = tbb::concurrent_map<int, int, std::greater<int>, MyAllocator<int, int>>; 38 using greater_multimap_type = tbb::concurrent_multimap<int, int, std::greater<int>, MyAllocator<int, int>>; 39 using checked_state_map_type = tbb::concurrent_map<intptr_t, FooWithAssign, std::less<intptr_t>, 40 MyAllocator<intptr_t, FooWithAssign>>; 41 using checked_state_multimap_type = tbb::concurrent_multimap<intptr_t, FooWithAssign, std::less<intptr_t>, 42 MyAllocator<intptr_t, FooWithAssign>>; 43 44 template <> 45 struct SpecialTests<map_type> { 46 static void Test() { 47 SpecialMapTests<map_type>(); 48 } 49 }; 50 51 template <> 52 struct SpecialTests<multimap_type> { 53 static void Test() { 54 SpecialMultiMapTests<multimap_type>(); 55 } 56 }; 57 58 struct COMapTraits : OrderedMoveTraitsBase { 59 template <typename T, typename Allocator> 60 using container_type = tbb::concurrent_map<T, T, std::less<T>, Allocator>; 61 62 template <typename T> 63 using container_value_type = std::pair<const T, T>; 64 65 using init_iterator_type = move_support_tests::FooPairIterator; 66 }; // struct COMapTraits 67 68 struct COMultimapTraits : OrderedMoveTraitsBase { 69 template <typename T, typename Allocator> 70 using container_type = tbb::concurrent_multimap<T, T, std::less<T>, Allocator>; 71 72 template <typename T> 73 using container_value_type = std::pair<const T, T>; 74 75 using init_iterator_type = move_support_tests::FooPairIterator; 76 }; // struct COMultimapTraits 77 78 struct OrderedMapTypesTester { 79 template <bool DefCtorPresent, typename ValueType> 80 void check( const std::list<ValueType>& lst ) { 81 using key_type = typename ValueType::first_type; 82 using mapped_type = typename ValueType::second_type; 83 84 TypeTester<DefCtorPresent, tbb::concurrent_map<key_type, mapped_type>>(lst); 85 TypeTester<DefCtorPresent, tbb::concurrent_multimap<key_type, mapped_type>>(lst); 86 } 87 }; // struct OrderedMapTypesTester 88 89 void test_specific_types() { 90 test_map_specific_types<OrderedMapTypesTester>(); 91 92 // Regression test for a problem with excessive requirements of emplace() 93 test_emplace_insert<tbb::concurrent_map<int*, test::unique_ptr<int>>,std::false_type> 94 (new int, new int); 95 test_emplace_insert<tbb::concurrent_multimap<int*, test::unique_ptr<int>>,std::false_type> 96 (new int, new int); 97 } 98 99 // Regression test for an issue in lock free algorithms 100 // In some cases this test hangs due to broken skip list internal structure on levels > 1 101 // This issue was resolved by adding index_number into the skip list node 102 void test_cycles_absense() { 103 for (std::size_t execution = 0; execution != 10; ++execution) { 104 tbb::concurrent_multimap<int, int> mmap; 105 std::vector<int> v(2); 106 int vector_size = int(v.size()); 107 108 for (int i = 0; i != vector_size; ++i) { 109 v[i] = i; 110 } 111 size_t num_threads = 4; // Can be changed to 2 for debugging 112 113 utils::NativeParallelFor(num_threads, [&](size_t) { 114 for (int i = 0; i != vector_size; ++i) { 115 mmap.emplace(i, i); 116 } 117 }); 118 119 for (int i = 0; i != vector_size; ++i) { 120 REQUIRE(mmap.count(i) == num_threads); 121 } 122 } 123 } 124 125 //! \brief \ref error_guessing 126 TEST_CASE("basic test for concurrent_map with greater compare") { 127 test_basic<greater_map_type>(); 128 } 129 130 //! \brief \ref error_guessing 131 TEST_CASE("basic test for concurrent_multimap with greater compare") { 132 test_basic<greater_multimap_type>(); 133 } 134 135 //! \brief \ref resource_usage 136 TEST_CASE("basic test for concurrent_map with elements ctor and dtor check") { 137 Checker<checked_map_type::value_type> checker; 138 test_basic<checked_map_type>(); 139 } 140 141 //! \brief \ref resource_usage 142 TEST_CASE("basic test for concurrent_multimap with elements ctor and dtor check") { 143 Checker<checked_multimap_type::value_type> checker; 144 test_basic<checked_multimap_type>(); 145 } 146 147 //! \brief \ref resource_usage 148 TEST_CASE("basic test for concurrent_map with elements state check") { 149 test_basic<checked_state_map_type, /*CheckState = */std::true_type>(); 150 } 151 152 //! \brief \ref resource_usage 153 TEST_CASE("basic test for concurrent_multimap with elements state check") { 154 test_basic<checked_state_multimap_type, /*CheckState = */std::true_type>(); 155 } 156 157 //! \brief \ref error_guessing 158 TEST_CASE("multithreading support in concurrent_map with greater compare") { 159 test_concurrent<greater_map_type>(); 160 } 161 162 //! \brief \ref error_guessing 163 TEST_CASE("multithreading support in concurrent_multimap with greater compare") { 164 test_concurrent<greater_multimap_type>(); 165 } 166 167 //! \brief \ref resource_usage 168 TEST_CASE("multithreading support in concurrent_map with elements ctor and dtor check") { 169 Checker<checked_map_type::value_type> checker; 170 test_concurrent<checked_map_type>(); 171 } 172 173 //! \brief \ref resource_usage 174 TEST_CASE("multithreading support in concurrent_multimap with elements ctor and dtor check") { 175 Checker<checked_multimap_type::value_type> checker; 176 test_concurrent<checked_multimap_type>(); 177 } 178 179 //! \brief \ref resource_usage 180 TEST_CASE("multithreading support in concurrent_map with elements state check") { 181 test_concurrent<checked_state_map_type>(); 182 } 183 184 //! \brief \ref resource_usage 185 TEST_CASE("multithreading support in concurrent_multimap with elements state check") { 186 test_concurrent<checked_state_multimap_type>(); 187 } 188 189 //! \brief \ref stress \ref error_guessing 190 TEST_CASE("multithreading support in concurrent_multimap no unique keys") { 191 test_concurrent<multimap_type>(true); 192 } 193 194 //! \brief \ref stress \ref error_guessing 195 TEST_CASE("multithreading support in concurrent_multimap with greater compare and no unique keys") { 196 test_concurrent<greater_multimap_type>(true); 197 } 198 199 //! \brief \ref interface \ref error_guessing 200 TEST_CASE("range based for support in concurrent_map") { 201 test_range_based_for_support<map_type>(); 202 } 203 204 //! \brief \ref interface \ref error_guessing 205 TEST_CASE("range based for support in concurrent_multimap") { 206 test_range_based_for_support<multimap_type>(); 207 } 208 209 //! \brief \ref regression 210 TEST_CASE("concurrent_map/multimap with specific key/mapped types") { 211 test_specific_types(); 212 } 213 214 // TODO: add test with scoped_allocator_adaptor with broken macro 215 216 //! \brief \ref regression 217 TEST_CASE("broken internal structure for multimap") { 218 test_cycles_absense(); 219 } 220 221 //! \brief \ref error_guessing 222 TEST_CASE("concurrent_map::swap with not always equal allocator") { 223 using not_always_equal_alloc_map_type = tbb::concurrent_map<int, int, std::less<int>, 224 NotAlwaysEqualAllocator<std::pair<const int, int>>>; 225 test_swap_not_always_equal_allocator<not_always_equal_alloc_map_type>(); 226 } 227 228 //! \brief \ref error_guessing 229 TEST_CASE("concurrent_multimap::swap with not always equal allocator") { 230 using not_always_equal_alloc_mmap_type = tbb::concurrent_multimap<int, int, std::less<int>, 231 NotAlwaysEqualAllocator<std::pair<const int, int>>>; 232 test_swap_not_always_equal_allocator<not_always_equal_alloc_mmap_type>(); 233 } 234 235 #if TBB_USE_EXCEPTIONS 236 //! \brief \ref error_guessing 237 TEST_CASE("concurrent_map throwing copy constructor") { 238 using exception_map_type = tbb::concurrent_map<ThrowOnCopy, ThrowOnCopy>; 239 test_exception_on_copy_ctor<exception_map_type>(); 240 } 241 242 //! \brief \ref error_guessing 243 TEST_CASE("concurrent_multimap throwing copy constructor") { 244 using exception_mmap_type = tbb::concurrent_multimap<ThrowOnCopy, ThrowOnCopy>; 245 test_exception_on_copy_ctor<exception_mmap_type>(); 246 } 247 #endif // TBB_USE_EXCEPTIONS 248 249 #if __TBB_CPP20_CONCEPTS_PRESENT 250 //! \brief \ref error_guessing 251 TEST_CASE("container_range concept for concurrent_map ranges") { 252 static_assert(test_concepts::container_range<typename tbb::concurrent_map<int, int>::range_type>); 253 static_assert(test_concepts::container_range<typename tbb::concurrent_map<int, int>::const_range_type>); 254 } 255 256 //! \brief \ref error_guessing 257 TEST_CASE("container_range concept for concurrent_multimap ranges") { 258 static_assert(test_concepts::container_range<typename tbb::concurrent_multimap<int, int>::range_type>); 259 static_assert(test_concepts::container_range<typename tbb::concurrent_multimap<int, int>::const_range_type>); 260 } 261 #endif // __TBB_CPP20_CONCEPTS_PRESENT 262