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_map.h>
36 namespace cc = cds::container;
38 class CuckooMap : public cds_test::container_map
41 typedef cds_test::container_map base_class;
43 template <typename Set>
46 // Precondition: set is empty
47 // Postcondition: set is empty
49 base_class::test_< Set::c_isSorted>( m );
59 struct store_hash_traits: public cc::cuckoo::traits
61 static bool const store_hash = true;
65 //************************************************************
68 TEST_F( CuckooMap, striped_list_unordered )
70 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
82 TEST_F( CuckooMap, striped_vector_unordered )
84 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
96 TEST_F( CuckooMap, striped_list_ordered_cmp )
98 typedef cc::CuckooMap< key_type, value_type
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 map_type m( 32, 6, 4 );
110 TEST_F( CuckooMap, striped_vector_ordered_cmp )
112 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
125 TEST_F( CuckooMap, striped_list_ordered_less )
127 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
136 map_type m( 32, 6, 4, ht );
140 TEST_F( CuckooMap, striped_vector_ordered_less )
142 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
151 map_type m( std::move( ht ) );
155 TEST_F( CuckooMap, striped_list_ordered_cmpmix )
157 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
167 map_type m( 32, 6, 0, std::move( ht ) );
171 TEST_F( CuckooMap, striped_vector_ordered_cmpmix )
173 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
183 map_type m( std::move( ht ) );
187 TEST_F( CuckooMap, striped_list_ordered_stat )
189 typedef cc::CuckooMap< key_type, value_type
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( CuckooMap, striped_vector_ordered_stat )
205 typedef cc::CuckooMap< key_type, value_type
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( CuckooMap, striped_list_unordered_storehash )
221 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
234 TEST_F( CuckooMap, striped_vector_unordered_storehash )
236 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
249 TEST_F( CuckooMap, striped_list_ordered_storehash )
251 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
262 map_type m( 32, 6, 0, std::move( ht ));
266 TEST_F( CuckooMap, striped_vector_ordered_storehash )
268 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
279 map_type m( std::move( ht ));
284 //************************************************************
287 TEST_F( CuckooMap, refinable_list_unordered )
289 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
302 TEST_F( CuckooMap, refinable_vector_unordered )
304 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
317 TEST_F( CuckooMap, refinable_list_ordered_cmp )
319 typedef cc::CuckooMap< key_type, value_type
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 map_type m( 32, 6, 4 );
332 TEST_F( CuckooMap, refinable_vector_ordered_cmp )
334 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
348 TEST_F( CuckooMap, refinable_list_ordered_less )
350 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
360 map_type m( 32, 6, 4, ht );
364 TEST_F( CuckooMap, refinable_vector_ordered_less )
366 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
376 map_type m( std::move( ht ) );
380 TEST_F( CuckooMap, refinable_list_ordered_cmpmix )
382 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
393 map_type m( 32, 6, 0, std::move( ht ) );
397 TEST_F( CuckooMap, refinable_vector_ordered_cmpmix )
399 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
410 map_type m( std::move( ht ) );
414 TEST_F( CuckooMap, refinable_list_ordered_stat )
416 typedef cc::CuckooMap< key_type, value_type
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( CuckooMap, refinable_vector_ordered_stat )
433 typedef cc::CuckooMap< key_type, value_type
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( CuckooMap, refinable_list_unordered_storehash )
450 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
464 TEST_F( CuckooMap, refinable_vector_unordered_storehash )
466 struct map_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::CuckooMap< key_type, value_type, map_traits > map_type;
480 TEST_F( CuckooMap, refinable_list_ordered_storehash )
482 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
494 map_type m( 32, 6, 0, std::move( ht ));
498 TEST_F( CuckooMap, refinable_vector_ordered_storehash )
500 typedef cc::CuckooMap< key_type, value_type
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 map_type::hash_tuple_type ht;
512 map_type m( std::move( ht ));