test/unit/striped-set/cuckoo_set.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_set.h"
  32
  33 #include <cds/container/cuckoo_set.h>
  34
  35 namespace {
  36     namespace cc = cds::container;
  37
  38     class CuckooSet : public cds_test::container_set
  39     {
  40     protected:
  41         typedef cds_test::container_set base_class;
  42
  43         template <typename Set>
  44         void test( Set& s )
  45         {
  46             // Precondition: set is empty
  47             // Postcondition: set is empty
  48
  49             base_class::test_< Set::c_isSorted>( s );
  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( CuckooSet, striped_list_unordered )
  69     {
  70         struct set_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::CuckooSet< int_item, set_traits > set_type;
  77
  78         set_type s;
  79         test( s );
  80     }
  81
  82     TEST_F( CuckooSet, striped_vector_unordered )
  83     {
  84         struct set_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::CuckooSet< int_item, set_traits > set_type;
  91
  92         set_type s( 32, 4 );
  93         test( s );
  94     }
  95
  96     TEST_F( CuckooSet, striped_list_ordered_cmp )
  97     {
  98         typedef cc::CuckooSet< int_item
  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         > set_type;
 105
 106         set_type s( 32, 6, 4 );
 107         test( s );
 108     }
 109
 110     TEST_F( CuckooSet, striped_vector_ordered_cmp )
 111     {
 112         typedef cc::CuckooSet< int_item
 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         > set_type;
 119
 120         typename set_type::hash_tuple_type ht;
 121         set_type s( ht );
 122         test( s );
 123     }
 124
 125     TEST_F( CuckooSet, striped_list_ordered_less )
 126     {
 127         typedef cc::CuckooSet< int_item
 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         > set_type;
 134
 135         typename set_type::hash_tuple_type ht;
 136         set_type s( 32, 6, 4, ht );
 137         test( s );
 138     }
 139
 140     TEST_F( CuckooSet, striped_vector_ordered_less )
 141     {
 142         typedef cc::CuckooSet< int_item
 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         > set_type;
 149
 150         typename set_type::hash_tuple_type ht;
 151         set_type s( std::move( ht ));
 152         test( s );
 153     }
 154
 155     TEST_F( CuckooSet, striped_list_ordered_cmpmix )
 156     {
 157         typedef cc::CuckooSet< int_item
 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         > set_type;
 165
 166         typename set_type::hash_tuple_type ht;
 167         set_type s( 32, 6, 0, std::move( ht ));
 168         test( s );
 169     }
 170
 171     TEST_F( CuckooSet, striped_vector_ordered_cmpmix )
 172     {
 173         typedef cc::CuckooSet< int_item
 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         > set_type;
 181
 182         typename set_type::hash_tuple_type ht;
 183         set_type s( std::move( ht ));
 184         test( s );
 185     }
 186
 187     TEST_F( CuckooSet, striped_list_ordered_stat )
 188     {
 189         typedef cc::CuckooSet< int_item
 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         > set_type;
 198
 199         set_type s;
 200         test( s );
 201     }
 202
 203     TEST_F( CuckooSet, striped_vector_ordered_stat )
 204     {
 205         typedef cc::CuckooSet< int_item
 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         > set_type;
 214
 215         set_type s;
 216         test( s );
 217     }
 218
 219     TEST_F( CuckooSet, striped_list_unordered_storehash )
 220     {
 221         struct set_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::CuckooSet< int_item, set_traits > set_type;
 229
 230         set_type s;
 231         test( s );
 232     }
 233
 234     TEST_F( CuckooSet, striped_vector_unordered_storehash )
 235     {
 236         struct set_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::CuckooSet< int_item, set_traits > set_type;
 244
 245         set_type s( 32, 4 );
 246         test( s );
 247     }
 248
 249     TEST_F( CuckooSet, striped_list_ordered_storehash )
 250     {
 251         typedef cc::CuckooSet< int_item
 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         > set_type;
 260
 261         typename set_type::hash_tuple_type ht;
 262         set_type s( 32, 6, 0, std::move( ht ));
 263         test( s );
 264     }
 265
 266     TEST_F( CuckooSet, striped_vector_ordered_storehash )
 267     {
 268         typedef cc::CuckooSet< int_item
 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         > set_type;
 277
 278         typename set_type::hash_tuple_type ht;
 279         set_type s( std::move( ht ));
 280         test( s );
 281     }
 282
 283
 284 //************************************************************
 285 // refinable set
 286
 287     TEST_F( CuckooSet, refinable_list_unordered )
 288     {
 289         struct set_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::CuckooSet< int_item, set_traits > set_type;
 297
 298         set_type s;
 299         test( s );
 300     }
 301
 302     TEST_F( CuckooSet, refinable_vector_unordered )
 303     {
 304         struct set_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::CuckooSet< int_item, set_traits > set_type;
 312
 313         set_type s( 32, 4 );
 314         test( s );
 315     }
 316
 317     TEST_F( CuckooSet, refinable_list_ordered_cmp )
 318     {
 319         typedef cc::CuckooSet< int_item
 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         > set_type;
 327
 328         set_type s( 32, 6, 4 );
 329         test( s );
 330     }
 331
 332     TEST_F( CuckooSet, refinable_vector_ordered_cmp )
 333     {
 334         typedef cc::CuckooSet< int_item
 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         > set_type;
 342
 343         typename set_type::hash_tuple_type ht;
 344         set_type s( ht );
 345         test( s );
 346     }
 347
 348     TEST_F( CuckooSet, refinable_list_ordered_less )
 349     {
 350         typedef cc::CuckooSet< int_item
 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         > set_type;
 358
 359         typename set_type::hash_tuple_type ht;
 360         set_type s( 32, 6, 4, ht );
 361         test( s );
 362     }
 363
 364     TEST_F( CuckooSet, refinable_vector_ordered_less )
 365     {
 366         typedef cc::CuckooSet< int_item
 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         > set_type;
 374
 375         typename set_type::hash_tuple_type ht;
 376         set_type s( std::move( ht ));
 377         test( s );
 378     }
 379
 380     TEST_F( CuckooSet, refinable_list_ordered_cmpmix )
 381     {
 382         typedef cc::CuckooSet< int_item
 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         > set_type;
 391
 392         typename set_type::hash_tuple_type ht;
 393         set_type s( 32, 6, 0, std::move( ht ));
 394         test( s );
 395     }
 396
 397     TEST_F( CuckooSet, refinable_vector_ordered_cmpmix )
 398     {
 399         typedef cc::CuckooSet< int_item
 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         > set_type;
 408
 409         typename set_type::hash_tuple_type ht;
 410         set_type s( std::move( ht ));
 411         test( s );
 412     }
 413
 414     TEST_F( CuckooSet, refinable_list_ordered_stat )
 415     {
 416         typedef cc::CuckooSet< int_item
 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         > set_type;
 426
 427         set_type s;
 428         test( s );
 429     }
 430
 431     TEST_F( CuckooSet, refinable_vector_ordered_stat )
 432     {
 433         typedef cc::CuckooSet< int_item
 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         > set_type;
 443
 444         set_type s;
 445         test( s );
 446     }
 447
 448     TEST_F( CuckooSet, refinable_list_unordered_storehash )
 449     {
 450         struct set_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::CuckooSet< int_item, set_traits > set_type;
 459
 460         set_type s;
 461         test( s );
 462     }
 463
 464     TEST_F( CuckooSet, refinable_vector_unordered_storehash )
 465     {
 466         struct set_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::CuckooSet< int_item, set_traits > set_type;
 475
 476         set_type s( 32, 4 );
 477         test( s );
 478     }
 479
 480     TEST_F( CuckooSet, refinable_list_ordered_storehash )
 481     {
 482         typedef cc::CuckooSet< int_item
 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         > set_type;
 492
 493         typename set_type::hash_tuple_type ht;
 494         set_type s( 32, 6, 0, std::move( ht ));
 495         test( s );
 496     }
 497
 498     TEST_F( CuckooSet, refinable_vector_ordered_storehash )
 499     {
 500         typedef cc::CuckooSet< int_item
 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         > set_type;
 510
 511         typename set_type::hash_tuple_type ht;
 512         set_type s( std::move( ht ));
 513         test( s );
 514     }
 515
 516
 517 } // namespace