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