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-2016
   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/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 size_t nSize = 100;
  49
  50             ASSERT_TRUE( q.empty());
  51             ASSERT_EQ( q.size(), 0u );
  52
  53             // enqueue/dequeue
  54             for ( size_t i = 0; i < nSize; ++i ) {
  55                 ASSERT_TRUE( q.enqueue( static_cast<value_type>(i)));
  56                 ASSERT_EQ( q.size(), i + 1 );
  57             }
  58             ASSERT_FALSE( q.empty());
  59             ASSERT_EQ( q.size(), nSize );
  60
  61             for ( size_t i = 0; i < nSize; ++i ) {
  62                 it = -1;
  63                 ASSERT_TRUE( q.dequeue( it ));
  64                 ASSERT_EQ( it, static_cast<value_type>( i ));
  65                 ASSERT_EQ( q.size(), nSize - i - 1 );
  66             }
  67             ASSERT_TRUE( q.empty());
  68             ASSERT_EQ( q.size(), 0u );
  69
  70             // push/pop
  71             for ( size_t i = 0; i < nSize; ++i ) {
  72                 ASSERT_TRUE( q.push( static_cast<value_type>(i)));
  73                 ASSERT_EQ( q.size(), i + 1 );
  74             }
  75             ASSERT_FALSE( q.empty());
  76             ASSERT_EQ( q.size(), nSize );
  77
  78             for ( size_t i = 0; i < nSize; ++i ) {
  79                 it = -1;
  80                 ASSERT_TRUE( q.pop( it ));
  81                 ASSERT_EQ( it, static_cast<value_type>( i ));
  82                 ASSERT_EQ( q.size(), nSize - i - 1 );
  83             }
  84             ASSERT_TRUE( q.empty());
  85             ASSERT_EQ( q.size(), 0u );
  86
  87             // clear
  88             for ( size_t i = 0; i < nSize; ++i ) {
  89                 ASSERT_TRUE( q.push( static_cast<value_type>( i )));
  90             }
  91             ASSERT_FALSE( q.empty());
  92             ASSERT_EQ( q.size(), nSize );
  93
  94             q.clear();
  95             ASSERT_TRUE( q.empty());
  96             ASSERT_EQ( q.size(), 0u );
  97
  98             // pop from empty queue
  99             it = 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
 142     TEST_F( FCQueue, std_deque )
 143     {
 144         typedef cds::container::FCQueue<int> queue_type;
 145
 146         queue_type q;
 147         test( q );
 148     }
 149
 150     TEST_F( FCQueue, std_deque_move )
 151     {
 152         typedef cds::container::FCQueue<std::string> queue_type;
 153
 154         queue_type q;
 155         test_string( q );
 156     }
 157
 158     TEST_F( FCQueue, std_empty_wait_strategy )
 159     {
 160         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 161             cds::container::fcqueue::make_traits<
 162                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
 163             >::type
 164         > queue_type;
 165
 166         queue_type q;
 167         test( q );
 168     }
 169
 170     TEST_F( FCQueue, std_deque_heavy_value )
 171     {
 172         typedef fc_test::heavy_value<> ValueType;
 173         typedef cds::container::FCQueue<ValueType> queue_type;
 174
 175         queue_type q;
 176         test( q );
 177     }
 178
 179     TEST_F( FCQueue, std_empty_wait_strategy_heavy_value )
 180     {
 181         typedef fc_test::heavy_value<> ValueType;
 182         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 183             cds::container::fcqueue::make_traits<
 184                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
 185             >::type
 186         > queue_type;
 187
 188         queue_type q;
 189         test( q );
 190     }
 191
 192     TEST_F( FCQueue, std_single_mutex_single_condvar_heavy_value )
 193     {
 194         typedef fc_test::heavy_value<> ValueType;
 195         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 196             cds::container::fcqueue::make_traits<
 197                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<> >
 198             >::type
 199         > queue_type;
 200
 201         queue_type q;
 202         test( q );
 203     }
 204
 205     TEST_F( FCQueue, std_single_mutex_multi_condvar_heavy_value )
 206     {
 207         typedef fc_test::heavy_value<> ValueType;
 208         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 209             cds::container::fcqueue::make_traits<
 210                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<> >
 211             >::type
 212         > queue_type;
 213
 214         queue_type q;
 215         test( q );
 216     }
 217
 218     TEST_F( FCQueue, std_multi_mutex_multi_condvar_heavy_value )
 219     {
 220         typedef fc_test::heavy_value<> ValueType;
 221         typedef cds::container::FCQueue<ValueType, std::queue< ValueType, std::deque<ValueType>>,
 222             cds::container::fcqueue::make_traits<
 223                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<> >
 224             >::type
 225         > queue_type;
 226
 227         queue_type q;
 228         test( q );
 229     }
 230
 231     TEST_F( FCQueue, std_single_mutex_single_condvar )
 232     {
 233         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 234             cds::container::fcqueue::make_traits<
 235                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<>>
 236             >::type
 237         > queue_type;
 238
 239         queue_type q;
 240         test( q );
 241     }
 242
 243     TEST_F( FCQueue, std_deque_elimination )
 244     {
 245         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 246             cds::container::fcqueue::make_traits<
 247                 cds::opt::enable_elimination< true >
 248             >::type
 249         > queue_type;
 250
 251         queue_type q;
 252         test( q );
 253     }
 254
 255     TEST_F( FCQueue, std_deque_elimination_single_mutex_multi_condvar )
 256     {
 257         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 258             cds::container::fcqueue::make_traits<
 259                 cds::opt::enable_elimination< true >
 260                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<2>>
 261             >::type
 262         > queue_type;
 263
 264         queue_type q;
 265         test( q );
 266     }
 267
 268     TEST_F( FCQueue, std_deque_elimination_move )
 269     {
 270         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::deque<std::string>>,
 271             cds::container::fcqueue::make_traits<
 272                 cds::opt::enable_elimination< true >
 273             >::type
 274         > queue_type;
 275
 276         queue_type q;
 277         test_string( q );
 278     }
 279
 280     TEST_F( FCQueue, std_deque_elimination_move_multi_mutex_multi_condvar )
 281     {
 282         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::deque<std::string>>,
 283             cds::container::fcqueue::make_traits<
 284                 cds::opt::enable_elimination< true >
 285                 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<>>
 286             >::type
 287         > queue_type;
 288
 289         queue_type q;
 290         test_string( q );
 291     }
 292
 293     TEST_F( FCQueue, std_deque_mutex )
 294     {
 295         typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
 296             cds::container::fcqueue::make_traits<
 297                 cds::opt::lock_type< std::mutex >
 298             >::type
 299         > queue_type;
 300
 301         queue_type q;
 302         test( q );
 303     }
 304
 305     TEST_F( FCQueue, std_list )
 306     {
 307         typedef cds::container::FCQueue<int, std::queue< int, std::list<int>>> queue_type;
 308
 309         queue_type q;
 310         test( q );
 311     }
 312
 313     TEST_F( FCQueue, std_list_move )
 314     {
 315         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::list<std::string>>> queue_type;
 316
 317         queue_type q;
 318         test_string( q );
 319     }
 320
 321     TEST_F( FCQueue, std_list_empty_wait_strategy )
 322     {
 323         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 324             cds::container::fcqueue::make_traits<
 325                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
 326             >::type
 327         > queue_type;
 328
 329         queue_type q;
 330         test( q );
 331     }
 332
 333     TEST_F( FCQueue, std_list_single_mutex_single_condvar )
 334     {
 335         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 336             cds::container::fcqueue::make_traits<
 337                 cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<5>>
 338             >::type
 339         > queue_type;
 340
 341         queue_type q;
 342         test( q );
 343     }
 344
 345     TEST_F( FCQueue, std_list_elimination )
 346     {
 347         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 348             cds::container::fcqueue::make_traits<
 349                 cds::opt::enable_elimination< true >
 350             >::type
 351         > queue_type;
 352
 353         queue_type q;
 354         test( q );
 355     }
 356
 357     TEST_F( FCQueue, std_list_elimination_multi_mutex_multi_condvar )
 358     {
 359         typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
 360             cds::container::fcqueue::make_traits<
 361                 cds::opt::enable_elimination< true >
 362                 ,cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<5>>
 363             >::type
 364         > queue_type;
 365
 366         queue_type q;
 367         test( q );
 368     }
 369
 370     TEST_F( FCQueue, std_list_elimination_move )
 371     {
 372         typedef cds::container::FCQueue<std::string, std::queue< std::string, std::list<std::string> >,
 373             cds::container::fcqueue::make_traits<
 374             cds::opt::enable_elimination< true >
 375             >::type
 376         > queue_type;
 377
 378         queue_type q;
 379         test_string( q );
 380     }
 381
 382     TEST_F( FCQueue, std_list_mutex )
 383     {
 384         typedef cds::container::FCQueue<int, std::queue<int, std::list<int> >,
 385             cds::container::fcqueue::make_traits<
 386                 cds::opt::lock_type< std::mutex >
 387             >::type
 388         > queue_type;
 389
 390         queue_type q;
 391         test( q );
 392     }
 393
 394 } // namespace