3 #ifndef __CDSTEST_HDR_STRIPED_MAP_H
4 #define __CDSTEST_HDR_STRIPED_MAP_H
5 #include "size_check.h"
7 #include "cppunit/cppunit_proxy.h"
8 #include <cds/os/timer.h>
9 #include <cds/opt/hash.h>
10 #include <functional> // ref
11 #include <algorithm> // random_shuffle
13 namespace cds { namespace container {}}
16 using misc::check_size;
18 namespace cc = cds::container;
19 namespace co = cds::opt;
21 class StripedMapHdrTest: public CppUnitMini::TestCase
37 value_type( value_type&& v )
41 value_type( value_type const& v )
45 value_type& operator=( value_type const& v )
52 typedef std::pair<key_type const, value_type> pair_type;
56 bool operator ()(int v1, int v2 ) const
63 int operator ()(int v1, int v2 ) const
67 return v1 > v2 ? 1 : 0;
72 bool operator ()(int v1, int v2 ) const
79 size_t operator()( int i ) const
81 return co::v::hash<int>()( i );
85 struct simple_item_counter {
107 operator size_t() const
113 template <typename Map>
114 struct insert_functor
116 typedef typename Map::value_type pair_type;
119 void operator()( pair_type& item )
121 item.second.m_val = item.first * 3;
125 void operator()( bool bNew, pair_type& item )
128 item.second.m_val = item.first * 2;
130 item.second.m_val = item.first * 5;
137 check_value( int nExpected )
138 : m_nExpected( nExpected )
141 template <typename T>
142 void operator ()( T& pair )
144 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
146 template <typename T, typename Q>
147 void operator ()( T& pair, Q )
149 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
153 struct extract_functor
156 void operator()( pair_type const& val )
158 *m_pVal = val.second.m_val;
163 void test_int_with( Map& m )
165 std::pair<bool, bool> ensureResult;
168 CPPUNIT_ASSERT( m.empty() );
169 CPPUNIT_ASSERT( check_size( m, 0 ));
170 CPPUNIT_ASSERT( !m.find(25) );
171 CPPUNIT_ASSERT( m.insert( 25 ) ) ; // value = 0
172 CPPUNIT_ASSERT( m.find(25) );
173 CPPUNIT_ASSERT( !m.empty() );
174 CPPUNIT_ASSERT( check_size( m, 1 ));
175 CPPUNIT_ASSERT( m.find(25) );
177 CPPUNIT_ASSERT( !m.insert( 25 ) );
178 CPPUNIT_ASSERT( !m.empty() );
179 CPPUNIT_ASSERT( check_size( m, 1 ));
181 CPPUNIT_ASSERT( !m.find(10) );
182 CPPUNIT_ASSERT( m.insert( 10, 10 ) );
183 CPPUNIT_ASSERT( !m.empty() );
184 CPPUNIT_ASSERT( check_size( m, 2 ));
185 CPPUNIT_ASSERT( m.find(10) );
187 CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
188 CPPUNIT_ASSERT( !m.empty() );
189 CPPUNIT_ASSERT( check_size( m, 2 ));
191 CPPUNIT_ASSERT( !m.find(30) );
192 CPPUNIT_ASSERT( m.insert_key( 30, insert_functor<Map>() ) ) ; // value = 90
193 CPPUNIT_ASSERT( !m.empty() );
194 CPPUNIT_ASSERT( check_size( m, 3 ));
195 CPPUNIT_ASSERT( m.find(30) );
197 CPPUNIT_ASSERT( !m.insert_key( 10, insert_functor<Map>() ) );
198 CPPUNIT_ASSERT( !m.insert_key( 25, insert_functor<Map>() ) );
199 CPPUNIT_ASSERT( !m.insert_key( 30, insert_functor<Map>() ) );
202 CPPUNIT_ASSERT( !m.find(27) );
203 ensureResult = m.ensure( 27, insert_functor<Map>() ) ; // value = 54
204 CPPUNIT_ASSERT( ensureResult.first );
205 CPPUNIT_ASSERT( ensureResult.second );
206 CPPUNIT_ASSERT( check_size( m, 4 ));
207 CPPUNIT_ASSERT( m.find(27) );
211 CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
213 CPPUNIT_ASSERT( m.find( 25, std::ref( chk ) ) );
214 chk.m_nExpected = 90;
215 CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
216 chk.m_nExpected = 54;
217 CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
219 ensureResult = m.ensure( 10, insert_functor<Map>() ) ; // value = 50
220 CPPUNIT_ASSERT( ensureResult.first );
221 CPPUNIT_ASSERT( !ensureResult.second );
222 chk.m_nExpected = 50;
223 CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
226 CPPUNIT_ASSERT( !m.find(100) );
227 CPPUNIT_ASSERT( !m.erase( 100 )) ; // not found
229 CPPUNIT_ASSERT( m.find(25) );
230 CPPUNIT_ASSERT( check_size( m, 4 ));
231 CPPUNIT_ASSERT( m.erase( 25 ));
232 CPPUNIT_ASSERT( !m.empty() );
233 CPPUNIT_ASSERT( check_size( m, 3 ));
234 CPPUNIT_ASSERT( !m.find(25) );
235 CPPUNIT_ASSERT( !m.erase( 25 ));
237 CPPUNIT_ASSERT( !m.find(258) );
238 CPPUNIT_ASSERT( m.insert(258))
239 CPPUNIT_ASSERT( check_size( m, 4 ));
240 CPPUNIT_ASSERT( m.find(258) );
241 CPPUNIT_ASSERT( m.erase( 258 ));
242 CPPUNIT_ASSERT( !m.empty() );
243 CPPUNIT_ASSERT( check_size( m, 3 ));
244 CPPUNIT_ASSERT( !m.find(258) );
245 CPPUNIT_ASSERT( !m.erase( 258 ));
251 CPPUNIT_ASSERT( !m.find(29) );
252 CPPUNIT_ASSERT( m.insert(29, 290));
253 CPPUNIT_ASSERT( check_size( m, 4 ));
254 CPPUNIT_ASSERT( m.erase( 29, std::ref( ext ) ) );
255 CPPUNIT_ASSERT( !m.empty() );
256 CPPUNIT_ASSERT( check_size( m, 3 ));
257 CPPUNIT_ASSERT( nVal == 290 );
259 CPPUNIT_ASSERT( !m.erase( 29, std::ref( ext ) ) );
260 CPPUNIT_ASSERT( nVal == -1 );
262 CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
263 CPPUNIT_ASSERT( !m.empty() );
264 CPPUNIT_ASSERT( check_size( m, 2 ));
265 CPPUNIT_ASSERT( nVal == 90 );
267 CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
268 CPPUNIT_ASSERT( nVal == -1 );
271 CPPUNIT_ASSERT( m.empty() );
272 CPPUNIT_ASSERT( check_size( m, 0 ));
275 CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
276 CPPUNIT_ASSERT( m.emplace(137, 731)) ; // key = 137, val = 731
277 CPPUNIT_ASSERT( m.emplace( 149, value_type(941) )) ; // key = 149, val = 941
279 CPPUNIT_ASSERT( !m.empty() );
280 CPPUNIT_ASSERT( check_size( m, 3 ));
283 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
284 chk.m_nExpected = 731;
285 CPPUNIT_ASSERT( m.find( 137, std::ref(chk) ));
286 chk.m_nExpected = 941;
287 CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
289 CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
291 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
292 CPPUNIT_ASSERT( !m.empty() );
293 CPPUNIT_ASSERT( check_size( m, 3 ));
296 CPPUNIT_ASSERT( m.empty() );
297 CPPUNIT_ASSERT( check_size( m, 0 ));
301 void test_iter( Map& s)
303 typedef typename Map::iterator iterator;
304 typedef typename Map::const_iterator const_iterator;
306 const int nMaxCount = 500;
307 for ( int i = 0; i < nMaxCount; ++i ) {
308 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
312 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
313 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
314 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
315 it->second.m_val = it->first;
318 CPPUNIT_ASSERT( nCount == nMaxCount );
320 Map const& refSet = s;
322 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
323 CPPUNIT_ASSERT( it->first == it->second.m_val );
324 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
327 CPPUNIT_ASSERT( nCount == nMaxCount );
334 CPPUNIT_ASSERT( m.bucket_count() == 32 );
335 CPPUNIT_ASSERT( m.lock_count() == 32 );
337 test_striped_with(m);
341 void test_striped_with(Map& m)
343 cds::OS::Timer timer;
347 // Iterators is not yet supported
349 //CPPUNIT_ASSERT( m.empty() );
350 //CPPUNIT_ASSERT( check_size( m, 0 ));
354 CPPUNIT_ASSERT( m.empty() );
355 CPPUNIT_ASSERT( check_size( m, 0 ));
358 for ( int i = 0; i < 40000; i++ ) {
362 CPPUNIT_MSG( " Duration=" << timer.duration() );
365 //*******************************************
366 // If erase_with && find_with are supported
368 void test_int_with2( Map& m )
370 std::pair<bool, bool> ensureResult;
373 CPPUNIT_ASSERT( m.empty() );
374 CPPUNIT_ASSERT( check_size( m, 0 ));
375 CPPUNIT_ASSERT( !m.find(25) );
376 CPPUNIT_ASSERT( m.insert( 25 ) ) ; // value = 0
377 CPPUNIT_ASSERT( m.find(25) );
378 CPPUNIT_ASSERT( !m.empty() );
379 CPPUNIT_ASSERT( check_size( m, 1 ));
380 CPPUNIT_ASSERT( m.find(25) );
382 CPPUNIT_ASSERT( !m.insert( 25 ) );
383 CPPUNIT_ASSERT( !m.empty() );
384 CPPUNIT_ASSERT( check_size( m, 1 ));
386 CPPUNIT_ASSERT( !m.find_with(10, less()) );
387 CPPUNIT_ASSERT( m.insert( 10, 10 ) );
388 CPPUNIT_ASSERT( !m.empty() );
389 CPPUNIT_ASSERT( check_size( m, 2 ));
390 CPPUNIT_ASSERT( m.find_with(10, less()) );
392 CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
393 CPPUNIT_ASSERT( !m.empty() );
394 CPPUNIT_ASSERT( check_size( m, 2 ));
396 CPPUNIT_ASSERT( !m.find(30) );
397 CPPUNIT_ASSERT( m.insert_key( 30, insert_functor<Map>() ) ) ; // value = 90
398 CPPUNIT_ASSERT( !m.empty() );
399 CPPUNIT_ASSERT( check_size( m, 3 ));
400 CPPUNIT_ASSERT( m.find(30) );
402 CPPUNIT_ASSERT( !m.insert_key( 10, insert_functor<Map>() ) );
403 CPPUNIT_ASSERT( !m.insert_key( 25, insert_functor<Map>() ) );
404 CPPUNIT_ASSERT( !m.insert_key( 30, insert_functor<Map>() ) );
407 CPPUNIT_ASSERT( !m.find(27) );
408 ensureResult = m.ensure( 27, insert_functor<Map>() ) ; // value = 54
409 CPPUNIT_ASSERT( ensureResult.first );
410 CPPUNIT_ASSERT( ensureResult.second );
411 CPPUNIT_ASSERT( m.find(27) );
415 CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
417 CPPUNIT_ASSERT( m.find_with( 25, less(), std::ref( chk ) ) );
418 chk.m_nExpected = 90;
419 CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
420 chk.m_nExpected = 54;
421 CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
423 ensureResult = m.ensure( 10, insert_functor<Map>() ) ; // value = 50
424 CPPUNIT_ASSERT( ensureResult.first );
425 CPPUNIT_ASSERT( !ensureResult.second );
426 chk.m_nExpected = 50;
427 CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
430 CPPUNIT_ASSERT( !m.find(100) );
431 CPPUNIT_ASSERT( !m.erase( 100 )) ; // not found
433 CPPUNIT_ASSERT( m.find(25) );
434 CPPUNIT_ASSERT( check_size( m, 4 ));
435 CPPUNIT_ASSERT( m.erase( 25 ));
436 CPPUNIT_ASSERT( !m.empty() );
437 CPPUNIT_ASSERT( check_size( m, 3 ));
438 CPPUNIT_ASSERT( !m.find(25) );
439 CPPUNIT_ASSERT( !m.erase( 25 ));
441 CPPUNIT_ASSERT( !m.find(258) );
442 CPPUNIT_ASSERT( m.insert(258))
443 CPPUNIT_ASSERT( check_size( m, 4 ));
444 CPPUNIT_ASSERT( m.find_with(258, less()) );
445 CPPUNIT_ASSERT( m.erase_with( 258, less() ));
446 CPPUNIT_ASSERT( !m.empty() );
447 CPPUNIT_ASSERT( check_size( m, 3 ));
448 CPPUNIT_ASSERT( !m.find(258) );
449 CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
455 CPPUNIT_ASSERT( !m.find(29) );
456 CPPUNIT_ASSERT( m.insert(29, 290))
457 CPPUNIT_ASSERT( m.erase_with( 29, less(), std::ref( ext ) ) );
458 CPPUNIT_ASSERT( !m.empty() );
459 CPPUNIT_ASSERT( check_size( m, 3 ));
460 CPPUNIT_ASSERT( nVal == 290 );
462 CPPUNIT_ASSERT( !m.erase_with( 29, less(), std::ref( ext ) ) );
463 CPPUNIT_ASSERT( nVal == -1 );
465 CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
466 CPPUNIT_ASSERT( !m.empty() );
467 CPPUNIT_ASSERT( check_size( m, 2 ));
468 CPPUNIT_ASSERT( nVal == 90 );
470 CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
471 CPPUNIT_ASSERT( nVal == -1 );
474 CPPUNIT_ASSERT( m.empty() );
475 CPPUNIT_ASSERT( check_size( m, 0 ));
478 CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
479 CPPUNIT_ASSERT( m.emplace(137, 731)) ; // key = 137, val = 731
480 CPPUNIT_ASSERT( m.emplace( 149, value_type(941) )) ; // key = 149, val = 941
482 CPPUNIT_ASSERT( !m.empty() );
483 CPPUNIT_ASSERT( check_size( m, 3 ));
486 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
487 chk.m_nExpected = 731;
488 CPPUNIT_ASSERT( m.find_with( 137, less(), std::ref(chk) ));
489 chk.m_nExpected = 941;
490 CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
492 CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
494 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
495 CPPUNIT_ASSERT( !m.empty() );
496 CPPUNIT_ASSERT( check_size( m, 3 ));
499 CPPUNIT_ASSERT( m.empty() );
500 CPPUNIT_ASSERT( check_size( m, 0 ));
504 void test_striped_with2(Map& m)
506 cds::OS::Timer timer;
510 // Iterators is not yet supported
512 //CPPUNIT_ASSERT( m.empty() );
513 //CPPUNIT_ASSERT( check_size( m, 0 ));
517 CPPUNIT_ASSERT( m.empty() );
518 CPPUNIT_ASSERT( check_size( m, 0 ));
521 for ( int i = 0; i < 40000; i++ ) {
525 CPPUNIT_MSG( " Duration=" << timer.duration() );
532 CPPUNIT_ASSERT( m.bucket_count() == 32 );
533 CPPUNIT_ASSERT( m.lock_count() == 32 );
535 test_striped_with2(m);
538 void Striped_hashmap();
541 void Striped_slist();
542 void Striped_boost_list();
543 void Striped_boost_flat_map();
544 void Striped_boost_map();
545 void Striped_boost_unordered_map();
547 void Refinable_hashmap();
548 void Refinable_list();
549 void Refinable_map();
550 void Refinable_slist();
551 void Refinable_boost_list();
552 void Refinable_boost_flat_map();
553 void Refinable_boost_map();
554 void Refinable_boost_unordered_map();
556 CPPUNIT_TEST_SUITE(StripedMapHdrTest)
557 CPPUNIT_TEST(Striped_hashmap)
558 CPPUNIT_TEST(Striped_list)
559 CPPUNIT_TEST(Striped_map)
560 CPPUNIT_TEST(Striped_slist)
561 CPPUNIT_TEST(Striped_boost_list)
562 CPPUNIT_TEST(Striped_boost_flat_map)
563 CPPUNIT_TEST(Striped_boost_map)
564 CPPUNIT_TEST(Striped_boost_unordered_map)
566 CPPUNIT_TEST(Refinable_hashmap)
567 CPPUNIT_TEST(Refinable_list)
568 CPPUNIT_TEST(Refinable_map)
569 CPPUNIT_TEST(Refinable_slist)
570 CPPUNIT_TEST(Refinable_boost_list)
571 CPPUNIT_TEST(Refinable_boost_flat_map)
572 CPPUNIT_TEST(Refinable_boost_map)
573 CPPUNIT_TEST(Refinable_boost_unordered_map)
574 CPPUNIT_TEST_SUITE_END()
579 #endif // #ifndef __CDSTEST_HDR_STRIPED_MAP_H