test/unit/intrusive-set/test_intrusive_split_michael_rcu.h

   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 #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_MICHAEL_RCU_H
  31 #define CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_MICHAEL_RCU_H
  32
  33 #include "test_intrusive_set_rcu.h"
  34 #include <cds/intrusive/michael_list_rcu.h>
  35 #include <cds/intrusive/split_list_rcu.h>
  36 #include <cds/intrusive/free_list.h>
  37
  38 namespace ci = cds::intrusive;
  39
  40 template <class RCU>
  41 class IntrusiveSplitMichaelSet: public cds_test::intrusive_set_rcu
  42 {
  43     typedef cds_test::intrusive_set_rcu base_class;
  44 public:
  45     typedef cds::urcu::gc<RCU> rcu_type;
  46     typedef typename base_class::base_int_item< ci::split_list::node<ci::michael_list::node<rcu_type>>>   base_item_type;
  47     typedef typename base_class::member_int_item< ci::split_list::node<ci::michael_list::node<rcu_type>>> member_item_type;
  48
  49 protected:
  50     void SetUp()
  51     {
  52         RCU::Construct();
  53         cds::threading::Manager::attachThread();
  54     }
  55
  56     void TearDown()
  57     {
  58         cds::threading::Manager::detachThread();
  59         RCU::Destruct();
  60     }
  61 };
  62
  63 TYPED_TEST_CASE_P( IntrusiveSplitMichaelSet );
  64
  65 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_cmp )
  66 {
  67     typedef typename TestFixture::rcu_type rcu_type;
  68     typedef typename TestFixture::base_item_type base_item_type;
  69     typedef typename TestFixture::mock_disposer mock_disposer;
  70     typedef typename TestFixture::template cmp<base_item_type> cmp;
  71     typedef typename TestFixture::hash_int hash_int;
  72
  73     typedef ci::MichaelList< rcu_type
  74         , base_item_type
  75         , typename ci::michael_list::make_traits<
  76             ci::opt::hook< ci::michael_list::base_hook< ci::opt::gc< rcu_type > > >
  77             , ci::opt::compare< cmp >
  78             , ci::opt::disposer< mock_disposer >
  79         >::type
  80     > bucket_type;
  81
  82     typedef ci::SplitListSet< rcu_type, bucket_type,
  83         typename ci::split_list::make_traits<
  84             ci::opt::hash< hash_int >
  85         >::type
  86     > set_type;
  87
  88     set_type s( TestFixture::kSize, 2 );
  89     this->test( s );
  90 }
  91
  92 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_less )
  93 {
  94     typedef typename TestFixture::rcu_type rcu_type;
  95     typedef typename TestFixture::base_item_type base_item_type;
  96     typedef typename TestFixture::mock_disposer mock_disposer;
  97     typedef typename TestFixture::template less<base_item_type> less;
  98     typedef typename TestFixture::hash_int hash_int;
  99
 100     typedef ci::MichaelList< rcu_type
 101         , base_item_type
 102         , typename ci::michael_list::make_traits<
 103             ci::opt::hook< ci::michael_list::base_hook< ci::opt::gc< rcu_type >>>
 104             , ci::opt::less< less >
 105             , ci::opt::disposer< mock_disposer >
 106         >::type
 107     > bucket_type;
 108
 109     typedef ci::SplitListSet< rcu_type, bucket_type,
 110         typename ci::split_list::make_traits<
 111             ci::opt::hash< hash_int >
 112             , ci::opt::item_counter< cds::atomicity::item_counter >
 113         >::type
 114     > set_type;
 115
 116     set_type s( TestFixture::kSize, 2 );
 117     this->test( s );
 118 }
 119
 120 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_cmpmix )
 121 {
 122     typedef typename TestFixture::rcu_type rcu_type;
 123     typedef typename TestFixture::base_item_type base_item_type;
 124     typedef typename TestFixture::mock_disposer mock_disposer;
 125     typedef typename TestFixture::hash_int hash_int;
 126
 127     struct list_traits : public ci::michael_list::traits
 128     {
 129         typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
 130         typedef typename TestFixture::template less<base_item_type> less;
 131         typedef typename TestFixture::template cmp<base_item_type> compare;
 132         typedef mock_disposer disposer;
 133     };
 134     typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
 135
 136     struct set_traits : public ci::split_list::traits
 137     {
 138         typedef hash_int hash;
 139         typedef typename TestFixture::simple_item_counter item_counter;
 140         typedef ci::split_list::stat<> stat;
 141     };
 142     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 143
 144     set_type s( TestFixture::kSize, 2 );
 145     this->test( s );
 146 }
 147
 148 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_static_bucket_table )
 149 {
 150     typedef typename TestFixture::rcu_type rcu_type;
 151     typedef typename TestFixture::base_item_type base_item_type;
 152     typedef typename TestFixture::mock_disposer mock_disposer;
 153     typedef typename TestFixture::hash_int hash_int;
 154
 155     struct list_traits: public ci::michael_list::traits
 156     {
 157         typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
 158         typedef typename TestFixture::template less<base_item_type> less;
 159         typedef typename TestFixture::template cmp<base_item_type> compare;
 160         typedef mock_disposer disposer;
 161     };
 162     typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
 163
 164     struct set_traits: public ci::split_list::traits
 165     {
 166         typedef hash_int hash;
 167         typedef typename TestFixture::simple_item_counter item_counter;
 168         typedef ci::split_list::stat<> stat;
 169         enum {
 170             dynamic_bucket_table = false
 171         };
 172     };
 173     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 174
 175     set_type s( TestFixture::kSize, 2 );
 176     this->test( s );
 177 }
 178
 179 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_static_bucket_table_free_list )
 180 {
 181     typedef typename TestFixture::rcu_type rcu_type;
 182     typedef typename TestFixture::base_item_type base_item_type;
 183     typedef typename TestFixture::mock_disposer mock_disposer;
 184     typedef typename TestFixture::hash_int hash_int;
 185
 186     struct list_traits: public ci::michael_list::traits
 187     {
 188         typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
 189         typedef typename TestFixture::template cmp<base_item_type> compare;
 190         typedef mock_disposer disposer;
 191     };
 192     typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
 193
 194     struct set_traits: public ci::split_list::traits
 195     {
 196         typedef hash_int hash;
 197         typedef typename TestFixture::simple_item_counter item_counter;
 198         enum {
 199             dynamic_bucket_table = false
 200         };
 201         typedef ci::FreeList free_list;
 202     };
 203     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 204
 205     set_type s( TestFixture::kSize, 2 );
 206     this->test( s );
 207 }
 208
 209 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_free_list )
 210 {
 211     typedef typename TestFixture::rcu_type rcu_type;
 212     typedef typename TestFixture::base_item_type base_item_type;
 213     typedef typename TestFixture::mock_disposer mock_disposer;
 214     typedef typename TestFixture::hash_int hash_int;
 215
 216     struct list_traits: public ci::michael_list::traits
 217     {
 218         typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
 219         typedef typename TestFixture::template less<base_item_type> less;
 220         typedef mock_disposer disposer;
 221     };
 222     typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
 223
 224     struct set_traits: public ci::split_list::traits
 225     {
 226         typedef hash_int hash;
 227         typedef typename TestFixture::simple_item_counter item_counter;
 228         typedef ci::split_list::stat<> stat;
 229         typedef ci::FreeList free_list;
 230     };
 231     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 232
 233     set_type s( TestFixture::kSize, 2 );
 234     this->test( s );
 235 }
 236
 237 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_bit_reverse_swar )
 238 {
 239     typedef typename TestFixture::rcu_type rcu_type;
 240     typedef typename TestFixture::base_item_type base_item_type;
 241     typedef typename TestFixture::mock_disposer mock_disposer;
 242     typedef typename TestFixture::hash_int hash_int;
 243
 244     struct list_traits: public ci::michael_list::traits
 245     {
 246         typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
 247         typedef typename TestFixture::template less<base_item_type> less;
 248         typedef mock_disposer disposer;
 249     };
 250     typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
 251
 252     struct set_traits: public ci::split_list::traits
 253     {
 254         typedef hash_int hash;
 255         typedef typename TestFixture::simple_item_counter item_counter;
 256         typedef ci::split_list::stat<> stat;
 257         typedef cds::algo::bit_reversal::swar bit_reversal;
 258     };
 259     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 260
 261     set_type s( TestFixture::kSize, 2 );
 262     this->test( s );
 263 }
 264
 265 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_bit_reverse_lookup )
 266 {
 267     typedef typename TestFixture::rcu_type rcu_type;
 268     typedef typename TestFixture::base_item_type base_item_type;
 269     typedef typename TestFixture::mock_disposer mock_disposer;
 270     typedef typename TestFixture::hash_int hash_int;
 271
 272     struct list_traits: public ci::michael_list::traits
 273     {
 274         typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
 275         typedef typename TestFixture::template less<base_item_type> less;
 276         typedef mock_disposer disposer;
 277     };
 278     typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
 279
 280     struct set_traits: public ci::split_list::traits
 281     {
 282         typedef hash_int hash;
 283         typedef typename TestFixture::simple_item_counter item_counter;
 284         typedef ci::split_list::stat<> stat;
 285         typedef cds::algo::bit_reversal::lookup bit_reversal;
 286     };
 287     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 288
 289     set_type s( TestFixture::kSize, 2 );
 290     this->test( s );
 291 }
 292
 293 TYPED_TEST_P( IntrusiveSplitMichaelSet, base_bit_reverse_muldiv )
 294 {
 295     typedef typename TestFixture::rcu_type rcu_type;
 296     typedef typename TestFixture::base_item_type base_item_type;
 297     typedef typename TestFixture::mock_disposer mock_disposer;
 298     typedef typename TestFixture::hash_int hash_int;
 299
 300     struct list_traits: public ci::michael_list::traits
 301     {
 302         typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
 303         typedef typename TestFixture::template less<base_item_type> less;
 304         typedef mock_disposer disposer;
 305     };
 306     typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
 307
 308     struct set_traits: public ci::split_list::traits
 309     {
 310         typedef hash_int hash;
 311         typedef typename TestFixture::simple_item_counter item_counter;
 312         typedef ci::split_list::stat<> stat;
 313         typedef cds::algo::bit_reversal::muldiv bit_reversal;
 314     };
 315     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 316
 317     set_type s( TestFixture::kSize, 2 );
 318     this->test( s );
 319 }
 320
 321
 322 TYPED_TEST_P( IntrusiveSplitMichaelSet, member_cmp )
 323 {
 324     typedef typename TestFixture::rcu_type rcu_type;
 325     typedef typename TestFixture::member_item_type member_item_type;
 326     typedef typename TestFixture::mock_disposer mock_disposer;
 327     typedef typename TestFixture::template cmp<member_item_type> cmp;
 328     typedef typename TestFixture::hash_int hash_int;
 329
 330     typedef ci::MichaelList< rcu_type
 331         , member_item_type
 332         , typename ci::michael_list::make_traits<
 333             ci::opt::hook< ci::michael_list::member_hook<
 334                 offsetof( member_item_type, hMember ),
 335                 ci::opt::gc<rcu_type>
 336             >>
 337             , ci::opt::compare< cmp >
 338             , ci::opt::disposer< mock_disposer >
 339         >::type
 340     >    bucket_type;
 341
 342     typedef ci::SplitListSet< rcu_type, bucket_type,
 343         typename ci::split_list::make_traits<
 344             ci::opt::hash< hash_int >
 345         >::type
 346     > set_type;
 347
 348     set_type s( TestFixture::kSize, 2 );
 349     this->test( s );
 350 }
 351
 352 TYPED_TEST_P( IntrusiveSplitMichaelSet, member_less )
 353 {
 354     typedef typename TestFixture::rcu_type rcu_type;
 355     typedef typename TestFixture::member_item_type member_item_type;
 356     typedef typename TestFixture::mock_disposer mock_disposer;
 357     typedef typename TestFixture::template less<member_item_type> less;
 358     typedef typename TestFixture::hash_int hash_int;
 359
 360     typedef ci::MichaelList< rcu_type
 361         , member_item_type
 362         , typename ci::michael_list::make_traits<
 363             ci::opt::hook< ci::michael_list::member_hook<
 364                 offsetof( member_item_type, hMember ),
 365                 ci::opt::gc<rcu_type>
 366             > >
 367             , ci::opt::less< less >
 368             , ci::opt::disposer< mock_disposer >
 369         >::type
 370     > bucket_type;
 371
 372     typedef ci::SplitListSet< rcu_type, bucket_type,
 373         typename ci::split_list::make_traits<
 374             ci::opt::hash< hash_int >
 375             , ci::opt::back_off< cds::backoff::pause >
 376         >::type
 377     > set_type;
 378
 379     set_type s( TestFixture::kSize, 2 );
 380     this->test( s );
 381 }
 382
 383 TYPED_TEST_P( IntrusiveSplitMichaelSet, member_cmpmix )
 384 {
 385     typedef typename TestFixture::rcu_type rcu_type;
 386     typedef typename TestFixture::member_item_type member_item_type;
 387     typedef typename TestFixture::mock_disposer mock_disposer;
 388     typedef typename TestFixture::hash_int hash_int;
 389
 390     struct list_traits : public ci::michael_list::traits
 391     {
 392         typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
 393         typedef typename TestFixture::template less<member_item_type> less;
 394         typedef typename TestFixture::template cmp<member_item_type> compare;
 395         typedef mock_disposer disposer;
 396     };
 397     typedef ci::MichaelList< rcu_type, member_item_type, list_traits > bucket_type;
 398
 399     struct set_traits : public ci::split_list::traits
 400     {
 401         typedef hash_int hash;
 402         typedef typename TestFixture::simple_item_counter item_counter;
 403     };
 404     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 405
 406     set_type s( TestFixture::kSize, 2 );
 407     this->test( s );
 408 }
 409
 410 TYPED_TEST_P( IntrusiveSplitMichaelSet, member_static_bucket_table )
 411 {
 412     typedef typename TestFixture::rcu_type rcu_type;
 413     typedef typename TestFixture::member_item_type member_item_type;
 414     typedef typename TestFixture::mock_disposer mock_disposer;
 415     typedef typename TestFixture::hash_int hash_int;
 416
 417     struct list_traits: public ci::michael_list::traits
 418     {
 419         typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
 420         typedef typename TestFixture::template less<member_item_type> less;
 421         typedef typename TestFixture::template cmp<member_item_type> compare;
 422         typedef mock_disposer disposer;
 423     };
 424     typedef ci::MichaelList< rcu_type, member_item_type, list_traits > bucket_type;
 425
 426     struct set_traits: public ci::split_list::traits
 427     {
 428         typedef hash_int hash;
 429         typedef typename TestFixture::simple_item_counter item_counter;
 430         enum {
 431             dynamic_bucket_table = false
 432         };
 433     };
 434     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 435
 436     set_type s( TestFixture::kSize, 2 );
 437     this->test( s );
 438 }
 439
 440 TYPED_TEST_P( IntrusiveSplitMichaelSet, member_static_bucket_table_free_list )
 441 {
 442     typedef typename TestFixture::rcu_type rcu_type;
 443     typedef typename TestFixture::member_item_type member_item_type;
 444     typedef typename TestFixture::mock_disposer mock_disposer;
 445     typedef typename TestFixture::hash_int hash_int;
 446
 447     struct list_traits: public ci::michael_list::traits
 448     {
 449         typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
 450         typedef typename TestFixture::template cmp<member_item_type> compare;
 451         typedef mock_disposer disposer;
 452     };
 453     typedef ci::MichaelList< rcu_type, member_item_type, list_traits > bucket_type;
 454
 455     struct set_traits: public ci::split_list::traits
 456     {
 457         typedef hash_int hash;
 458         typedef typename TestFixture::simple_item_counter item_counter;
 459         enum {
 460             dynamic_bucket_table = false
 461         };
 462         typedef ci::FreeList free_list;
 463     };
 464     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 465
 466     set_type s( TestFixture::kSize, 2 );
 467     this->test( s );
 468 }
 469
 470 TYPED_TEST_P( IntrusiveSplitMichaelSet, member_free_list )
 471 {
 472     typedef typename TestFixture::rcu_type rcu_type;
 473     typedef typename TestFixture::member_item_type member_item_type;
 474     typedef typename TestFixture::mock_disposer mock_disposer;
 475     typedef typename TestFixture::hash_int hash_int;
 476
 477     struct list_traits: public ci::michael_list::traits
 478     {
 479         typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
 480         typedef typename TestFixture::template less<member_item_type> less;
 481         typedef mock_disposer disposer;
 482     };
 483     typedef ci::MichaelList< rcu_type, member_item_type, list_traits > bucket_type;
 484
 485     struct set_traits: public ci::split_list::traits
 486     {
 487         typedef hash_int hash;
 488         typedef typename TestFixture::simple_item_counter item_counter;
 489         typedef ci::FreeList free_list;
 490     };
 491     typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
 492
 493     set_type s( TestFixture::kSize, 2 );
 494     this->test( s );
 495 }
 496
 497 // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
 498 // "No test named <test_name> can be found in this test case"
 499 REGISTER_TYPED_TEST_CASE_P( IntrusiveSplitMichaelSet,
 500     base_cmp, base_less, base_cmpmix, base_static_bucket_table, base_static_bucket_table_free_list, base_free_list, base_bit_reverse_swar, base_bit_reverse_lookup, base_bit_reverse_muldiv, member_cmp, member_less, member_cmpmix, member_static_bucket_table, member_static_bucket_table_free_list, member_free_list
 501 );
 502
 503
 504 #endif // CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_MICHAEL_RCU_H
 505