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