test/unit/queue/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/container/fcqueue.h>
  33 #include <test/include/cds_test/fc_hevy_value.h>
  34
  35 #include <list>
  36
  37 namespace {
  38
  39     class FCQueue: public ::testing::Test
  40     {
  41     protected:
  42         template <class Queue>
  43         void test( Queue& q )
  44         {
  45             typedef typename Queue::value_type value_type;
  46             value_type it;
  47
  48             const int nSize = 100;
  49
  50             ASSERT_TRUE( q.empty());
  51             ASSERT_EQ( q.size(), 0u );
  52
  53             // enqueue/dequeue
  54             for ( int i = 0; i < nSize; ++i ) {
  55                 ASSERT_TRUE( q.enqueue( value_type(i)));
  56                 ASSERT_EQ( q.size(), static_cast<size_t>(i + 1));
  57             }
  58             ASSERT_FALSE( q.empty());
  59             ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
  60
  61             for ( int i = 0; i < nSize; ++i ) {
  62                 it = value_type( -1 );
  63                 ASSERT_TRUE( q.dequeue( it ));
  64                 ASSERT_EQ( it, value_type( i ));
  65                 ASSERT_EQ( q.size(), static_cast<size_t>( nSize - i - 1 ));
  66             }
  67             ASSERT_TRUE( q.empty());
  68             ASSERT_EQ( q.size(), 0u );
  69
  70             // push/pop
  71             for ( int i = 0; i < nSize; ++i ) {
  72                 ASSERT_TRUE( q.push( value_type(i)));
  73                 ASSERT_EQ( q.size(), static_cast<size_t>( i + 1 ));
  74             }
  75             ASSERT_FALSE( q.empty());
  76             ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
  77
  78             for ( int i = 0; i < nSize; ++i ) {
  79                 it = value_type( -1 );
  80                 ASSERT_TRUE( q.pop( it ));
  81                 ASSERT_EQ( it, value_type( i ));
  82                 ASSERT_EQ( q.size(), static_cast<size_t>( nSize - i - 1 ));
  83             }
  84             ASSERT_TRUE( q.empty());
  85             ASSERT_EQ( q.size(), 0u );
  86
  87             // clear
  88             for ( int i = 0; i < nSize; ++i ) {
  89                 ASSERT_TRUE( q.push( value_type( i )));
  90             }
  91             ASSERT_FALSE( q.empty());
  92             ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
  93
  94             q.clear();
  95             ASSERT_TRUE( q.empty());
  96             ASSERT_EQ( q.size(), 0u );
  97
  98             // pop from empty queue
  99             it = value_type( nSize * 2 );
 100             ASSERT_FALSE( q.pop( it ));
 101             ASSERT_EQ( it, static_cast<value_type>( nSize * 2 ));
 102             ASSERT_TRUE( q.empty());
 103             ASSERT_EQ( q.size(), 0u );
 104
 105             ASSERT_FALSE( q.dequeue( it ));
 106             ASSERT_EQ( it, static_cast<value_type>( nSize * 2 ));
 107             ASSERT_TRUE( q.empty());
 108             ASSERT_EQ( q.size(), 0u );
 109         }
 110
 111         template <class Queue>
 112         void test_string( Queue& q )
 113         {
 114             std::string str[3];
 115             str[0] = "one";
 116             str[1] = "two";
 117             str[2] = "three";
 118             const size_t nSize = sizeof( str ) / sizeof( str[0] );
 119
 120             // move push
 121             for ( size_t i = 0; i < nSize; ++i ) {
 122                 std::string s = str[i];
 123                 ASSERT_FALSE( s.empty());
 124                 ASSERT_TRUE( q.enqueue( std::move( s )));
 125                 ASSERT_FALSE( s.empty());
 126                 ASSERT_EQ( q.size(), i + 1 );
 127             }
 128             ASSERT_FALSE( q.empty());
 129             ASSERT_EQ( q.size(), nSize );
 130
 131             for ( size_t i = 0; i < nSize; ++i ) {
 132                 std::string s;
 133                 ASSERT_TRUE( q.pop( s ));
 134                 ASSERT_EQ( q.size(), nSize - i - 1 );
 135                 ASSERT_EQ( s, str[i] );
 136             }
 137             ASSERT_TRUE( q.empty());
 138             ASSERT_EQ( q.size(), 0u );
 139         }
 140
 141         template <class Queue>
 142         void test_heavy( Queue& q )
 143         {
 144             typedef typename Queue::value_type value_type;
 145             value_type it;
 146
 147             const int nSize = 100;
 148
 149             ASSERT_TRUE( q.empty() );
 150             ASSERT_EQ( q.size(), 0u );
 151
 152             // enqueue/dequeue
 153             for ( int i = 0; i < nSize; ++i ) {
 154                 ASSERT_TRUE( q.enqueue( value_type( i )));
 155                 ASSERT_EQ( q.size(), static_cast<size_t>( i + 1 ));
 156             }
 157             ASSERT_FALSE( q.empty() );
 158             ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
 159
 160             for ( int i = 0; i < nSize; ++i ) {
 161                 it.value = -1;
 162                 ASSERT_TRUE( q.dequeue( it ) );
 163                 ASSERT_EQ( it.value, i );
 164                 ASSERT_EQ( q.size(), static_cast<size_t>( nSize - i - 1 ));
 165             }
 166             ASSERT_TRUE( q.empty() );
 167             ASSERT_EQ( q.size(), 0u );
 168
 169             // push/pop
 170             for ( int i = 0; i < nSize; ++i ) {
 171                 ASSERT_TRUE( q.push( value_type( i )));
 172                 ASSERT_EQ( q.size(), static_cast<size_t>( i + 1 ));
 173             }
 174             ASSERT_FALSE( q.empty() );
 175             ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
 176
 177             for ( int i = 0; i < nSize; ++i ) {
 178                 it.value = -1;
 179                 ASSERT_TRUE( q.pop( it ) );
 180                 ASSERT_EQ( it.value, i );
 181                 ASSERT_EQ( q.size(), static_cast<size_t>( nSize - i - 1 ));
 182             }
 183             ASSERT_TRUE( q.empty() );
 184             ASSERT_EQ( q.size(), 0u );
 185
 186             // clear
 187             for ( int i = 0; i < nSize; ++i ) {
 188                 ASSERT_TRUE( q.push( value_type( i )));
 189             }
 190             ASSERT_FALSE( q.empty() );
 191             ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
 192
 193             q.clear();
 194             ASSERT_TRUE( q.empty() );
 195             ASSERT_EQ( q.size(), 0u );
 196
 197             // pop from empty queue
 198             it = value_type( nSize * 2 );
 199             ASSERT_FALSE( q.pop( it ) );
 200             ASSERT_EQ( it.value, nSize * 2 );
 201             ASSERT_TRUE( q.empty() );
 202             ASSERT_EQ( q.size(), 0u );
 203
 204             ASSERT_FALSE( q.dequeue( it ) );
 205             ASSERT_EQ( it.value, nSize * 2 );
 206             ASSERT_TRUE( q.empty() );
 207             ASSERT_EQ( q.size(), 0u );
 208         }
 209
 210     };
 211
 212     TEST_F( FCQueue, std_deque )
 213     {
 214         typedef cds::container::FCQueue<int> queue_type;
 215
 216         queue_type q;
 217         test( q );
 218     }
 219
 220     TEST_F( FCQueue, std_deque_move )
 221     {
 222         typedef cds::container::FCQueue<std::string> queue_type;
 223
 224         queue_type q;
 225         test_string( q );
 226     }
 227
 228     TEST_F( FCQueue, std_empty_wait_strategy )
 229     {
 230         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 231             cds::container::fcqueue::make_traits<
 232                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
 233             >::type
 234         > queue_type;
 235
 236         queue_type q;
 237         test( q );
 238     }
 239
 240     TEST_F( FCQueue, std_deque_heavy_value )
 241     {
 242         typedef fc_test::heavy_value<> ValueType;
 243         typedef cds::container::FCQueue<ValueType> queue_type;
 244
 245         queue_type q;
 246         test_heavy( q );
 247     }
 248
 249     TEST_F( FCQueue, std_empty_wait_strategy_heavy_value )
 250     {
 251         typedef fc_test::heavy_value<> ValueType;
 252         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 253             cds::container::fcqueue::make_traits<
 254                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
 255             >::type
 256         > queue_type;
 257
 258         queue_type q;
 259         test_heavy( q );
 260     }
 261
 262     TEST_F( FCQueue, std_single_mutex_single_condvar_heavy_value )
 263     {
 264         typedef fc_test::heavy_value<> ValueType;
 265         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 266             cds::container::fcqueue::make_traits<
 267                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<> >
 268             >::type
 269         > queue_type;
 270
 271         queue_type q;
 272         test_heavy( q );
 273     }
 274
 275     TEST_F( FCQueue, std_single_mutex_multi_condvar_heavy_value )
 276     {
 277         typedef fc_test::heavy_value<> ValueType;
 278         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 279             cds::container::fcqueue::make_traits<
 280                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<> >
 281             >::type
 282         > queue_type;
 283
 284         queue_type q;
 285         test_heavy( q );
 286     }
 287
 288     TEST_F( FCQueue, std_multi_mutex_multi_condvar_heavy_value )
 289     {
 290         typedef fc_test::heavy_value<> ValueType;
 291         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 292             cds::container::fcqueue::make_traits<
 293                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<> >
 294             >::type
 295         > queue_type;
 296
 297         queue_type q;
 298         test_heavy( q );
 299     }
 300
 301     TEST_F( FCQueue, std_single_mutex_single_condvar )
 302     {
 303         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 304             cds::container::fcqueue::make_traits<
 305                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<>>
 306             >::type
 307         > queue_type;
 308
 309         queue_type q;
 310         test( q );
 311     }
 312
 313     TEST_F( FCQueue, std_deque_elimination )
 314     {
 315         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 316             cds::container::fcqueue::make_traits<
 317                 cds::opt::enable_elimination< true >
 318             >::type
 319         > queue_type;
 320
 321         queue_type q;
 322         test( q );
 323     }
 324
 325     TEST_F( FCQueue, std_deque_elimination_single_mutex_multi_condvar )
 326     {
 327         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 328             cds::container::fcqueue::make_traits<
 329                 cds::opt::enable_elimination< true >
 330                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<2>>
 331             >::type
 332         > queue_type;
 333
 334         queue_type q;
 335         test( q );
 336     }
 337
 338     TEST_F( FCQueue, std_deque_elimination_move )
 339     {
 340         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::deque<std::string>>,
 341             cds::container::fcqueue::make_traits<
 342                 cds::opt::enable_elimination< true >
 343             >::type
 344         > queue_type;
 345
 346         queue_type q;
 347         test_string( q );
 348     }
 349
 350     TEST_F( FCQueue, std_deque_elimination_move_multi_mutex_multi_condvar )
 351     {
 352         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::deque<std::string>>,
 353             cds::container::fcqueue::make_traits<
 354                 cds::opt::enable_elimination< true >
 355                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<>>
 356             >::type
 357         > queue_type;
 358
 359         queue_type q;
 360         test_string( q );
 361     }
 362
 363     TEST_F( FCQueue, std_deque_mutex )
 364     {
 365         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 366             cds::container::fcqueue::make_traits<
 367                 cds::opt::lock_type< std::mutex >
 368             >::type
 369         > queue_type;
 370
 371         queue_type q;
 372         test( q );
 373     }
 374
 375     TEST_F( FCQueue, std_list )
 376     {
 377         typedef cds::container::FCQueue<int, std::queue< int, std::list<int>>> queue_type;
 378
 379         queue_type q;
 380         test( q );
 381     }
 382
 383     TEST_F( FCQueue, std_list_move )
 384     {
 385         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::list<std::string>>> queue_type;
 386
 387         queue_type q;
 388         test_string( q );
 389     }
 390
 391     TEST_F( FCQueue, std_list_empty_wait_strategy )
 392     {
 393         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 394             cds::container::fcqueue::make_traits<
 395                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
 396             >::type
 397         > queue_type;
 398
 399         queue_type q;
 400         test( q );
 401     }
 402
 403     TEST_F( FCQueue, std_list_single_mutex_single_condvar )
 404     {
 405         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 406             cds::container::fcqueue::make_traits<
 407                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<5>>
 408             >::type
 409         > queue_type;
 410
 411         queue_type q;
 412         test( q );
 413     }
 414
 415     TEST_F( FCQueue, std_list_elimination )
 416     {
 417         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 418             cds::container::fcqueue::make_traits<
 419                 cds::opt::enable_elimination< true >
 420             >::type
 421         > queue_type;
 422
 423         queue_type q;
 424         test( q );
 425     }
 426
 427     TEST_F( FCQueue, std_list_elimination_multi_mutex_multi_condvar )
 428     {
 429         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 430             cds::container::fcqueue::make_traits<
 431                 cds::opt::enable_elimination< true >
 432                 ,cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<5>>
 433             >::type
 434         > queue_type;
 435
 436         queue_type q;
 437         test( q );
 438     }
 439
 440     TEST_F( FCQueue, std_list_elimination_move )
 441     {
 442         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::list<std::string> >,
 443             cds::container::fcqueue::make_traits<
 444             cds::opt::enable_elimination< true >
 445             >::type
 446         > queue_type;
 447
 448         queue_type q;
 449         test_string( q );
 450     }
 451
 452     TEST_F( FCQueue, std_list_mutex )
 453     {
 454         typedef cds::container::FCQueue<int, std::queue<int, std::list<int> >,
 455             cds::container::fcqueue::make_traits<
 456                 cds::opt::lock_type< std::mutex >
 457             >::type
 458         > queue_type;
 459
 460         queue_type q;
 461         test( q );
 462     }
 463
 464 } // namespace