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