3 #ifndef CDSTEST_HDR_MICHAEL_KV_H
4 #define CDSTEST_HDR_MICHAEL_KV_H
6 #include "cppunit/cppunit_proxy.h"
7 #include <cds/container/details/michael_list_base.h>
10 namespace cc = cds::container;
11 namespace co = cds::container::opt;
13 class MichaelKVListTestHeader: public CppUnitMini::TestCase
32 bool operator ()(const T& v1, const T& v2 ) const
40 int operator ()(const T& v1, const T& v2 ) const
44 return v1 > v2 ? 1 : 0;
51 check_value( int nExpected )
52 : m_nExpected( nExpected )
56 void operator ()( T& pair )
58 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
62 struct insert_functor {
64 void operator()( T& pair )
66 pair.second.m_val = pair.first * 10;
70 struct ensure_functor {
72 void operator()( bool /*bNew*/, T& pair )
74 pair.second.m_val = pair.first * 50;
78 struct erase_functor {
88 void operator()( T& i )
91 nVal = i.second.m_val;
95 typedef float other_key;
97 bool operator()( float f, int i ) const
101 bool operator()( int i, float f ) const
108 template <class OrdList>
109 void test_with( OrdList& l)
111 typedef typename OrdList::value_type value_type;
113 typename OrdList::iterator itTest;
114 typename OrdList::const_iterator citTest;
116 CPPUNIT_ASSERT( l.empty() );
118 // insert / find test
119 CPPUNIT_ASSERT( !l.find( 100 ));
120 CPPUNIT_ASSERT( l.insert( 100 ));
121 CPPUNIT_ASSERT( !l.empty() );
122 CPPUNIT_ASSERT( l.find( 100 ));
125 CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
127 CPPUNIT_ASSERT( !l.find_with( 50, lt<key_type>() ));
128 CPPUNIT_ASSERT( l.insert( 50, 500 ));
129 CPPUNIT_ASSERT( l.find_with( 50, lt<key_type>() ));
130 CPPUNIT_ASSERT( !l.insert( 50, 5 ));
131 chk.m_nExpected = 500;
132 CPPUNIT_ASSERT( l.find_with( 50, lt<key_type>(), std::ref( chk ) ) );
134 CPPUNIT_ASSERT( l.find_with( 100, lt<key_type>(), std::ref( chk ) ) );
135 CPPUNIT_ASSERT( !l.empty() );
137 CPPUNIT_ASSERT( !l.find( 150 ));
138 CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ));
139 CPPUNIT_ASSERT( l.find( 150 ));
140 chk.m_nExpected = 1500;
141 CPPUNIT_ASSERT( l.find( 150, std::ref( chk ) ) );
143 CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
144 chk.m_nExpected = 500;
145 CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
146 CPPUNIT_ASSERT( !l.empty() );
150 CPPUNIT_ASSERT( !l.erase( 500 ));
151 CPPUNIT_ASSERT( !l.empty() );
153 CPPUNIT_ASSERT( l.find( 50 ));
156 l.erase( 50, std::ref( ef ) );
157 CPPUNIT_ASSERT( ef.nKey == 50 );
158 CPPUNIT_ASSERT( ef.nVal == 500 );
160 CPPUNIT_ASSERT( !l.find( 50 ));
163 std::pair<bool, bool> bEnsureResult;
164 bEnsureResult = l.ensure( 100, ensure_functor() );
165 CPPUNIT_ASSERT( bEnsureResult.first );
166 CPPUNIT_ASSERT( !bEnsureResult.second );
167 chk.m_nExpected = 5000;
168 CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
172 bEnsureResult = l.ensure( 50, std::ref( ef ) );
174 CPPUNIT_ASSERT( bEnsureResult.first );
175 CPPUNIT_ASSERT( bEnsureResult.second );
176 chk.m_nExpected = 2500;
177 CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
180 CPPUNIT_ASSERT( !l.empty() );
181 CPPUNIT_ASSERT( l.insert_with( 200, insert_functor() ));
182 CPPUNIT_ASSERT( l.insert( 25 ));
183 CPPUNIT_ASSERT( l.erase( 100 ));
184 CPPUNIT_ASSERT( l.erase( 150 ));
187 CPPUNIT_ASSERT( l.erase_with( 200, lt<key_type>(), std::ref(ef)) );
188 CPPUNIT_ASSERT( ef.nKey == 200 );
189 CPPUNIT_ASSERT( ef.nVal == 2000 );
191 CPPUNIT_ASSERT( l.erase_with( 25, lt<key_type>()))
192 CPPUNIT_ASSERT( l.erase( 50 ));
193 CPPUNIT_ASSERT( l.empty() );
197 CPPUNIT_ASSERT( l.empty() );
200 CPPUNIT_ASSERT( l.emplace( 501 ) );
201 CPPUNIT_ASSERT( l.emplace( 251, 152 ));
203 // insert failed - such key exists
204 CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
205 CPPUNIT_ASSERT( !l.emplace( 251, 10) );
208 CPPUNIT_ASSERT( l.find( 501, std::ref(cv) ));
209 cv.m_nExpected = 152;
210 CPPUNIT_ASSERT( l.find( 251, std::ref(cv) ));
213 CPPUNIT_ASSERT( l.empty() );
218 for ( int i = 0; i < nCount; ++i )
219 CPPUNIT_ASSERT( l.insert(i, i * 2 ) );
222 typename OrdList::iterator it( l.begin() );
223 typename OrdList::const_iterator cit( l.cbegin() );
224 CPPUNIT_CHECK( it == cit );
225 CPPUNIT_CHECK( it != l.end() );
226 CPPUNIT_CHECK( it != l.cend() );
227 CPPUNIT_CHECK( cit != l.end() );
228 CPPUNIT_CHECK( cit != l.cend() );
230 CPPUNIT_CHECK( it != cit );
231 CPPUNIT_CHECK( it != l.end() );
232 CPPUNIT_CHECK( it != l.cend() );
233 CPPUNIT_CHECK( cit != l.end() );
234 CPPUNIT_CHECK( cit != l.cend() );
236 CPPUNIT_CHECK( it == cit );
237 CPPUNIT_CHECK( it != l.end() );
238 CPPUNIT_CHECK( it != l.cend() );
239 CPPUNIT_CHECK( cit != l.end() );
240 CPPUNIT_CHECK( cit != l.cend() );
244 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
245 CPPUNIT_ASSERT( it.key() == i );
246 CPPUNIT_ASSERT( it->first == i );
247 CPPUNIT_ASSERT( (*it).first == i );
249 CPPUNIT_ASSERT( it.val().m_val == i * 2 );
250 CPPUNIT_ASSERT( it->second.m_val == i * 2 );
251 CPPUNIT_ASSERT( (*it).second.m_val == i * 2 );
252 it.val().m_val = i * 3;
255 // Check that we have visited all items
256 for ( int i = 0; i < nCount; ++i ) {
257 chk.m_nExpected = i * 3;
258 CPPUNIT_ASSERT( l.find( i, std::ref( chk ) ) );
262 CPPUNIT_ASSERT( l.empty() );
265 for ( int i = 0; i < nCount; ++i )
266 CPPUNIT_ASSERT( l.insert(i, i * 7) );
269 const OrdList& rl = l;
270 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
271 CPPUNIT_ASSERT( it.key() == i );
272 CPPUNIT_ASSERT( it->first == i );
273 CPPUNIT_ASSERT( (*it).first == i );
275 CPPUNIT_ASSERT( it.val().m_val == i * 7 );
276 CPPUNIT_ASSERT( it->second.m_val == i * 7 );
277 CPPUNIT_ASSERT( (*it).second.m_val == i * 7 );
280 // Check that we have visited all items
281 for ( int i = 0; i < nCount; ++i ) {
282 chk.m_nExpected = i * 7;
283 CPPUNIT_ASSERT( l.find_with( i, lt<key_type>(), std::ref( chk ) ) );
287 CPPUNIT_ASSERT( l.empty() );
291 template <class OrdList>
297 typedef typename OrdList::guarded_ptr guarded_ptr;
299 static int const nLimit = 20;
301 for ( int i = 0; i < nLimit; i++ )
303 shuffle( arr, arr + nLimit );
306 for ( int i = 0; i < nLimit; ++i )
307 l.insert( arr[i], arr[i] * 2 );
310 for ( int i = 0; i < nLimit; ++i ) {
314 CPPUNIT_ASSERT( gp );
315 CPPUNIT_ASSERT( !gp.empty());
316 CPPUNIT_CHECK( gp->first == nKey );
317 CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
319 CPPUNIT_CHECK( gp.empty() );
321 gp = l.extract( nKey );
322 CPPUNIT_ASSERT( gp );
323 CPPUNIT_ASSERT( !gp.empty());
324 CPPUNIT_CHECK( gp->first == nKey );
325 CPPUNIT_CHECK( gp->second.m_val == nKey*2 );
329 CPPUNIT_CHECK( !gp );
330 CPPUNIT_CHECK( gp.empty());
331 CPPUNIT_CHECK( !l.extract( nKey));
332 CPPUNIT_CHECK( gp.empty());
334 CPPUNIT_ASSERT( l.empty());
335 CPPUNIT_CHECK( !l.get(arr[0]));
336 CPPUNIT_CHECK( gp.empty());
337 CPPUNIT_CHECK( !l.extract( arr[0]));
338 CPPUNIT_CHECK( gp.empty());
341 // extract_with/get_with
342 for ( int i = 0; i < nLimit; ++i )
343 l.insert( arr[i], arr[i] * 2 );
346 for ( int i = 0; i < nLimit; ++i ) {
348 other_key key = float(nKey + 0.3);
350 gp = l.get_with( key, other_less() );
351 CPPUNIT_ASSERT( gp );
352 CPPUNIT_ASSERT( !gp.empty());
353 CPPUNIT_CHECK( gp->first == nKey );
354 CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
357 gp = l.extract_with( key, other_less() );
358 CPPUNIT_ASSERT( gp );
359 CPPUNIT_ASSERT( !gp.empty());
360 CPPUNIT_CHECK( gp->first == nKey );
361 CPPUNIT_CHECK( gp->second.m_val == nKey*2 );
364 gp = l.get_with( key, other_less() );
365 CPPUNIT_CHECK( !gp );
366 CPPUNIT_CHECK( gp.empty());
367 CPPUNIT_CHECK( !l.extract_with( key, other_less()));
368 CPPUNIT_CHECK( gp.empty());
370 CPPUNIT_ASSERT( l.empty());
371 CPPUNIT_CHECK( !l.get_with( 3.4f, other_less()));
372 CPPUNIT_CHECK( gp.empty());
373 CPPUNIT_CHECK( !l.extract_with( 3.4f, other_less()));
374 CPPUNIT_CHECK( gp.empty());
378 template <class OrdList>
384 static int const nLimit = 20;
386 typedef typename OrdList::rcu_lock rcu_lock;
387 typedef typename OrdList::value_type value_type;
388 typedef typename OrdList::gc rcu_type;
392 for (int i = 0; i < nLimit; ++i)
394 shuffle( a, a + nLimit );
397 for ( int i = 0; i < nLimit; ++i )
398 CPPUNIT_ASSERT( l.insert( a[i], a[i]*2 ) );
400 typename OrdList::exempt_ptr ep;
402 for ( int i = 0; i < nLimit; ++i ) {
405 value_type * pGet = l.get( a[i] );
406 CPPUNIT_ASSERT( pGet != nullptr );
407 CPPUNIT_CHECK( pGet->first == a[i] );
408 CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 );
410 ep = l.extract( a[i] );
411 CPPUNIT_ASSERT( ep );
412 CPPUNIT_ASSERT( !ep.empty() );
413 CPPUNIT_CHECK( ep->first == a[i] );
414 CPPUNIT_CHECK( (*ep).second.m_val == a[i] * 2 );
419 CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
420 ep = l.extract( a[i] );
421 CPPUNIT_CHECK( !ep );
422 CPPUNIT_CHECK( ep.empty() );
425 CPPUNIT_ASSERT( l.empty() );
429 CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
430 CPPUNIT_CHECK( !l.extract( a[0] ) );
431 CPPUNIT_CHECK( ep.empty() );
434 // extract_with/get_with
435 for ( int i = 0; i < nLimit; ++i ) {
436 CPPUNIT_ASSERT( l.insert( a[i], a[i]*2 ) );
439 for ( int i = 0; i < nLimit; ++i ) {
440 float itm = a[i] + 0.3f;
443 value_type * pGet = l.get_with( itm, other_less() );
444 CPPUNIT_ASSERT( pGet != nullptr );
445 CPPUNIT_CHECK( pGet->first == a[i] );
446 CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 );
448 ep = l.extract_with( itm, other_less() );
449 CPPUNIT_ASSERT( ep );
450 CPPUNIT_ASSERT( !ep.empty() );
451 CPPUNIT_CHECK( ep->first == a[i] );
452 CPPUNIT_CHECK( ep->second.m_val == a[i] * 2 );
457 CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
458 ep = l.extract_with( itm, other_less() );
459 CPPUNIT_CHECK( !ep );
460 CPPUNIT_CHECK( ep.empty() );
463 CPPUNIT_ASSERT( l.empty() );
467 CPPUNIT_CHECK( l.get_with( 3.14f, other_less() ) == nullptr );
468 CPPUNIT_CHECK( !l.extract_with( 3.14f, other_less() ));
469 CPPUNIT_CHECK( ep.empty() );
475 template <class OrdList>
478 typedef typename OrdList::value_type value_type;
479 typedef typename OrdList::iterator iterator;
485 CPPUNIT_ASSERT( l.empty() );
487 // insert / find test
488 CPPUNIT_ASSERT( l.find( 100 ) == l.end() );
489 CPPUNIT_ASSERT( l.insert( 100 ) != l.end() );
490 CPPUNIT_ASSERT( !l.empty() );
491 it = l.find_with( 100, lt<key_type>() );
492 CPPUNIT_ASSERT( it != l.end() );
493 CPPUNIT_ASSERT( it.key() == 100 );
494 CPPUNIT_ASSERT( it.val().m_val == 0 );
496 CPPUNIT_ASSERT( l.find_with( 50, lt<key_type>() ) == l.end() );
497 CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end());
499 CPPUNIT_ASSERT( it != l.end() );
500 CPPUNIT_ASSERT( it.key() == 50 );
501 CPPUNIT_ASSERT( it.val().m_val == 500 );
503 CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() );
505 CPPUNIT_ASSERT( it != l.end() );
506 CPPUNIT_ASSERT( it.key() == 50 );
507 CPPUNIT_ASSERT( it.val().m_val == 500 );
508 CPPUNIT_ASSERT( !l.empty() );
510 CPPUNIT_ASSERT( l.find( 150 ) == l.end() );
511 CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() );
513 CPPUNIT_ASSERT( it != l.end() );
514 CPPUNIT_ASSERT( it.key() == 150 );
515 CPPUNIT_ASSERT( it.val().m_val == 1500 );
517 CPPUNIT_ASSERT( it != l.end() );
518 CPPUNIT_ASSERT( it.key() == 100 );
519 CPPUNIT_ASSERT( it.val().m_val == 0 );
521 CPPUNIT_ASSERT( it != l.end() );
522 CPPUNIT_ASSERT( it.key() == 50 );
523 CPPUNIT_ASSERT( it.val().m_val == 500 );
526 CPPUNIT_ASSERT( it != l.end() );
527 CPPUNIT_ASSERT( it.key() == 50 );
528 CPPUNIT_ASSERT( it.val().m_val == 25 );
529 CPPUNIT_ASSERT( !l.empty() );
531 // ensure existing item
532 std::pair<iterator, bool> ensureResult;
533 ensureResult = l.ensure( 100 );
534 CPPUNIT_ASSERT( !ensureResult.second );
535 CPPUNIT_ASSERT( ensureResult.first.key() == 100 );
536 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 );
537 ensureResult.first.val().m_val = 5;
539 CPPUNIT_ASSERT( it != l.end() );
540 CPPUNIT_ASSERT( it.key() == 100 );
541 CPPUNIT_ASSERT( it.val().m_val == 5 );
543 CPPUNIT_ASSERT( !l.empty() );
546 ensureResult = l.ensure( 1000 );
547 CPPUNIT_ASSERT( ensureResult.second );
548 CPPUNIT_ASSERT( ensureResult.first.key() == 1000 );
549 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 );
550 ensureResult.first.val().m_val = 33;
551 ensureResult = l.ensure( 1000 );
552 CPPUNIT_ASSERT( !ensureResult.second );
553 CPPUNIT_ASSERT( ensureResult.first.key() == 1000 );
554 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 33 );
558 CPPUNIT_ASSERT( l.empty() );
561 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
562 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
564 // insert failed - such key exists
565 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
566 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
569 CPPUNIT_ASSERT( it != l.end());
570 CPPUNIT_ASSERT( it.key() == 501 );
571 CPPUNIT_ASSERT( it.val().m_val == 0 );
574 CPPUNIT_ASSERT( it != l.end());
575 CPPUNIT_ASSERT( it.key() == 251 );
576 CPPUNIT_ASSERT( it.val().m_val == 152 );
579 CPPUNIT_ASSERT( l.empty() );
584 for ( int i = 0; i < nCount; ++i )
585 CPPUNIT_ASSERT( l.insert(i, i * 2 ) != l.end() );
588 typename OrdList::iterator it( l.begin() );
589 typename OrdList::const_iterator cit( l.cbegin() );
590 CPPUNIT_CHECK( it == cit );
591 CPPUNIT_CHECK( it != l.end() );
592 CPPUNIT_CHECK( it != l.cend() );
593 CPPUNIT_CHECK( cit != l.end() );
594 CPPUNIT_CHECK( cit != l.cend() );
596 CPPUNIT_CHECK( it != cit );
597 CPPUNIT_CHECK( it != l.end() );
598 CPPUNIT_CHECK( it != l.cend() );
599 CPPUNIT_CHECK( cit != l.end() );
600 CPPUNIT_CHECK( cit != l.cend() );
602 CPPUNIT_CHECK( it == cit );
603 CPPUNIT_CHECK( it != l.end() );
604 CPPUNIT_CHECK( it != l.cend() );
605 CPPUNIT_CHECK( cit != l.end() );
606 CPPUNIT_CHECK( cit != l.cend() );
610 for ( typename OrdList::iterator iter = l.begin(), itEnd = l.end(); iter != itEnd; ++iter, ++i ) {
611 CPPUNIT_ASSERT( iter.key() == i );
612 CPPUNIT_ASSERT( iter->first == i );
613 CPPUNIT_ASSERT( (*iter).first == i );
615 CPPUNIT_ASSERT( iter.val().m_val == i * 2 );
616 CPPUNIT_ASSERT( iter->second.m_val == i * 2 );
617 CPPUNIT_ASSERT( (*iter).second.m_val == i * 2 );
619 iter.val().m_val = i * 3;
622 // Check that we have visited all items
623 for ( int i = 0; i < nCount; ++i ) {
625 CPPUNIT_ASSERT( it != l.end() );
626 CPPUNIT_ASSERT( it.key() == i );
627 CPPUNIT_ASSERT( it.val().m_val == i * 3 );
631 CPPUNIT_ASSERT( l.empty() );
634 for ( int i = 0; i < nCount; ++i )
635 CPPUNIT_ASSERT( l.insert(i, i * 7) != l.end() );
638 const OrdList& rl = l;
639 for ( typename OrdList::const_iterator iter = rl.begin(), itEnd = rl.end(); iter != itEnd; ++iter, ++i ) {
640 CPPUNIT_ASSERT( iter.key() == i );
641 CPPUNIT_ASSERT( iter->first == i );
642 CPPUNIT_ASSERT( (*iter).first == i );
644 CPPUNIT_ASSERT( iter.val().m_val == i * 7 );
645 CPPUNIT_ASSERT( iter->second.m_val == i * 7 );
646 CPPUNIT_ASSERT( (*iter).second.m_val == i * 7 );
648 // it.val().m_val = i * 3 ; // error: const-iterator
652 CPPUNIT_ASSERT( l.empty() );
670 void RCU_GPI_cmpmix();
675 void RCU_GPB_cmpmix();
680 void RCU_GPT_cmpmix();
685 void RCU_SHB_cmpmix();
690 void RCU_SHT_cmpmix();
698 CPPUNIT_TEST_SUITE(MichaelKVListTestHeader)
700 CPPUNIT_TEST(HP_less)
701 CPPUNIT_TEST(HP_cmpmix)
704 CPPUNIT_TEST(DHP_cmp)
705 CPPUNIT_TEST(DHP_less)
706 CPPUNIT_TEST(DHP_cmpmix)
709 CPPUNIT_TEST(RCU_GPI_cmp)
710 CPPUNIT_TEST(RCU_GPI_less)
711 CPPUNIT_TEST(RCU_GPI_cmpmix)
712 CPPUNIT_TEST(RCU_GPI_ic)
714 CPPUNIT_TEST(RCU_GPB_cmp)
715 CPPUNIT_TEST(RCU_GPB_less)
716 CPPUNIT_TEST(RCU_GPB_cmpmix)
717 CPPUNIT_TEST(RCU_GPB_ic)
719 CPPUNIT_TEST(RCU_GPT_cmp)
720 CPPUNIT_TEST(RCU_GPT_less)
721 CPPUNIT_TEST(RCU_GPT_cmpmix)
722 CPPUNIT_TEST(RCU_GPT_ic)
724 CPPUNIT_TEST(RCU_SHB_cmp)
725 CPPUNIT_TEST(RCU_SHB_less)
726 CPPUNIT_TEST(RCU_SHB_cmpmix)
727 CPPUNIT_TEST(RCU_SHB_ic)
729 CPPUNIT_TEST(RCU_SHT_cmp)
730 CPPUNIT_TEST(RCU_SHT_less)
731 CPPUNIT_TEST(RCU_SHT_cmpmix)
732 CPPUNIT_TEST(RCU_SHT_ic)
734 CPPUNIT_TEST(NOGC_cmp)
735 CPPUNIT_TEST(NOGC_less)
736 CPPUNIT_TEST(NOGC_cmpmix)
737 CPPUNIT_TEST(NOGC_ic)
738 CPPUNIT_TEST_SUITE_END()
741 } // namespace ordlist
743 #endif // #ifndef CDSTEST_HDR_MICHAEL_KV_H