1 /*
2     Copyright (c) 2005-2023 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_unordered_common
18 #define __TBB_test_common_concurrent_unordered_common
19 
20 #define __TBB_UNORDERED_TEST 1
21 
22 #include "test.h"
23 #include <memory>
24 #include "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     REQUIRE( a.items_allocated == a.allocations);
31     REQUIRE( a.items_freed == a.frees);
32     REQUIRE( a.items_allocated == a.items_freed );
33     CheckAllocator<MyTable>(a, expected_allocs, expected_frees, exact);
34 }
35 
36 template<typename Container>
37 inline void CheckNoAllocations(Container &cont){
38     CheckContainerAllocator(cont, 0, 0, false);
39 }
40 
41 template<typename T>
42 struct degenerate_hash {
43     size_t operator()(const T& /*a*/) const {
44         return 1;
45     }
46 };
47 
48 template <typename T>
49 void test_unordered_methods(){
50     T cont;
51     cont.insert(Value<T>::make(1));
52     cont.insert(Value<T>::make(2));
53     // unordered_specific
54     // void rehash(size_type n);
55     cont.rehash(16);
56 
57     // float load_factor() const;
58     // float max_load_factor() const;
59     REQUIRE_MESSAGE(cont.load_factor() <= cont.max_load_factor(), "Load factor is invalid");
60 
61     // void max_load_factor(float z);
62     cont.max_load_factor(16.0f);
63     REQUIRE_MESSAGE(cont.max_load_factor() == 16.0f, "Max load factor has not been changed properly");
64 
65     // hasher hash_function() const;
66     cont.hash_function();
67 
68     // key_equal key_eq() const;
69     cont.key_eq();
70 
71     cont.clear();
72     CheckNoAllocations(cont);
73     for (int i = 0; i < 256; i++)
74     {
75         std::pair<typename T::iterator, bool> ins3 = cont.insert(Value<T>::make(i));
76         REQUIRE_MESSAGE((ins3.second == true && Value<T>::get(*(ins3.first)) == i), "Element 1 has not been inserted properly");
77     }
78     REQUIRE_MESSAGE(cont.size() == 256, "Wrong number of elements have been inserted");
79     // size_type unsafe_bucket_count() const;
80     REQUIRE_MESSAGE(cont.unsafe_bucket_count() == 16, "Wrong number of buckets");
81 
82     // size_type unsafe_max_bucket_count() const;
83     //REQUIRE_MESSAGE(cont.unsafe_max_bucket_count() > 65536, "Wrong max number of buckets");
84 
85     for (unsigned int i = 0; i < 256; i++)
86     {
87         typename T::size_type buck = cont.unsafe_bucket(i);
88 
89         // size_type unsafe_bucket(const key_type& k) const;
90         REQUIRE_MESSAGE(buck < 16, "Wrong bucket mapping");
91     }
92 
93     typename T::size_type bucketSizeSum = 0;
94     typename T::size_type iteratorSizeSum = 0;
95 
96     for (unsigned int i = 0; i < 16; i++)
97     {
98         bucketSizeSum += cont.unsafe_bucket_size(i);
99         for (typename T::iterator bit = cont.unsafe_begin(i); bit != cont.unsafe_end(i); bit++) iteratorSizeSum++;
100     }
101     REQUIRE_MESSAGE(bucketSizeSum == 256, "sum of bucket counts incorrect");
102     REQUIRE_MESSAGE(iteratorSizeSum == 256, "sum of iterator counts incorrect");
103 }
104 
105 template<typename Container, typename CheckElementState = std::false_type>
106 void test_basic(){
107     test_basic_common<Container, CheckElementState>();
108     test_unordered_methods<Container>();
109 }
110 
111 template <typename Container>
112 void test_concurrent( bool asymptotic = false ) {
113     test_concurrent_common<Container>(asymptotic);
114 }
115 
116 struct UnorderedMoveTraitsBase {
117     static constexpr std::size_t expected_number_of_items_to_allocate_for_steal_move = 3; // TODO: check
118 
119     template <typename UnorderedType, typename Iterator>
120     static UnorderedType& construct_container( typename std::aligned_storage<sizeof(UnorderedType)>::type& storage,
121                                                Iterator begin, Iterator end )
122     {
123         UnorderedType* ptr = reinterpret_cast<UnorderedType*>(&storage);
124         new (ptr) UnorderedType(begin, end);
125         return *ptr;
126     }
127 
128     template <typename UnorderedType, typename Iterator, typename Allocator>
129     static UnorderedType& construct_container( typename std::aligned_storage<sizeof(UnorderedType)>::type& storage,
130                                                 Iterator begin, Iterator end, const Allocator& alloc )
131     {
132         UnorderedType* ptr = reinterpret_cast<UnorderedType*>(&storage);
133         new (ptr) UnorderedType(begin, end, /*bucket_count = */4, alloc);
134         return *ptr;
135     }
136 
137     template <typename UnorderedType, typename Iterator>
138     static bool equal( const UnorderedType& c, Iterator begin, Iterator end ) {
139         if (std::size_t(std::distance(begin, end)) != c.size()) {
140             return false;
141         }
142 
143         for (Iterator it = begin; it != end; ++it) {
144             if (!c.contains(Value<UnorderedType>::key(*it))) {
145                 return false;
146             }
147         }
148         return true;
149     }
150 }; // struct UnorderedMoveTraitsBase
151 
152 template <bool DefCtorPresent, typename Table>
153 void CustomExamine( Table c, const std::list<typename Table::value_type>& lst ) {
154     using size_type = typename Table::size_type;
155     const Table constC = c;
156 
157     const size_type bucket_count = c.unsafe_bucket_count();
158     REQUIRE(c.unsafe_max_bucket_count() >= bucket_count);
159 
160     size_type counter = 0;
161     for (size_type i = 0; i < bucket_count; ++i) {
162         const size_type size = c.unsafe_bucket_size(i);
163         using diff_type = typename Table::difference_type;
164 
165         REQUIRE(std::distance(c.unsafe_begin(i), c.unsafe_end(i)) == diff_type(size));
166         REQUIRE(std::distance(c.unsafe_cbegin(i), c.unsafe_cend(i)) == diff_type(size));
167         REQUIRE(std::distance(constC.unsafe_begin(i), constC.unsafe_end(i)) == diff_type(size));
168         REQUIRE(std::distance(constC.unsafe_cbegin(i), constC.unsafe_cend(i)) == diff_type(size));
169         counter += size;
170     }
171 
172     REQUIRE(counter == lst.size());
173 
174     for (auto it = lst.begin(); it != lst.end();) {
175         const size_type index = c.unsafe_bucket(Value<Table>::key(*it));
176         auto prev_it = it++;
177         REQUIRE(std::search(c.unsafe_begin(index), c.unsafe_end(index), prev_it, it, utils::IsEqual()) != c.unsafe_end(index));
178     }
179 
180     c.rehash(2*bucket_count);
181     REQUIRE(c.unsafe_bucket_count() > bucket_count);
182 
183     auto count = 2 * c.max_load_factor() * c.unsafe_bucket_count();
184     c.reserve(size_type(count));
185     REQUIRE(c.max_load_factor() * c.unsafe_bucket_count() >= count);
186 
187     REQUIRE(c.load_factor() <= c.max_load_factor());
188     c.max_load_factor(1.0f);
189     c.hash_function();
190     c.key_eq();
191 }
192 
193 template <bool DefCtorPresent, typename Table>
194 void Examine( Table c, const std::list<typename Table::value_type>& lst ) {
195     CommonExamine<DefCtorPresent>(c, lst);
196     CustomExamine<DefCtorPresent>(c, lst);
197 }
198 
199 // Necessary to avoid warnings about explicit copy assignment to itself
200 template <typename T>
201 T& self( T& obj ) {
202     return obj;
203 }
204 
205 template <bool DefCtorPresent, typename Table>
206 void TypeTester( const std::list<typename Table::value_type>& lst ) {
207     REQUIRE_MESSAGE(lst.size() >= 5, "Array should have at least 5 elements");
208     REQUIRE_MESSAGE(lst.size() <= 100, "The test hash O(n^2) complexity so a big number of elements can lead long execution time");
209 
210     Table c1;
211     c1.insert(lst.begin(), lst.end());
212 
213     Examine<DefCtorPresent>(c1, lst);
214 
215     typename Table::size_type initial_bucket_number = 8;
216     typename Table::allocator_type allocator;
217     typename Table::hasher hasher;
218 
219     auto it = lst.begin();
220     Table c2({*it++, *it++, *it++});
221     c2.insert(it, lst.end());
222     Examine<DefCtorPresent>(c2, lst);
223 
224     it = lst.begin();
225     // Constructor from an std::initializer_list, default hasher and key_equal and non-default allocator
226     Table c2_alloc({*it++, *it++, *it++}, initial_bucket_number, allocator);
227     c2_alloc.insert(it, lst.end());
228     Examine<DefCtorPresent>(c2_alloc, lst);
229 
230     it = lst.begin();
231     // Constructor from an std::initializer_list, default key_equal and non-default hasher and allocator
232     Table c2_hash_alloc({*it++, *it++, *it++}, initial_bucket_number, hasher, allocator);
233     c2_hash_alloc.insert(it, lst.end());
234     Examine<DefCtorPresent>(c2_hash_alloc, lst);
235 
236     // Copy ctor
237     Table c3(c1);
238     Examine<DefCtorPresent>(c3, lst);
239 
240     // Copy ctor with the allocator
241     Table c3_alloc(c1, allocator);
242     Examine<DefCtorPresent>(c3_alloc, lst);
243 
244     // Construct an empty table with n preallocated buckets
245     Table c4(lst.size());
246     c4.insert(lst.begin(), lst.end());
247     Examine<DefCtorPresent>(c4, lst);
248 
249     // Construct an empty table with n preallocated buckets, default hasher and key_equal and non-default allocator
250     Table c4_alloc(lst.size(), allocator);
251     c4_alloc.insert(lst.begin(), lst.end());
252     Examine<DefCtorPresent>(c4_alloc, lst);
253 
254     // Construct an empty table with n preallocated buckets, default key_equal and non-default hasher and allocator
255     Table c4_hash_alloc(lst.size(), hasher, allocator);
256     c4_hash_alloc.insert(lst.begin(), lst.end());
257     Examine<DefCtorPresent>(c4_hash_alloc, lst);
258 
259     // Construction from the iteration range
260     Table c5(c1.begin(), c1.end());
261     Examine<DefCtorPresent>(c5, lst);
262 
263     // Construction from the iteration range, default hasher and key_equal and non-default allocator
264     Table c5_alloc(c1.begin(), c2.end(), initial_bucket_number, allocator);
265     Examine<DefCtorPresent>(c5_alloc, lst);
266 
267     // Construction from the iteration range, default key_equal and non-default hasher and allocator
268     Table c5_hash_alloc(c1.begin(), c2.end(), initial_bucket_number, hasher, allocator);
269     Examine<DefCtorPresent>(c5_hash_alloc, lst);
270 
271     // Copy assignment
272     Table c6;
273     c6 = c1;
274     Examine<DefCtorPresent>(c6, lst);
275 
276     // Copy assignment to itself
277     c6 = self(c6);
278     Examine<DefCtorPresent>(c6, lst);
279 
280     // Move assignment
281     Table c7;
282     c7 = std::move(c6);
283     Examine<DefCtorPresent>(c7, lst);
284 
285     // Move assignment to itself
286     c7 = std::move(self(c7));
287     Examine<DefCtorPresent>(c7, lst);
288 
289     // Assignment to the std::initializer_list
290     Table c8;
291     it = lst.begin();
292     c8 = {*it++, *it++, *it++};
293     c8.insert(it, lst.end());
294     Examine<DefCtorPresent>(c8, lst);
295 }
296 
297 struct transparent_key_equality {
298 template <typename T>
299     bool operator()(const T&, const T&) const {
300         return true;
301     }
302     using is_transparent = void;
303 };
304 
305 struct hasher_with_transparent_key_equal {
306 template <typename T>
307     std::size_t operator()(const T&) {
308         return 0;
309     }
310     using transparent_key_equal = transparent_key_equality;
311 };
312 
313 template <template <typename...> class Container, typename... Args>
314 void check_heterogeneous_functions_key_int() {
315     check_heterogeneous_functions_key_int_impl<Container<Args..., hash_with_transparent_key_equal>>();
316 }
317 
318 template <template <typename...> class Container, typename... Args>
319 void check_heterogeneous_functions_key_string() {
320     check_heterogeneous_functions_key_string_impl<Container<Args..., hash_with_transparent_key_equal>>();
321 }
322 
323 template <typename Container>
324 void test_comparisons_basic() {
325     using comparisons_testing::testEqualityComparisons;
326     Container c1, c2;
327     testEqualityComparisons</*ExpectEqual = */true>(c1, c2);
328 
329     c1.insert(Value<Container>::make(1));
330     testEqualityComparisons</*ExpectEqual = */false>(c1, c2);
331 
332     c2.insert(Value<Container>::make(1));
333     testEqualityComparisons</*ExpectEqual = */true>(c1, c2);
334 
335     c2.insert(Value<Container>::make(2));
336     testEqualityComparisons</*ExpectEqual = */false>(c1, c2);
337 
338     c1.clear();
339     c2.clear();
340     testEqualityComparisons</*ExpectEqual = */true>(c1, c2);
341 }
342 
343 template <typename TwoWayComparableContainerType>
344 void test_two_way_comparable_container() {
345     TwoWayComparableContainerType c1, c2;
346     c1.insert(Value<TwoWayComparableContainerType>::make(1));
347     c2.insert(Value<TwoWayComparableContainerType>::make(1));
348     comparisons_testing::TwoWayComparable::reset();
349     REQUIRE_MESSAGE(c1 == c2, "Incorrect operator == result");
350     comparisons_testing::check_equality_comparison();
351     REQUIRE_MESSAGE(!(c1 != c2), "Incorrect operator != result");
352     comparisons_testing::check_equality_comparison();
353 }
354 
355 template <template <typename...> class ContainerType>
356 void test_map_comparisons() {
357     using integral_container = ContainerType<int, int>;
358     using two_way_comparable_container = ContainerType<comparisons_testing::TwoWayComparable,
359                                                        comparisons_testing::TwoWayComparable>;
360     test_comparisons_basic<integral_container>();
361     test_comparisons_basic<two_way_comparable_container>();
362     test_two_way_comparable_container<two_way_comparable_container>();
363 }
364 
365 template <template <typename...> class ContainerType>
366 void test_set_comparisons() {
367     using integral_container = ContainerType<int>;
368     using two_way_comparable_container = ContainerType<comparisons_testing::TwoWayComparable>;
369 
370     test_comparisons_basic<integral_container>();
371     test_comparisons_basic<two_way_comparable_container>();
372     test_two_way_comparable_container<two_way_comparable_container>();
373 }
374 
375 template <typename Container>
376 void test_reserve_regression() {
377     Container container;
378 
379     float lf = container.max_load_factor();
380     std::size_t buckets = container.unsafe_bucket_count();
381     std::size_t capacity = std::size_t(buckets * lf);
382 
383     for (std::size_t elements = 0; elements < capacity; ++elements) {
384         container.reserve(elements);
385         REQUIRE_MESSAGE(container.unsafe_bucket_count() == buckets,
386                         "reserve() should not increase bucket count if the capacity is not reached");
387     }
388 
389     container.reserve(capacity * 2);
390     REQUIRE_MESSAGE(container.unsafe_bucket_count() > buckets, "reserve() should increase bucket count if the capacity is reached");
391 }
392 
393 #endif // __TBB_test_common_concurrent_unordered_common
394