test/unit/intrusive-set/intrusive_split_michael_dhp.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_intrusive_set_hp.h"
  32
  33 #include <cds/intrusive/michael_list_dhp.h>
  34 #include <cds/intrusive/split_list.h>
  35 #include <cds/intrusive/free_list.h>
  36
  37 namespace {
  38     namespace ci = cds::intrusive;
  39     typedef cds::gc::DHP gc_type;
  40
  41     class IntrusiveSplitListSet_DHP : public cds_test::intrusive_set_hp
  42     {
  43     protected:
  44         typedef cds_test::intrusive_set_hp base_class;
  45
  46     protected:
  47         typedef typename base_class::base_int_item< ci::split_list::node< ci::michael_list::node<gc_type>>>   base_item_type;
  48         typedef typename base_class::member_int_item< ci::split_list::node< ci::michael_list::node<gc_type>>> member_item_type;
  49
  50         void SetUp()
  51         {
  52             struct list_traits : public ci::michael_list::traits
  53             {
  54                 typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
  55             };
  56             typedef ci::MichaelList< gc_type, base_item_type, list_traits > list_type;
  57             typedef ci::SplitListSet< gc_type, list_type >   set_type;
  58
  59             cds::gc::dhp::smr::construct( set_type::c_nHazardPtrCount );
  60             cds::threading::Manager::attachThread();
  61         }
  62
  63         void TearDown()
  64         {
  65             cds::threading::Manager::detachThread();
  66             cds::gc::dhp::smr::destruct();
  67         }
  68     };
  69
  70
  71     TEST_F( IntrusiveSplitListSet_DHP, base_cmp )
  72     {
  73         typedef ci::MichaelList< gc_type
  74             , base_item_type
  75             ,ci::michael_list::make_traits<
  76                 ci::opt::hook< ci::michael_list::base_hook< ci::opt::gc< gc_type > > >
  77                 ,ci::opt::compare< cmp<base_item_type> >
  78                 ,ci::opt::disposer< mock_disposer >
  79             >::type
  80         > bucket_type;
  81
  82         typedef ci::SplitListSet< gc_type, bucket_type,
  83             ci::split_list::make_traits<
  84                 ci::opt::hash< hash_int >
  85             >::type
  86         > set_type;
  87
  88         set_type s( kSize, 2 );
  89         test( s );
  90     }
  91
  92     TEST_F( IntrusiveSplitListSet_DHP, base_less )
  93     {
  94         typedef ci::MichaelList< gc_type
  95             , base_item_type
  96             ,ci::michael_list::make_traits<
  97                 ci::opt::hook< ci::michael_list::base_hook< ci::opt::gc< gc_type >>>
  98                 ,ci::opt::less< less<base_item_type> >
  99                 ,ci::opt::disposer< mock_disposer >
 100             >::type
 101         > bucket_type;
 102
 103         typedef ci::SplitListSet< gc_type, bucket_type,
 104             ci::split_list::make_traits<
 105                 ci::opt::hash< hash_int >
 106                 ,ci::opt::item_counter< cds::atomicity::item_counter >
 107             >::type
 108         > set_type;
 109
 110         set_type s( kSize, 2 );
 111         test( s );
 112     }
 113
 114     TEST_F( IntrusiveSplitListSet_DHP, base_cmpmix )
 115     {
 116         struct list_traits : public ci::michael_list::traits
 117         {
 118             typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
 119             typedef base_class::less<base_item_type> less;
 120             typedef cmp<base_item_type> compare;
 121             typedef mock_disposer disposer;
 122         };
 123         typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
 124
 125         struct set_traits : public ci::split_list::traits
 126         {
 127             typedef hash_int hash;
 128             typedef simple_item_counter item_counter;
 129             typedef ci::split_list::stat<> stat;
 130         };
 131         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 132
 133         set_type s( kSize, 2 );
 134         test( s );
 135     }
 136
 137     TEST_F( IntrusiveSplitListSet_DHP, base_static_bucket_table )
 138     {
 139         struct list_traits: public ci::michael_list::traits
 140         {
 141             typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
 142             typedef base_class::less<base_item_type> less;
 143             typedef cmp<base_item_type> compare;
 144             typedef mock_disposer disposer;
 145         };
 146         typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
 147
 148         struct set_traits: public ci::split_list::traits
 149         {
 150             typedef hash_int hash;
 151             typedef simple_item_counter item_counter;
 152             typedef ci::split_list::stat<> stat;
 153             enum {
 154                 dynamic_bucket_table = false
 155             };
 156         };
 157         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 158
 159         set_type s( kSize, 2 );
 160         test( s );
 161     }
 162
 163     TEST_F( IntrusiveSplitListSet_DHP, base_static_bucket_table_free_list )
 164     {
 165         struct list_traits: public ci::michael_list::traits
 166         {
 167             typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
 168             typedef cmp<base_item_type> compare;
 169             typedef mock_disposer disposer;
 170         };
 171         typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
 172
 173         struct set_traits: public ci::split_list::traits
 174         {
 175             typedef hash_int hash;
 176             typedef simple_item_counter item_counter;
 177             typedef ci::split_list::stat<> stat;
 178             enum {
 179                 dynamic_bucket_table = false
 180             };
 181             typedef ci::FreeList free_list;
 182         };
 183         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 184
 185         set_type s( kSize, 2 );
 186         test( s );
 187     }
 188
 189     TEST_F( IntrusiveSplitListSet_DHP, base_free_list )
 190     {
 191         struct list_traits: public ci::michael_list::traits
 192         {
 193             typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
 194             typedef base_class::less<base_item_type> less;
 195             typedef mock_disposer disposer;
 196         };
 197         typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
 198
 199         struct set_traits: public ci::split_list::traits
 200         {
 201             typedef hash_int hash;
 202             typedef simple_item_counter item_counter;
 203             typedef ci::split_list::stat<> stat;
 204             typedef ci::FreeList free_list;
 205         };
 206         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 207
 208         set_type s( kSize, 2 );
 209         test( s );
 210     }
 211
 212     TEST_F( IntrusiveSplitListSet_DHP, base_bit_reversal_swar )
 213     {
 214         struct list_traits: public ci::michael_list::traits
 215         {
 216             typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
 217             typedef cmp<base_item_type> compare;
 218             typedef mock_disposer disposer;
 219         };
 220         typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
 221
 222         struct set_traits: public ci::split_list::traits
 223         {
 224             typedef hash_int hash;
 225             typedef simple_item_counter item_counter;
 226             typedef ci::split_list::stat<> stat;
 227             typedef cds::algo::bit_reversal::swar bit_reversal;
 228         };
 229         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 230
 231         set_type s( kSize, 2 );
 232         test( s );
 233     }
 234
 235     TEST_F( IntrusiveSplitListSet_DHP, base_bit_reversal_lookup )
 236     {
 237         struct list_traits: public ci::michael_list::traits
 238         {
 239             typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
 240             typedef cmp<base_item_type> compare;
 241             typedef mock_disposer disposer;
 242         };
 243         typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
 244
 245         struct set_traits: public ci::split_list::traits
 246         {
 247             typedef hash_int hash;
 248             typedef simple_item_counter item_counter;
 249             typedef ci::split_list::stat<> stat;
 250             typedef cds::algo::bit_reversal::lookup bit_reversal;
 251         };
 252         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 253
 254         set_type s( kSize, 2 );
 255         test( s );
 256     }
 257
 258     TEST_F( IntrusiveSplitListSet_DHP, base_bit_reversal_muldiv )
 259     {
 260         struct list_traits: public ci::michael_list::traits
 261         {
 262             typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
 263             typedef cmp<base_item_type> compare;
 264             typedef mock_disposer disposer;
 265         };
 266         typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
 267
 268         struct set_traits: public ci::split_list::traits
 269         {
 270             typedef hash_int hash;
 271             typedef simple_item_counter item_counter;
 272             typedef ci::split_list::stat<> stat;
 273             typedef cds::algo::bit_reversal::muldiv bit_reversal;
 274         };
 275         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 276
 277         set_type s( kSize, 2 );
 278         test( s );
 279     }
 280
 281     TEST_F( IntrusiveSplitListSet_DHP, member_cmp )
 282     {
 283         typedef ci::MichaelList< gc_type
 284             ,member_item_type
 285             ,ci::michael_list::make_traits<
 286                 ci::opt::hook< ci::michael_list::member_hook<
 287                     offsetof( member_item_type, hMember ),
 288                     ci::opt::gc<gc_type>
 289                 > >
 290                 ,ci::opt::compare< cmp<member_item_type> >
 291                 ,ci::opt::disposer< mock_disposer >
 292             >::type
 293         >    bucket_type;
 294
 295         typedef ci::SplitListSet< gc_type, bucket_type,
 296             ci::split_list::make_traits<
 297                 ci::opt::hash< hash_int >
 298             >::type
 299         > set_type;
 300
 301         set_type s( kSize, 2 );
 302         test( s );
 303     }
 304
 305     TEST_F( IntrusiveSplitListSet_DHP, member_less )
 306     {
 307         typedef ci::MichaelList< gc_type
 308             , member_item_type
 309             ,ci::michael_list::make_traits<
 310                 ci::opt::hook< ci::michael_list::member_hook<
 311                     offsetof( member_item_type, hMember ),
 312                     ci::opt::gc<gc_type>
 313                 > >
 314                 ,ci::opt::less< less<member_item_type> >
 315                 ,ci::opt::disposer< mock_disposer >
 316             >::type
 317         > bucket_type;
 318
 319         typedef ci::SplitListSet< gc_type, bucket_type,
 320             ci::split_list::make_traits<
 321                 ci::opt::hash< hash_int >
 322                 ,ci::opt::back_off< cds::backoff::pause >
 323             >::type
 324         > set_type;
 325
 326         set_type s( kSize, 2 );
 327         test( s );
 328     }
 329
 330     TEST_F( IntrusiveSplitListSet_DHP, member_cmpmix )
 331     {
 332         struct list_traits : public ci::michael_list::traits
 333         {
 334             typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
 335             typedef base_class::less<member_item_type> less;
 336             typedef cmp<member_item_type> compare;
 337             typedef mock_disposer disposer;
 338         };
 339         typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
 340
 341         struct set_traits : public ci::split_list::traits
 342         {
 343             typedef hash_int hash;
 344             typedef simple_item_counter item_counter;
 345         };
 346         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 347
 348         set_type s( kSize, 2 );
 349         test( s );
 350     }
 351
 352     TEST_F( IntrusiveSplitListSet_DHP, member_static_bucket_table )
 353     {
 354         struct list_traits: public ci::michael_list::traits
 355         {
 356             typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
 357             typedef base_class::less<member_item_type> less;
 358             typedef cmp<member_item_type> compare;
 359             typedef mock_disposer disposer;
 360         };
 361         typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
 362
 363         struct set_traits: public ci::split_list::traits
 364         {
 365             typedef hash_int hash;
 366             typedef simple_item_counter item_counter;
 367             enum {
 368                 dynami_bucket_table = false
 369             };
 370         };
 371         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 372
 373         set_type s( kSize, 2 );
 374         test( s );
 375     }
 376
 377     TEST_F( IntrusiveSplitListSet_DHP, member_static_bucket_table_free_list )
 378     {
 379         struct list_traits: public ci::michael_list::traits
 380         {
 381             typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
 382             typedef base_class::less<member_item_type> less;
 383             typedef mock_disposer disposer;
 384         };
 385         typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
 386
 387         struct set_traits: public ci::split_list::traits
 388         {
 389             typedef hash_int hash;
 390             typedef simple_item_counter item_counter;
 391             enum {
 392                 dynami_bucket_table = false
 393             };
 394             typedef ci::FreeList free_list;
 395         };
 396         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 397
 398         set_type s( kSize, 2 );
 399         test( s );
 400     }
 401
 402     TEST_F( IntrusiveSplitListSet_DHP, member_free_list )
 403     {
 404         struct list_traits: public ci::michael_list::traits
 405         {
 406             typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
 407             typedef base_class::less<member_item_type> less;
 408             typedef mock_disposer disposer;
 409         };
 410         typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
 411
 412         struct set_traits: public ci::split_list::traits
 413         {
 414             typedef hash_int hash;
 415             typedef simple_item_counter item_counter;
 416             typedef ci::FreeList free_list;
 417         };
 418         typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
 419
 420         set_type s( kSize, 2 );
 421         test( s );
 422     }
 423
 424 } // namespace