tests/test-hdr/map/hdr_cuckoo_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_CUCKOO_MAP_H
   4 #define CDSTEST_HDR_CUCKOO_MAP_H
   5 #include "size_check.h"
   6
   7 #include "cppunit/cppunit_proxy.h"
   8 #include <cds/os/timer.h>
   9 #include <cds/opt/hash.h>
  10 #include <functional>   // ref
  11
  12 namespace cds { namespace container {}}
  13
  14 namespace map {
  15     using misc::check_size;
  16
  17     namespace cc = cds::container;
  18     namespace co = cds::opt;
  19
  20     class CuckooMapHdrTest: public CppUnitMini::TestCase
  21     {
  22     public:
  23         typedef int key_type;
  24
  25         struct value_type {
  26             int m_val;
  27
  28             value_type()
  29                 : m_val(0)
  30             {}
  31
  32             value_type( int n )
  33                 : m_val( n )
  34             {}
  35
  36             value_type( value_type&& v )
  37                 : m_val( v.m_val )
  38             {}
  39
  40             value_type( value_type const& v )
  41                 : m_val( v.m_val )
  42             {}
  43
  44             value_type& operator=( value_type const& v )
  45             {
  46                 m_val = v.m_val;
  47                 return *this;
  48             }
  49         };
  50
  51         typedef std::pair<key_type const, value_type> pair_type;
  52
  53         struct less
  54         {
  55             bool operator ()(int v1, int v2 ) const
  56             {
  57                 return v1 < v2;
  58             }
  59         };
  60
  61         struct cmp {
  62             int operator ()(int v1, int v2 ) const
  63             {
  64                 if ( v1 < v2 )
  65                     return -1;
  66                 return v1 > v2 ? 1 : 0;
  67             }
  68         };
  69
  70         struct equal {
  71             bool operator ()(int v1, int v2 ) const
  72             {
  73                 return v1 == v2;
  74             }
  75         };
  76
  77         struct hash_int {
  78             size_t operator()( int i ) const
  79             {
  80                 return co::v::hash<int>()( i );
  81             }
  82         };
  83
  84         struct simple_item_counter {
  85             size_t  m_nCount;
  86
  87             simple_item_counter()
  88                 : m_nCount(0)
  89             {}
  90
  91             size_t operator ++()
  92             {
  93                 return ++m_nCount;
  94             }
  95
  96             size_t operator --()
  97             {
  98                 return --m_nCount;
  99             }
 100
 101             void reset()
 102             {
 103                 m_nCount = 0;
 104             }
 105
 106             operator size_t() const
 107             {
 108                 return m_nCount;
 109             }
 110         };
 111
 112         template <typename Map>
 113         struct insert_functor
 114         {
 115             typedef typename Map::value_type pair_type;
 116
 117             // insert ftor
 118             void operator()( pair_type& item )
 119             {
 120                 item.second.m_val = item.first * 3;
 121             }
 122
 123             // update() ftor
 124             void operator()( bool bNew, pair_type& item )
 125             {
 126                 if ( bNew )
 127                     item.second.m_val = item.first * 2;
 128                 else
 129                     item.second.m_val = item.first * 5;
 130             }
 131         };
 132
 133         struct check_value {
 134             int     m_nExpected;
 135
 136             check_value( int nExpected )
 137                 : m_nExpected( nExpected )
 138             {}
 139
 140             template <typename T>
 141             void operator ()( T& pair )
 142             {
 143                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 144             }
 145             template <typename T, typename Q>
 146             void operator ()( T& pair, Q )
 147             {
 148                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 149             }
 150         };
 151
 152         struct extract_functor
 153         {
 154             int *   m_pVal;
 155             void operator()( pair_type const& val )
 156             {
 157                 *m_pVal = val.second.m_val;
 158             }
 159         };
 160
 161         /*
 162         template <class Map>
 163         void test_iter( Map& s)
 164         {
 165             typedef typename Map::iterator          iterator;
 166             typedef typename Map::const_iterator    const_iterator;
 167
 168             const int nMaxCount = 500;
 169             for ( int i = 0; i < nMaxCount; ++i ) {
 170                 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
 171             }
 172
 173             int nCount = 0;
 174             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 175                 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
 176                 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
 177                 it->second.m_val = it->first;
 178                 ++nCount;
 179             }
 180             CPPUNIT_ASSERT( nCount == nMaxCount );
 181
 182             Map const& refSet = s;
 183             nCount = 0;
 184             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 185                 CPPUNIT_ASSERT( it->first == it->second.m_val );
 186                 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 187                 ++nCount;
 188             }
 189             CPPUNIT_ASSERT( nCount == nMaxCount );
 190         }
 191         */
 192
 193
 194         template <class Map>
 195         void test_cuckoo()
 196         {
 197             Map m( 32, 4, 3 );
 198             CPPUNIT_ASSERT( m.bucket_count() == 32 );
 199             CPPUNIT_ASSERT( m.lock_count() == 32 );
 200
 201             test_cuckoo_with( m );
 202
 203             // Iterators is not yet supported for CuckooMap
 204             //m.clear();
 205             //CPPUNIT_ASSERT( m.empty() );
 206             //CPPUNIT_ASSERT( check_size( m, 0 ));
 207             //test_iter(m);
 208         }
 209
 210         //*******************************************
 211         // If erase_with && find_with are supported
 212         template <class Map>
 213         void test_int_with( Map& m )
 214         {
 215             std::pair<bool, bool> updateResult;
 216             typedef typename std::conditional< Map::c_isSorted, less, equal >::type predicate;
 217
 218             // insert
 219             CPPUNIT_ASSERT( m.empty() );
 220             CPPUNIT_ASSERT( check_size( m, 0 ));
 221             CPPUNIT_ASSERT( !m.contains(25) );
 222             CPPUNIT_ASSERT( m.insert( 25 ) )    ;   // value = 0
 223             CPPUNIT_ASSERT( m.contains(25) );
 224             CPPUNIT_ASSERT( !m.empty() );
 225             CPPUNIT_ASSERT( check_size( m, 1 ));
 226             CPPUNIT_ASSERT( m.contains(25) );
 227
 228             CPPUNIT_ASSERT( !m.insert( 25 ) );
 229             CPPUNIT_ASSERT( !m.empty() );
 230             CPPUNIT_ASSERT( check_size( m, 1 ));
 231
 232             CPPUNIT_ASSERT( !m.contains(10, predicate()) );
 233             CPPUNIT_ASSERT( m.insert( 10, 10 ) );
 234             CPPUNIT_ASSERT( !m.empty() );
 235             CPPUNIT_ASSERT( check_size( m, 2 ));
 236             CPPUNIT_ASSERT( m.contains(10, predicate()) );
 237
 238             CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
 239             CPPUNIT_ASSERT( !m.empty() );
 240             CPPUNIT_ASSERT( check_size( m, 2 ));
 241
 242             CPPUNIT_ASSERT( !m.contains(30) );
 243             CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) )    ; // value = 90
 244             CPPUNIT_ASSERT( !m.empty() );
 245             CPPUNIT_ASSERT( check_size( m, 3 ));
 246             CPPUNIT_ASSERT( m.contains(30) );
 247
 248             CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
 249             CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
 250             CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
 251
 252             // update (new key)
 253             CPPUNIT_ASSERT( !m.contains(27) );
 254             updateResult = m.update(27, insert_functor<Map>(), false);
 255             CPPUNIT_ASSERT(!updateResult.first);
 256             CPPUNIT_ASSERT(!updateResult.second);
 257             CPPUNIT_ASSERT(!m.contains(27));
 258             updateResult = m.update( 27, insert_functor<Map>() ) ;   // value = 54
 259             CPPUNIT_ASSERT( updateResult.first );
 260             CPPUNIT_ASSERT( updateResult.second );
 261             CPPUNIT_ASSERT( m.contains(27) );
 262
 263             // find test
 264             check_value chk(10);
 265             CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
 266             chk.m_nExpected = 0;
 267             CPPUNIT_ASSERT( m.find_with( 25, predicate(), std::ref(chk) ));
 268             chk.m_nExpected = 90;
 269             CPPUNIT_ASSERT( m.find( 30, std::ref(chk) ));
 270             chk.m_nExpected = 54;
 271             CPPUNIT_ASSERT( m.find( 27, std::ref(chk) ));
 272
 273             updateResult = m.update( 10, insert_functor<Map>() ) ;   // value = 50
 274             CPPUNIT_ASSERT( updateResult.first );
 275             CPPUNIT_ASSERT( !updateResult.second );
 276             chk.m_nExpected = 50;
 277             CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
 278
 279             // erase test
 280             CPPUNIT_ASSERT( !m.contains(100) );
 281             CPPUNIT_ASSERT( !m.erase( 100 )) ;  // not found
 282
 283             CPPUNIT_ASSERT( m.contains(25) );
 284             CPPUNIT_ASSERT( check_size( m, 4 ));
 285             CPPUNIT_ASSERT( m.erase( 25 ));
 286             CPPUNIT_ASSERT( !m.empty() );
 287             CPPUNIT_ASSERT( check_size( m, 3 ));
 288             CPPUNIT_ASSERT( !m.contains(25) );
 289             CPPUNIT_ASSERT( !m.erase( 25 ));
 290
 291             CPPUNIT_ASSERT( !m.contains(258) );
 292             CPPUNIT_ASSERT( m.insert(258))
 293             CPPUNIT_ASSERT( check_size( m, 4 ));
 294             CPPUNIT_ASSERT( m.contains(258, predicate()) );
 295             CPPUNIT_ASSERT( m.erase_with( 258, predicate() ));
 296             CPPUNIT_ASSERT( !m.empty() );
 297             CPPUNIT_ASSERT( check_size( m, 3 ));
 298             CPPUNIT_ASSERT( !m.contains(258) );
 299             CPPUNIT_ASSERT( !m.erase_with( 258, predicate() ));
 300
 301             int nVal;
 302             extract_functor ext;
 303             ext.m_pVal = &nVal;
 304
 305             CPPUNIT_ASSERT( !m.contains(29) );
 306             CPPUNIT_ASSERT( m.insert(29, 290))
 307             CPPUNIT_ASSERT( m.erase_with( 29, predicate(), std::ref(ext)));
 308             CPPUNIT_ASSERT( !m.empty() );
 309             CPPUNIT_ASSERT( check_size( m, 3 ));
 310             CPPUNIT_ASSERT( nVal == 290 );
 311             nVal = -1;
 312             CPPUNIT_ASSERT( !m.erase_with( 29, predicate(), std::ref( ext ) ) );
 313             CPPUNIT_ASSERT( nVal == -1 );
 314
 315             CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
 316             CPPUNIT_ASSERT( !m.empty() );
 317             CPPUNIT_ASSERT( check_size( m, 2 ));
 318             CPPUNIT_ASSERT( nVal == 90 );
 319             nVal = -1;
 320             CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
 321             CPPUNIT_ASSERT( nVal == -1 );
 322
 323             m.clear();
 324             CPPUNIT_ASSERT( m.empty() );
 325             CPPUNIT_ASSERT( check_size( m, 0 ));
 326
 327             // emplace test
 328             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 329             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 330             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 331
 332             CPPUNIT_ASSERT( !m.empty() );
 333             CPPUNIT_ASSERT( check_size( m, 3 ));
 334
 335             chk.m_nExpected = 0;
 336             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 337             chk.m_nExpected = 731;
 338             CPPUNIT_ASSERT( m.find_with( 137, predicate(), std::ref(chk) ));
 339             chk.m_nExpected = 941;
 340             CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
 341
 342             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 343             chk.m_nExpected = 0;
 344             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 345             CPPUNIT_ASSERT( !m.empty() );
 346             CPPUNIT_ASSERT( check_size( m, 3 ));
 347
 348             m.clear();
 349             CPPUNIT_ASSERT( m.empty() );
 350             CPPUNIT_ASSERT( check_size( m, 0 ));
 351         }
 352
 353         template <class Map>
 354         void test_cuckoo_with(Map& m)
 355         {
 356             cds::OS::Timer    timer;
 357
 358             test_int_with( m );
 359
 360             // Iterators is not yet supported
 361             //m.clear();
 362             //CPPUNIT_ASSERT( m.empty() );
 363             //CPPUNIT_ASSERT( check_size( m, 0 ));
 364             //test_iter(m);
 365
 366             m.clear();
 367             CPPUNIT_ASSERT( m.empty() );
 368             CPPUNIT_ASSERT( check_size( m, 0 ));
 369
 370             // Resizing test
 371             for ( int i = 0; i < 40000; i++ ) {
 372                 m.insert( i );
 373             }
 374
 375             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 376         }
 377
 378         void Cuckoo_striped_list();
 379         void Cuckoo_striped_vector();
 380         void Cuckoo_refinable_list();
 381         void Cuckoo_refinable_vector();
 382
 383         CPPUNIT_TEST_SUITE(CuckooMapHdrTest)
 384             CPPUNIT_TEST(Cuckoo_striped_list)
 385             CPPUNIT_TEST(Cuckoo_striped_vector)
 386             CPPUNIT_TEST(Cuckoo_refinable_list)
 387             CPPUNIT_TEST(Cuckoo_refinable_vector)
 388         CPPUNIT_TEST_SUITE_END()
 389
 390     };
 391 }   // namespace map
 392
 393 #endif // #ifndef CDSTEST_HDR_CUCKOO_MAP_H