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_node_handling_support_H
18 #define __TBB_test_common_node_handling_support_H
19 
20 #include "common/test.h"
21 #include <utility>
22 
23 template <typename T>
24 struct AllowMultimapping;
25 
26 template <typename Container>
27 struct Value;
28 
29 namespace node_handling_tests {
30 
31 template <typename Handle>
32 bool compare_handle_getters( const Handle& node, const std::pair<typename Handle::key_type, typename Handle::mapped_type>& value  ) {
33     return node.key() == value.first && node.mapped() == value.second;
34 }
35 
36 template <typename Handle>
37 bool compare_handle_getters( const Handle& node, const typename Handle::value_type& value ) {
38     return node.value() == value;
39 }
40 
41 template <typename Handle>
42 void set_node_handle_value( Handle& node, const std::pair<typename Handle::key_type, typename Handle::mapped_type>& value ) {
43     node.key() = value.first;
44     node.mapped() = value.second;
45 }
46 
47 template <typename Handle>
48 void set_node_handle_value( Handle& node, const typename Handle::value_type& value ) {
49     node.value() = value;
50 }
51 
52 template <typename NodeType>
53 void test_node_handle_traits() {
54     REQUIRE_MESSAGE(!std::is_copy_constructible<NodeType>::value,
55                     "Node handle: handle should not be copy constructible");
56     REQUIRE_MESSAGE(!std::is_copy_assignable<NodeType>::value,
57                     "Node handle: handle should not be copy assignable");
58     REQUIRE_MESSAGE(std::is_move_constructible<NodeType>::value,
59                     "Node handle: handle should be move constructible");
60     REQUIRE_MESSAGE(std::is_move_assignable<NodeType>::value,
61                     "Node handle: handle should be move assignable");
62     REQUIRE_MESSAGE(std::is_default_constructible<NodeType>::value,
63                     "Node handle: handle should be default constructible");
64     REQUIRE_MESSAGE(std::is_destructible<NodeType>::value,
65                     "Node handle: handle should be destructible");
66 }
67 
68 template <typename Container>
69 void test_node_handle( Container test_table ) {
70     REQUIRE_MESSAGE(test_table.size() > 1, "Node handle: Container must contain 2 or more elements");
71     // Initialization
72     using node_type = typename Container::node_type;
73 
74     test_node_handle_traits<node_type>();
75 
76     // Default ctor and empty initialization
77     node_type nh;
78     REQUIRE_MESSAGE(nh.empty(), "Node handle: node_type object is not empty after default ctor");
79 
80     // Move assignment
81     // key/mapped/value function
82     auto expected_value = *test_table.begin();
83 
84     nh = test_table.unsafe_extract(test_table.begin());
85     REQUIRE_MESSAGE(!nh.empty(), "Node handle: node_type object is empty after valid move assignment");
86     REQUIRE_MESSAGE(nh.get_allocator() == test_table.get_allocator(), "Node handle: node_type object allocator is incorrect");
87     REQUIRE_MESSAGE(compare_handle_getters(nh, expected_value),
88                     "Node handle: node_type object does not contains expected value after valid move assignment");
89 
90     // Move ctor
91     node_type nh2(std::move(nh));
92     REQUIRE_MESSAGE(nh.empty(), "Node handle: moved-from node_type object is not empty");
93     REQUIRE_MESSAGE(!nh2.empty(), "Node handle: node_type object is empty after valid move construction");
94     REQUIRE_MESSAGE(compare_handle_getters(nh2, expected_value),
95             "Node handle: node_type object does not contains expected value after valid move ctor");
96 
97     // bool conversion
98     REQUIRE_MESSAGE(nh2, "Node handle: Wrong node handle bool conversion");
99 
100     auto expected_value2 = *test_table.begin();
101     set_node_handle_value(nh2, expected_value2);
102     REQUIRE_MESSAGE(compare_handle_getters(nh2, expected_value2),
103                     "Node handle: Wrond node handle key/mapped/value change behaviour");
104 
105     // Member and non-member swap check
106     node_type empty_node;
107     // Extract an element for nh2 and nh3 difference
108     test_table.unsafe_extract(test_table.begin());
109     auto expected_value3 = *test_table.begin();
110     node_type nh3(test_table.unsafe_extract(test_table.begin()));
111 
112     // Both of node handles are not empty
113     nh3.swap(nh2);
114     REQUIRE_MESSAGE(!nh2.empty(), "Node handle: Wrong node handle swap behavior");
115     REQUIRE_MESSAGE(!nh3.empty(), "Node handle: Wrong node handle swap behavior");
116     REQUIRE_MESSAGE(compare_handle_getters(nh3, expected_value2),
117                     "Node handle: Wrong node handle swap behavior");
118     REQUIRE_MESSAGE(compare_handle_getters(nh2, expected_value3),
119                     "Node handle: Wrong node handle swap behavior");
120 
121     using std::swap;
122     swap(nh2, nh3);
123     REQUIRE_MESSAGE(!nh2.empty(), "Node handle: Wrong node handle swap behavior");
124     REQUIRE_MESSAGE(!nh3.empty(), "Node handle: Wrong node handle swap behavior");
125     REQUIRE_MESSAGE(compare_handle_getters(nh3, expected_value3),
126                     "Node handle: Wrong node handle swap behavior");
127     REQUIRE_MESSAGE(compare_handle_getters(nh2, expected_value2),
128                     "Node handle: Wrong node handle swap behavior");
129 
130     // One of the handles is empty
131     nh3.swap(empty_node);
132     REQUIRE_MESSAGE(nh3.empty(), "Node handle: Wrong node handle swap behavior");
133     REQUIRE_MESSAGE(compare_handle_getters(empty_node, expected_value3),
134                     "Node handle: Wrong node handle swap behavior");
135 
136     swap(empty_node, nh3);
137     REQUIRE_MESSAGE(empty_node.empty(), "Node handle: Wrong node handle swap behavior");
138     REQUIRE_MESSAGE(compare_handle_getters(nh3, expected_value3),
139                     "Node handle: Wrong node handle swap behavior");
140 
141     empty_node.swap(nh3);
142     REQUIRE_MESSAGE(nh3.empty(), "Node handle: Wrong node handle swap behavior");
143     REQUIRE_MESSAGE(compare_handle_getters(empty_node, expected_value3),
144                     "Node handle: Wrong node handle swap behavior");
145 }
146 
147 template <typename Container>
148 typename Container::node_type generate_node_handle( const typename Container::value_type& value ) {
149     Container table;
150     table.insert(value);
151     return table.unsafe_extract(table.begin());
152 }
153 
154 template <typename Container>
155 void check_insert( const Container& table,
156                    typename Container::iterator result,
157                    const typename Container::value_type* node_value = nullptr )
158 {
159     if (node_value == nullptr) {
160         REQUIRE_MESSAGE(result == table.end(),
161                         "Insert: Result iterator does not point to the end after empty node insertion");
162     } else {
163         if (AllowMultimapping<Container>::value) {
164             REQUIRE_MESSAGE(*result == *node_value,
165                     "Insert: Result iterator points to the wrong element after successful insertion");
166 
167             for (auto it = table.begin(); it != table.end(); ++it) {
168                 if (it == result) return;
169             }
170             REQUIRE_MESSAGE(false, "Insert: iterator does not point to the element in the container");
171         } else {
172             REQUIRE_MESSAGE((result == table.find(Value<Container>::key(*node_value)) &&
173                              result != table.end()),
174                              "Insert: Iterator does not point to the equal element in the container");
175         }
176     }
177 }
178 
179 // Overload for sets
180 template <typename Container>
181 void check_insert( const Container& table,
182                    typename Container::iterator result,
183                    bool,
184                    const typename Container::value_type* node_value = nullptr )
185 {
186     check_insert(table, result, node_value);
187 }
188 
189 // Overload for maps
190 template <typename Container>
191 void check_insert( const Container& table,
192                    const std::pair<typename Container::iterator, bool>& result,
193                    bool successful,
194                    const typename Container::value_type* node_value = nullptr )
195 {
196     check_insert(table, result.first, node_value);
197     REQUIRE_MESSAGE((result.second == successful || AllowMultimapping<Container>::value),
198                     "Insert: Wrong bool returned after node insertion");
199 }
200 
201 // Can't delete reference from table_to_insert argument because hint must point to the element in the table
202 template <typename Container, typename... Hint>
203 void test_insert_overloads(Container& table_to_insert, const typename Container::value_type& value, const Hint&... hint) {
204     // Insert an empty element
205     typename Container::node_type nh;
206 
207     auto table_size = table_to_insert.size();
208     auto result = table_to_insert.insert(hint..., std::move(nh));
209     check_insert(table_to_insert, result, /*successful = */false);
210 
211     REQUIRE_MESSAGE(table_to_insert.size() == table_size,
212                     "Insert: Container size changed after the insertion of the empty node handle");
213 
214     // Standard insertion
215     nh = generate_node_handle<Container>(value);
216 
217     result = table_to_insert.insert(hint..., std::move(nh));
218     REQUIRE_MESSAGE(nh.empty(), "Insert: Not empty node handle after successful insertion");
219     check_insert(table_to_insert, result, /*successful = */true, &value);
220 
221     // Insert existing node
222     nh = generate_node_handle<Container>(value);
223     result = table_to_insert.insert(hint..., std::move(nh));
224 
225     check_insert(table_to_insert, result, /*successful = */false, &value);
226 
227     if (AllowMultimapping<Container>::value) {
228         REQUIRE_MESSAGE(nh.empty(), "Insert: Failed insertion to multitable");
229     } else {
230         REQUIRE_MESSAGE(!nh.empty(), "Insert: Empty node handle after failed insertion");
231         REQUIRE_MESSAGE(compare_handle_getters(nh, value),
232                         "Insert: Existing data does not equal to the one being inserted");
233     }
234 }
235 
236 template <typename Container>
237 void test_insert( Container table, const typename Container::value_type& value ) {
238     REQUIRE_MESSAGE(!table.empty(), "Insert: container should contains 1 or more elements");
239     Container table_backup(table);
240     test_insert_overloads(table, value); // test insert
241     test_insert_overloads(table_backup, value, table_backup.begin()); // test insert with the hint
242 }
243 
244 template <typename Container>
245 void test_extract( Container table_for_extract, typename Container::key_type new_key ) {
246     REQUIRE_MESSAGE(table_for_extract.size() > 1, "Extract: container must contain 2 or more elements");
247     REQUIRE_MESSAGE(!table_for_extract.contains(new_key), "Extract: container must not contain new element");
248 
249     // Extract new_element
250     auto nh = table_for_extract.unsafe_extract(new_key);
251     REQUIRE_MESSAGE(nh.empty(), "Extract: node handle is not empty after extraction of key which is not is the container");
252 
253     // Valid key extraction
254     auto expected_value = *table_for_extract.begin();
255     auto key = Value<Container>::key(expected_value);
256     auto count = table_for_extract.count(key);
257 
258     nh = table_for_extract.unsafe_extract(key);
259     REQUIRE_MESSAGE(!nh.empty(), "Extract: node handle is empty after successful extraction");
260     REQUIRE_MESSAGE(compare_handle_getters(nh, expected_value), "Extract: node handle contains wrong node after successful extraction");
261     REQUIRE_MESSAGE(table_for_extract.count(key) == count -1, "Extract: more than one elements were extracted");
262 
263     // Valid iterator extraction
264     auto expected_value2 = *table_for_extract.begin();
265     auto key2 = Value<Container>::key(expected_value2);
266     auto count2 = table_for_extract.count(key2);
267 
268     nh = table_for_extract.unsafe_extract(table_for_extract.cbegin());
269     REQUIRE_MESSAGE(!nh.empty(), "Extract: node handle is empty after successful extraction");
270     REQUIRE_MESSAGE(compare_handle_getters(nh, expected_value2), "Extract: node handle contains wrong node after successful extraction");
271     REQUIRE_MESSAGE(table_for_extract.count(key2) == count2 -1, "Extract: more than one elements were extracted");
272 }
273 
274 template <typename Container>
275 void test_node_handling( const Container& container, const typename Container::value_type& new_value ) {
276     test_node_handle(container);
277     test_insert(container, new_value);
278     test_extract(container, Value<Container>::key(new_value));
279 }
280 
281 template <typename Container>
282 void test_node_handling_support() {
283     Container cont;
284 
285     for (int i = 1; i < 5; ++i) {
286         cont.insert(Value<Container>::make(i));
287     }
288 
289     if (AllowMultimapping<Container>::value) {
290         cont.insert(Value<Container>::make(4));
291     }
292 
293     test_node_handling(cont, Value<Container>::make(5));
294 }
295 
296 template <typename Container1, typename Container2>
297 void test_merge_basic( Container1 table1, Container2&& table2 ) {
298     using container2_pure_type = typename std::decay<Container2>::type;
299 
300     // Initialization
301     Container1 table1_backup = table1;
302     container2_pure_type table2_backup = table2;
303 
304     table1.merge(std::forward<Container2>(table2));
305     for (auto it : table2) {
306         REQUIRE_MESSAGE(table1.contains(Value<container2_pure_type>::key(it)),
307                         "Merge: Some key was not merged");
308     }
309 
310     // After the following step table1 will contains only merged elements from table2
311     for (auto it : table1_backup) {
312         table1.unsafe_extract(Value<Container1>::key(it));
313     }
314     // After the following step table2_backup will contains only merged elements from table2
315     for (auto it : table2) {
316         table2_backup.unsafe_extract(Value<container2_pure_type>::key(it));
317     }
318 
319     REQUIRE_MESSAGE(table1.size() == table2_backup.size(), "Merge: Sizes of tables are not equal");
320     for (auto it : table2_backup) {
321         REQUIRE_MESSAGE(table1.contains(Value<container2_pure_type>::key(it)),
322                         "Merge: Wrong merge behavior");
323     }
324 }
325 
326 template <typename Container1, typename Container2>
327 void test_merge_overloads( const Container1& table1, Container2 table2 ) {
328     Container2 table_backup(table2);
329     test_merge_basic(table1, table2);
330     test_merge_basic(table1, std::move(table_backup));
331 }
332 
333 template <typename UniqueContainer, typename MultiContainer>
334 void test_merge_transposition( UniqueContainer table1, UniqueContainer table2,
335                                MultiContainer multitable1, MultiContainer multitable2 ) {
336     UniqueContainer empty_table;
337     MultiContainer empty_multitable;
338 
339     // Unique table transpositions
340     test_merge_overloads(table1, table2);
341     test_merge_overloads(table1, empty_table);
342     test_merge_overloads(empty_table, table2);
343 
344     // Multi table transpositions
345     test_merge_overloads(multitable1, multitable2);
346     test_merge_overloads(multitable1, empty_multitable);
347     test_merge_overloads(empty_multitable, multitable2);
348 
349     // Unique/Multi tables transpositions
350     test_merge_overloads(table1, multitable1);
351     test_merge_overloads(multitable2, table2);
352 }
353 
354 template <typename SrcTableType, typename DstTableType>
355 void check_concurrent_merge( SrcTableType& start_data, DstTableType& dst_table,
356                              std::vector<SrcTableType>& src_tables, std::true_type )
357 {
358     REQUIRE_MESSAGE(dst_table.size() == start_data.size() * src_tables.size(),
359                     "Merge: Incorrect merge for some elements");
360 
361     for (auto it : start_data) {
362         REQUIRE_MESSAGE(dst_table.count(Value<DstTableType>::key(it)) ==
363                         start_data.count(Value<SrcTableType>::key(it)) * src_tables.size(),
364                         "Merge: Incorrect merge for some elements");
365     }
366 
367     for (size_t i = 0; i < src_tables.size(); ++i) {
368         REQUIRE_MESSAGE(src_tables[i].empty(), "Merge: Some elements were not merged");
369     }
370 }
371 
372 template <typename SrcTableType, typename DstTableType>
373 void check_concurrent_merge( SrcTableType& start_data, DstTableType& dst_table,
374                              std::vector<SrcTableType>& src_tables, std::false_type )
375 {
376     SrcTableType expected_result;
377     for (auto table : src_tables) {
378         for (auto it : start_data) {
379             // If we cannot find some element in some table, then it has been moved
380             if (!table.contains(Value<SrcTableType>::key(it))) {
381                 bool result = expected_result.insert(it).second;
382                 REQUIRE_MESSAGE(result,
383                                 "Merge: Some element was merged twice or was not returned to his owner after unsuccessful merge");
384             }
385         }
386     }
387 
388     REQUIRE_MESSAGE((expected_result.size() == dst_table.size() && start_data.size() == dst_table.size()),
389                     "Merge: wrong size of result table");
390 
391     for (auto it : expected_result) {
392         if (dst_table.contains(Value<SrcTableType>::key(it)) &&
393             start_data.contains(Value<DstTableType>::key(it)))
394         {
395             dst_table.unsafe_extract(Value<SrcTableType>::key(it));
396             start_data.unsafe_extract(Value<DstTableType>::key(it));
397         } else {
398             REQUIRE_MESSAGE(false, "Merge: Incorrect merge for some element");
399         }
400     }
401 
402     REQUIRE_MESSAGE((dst_table.empty() && start_data.empty()), "Merge: Some elements were not merged");
403 }
404 
405 template <typename SrcTableType, typename DstTableType>
406 void test_concurrent_merge( SrcTableType table_data ) {
407     for (std::size_t num_threads = utils::MinThread; num_threads <= utils::MaxThread; ++num_threads) {
408         std::vector<SrcTableType> src_tables;
409         DstTableType dst_table;
410 
411         for (std::size_t j = 0; j < num_threads; ++j) {
412             src_tables.push_back(table_data);
413         }
414 
415         utils::NativeParallelFor(num_threads, [&](std::size_t index) { dst_table.merge(src_tables[index]); } );
416 
417         check_concurrent_merge(table_data, dst_table, src_tables,
418                             AllowMultimapping<DstTableType>{});
419     }
420 }
421 
422 template <typename Container1, typename Container2>
423 void test_merge( int size ) {
424     Container1 table1_1;
425     Container1 table1_2;
426     int i = 1;
427 
428     for (; i < 5; ++i) {
429         table1_1.insert(Value<Container1>::make(i));
430         table1_2.insert(Value<Container1>::make(i * i));
431     }
432     if (AllowMultimapping<Container1>::value) {
433         table1_1.insert(Value<Container1>::make(i));
434         table1_2.insert(Value<Container1>::make(i * i));
435     }
436 
437     Container2 table2_1;
438     Container2 table2_2;
439 
440     for (i = 3; i < 7; ++i) {
441         table2_1.insert(Value<Container2>::make(i));
442         table2_2.insert(Value<Container2>::make(i * i));
443     }
444     if (AllowMultimapping<Container2>::value) {
445         table2_1.insert(Value<Container2>::make(i));
446         table2_2.insert(Value<Container2>::make(i * i));
447     }
448 
449     test_merge_transposition(table1_1, table1_2, table2_1, table2_2);
450 
451     Container1 table1_3;
452     Container2 table2_3;
453     for (i = 0; i < size; ++i) {
454         table1_3.insert(Value<Container1>::make(i));
455         table2_3.insert(Value<Container2>::make(i));
456     }
457 
458     test_concurrent_merge<Container1, Container2>(table1_3);
459     test_concurrent_merge<Container2, Container1>(table2_3);
460 }
461 
462 } // namespace node_handling tests
463 
464 #endif // __TBB_test_common_node_handling_support_H
465