gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/test/unit/queue/intrusive_fcqueue.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 <cds_test/ext_gtest.h>
  32 #include <cds/intrusive/fcqueue.h>
  33
  34 #include <vector>
  35 #include <boost/intrusive/slist.hpp>
  36
  37 namespace {
  38
  39     class IntrusiveFCQueue : public ::testing::Test
  40     {
  41     protected:
  42         template <typename Hook>
  43         struct base_hook_item : public Hook
  44         {
  45             int nVal;
  46             int nDisposeCount;
  47
  48             base_hook_item()
  49                 : nDisposeCount( 0 )
  50             {}
  51         };
  52
  53         template <typename Hook>
  54         struct member_hook_item
  55         {
  56             int nVal;
  57             int nDisposeCount;
  58             Hook hMember;
  59
  60             member_hook_item()
  61                 : nDisposeCount( 0 )
  62             {}
  63         };
  64
  65     public:
  66         struct disposer
  67         {
  68             template <typename T>
  69             void operator ()( T * p )
  70             {
  71                 ++p->nDisposeCount;
  72             }
  73         };
  74
  75     protected:
  76         template <typename Queue>
  77         void test( Queue& q )
  78         {
  79             typedef typename Queue::value_type value_type;
  80             typedef typename Queue::container_type underlying_queue_type;
  81
  82             size_t const nSize = 100;
  83             value_type * pv;
  84             std::vector<value_type> arr;
  85             arr.resize( nSize );
  86             int total_sum = 0;
  87             for ( size_t i = 0; i < nSize; ++i ) {
  88                 arr[i].nVal = static_cast<int>( i );
  89                 total_sum += static_cast<int>( i );
  90             }
  91
  92             ASSERT_TRUE( q.empty());
  93             ASSERT_EQ( q.size(), 0u );
  94
  95             // pop from empty queue
  96             pv = q.pop();
  97             ASSERT_TRUE( pv == nullptr );
  98             ASSERT_TRUE( q.empty());
  99             ASSERT_EQ( q.size(), 0u );
 100
 101             pv = q.dequeue();
 102             ASSERT_TRUE( pv == nullptr );
 103             ASSERT_TRUE( q.empty());
 104             ASSERT_EQ( q.size(), 0u );
 105
 106             // push/pop test
 107             for ( size_t i = 0; i < nSize; ++i ) {
 108                 if ( i & 1 )
 109                     q.push( arr[i] );
 110                 else
 111                     q.enqueue( arr[i] );
 112                 ASSERT_FALSE( q.empty());
 113                 ASSERT_EQ( q.size(), i + 1 );
 114             }
 115
 116             int sum = 0;
 117             q.apply( [&sum]( underlying_queue_type& queue )
 118             {
 119                 for ( auto const& el : queue )
 120                     sum += el.nVal;
 121             } );
 122             EXPECT_EQ( sum, total_sum );
 123
 124
 125             for ( size_t i = 0; i < nSize; ++i ) {
 126                 ASSERT_FALSE( q.empty());
 127                 ASSERT_EQ( q.size(), nSize - i );
 128                 if ( i & 1 )
 129                     pv = q.pop();
 130                 else
 131                     pv = q.dequeue();
 132                 ASSERT_FALSE( pv == nullptr );
 133                 ASSERT_EQ( pv->nVal, static_cast<int>(i));
 134             }
 135             ASSERT_TRUE( q.empty());
 136             ASSERT_EQ( q.size(), 0u );
 137
 138             // pop() doesn't call disposer
 139             for ( size_t i = 0; i < nSize; ++i ) {
 140                 ASSERT_EQ( arr[i].nDisposeCount, 0 );
 141             }
 142
 143             // clear with disposer
 144             for ( size_t i = 0; i < nSize; ++i )
 145                 q.push( arr[i] );
 146
 147             ASSERT_FALSE( q.empty());
 148             ASSERT_EQ( q.size(), nSize );
 149
 150             q.clear( true );
 151             ASSERT_TRUE( q.empty());
 152             ASSERT_EQ( q.size(), 0u );
 153
 154             for ( size_t i = 0; i < nSize; ++i ) {
 155                 ASSERT_EQ( arr[i].nDisposeCount, 1 );
 156             }
 157
 158             // clear without disposer
 159             for ( size_t i = 0; i < nSize; ++i )
 160                 q.push( arr[i] );
 161
 162             q.clear();
 163             ASSERT_TRUE( q.empty());
 164             ASSERT_EQ( q.size(), 0u );
 165
 166             for ( size_t i = 0; i < nSize; ++i ) {
 167                 ASSERT_EQ( arr[i].nDisposeCount, 1 );
 168             }
 169         }
 170     };
 171
 172     TEST_F( IntrusiveFCQueue, base )
 173     {
 174         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 175         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >,
 176             cds::intrusive::fcqueue::make_traits<
 177                 cds::intrusive::opt::disposer< disposer >
 178             >::type
 179         > queue_type;
 180
 181         queue_type q;
 182         test( q );
 183     }
 184
 185     TEST_F( IntrusiveFCQueue, base_empty_wait_strategy )
 186     {
 187         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 188         struct traits: public cds::intrusive::fcqueue::traits
 189         {
 190             typedef IntrusiveFCQueue::disposer disposer;
 191             typedef cds::algo::flat_combining::wait_strategy::empty wait_strategy;
 192             typedef cds::intrusive::fcqueue::stat<> stat;
 193         };
 194         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 195
 196         queue_type q;
 197         test( q );
 198     }
 199
 200     TEST_F( IntrusiveFCQueue, base_single_mutex_single_condvar )
 201     {
 202         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 203         struct traits: public cds::intrusive::fcqueue::traits
 204         {
 205             typedef IntrusiveFCQueue::disposer disposer;
 206             typedef cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<> wait_strategy;
 207             typedef cds::intrusive::fcqueue::stat<> stat;
 208         };
 209         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 210
 211         queue_type q;
 212         test( q );
 213     }
 214
 215     TEST_F( IntrusiveFCQueue, base_mutex )
 216     {
 217         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 218         struct traits : public cds::intrusive::fcqueue::traits
 219         {
 220             typedef IntrusiveFCQueue::disposer disposer;
 221             typedef std::mutex lock_type;
 222             typedef cds::intrusive::fcqueue::stat<> stat;
 223         };
 224         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 225
 226         queue_type q;
 227         test( q );
 228     }
 229
 230     TEST_F( IntrusiveFCQueue, base_mutex_single_mutex_multi_condvar )
 231     {
 232         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 233         struct traits: public cds::intrusive::fcqueue::traits
 234         {
 235             typedef IntrusiveFCQueue::disposer disposer;
 236             typedef std::mutex lock_type;
 237             typedef cds::intrusive::fcqueue::stat<> stat;
 238             typedef cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<> wait_strategy;
 239         };
 240         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 241
 242         queue_type q;
 243         test( q );
 244     }
 245
 246     TEST_F( IntrusiveFCQueue, base_elimination )
 247     {
 248         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 249         struct traits : public
 250             cds::intrusive::fcqueue::make_traits <
 251                 cds::intrusive::opt::disposer< disposer >
 252                 , cds::opt::enable_elimination < true >
 253             > ::type
 254         {};
 255         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 256
 257         queue_type q;
 258         test( q );
 259     }
 260
 261     TEST_F( IntrusiveFCQueue, base_elimination_multi_mutex_multi_condvar )
 262     {
 263         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 264         struct traits: public
 265             cds::intrusive::fcqueue::make_traits <
 266                 cds::intrusive::opt::disposer< disposer >
 267                 , cds::opt::enable_elimination < true >
 268                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<>>
 269             > ::type
 270         {};
 271         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 272
 273         queue_type q;
 274         test( q );
 275     }
 276
 277     TEST_F( IntrusiveFCQueue, member )
 278     {
 279         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 280         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 281
 282         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 283             cds::intrusive::fcqueue::make_traits<
 284                 cds::intrusive::opt::disposer< disposer >
 285             >::type
 286         > queue_type;
 287
 288         queue_type q;
 289         test( q );
 290     }
 291
 292     TEST_F( IntrusiveFCQueue, member_mutex )
 293     {
 294         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 295         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 296
 297         struct traits : public cds::intrusive::fcqueue::traits
 298         {
 299             typedef IntrusiveFCQueue::disposer disposer;
 300             typedef std::mutex lock_type;
 301             typedef cds::intrusive::fcqueue::stat<> stat;
 302         };
 303         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >, traits > queue_type;
 304
 305         queue_type q;
 306         test( q );
 307     }
 308
 309     TEST_F( IntrusiveFCQueue, member_empty_wait_strategy )
 310     {
 311         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 312         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 313
 314         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 315             cds::intrusive::fcqueue::make_traits<
 316                 cds::intrusive::opt::disposer< disposer >
 317                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
 318             >::type
 319         > queue_type;
 320
 321         queue_type q;
 322         test( q );
 323     }
 324
 325     TEST_F( IntrusiveFCQueue, member_single_mutex_single_condvar )
 326     {
 327         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 328         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 329
 330         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 331             cds::intrusive::fcqueue::make_traits<
 332                 cds::intrusive::opt::disposer< disposer >
 333                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<2>>
 334             >::type
 335         > queue_type;
 336
 337         queue_type q;
 338         test( q );
 339     }
 340
 341     TEST_F( IntrusiveFCQueue, member_multi_mutex_multi_condvar )
 342     {
 343         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 344         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 345
 346         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 347             cds::intrusive::fcqueue::make_traits<
 348                 cds::intrusive::opt::disposer< disposer >
 349                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<>>
 350             >::type
 351         > queue_type;
 352
 353         queue_type q;
 354         test( q );
 355     }
 356
 357     TEST_F( IntrusiveFCQueue, member_elimination )
 358     {
 359         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 360         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 361
 362         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 363             cds::intrusive::fcqueue::make_traits<
 364                 cds::intrusive::opt::disposer< disposer >
 365                 ,cds::opt::enable_elimination< true >
 366             >::type
 367         > queue_type;
 368
 369         queue_type q;
 370         test( q );
 371     }
 372
 373     TEST_F( IntrusiveFCQueue, member_elimination_single_mutex_multi_condvar )
 374     {
 375         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 376         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 377
 378         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 379             cds::intrusive::fcqueue::make_traits<
 380                 cds::intrusive::opt::disposer< disposer >
 381                 ,cds::opt::enable_elimination< true >
 382                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<2>>
 383             >::type
 384         > queue_type;
 385
 386         queue_type q;
 387         test( q );
 388     }
 389
 390     TEST_F( IntrusiveFCQueue, slist_base )
 391     {
 392         typedef base_hook_item< boost::intrusive::slist_base_hook<>> value_type;
 393         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>,
 394             cds::intrusive::fcqueue::make_traits<
 395                 cds::intrusive::opt::disposer< disposer >
 396             >::type
 397         > queue_type;
 398
 399         queue_type q;
 400         test( q );
 401     }
 402
 403     TEST_F( IntrusiveFCQueue, slist_base_elimination )
 404     {
 405         typedef base_hook_item< boost::intrusive::slist_base_hook<> > value_type;
 406         struct traits : public
 407             cds::intrusive::fcqueue::make_traits <
 408                 cds::intrusive::opt::disposer< disposer >
 409                 , cds::opt::enable_elimination < true >
 410                 , cds::opt::lock_type< std::mutex >
 411             > ::type
 412         {};
 413         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>, traits > queue_type;
 414
 415         queue_type q;
 416         test( q );
 417     }
 418
 419     TEST_F( IntrusiveFCQueue, slist_member )
 420     {
 421         typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
 422         typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
 423
 424         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
 425             cds::intrusive::fcqueue::make_traits<
 426                 cds::intrusive::opt::disposer< disposer >
 427             >::type
 428         > queue_type;
 429
 430         queue_type q;
 431         test( q );
 432     }
 433
 434     TEST_F( IntrusiveFCQueue, slist_member_elimination )
 435     {
 436         typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
 437         typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
 438
 439         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
 440             cds::intrusive::fcqueue::make_traits<
 441                 cds::intrusive::opt::disposer< disposer >
 442                 ,cds::opt::enable_elimination< true >
 443             >::type
 444         > queue_type;
 445
 446         queue_type q;
 447         test( q );
 448     }
 449
 450 } // namepace