2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #include <gtest/gtest.h>
32 #include <cds/container/fcqueue.h>
33 #include <test/include/cds_test/fc_hevy_value.h>
39 class FCQueue: public ::testing::Test
42 template <class Queue>
45 typedef typename Queue::value_type value_type;
48 const int nSize = 100;
50 ASSERT_TRUE( q.empty());
51 ASSERT_EQ( q.size(), 0u );
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));
58 ASSERT_FALSE( q.empty());
59 ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
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 ));
67 ASSERT_TRUE( q.empty());
68 ASSERT_EQ( q.size(), 0u );
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 ));
75 ASSERT_FALSE( q.empty());
76 ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
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 ));
84 ASSERT_TRUE( q.empty());
85 ASSERT_EQ( q.size(), 0u );
88 for ( int i = 0; i < nSize; ++i ) {
89 ASSERT_TRUE( q.push( value_type( i )));
91 ASSERT_FALSE( q.empty());
92 ASSERT_EQ( q.size(), static_cast<size_t>( nSize ));
95 ASSERT_TRUE( q.empty());
96 ASSERT_EQ( q.size(), 0u );
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 );
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 );
111 template <class Queue>
112 void test_string( Queue& q )
118 const size_t nSize = sizeof( str ) / sizeof( str[0] );
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 );
128 ASSERT_FALSE( q.empty());
129 ASSERT_EQ( q.size(), nSize );
131 for ( size_t i = 0; i < nSize; ++i ) {
133 ASSERT_TRUE( q.pop( s ));
134 ASSERT_EQ( q.size(), nSize - i - 1 );
135 ASSERT_EQ( s, str[i] );
137 ASSERT_TRUE( q.empty());
138 ASSERT_EQ( q.size(), 0u );
141 template <class Queue>
142 void test_heavy( Queue& q )
144 typedef typename Queue::value_type value_type;
147 const int nSize = 100;
149 ASSERT_TRUE( q.empty() );
150 ASSERT_EQ( q.size(), 0u );
153 for ( int i = 0; i < nSize; ++i ) {
154 ASSERT_TRUE( q.enqueue( value_type( i )));
155 ASSERT_EQ( q.size(), i + 1 );
157 ASSERT_FALSE( q.empty() );
158 ASSERT_EQ( q.size(), nSize );
160 for ( int i = 0; i < nSize; ++i ) {
162 ASSERT_TRUE( q.dequeue( it ) );
163 ASSERT_EQ( it.value, i );
164 ASSERT_EQ( q.size(), nSize - i - 1 );
166 ASSERT_TRUE( q.empty() );
167 ASSERT_EQ( q.size(), 0u );
170 for ( int i = 0; i < nSize; ++i ) {
171 ASSERT_TRUE( q.push( value_type( i )));
172 ASSERT_EQ( q.size(), i + 1 );
174 ASSERT_FALSE( q.empty() );
175 ASSERT_EQ( q.size(), nSize );
177 for ( int i = 0; i < nSize; ++i ) {
179 ASSERT_TRUE( q.pop( it ) );
180 ASSERT_EQ( it.value, i );
181 ASSERT_EQ( q.size(), nSize - i - 1 );
183 ASSERT_TRUE( q.empty() );
184 ASSERT_EQ( q.size(), 0u );
187 for ( int i = 0; i < nSize; ++i ) {
188 ASSERT_TRUE( q.push( value_type( i )));
190 ASSERT_FALSE( q.empty() );
191 ASSERT_EQ( q.size(), nSize );
194 ASSERT_TRUE( q.empty() );
195 ASSERT_EQ( q.size(), 0u );
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 );
204 ASSERT_FALSE( q.dequeue( it ) );
205 ASSERT_EQ( it.value, nSize * 2 );
206 ASSERT_TRUE( q.empty() );
207 ASSERT_EQ( q.size(), 0u );
212 TEST_F( FCQueue, std_deque )
214 typedef cds::container::FCQueue<int> queue_type;
220 TEST_F( FCQueue, std_deque_move )
222 typedef cds::container::FCQueue<std::string> queue_type;
228 TEST_F( FCQueue, std_empty_wait_strategy )
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 >
240 TEST_F( FCQueue, std_deque_heavy_value )
242 typedef fc_test::heavy_value<> ValueType;
243 typedef cds::container::FCQueue<ValueType> queue_type;
249 TEST_F( FCQueue, std_empty_wait_strategy_heavy_value )
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 >
262 TEST_F( FCQueue, std_single_mutex_single_condvar_heavy_value )
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<> >
275 TEST_F( FCQueue, std_single_mutex_multi_condvar_heavy_value )
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<> >
288 TEST_F( FCQueue, std_multi_mutex_multi_condvar_heavy_value )
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<> >
301 TEST_F( FCQueue, std_single_mutex_single_condvar )
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<>>
313 TEST_F( FCQueue, std_deque_elimination )
315 typedef cds::container::FCQueue<int, std::queue< int, std::deque<int>>,
316 cds::container::fcqueue::make_traits<
317 cds::opt::enable_elimination< true >
325 TEST_F( FCQueue, std_deque_elimination_single_mutex_multi_condvar )
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>>
338 TEST_F( FCQueue, std_deque_elimination_move )
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 >
350 TEST_F( FCQueue, std_deque_elimination_move_multi_mutex_multi_condvar )
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<>>
363 TEST_F( FCQueue, std_deque_mutex )
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 >
375 TEST_F( FCQueue, std_list )
377 typedef cds::container::FCQueue<int, std::queue< int, std::list<int>>> queue_type;
383 TEST_F( FCQueue, std_list_move )
385 typedef cds::container::FCQueue<std::string, std::queue< std::string, std::list<std::string>>> queue_type;
391 TEST_F( FCQueue, std_list_empty_wait_strategy )
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 >
403 TEST_F( FCQueue, std_list_single_mutex_single_condvar )
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>>
415 TEST_F( FCQueue, std_list_elimination )
417 typedef cds::container::FCQueue<int, std::queue< int, std::list<int> >,
418 cds::container::fcqueue::make_traits<
419 cds::opt::enable_elimination< true >
427 TEST_F( FCQueue, std_list_elimination_multi_mutex_multi_condvar )
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>>
440 TEST_F( FCQueue, std_list_elimination_move )
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 >
452 TEST_F( FCQueue, std_list_mutex )
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 >