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