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