test/unit/striped-map/cuckoo_map.cpp

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #include "test_map.h"
  32
  33 #include <cds/container/cuckoo_map.h>
  34
  35 namespace {
  36     namespace cc = cds::container;
  37
  38     class CuckooMap : public cds_test::container_map
  39     {
  40     protected:
  41         typedef cds_test::container_map base_class;
  42
  43         template <typename Set>
  44         void test( Set& m )
  45         {
  46             // Precondition: set is empty
  47             // Postcondition: set is empty
  48
  49             base_class::test_< Set::c_isSorted>( m );
  50         }
  51
  52         //void SetUp()
  53         //{}
  54
  55         //void TearDown()
  56         //{}
  57     };
  58
  59     struct store_hash_traits: public cc::cuckoo::traits
  60     {
  61         static bool const store_hash = true;
  62     };
  63
  64
  65 //************************************************************
  66 // striped set
  67
  68     TEST_F( CuckooMap, striped_list_unordered )
  69     {
  70         struct map_traits: public cc::cuckoo::traits
  71         {
  72             typedef cds::opt::hash_tuple< hash1, hash2 > hash;
  73             typedef base_class::equal_to equal_to;
  74             typedef cc::cuckoo::list probeset_type;
  75         };
  76         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
  77
  78         map_type m;
  79         test( m );
  80     }
  81
  82     TEST_F( CuckooMap, striped_vector_unordered )
  83     {
  84         struct map_traits: public cc::cuckoo::traits
  85         {
  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;
  89         };
  90         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
  91
  92         map_type m( 32, 4 );
  93         test( m );
  94     }
  95
  96     TEST_F( CuckooMap, striped_list_ordered_cmp )
  97     {
  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 >
 103             >::type
 104         > map_type;
 105
 106         map_type m( 32, 6, 4 );
 107         test( m );
 108     }
 109
 110     TEST_F( CuckooMap, striped_vector_ordered_cmp )
 111     {
 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>>
 117             >::type
 118         > map_type;
 119
 120         typename map_type::hash_tuple_type ht;
 121         map_type m( ht );
 122         test( m );
 123     }
 124
 125     TEST_F( CuckooMap, striped_list_ordered_less )
 126     {
 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 >
 132             >::type
 133         > map_type;
 134
 135         typename map_type::hash_tuple_type ht;
 136         map_type m( 32, 6, 4, ht );
 137         test( m );
 138     }
 139
 140     TEST_F( CuckooMap, striped_vector_ordered_less )
 141     {
 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>>
 147             >::type
 148         > map_type;
 149
 150         typename map_type::hash_tuple_type ht;
 151         map_type m( std::move( ht ));
 152         test( m );
 153     }
 154
 155     TEST_F( CuckooMap, striped_list_ordered_cmpmix )
 156     {
 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 >
 163             >::type
 164         > map_type;
 165
 166         typename map_type::hash_tuple_type ht;
 167         map_type m( 32, 6, 0, std::move( ht ));
 168         test( m );
 169     }
 170
 171     TEST_F( CuckooMap, striped_vector_ordered_cmpmix )
 172     {
 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>>
 179             >::type
 180         > map_type;
 181
 182         typename map_type::hash_tuple_type ht;
 183         map_type m( std::move( ht ));
 184         test( m );
 185     }
 186
 187     TEST_F( CuckooMap, striped_list_ordered_stat )
 188     {
 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 >
 196             >::type
 197         > map_type;
 198
 199         map_type m;
 200         test( m );
 201     }
 202
 203     TEST_F( CuckooMap, striped_vector_ordered_stat )
 204     {
 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>>
 212             >::type
 213         > map_type;
 214
 215         map_type m;
 216         test( m );
 217     }
 218
 219     TEST_F( CuckooMap, striped_list_unordered_storehash )
 220     {
 221         struct map_traits: public store_hash_traits
 222         {
 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;
 227         };
 228         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
 229
 230         map_type m;
 231         test( m );
 232     }
 233
 234     TEST_F( CuckooMap, striped_vector_unordered_storehash )
 235     {
 236         struct map_traits: public store_hash_traits
 237         {
 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;
 242         };
 243         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
 244
 245         map_type m( 32, 4 );
 246         test( m );
 247     }
 248
 249     TEST_F( CuckooMap, striped_list_ordered_storehash )
 250     {
 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 >
 258             >::type
 259         > map_type;
 260
 261         typename map_type::hash_tuple_type ht;
 262         map_type m( 32, 6, 0, std::move( ht ));
 263         test( m );
 264     }
 265
 266     TEST_F( CuckooMap, striped_vector_ordered_storehash )
 267     {
 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 >
 275             >::type
 276         > map_type;
 277
 278         typename map_type::hash_tuple_type ht;
 279         map_type m( std::move( ht ));
 280         test( m );
 281     }
 282
 283
 284 //************************************************************
 285 // refinable set
 286
 287     TEST_F( CuckooMap, refinable_list_unordered )
 288     {
 289         struct map_traits: public cc::cuckoo::traits
 290         {
 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;
 295         };
 296         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
 297
 298         map_type m;
 299         test( m );
 300     }
 301
 302     TEST_F( CuckooMap, refinable_vector_unordered )
 303     {
 304         struct map_traits: public cc::cuckoo::traits
 305         {
 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;
 310         };
 311         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
 312
 313         map_type m( 32, 4 );
 314         test( m );
 315     }
 316
 317     TEST_F( CuckooMap, refinable_list_ordered_cmp )
 318     {
 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 >
 325             >::type
 326         > map_type;
 327
 328         map_type m( 32, 6, 4 );
 329         test( m );
 330     }
 331
 332     TEST_F( CuckooMap, refinable_vector_ordered_cmp )
 333     {
 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>>
 340             >::type
 341         > map_type;
 342
 343         typename map_type::hash_tuple_type ht;
 344         map_type m( ht );
 345         test( m );
 346     }
 347
 348     TEST_F( CuckooMap, refinable_list_ordered_less )
 349     {
 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 >
 356             >::type
 357         > map_type;
 358
 359         typename map_type::hash_tuple_type ht;
 360         map_type m( 32, 6, 4, ht );
 361         test( m );
 362     }
 363
 364     TEST_F( CuckooMap, refinable_vector_ordered_less )
 365     {
 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>>
 372             >::type
 373         > map_type;
 374
 375         typename map_type::hash_tuple_type ht;
 376         map_type m( std::move( ht ));
 377         test( m );
 378     }
 379
 380     TEST_F( CuckooMap, refinable_list_ordered_cmpmix )
 381     {
 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 >
 389             >::type
 390         > map_type;
 391
 392         typename map_type::hash_tuple_type ht;
 393         map_type m( 32, 6, 0, std::move( ht ));
 394         test( m );
 395     }
 396
 397     TEST_F( CuckooMap, refinable_vector_ordered_cmpmix )
 398     {
 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>>
 406             >::type
 407         > map_type;
 408
 409         typename map_type::hash_tuple_type ht;
 410         map_type m( std::move( ht ));
 411         test( m );
 412     }
 413
 414     TEST_F( CuckooMap, refinable_list_ordered_stat )
 415     {
 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 >
 424             >::type
 425         > map_type;
 426
 427         map_type m;
 428         test( m );
 429     }
 430
 431     TEST_F( CuckooMap, refinable_vector_ordered_stat )
 432     {
 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>>
 441             >::type
 442         > map_type;
 443
 444         map_type m;
 445         test( m );
 446     }
 447
 448     TEST_F( CuckooMap, refinable_list_unordered_storehash )
 449     {
 450         struct map_traits: public store_hash_traits
 451         {
 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;
 457         };
 458         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
 459
 460         map_type m;
 461         test( m );
 462     }
 463
 464     TEST_F( CuckooMap, refinable_vector_unordered_storehash )
 465     {
 466         struct map_traits: public store_hash_traits
 467         {
 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;
 473         };
 474         typedef cc::CuckooMap< key_type, value_type, map_traits > map_type;
 475
 476         map_type m( 32, 4 );
 477         test( m );
 478     }
 479
 480     TEST_F( CuckooMap, refinable_list_ordered_storehash )
 481     {
 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 >
 490             >::type
 491         > map_type;
 492
 493         typename map_type::hash_tuple_type ht;
 494         map_type m( 32, 6, 0, std::move( ht ));
 495         test( m );
 496     }
 497
 498     TEST_F( CuckooMap, refinable_vector_ordered_storehash )
 499     {
 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 >
 508             >::type
 509         > map_type;
 510
 511         typename map_type::hash_tuple_type ht;
 512         map_type m( std::move( ht ));
 513         test( m );
 514     }
 515
 516
 517 } // namespace