2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 #include <cds/container/cuckoo_set.h>
36 namespace cc = cds::container;
38 class CuckooSet : public cds_test::container_set
41 typedef cds_test::container_set base_class;
43 template <typename Set>
46 // Precondition: set is empty
47 // Postcondition: set is empty
49 base_class::test_< Set::c_isSorted>( s );
59 struct store_hash_traits: public cc::cuckoo::traits
61 static bool const store_hash = true;
65 //************************************************************
68 TEST_F( CuckooSet, striped_list_unordered )
70 struct set_traits: public cc::cuckoo::traits
72 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
73 typedef base_class::equal_to equal_to;
74 typedef cc::cuckoo::list probeset_type;
76 typedef cc::CuckooSet< int_item, set_traits > set_type;
82 TEST_F( CuckooSet, striped_vector_unordered )
84 struct set_traits: public cc::cuckoo::traits
86 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
87 typedef base_class::equal_to equal_to;
88 typedef cc::cuckoo::vector<4> probeset_type;
90 typedef cc::CuckooSet< int_item, set_traits > set_type;
96 TEST_F( CuckooSet, striped_list_ordered_cmp )
98 typedef cc::CuckooSet< int_item
99 , cc::cuckoo::make_traits<
100 cds::opt::hash< std::tuple< hash1, hash2 > >
101 ,cds::opt::compare< cmp >
102 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
106 set_type s( 32, 6, 4 );
110 TEST_F( CuckooSet, striped_vector_ordered_cmp )
112 typedef cc::CuckooSet< int_item
113 , cc::cuckoo::make_traits<
114 cds::opt::hash< std::tuple< hash1, hash2 > >
115 ,cds::opt::compare< cmp >
116 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>>
120 typename set_type::hash_tuple_type ht;
125 TEST_F( CuckooSet, striped_list_ordered_less )
127 typedef cc::CuckooSet< int_item
128 , cc::cuckoo::make_traits<
129 cds::opt::hash< std::tuple< hash1, hash2 > >
130 ,cds::opt::less< less >
131 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
135 typename set_type::hash_tuple_type ht;
136 set_type s( 32, 6, 4, ht );
140 TEST_F( CuckooSet, striped_vector_ordered_less )
142 typedef cc::CuckooSet< int_item
143 , cc::cuckoo::make_traits<
144 cds::opt::hash< std::tuple< hash1, hash2 > >
145 ,cds::opt::less< less >
146 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>>
150 typename set_type::hash_tuple_type ht;
151 set_type s( std::move( ht ) );
155 TEST_F( CuckooSet, striped_list_ordered_cmpmix )
157 typedef cc::CuckooSet< int_item
158 , cc::cuckoo::make_traits<
159 cds::opt::hash< std::tuple< hash1, hash2 > >
160 ,cds::opt::less< less >
161 ,cds::opt::compare< cmp >
162 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
166 typename set_type::hash_tuple_type ht;
167 set_type s( 32, 6, 0, std::move( ht ) );
171 TEST_F( CuckooSet, striped_vector_ordered_cmpmix )
173 typedef cc::CuckooSet< int_item
174 , cc::cuckoo::make_traits<
175 cds::opt::hash< std::tuple< hash1, hash2 > >
176 ,cds::opt::less< less >
177 ,cds::opt::compare< cmp >
178 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>>
182 typename set_type::hash_tuple_type ht;
183 set_type s( std::move( ht ) );
187 TEST_F( CuckooSet, striped_list_ordered_stat )
189 typedef cc::CuckooSet< int_item
190 , cc::cuckoo::make_traits<
191 cds::opt::hash< std::tuple< hash1, hash2 > >
192 ,cds::opt::less< less >
193 ,cds::opt::compare< cmp >
194 ,cds::opt::stat< cc::cuckoo::stat >
195 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
203 TEST_F( CuckooSet, striped_vector_ordered_stat )
205 typedef cc::CuckooSet< int_item
206 , cc::cuckoo::make_traits<
207 cds::opt::hash< std::tuple< hash1, hash2 > >
208 ,cds::opt::less< less >
209 ,cds::opt::compare< cmp >
210 ,cds::opt::stat< cc::cuckoo::stat >
211 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>>
219 TEST_F( CuckooSet, striped_list_unordered_storehash )
221 struct set_traits: public store_hash_traits
223 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
224 typedef base_class::equal_to equal_to;
225 typedef cc::cuckoo::list probeset_type;
226 typedef cc::cuckoo::stat stat;
228 typedef cc::CuckooSet< int_item, set_traits > set_type;
234 TEST_F( CuckooSet, striped_vector_unordered_storehash )
236 struct set_traits: public store_hash_traits
238 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
239 typedef base_class::equal_to equal_to;
240 typedef cc::cuckoo::stat stat;
241 typedef cc::cuckoo::vector<4> probeset_type;
243 typedef cc::CuckooSet< int_item, set_traits > set_type;
249 TEST_F( CuckooSet, striped_list_ordered_storehash )
251 typedef cc::CuckooSet< int_item
252 ,cc::cuckoo::make_traits<
253 cds::opt::hash< std::tuple< hash1, hash2 > >
254 ,cds::opt::less< less >
255 ,cds::opt::compare< cmp >
256 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
257 ,cc::cuckoo::store_hash< true >
261 typename set_type::hash_tuple_type ht;
262 set_type s( 32, 6, 0, std::move( ht ));
266 TEST_F( CuckooSet, striped_vector_ordered_storehash )
268 typedef cc::CuckooSet< int_item
269 ,cc::cuckoo::make_traits<
270 cds::opt::hash< std::tuple< hash1, hash2 > >
271 ,cds::opt::less< less >
272 ,cds::opt::compare< cmp >
273 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>>
274 ,cc::cuckoo::store_hash< true >
278 typename set_type::hash_tuple_type ht;
279 set_type s( std::move( ht ));
284 //************************************************************
287 TEST_F( CuckooSet, refinable_list_unordered )
289 struct set_traits: public cc::cuckoo::traits
291 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
292 typedef base_class::equal_to equal_to;
293 typedef cc::cuckoo::list probeset_type;
294 typedef cc::cuckoo::refinable<> mutex_policy;
296 typedef cc::CuckooSet< int_item, set_traits > set_type;
302 TEST_F( CuckooSet, refinable_vector_unordered )
304 struct set_traits: public cc::cuckoo::traits
306 typedef cc::cuckoo::refinable<> mutex_policy;
307 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
308 typedef base_class::equal_to equal_to;
309 typedef cc::cuckoo::vector<4> probeset_type;
311 typedef cc::CuckooSet< int_item, set_traits > set_type;
317 TEST_F( CuckooSet, refinable_list_ordered_cmp )
319 typedef cc::CuckooSet< int_item
320 , cc::cuckoo::make_traits<
321 cds::opt::hash< std::tuple< hash1, hash2 > >
322 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
323 ,cds::opt::compare< cmp >
324 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
328 set_type s( 32, 6, 4 );
332 TEST_F( CuckooSet, refinable_vector_ordered_cmp )
334 typedef cc::CuckooSet< int_item
335 , cc::cuckoo::make_traits<
336 cds::opt::hash< std::tuple< hash1, hash2 >>
337 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
338 ,cds::opt::compare< cmp >
339 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>>
343 typename set_type::hash_tuple_type ht;
348 TEST_F( CuckooSet, refinable_list_ordered_less )
350 typedef cc::CuckooSet< int_item
351 , cc::cuckoo::make_traits<
352 cds::opt::hash< std::tuple< hash1, hash2 > >
353 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
354 ,cds::opt::less< less >
355 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
359 typename set_type::hash_tuple_type ht;
360 set_type s( 32, 6, 4, ht );
364 TEST_F( CuckooSet, refinable_vector_ordered_less )
366 typedef cc::CuckooSet< int_item
367 , cc::cuckoo::make_traits<
368 cds::opt::hash< std::tuple< hash1, hash2 > >
369 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
370 ,cds::opt::less< less >
371 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>>
375 typename set_type::hash_tuple_type ht;
376 set_type s( std::move( ht ) );
380 TEST_F( CuckooSet, refinable_list_ordered_cmpmix )
382 typedef cc::CuckooSet< int_item
383 , cc::cuckoo::make_traits<
384 cds::opt::hash< std::tuple< hash1, hash2 > >
385 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
386 ,cds::opt::less< less >
387 ,cds::opt::compare< cmp >
388 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
392 typename set_type::hash_tuple_type ht;
393 set_type s( 32, 6, 0, std::move( ht ) );
397 TEST_F( CuckooSet, refinable_vector_ordered_cmpmix )
399 typedef cc::CuckooSet< int_item
400 , cc::cuckoo::make_traits<
401 cds::opt::hash< std::tuple< hash1, hash2 > >
402 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
403 ,cds::opt::less< less >
404 ,cds::opt::compare< cmp >
405 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>>
409 typename set_type::hash_tuple_type ht;
410 set_type s( std::move( ht ) );
414 TEST_F( CuckooSet, refinable_list_ordered_stat )
416 typedef cc::CuckooSet< int_item
417 , cc::cuckoo::make_traits<
418 cds::opt::hash< std::tuple< hash1, hash2 > >
419 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
420 ,cds::opt::less< less >
421 ,cds::opt::compare< cmp >
422 ,cds::opt::stat< cc::cuckoo::stat >
423 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
431 TEST_F( CuckooSet, refinable_vector_ordered_stat )
433 typedef cc::CuckooSet< int_item
434 , cc::cuckoo::make_traits<
435 cds::opt::hash< std::tuple< hash1, hash2 > >
436 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
437 ,cds::opt::less< less >
438 ,cds::opt::compare< cmp >
439 ,cds::opt::stat< cc::cuckoo::stat >
440 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>>
448 TEST_F( CuckooSet, refinable_list_unordered_storehash )
450 struct set_traits: public store_hash_traits
452 typedef cc::cuckoo::refinable<> mutex_policy;
453 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
454 typedef base_class::equal_to equal_to;
455 typedef cc::cuckoo::list probeset_type;
456 typedef cc::cuckoo::stat stat;
458 typedef cc::CuckooSet< int_item, set_traits > set_type;
464 TEST_F( CuckooSet, refinable_vector_unordered_storehash )
466 struct set_traits: public store_hash_traits
468 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
469 typedef cc::cuckoo::refinable<> mutex_policy;
470 typedef base_class::equal_to equal_to;
471 typedef cc::cuckoo::stat stat;
472 typedef cc::cuckoo::vector<4> probeset_type;
474 typedef cc::CuckooSet< int_item, set_traits > set_type;
480 TEST_F( CuckooSet, refinable_list_ordered_storehash )
482 typedef cc::CuckooSet< int_item
483 ,cc::cuckoo::make_traits<
484 cds::opt::hash< std::tuple< hash1, hash2 > >
485 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
486 ,cds::opt::less< less >
487 ,cds::opt::compare< cmp >
488 ,cc::cuckoo::probeset_type< cc::cuckoo::list >
489 ,cc::cuckoo::store_hash< true >
493 typename set_type::hash_tuple_type ht;
494 set_type s( 32, 6, 0, std::move( ht ));
498 TEST_F( CuckooSet, refinable_vector_ordered_storehash )
500 typedef cc::CuckooSet< int_item
501 ,cc::cuckoo::make_traits<
502 cds::opt::hash< std::tuple< hash1, hash2 > >
503 ,cds::opt::mutex_policy< cc::cuckoo::refinable<>>
504 ,cds::opt::less< less >
505 ,cds::opt::compare< cmp >
506 ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>>
507 ,cc::cuckoo::store_hash< true >
511 typename set_type::hash_tuple_type ht;
512 set_type s( std::move( ht ));