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 <cds_test/ext_gtest.h>
32 #include <cds/intrusive/fcqueue.h>
35 #include <boost/intrusive/slist.hpp>
39 class IntrusiveFCQueue : public ::testing::Test
42 template <typename Hook>
43 struct base_hook_item : public Hook
53 template <typename Hook>
54 struct member_hook_item
69 void operator ()( T * p )
76 template <typename Queue>
79 typedef typename Queue::value_type value_type;
80 typedef typename Queue::container_type underlying_queue_type;
82 size_t const nSize = 100;
84 std::vector<value_type> arr;
87 for ( size_t i = 0; i < nSize; ++i ) {
88 arr[i].nVal = static_cast<int>( i );
89 total_sum += static_cast<int>( i );
92 ASSERT_TRUE( q.empty());
93 ASSERT_EQ( q.size(), 0u );
95 // pop from empty queue
97 ASSERT_TRUE( pv == nullptr );
98 ASSERT_TRUE( q.empty());
99 ASSERT_EQ( q.size(), 0u );
102 ASSERT_TRUE( pv == nullptr );
103 ASSERT_TRUE( q.empty());
104 ASSERT_EQ( q.size(), 0u );
107 for ( size_t i = 0; i < nSize; ++i ) {
112 ASSERT_FALSE( q.empty());
113 ASSERT_EQ( q.size(), i + 1 );
117 q.apply( [&sum]( underlying_queue_type& queue )
119 for ( auto const& el : queue )
122 EXPECT_EQ( sum, total_sum );
125 for ( size_t i = 0; i < nSize; ++i ) {
126 ASSERT_FALSE( q.empty());
127 ASSERT_EQ( q.size(), nSize - i );
132 ASSERT_FALSE( pv == nullptr );
133 ASSERT_EQ( pv->nVal, static_cast<int>(i));
135 ASSERT_TRUE( q.empty());
136 ASSERT_EQ( q.size(), 0u );
138 // pop() doesn't call disposer
139 for ( size_t i = 0; i < nSize; ++i ) {
140 ASSERT_EQ( arr[i].nDisposeCount, 0 );
143 // clear with disposer
144 for ( size_t i = 0; i < nSize; ++i )
147 ASSERT_FALSE( q.empty());
148 ASSERT_EQ( q.size(), nSize );
151 ASSERT_TRUE( q.empty());
152 ASSERT_EQ( q.size(), 0u );
154 for ( size_t i = 0; i < nSize; ++i ) {
155 ASSERT_EQ( arr[i].nDisposeCount, 1 );
158 // clear without disposer
159 for ( size_t i = 0; i < nSize; ++i )
163 ASSERT_TRUE( q.empty());
164 ASSERT_EQ( q.size(), 0u );
166 for ( size_t i = 0; i < nSize; ++i ) {
167 ASSERT_EQ( arr[i].nDisposeCount, 1 );
172 TEST_F( IntrusiveFCQueue, base )
174 typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
175 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >,
176 cds::intrusive::fcqueue::make_traits<
177 cds::intrusive::opt::disposer< disposer >
185 TEST_F( IntrusiveFCQueue, base_empty_wait_strategy )
187 typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
188 struct traits: public cds::intrusive::fcqueue::traits
190 typedef IntrusiveFCQueue::disposer disposer;
191 typedef cds::algo::flat_combining::wait_strategy::empty wait_strategy;
192 typedef cds::intrusive::fcqueue::stat<> stat;
194 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
200 TEST_F( IntrusiveFCQueue, base_single_mutex_single_condvar )
202 typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
203 struct traits: public cds::intrusive::fcqueue::traits
205 typedef IntrusiveFCQueue::disposer disposer;
206 typedef cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<> wait_strategy;
207 typedef cds::intrusive::fcqueue::stat<> stat;
209 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
215 TEST_F( IntrusiveFCQueue, base_mutex )
217 typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
218 struct traits : public cds::intrusive::fcqueue::traits
220 typedef IntrusiveFCQueue::disposer disposer;
221 typedef std::mutex lock_type;
222 typedef cds::intrusive::fcqueue::stat<> stat;
224 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
230 TEST_F( IntrusiveFCQueue, base_mutex_single_mutex_multi_condvar )
232 typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
233 struct traits: public cds::intrusive::fcqueue::traits
235 typedef IntrusiveFCQueue::disposer disposer;
236 typedef std::mutex lock_type;
237 typedef cds::intrusive::fcqueue::stat<> stat;
238 typedef cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<> wait_strategy;
240 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
246 TEST_F( IntrusiveFCQueue, base_elimination )
248 typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
249 struct traits : public
250 cds::intrusive::fcqueue::make_traits <
251 cds::intrusive::opt::disposer< disposer >
252 , cds::opt::enable_elimination < true >
255 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
261 TEST_F( IntrusiveFCQueue, base_elimination_multi_mutex_multi_condvar )
263 typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
264 struct traits: public
265 cds::intrusive::fcqueue::make_traits <
266 cds::intrusive::opt::disposer< disposer >
267 , cds::opt::enable_elimination < true >
268 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<>>
271 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
277 TEST_F( IntrusiveFCQueue, member )
279 typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
280 typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
282 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
283 cds::intrusive::fcqueue::make_traits<
284 cds::intrusive::opt::disposer< disposer >
292 TEST_F( IntrusiveFCQueue, member_mutex )
294 typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
295 typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
297 struct traits : public cds::intrusive::fcqueue::traits
299 typedef IntrusiveFCQueue::disposer disposer;
300 typedef std::mutex lock_type;
301 typedef cds::intrusive::fcqueue::stat<> stat;
303 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >, traits > queue_type;
309 TEST_F( IntrusiveFCQueue, member_empty_wait_strategy )
311 typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
312 typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
314 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
315 cds::intrusive::fcqueue::make_traits<
316 cds::intrusive::opt::disposer< disposer >
317 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::empty >
325 TEST_F( IntrusiveFCQueue, member_single_mutex_single_condvar )
327 typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
328 typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
330 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
331 cds::intrusive::fcqueue::make_traits<
332 cds::intrusive::opt::disposer< disposer >
333 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_single_condvar<2>>
341 TEST_F( IntrusiveFCQueue, member_multi_mutex_multi_condvar )
343 typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
344 typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
346 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
347 cds::intrusive::fcqueue::make_traits<
348 cds::intrusive::opt::disposer< disposer >
349 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::multi_mutex_multi_condvar<>>
357 TEST_F( IntrusiveFCQueue, member_elimination )
359 typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
360 typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
362 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
363 cds::intrusive::fcqueue::make_traits<
364 cds::intrusive::opt::disposer< disposer >
365 ,cds::opt::enable_elimination< true >
373 TEST_F( IntrusiveFCQueue, member_elimination_single_mutex_multi_condvar )
375 typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
376 typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
378 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
379 cds::intrusive::fcqueue::make_traits<
380 cds::intrusive::opt::disposer< disposer >
381 ,cds::opt::enable_elimination< true >
382 , cds::opt::wait_strategy< cds::algo::flat_combining::wait_strategy::single_mutex_multi_condvar<2>>
390 TEST_F( IntrusiveFCQueue, slist_base )
392 typedef base_hook_item< boost::intrusive::slist_base_hook<>> value_type;
393 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>,
394 cds::intrusive::fcqueue::make_traits<
395 cds::intrusive::opt::disposer< disposer >
403 TEST_F( IntrusiveFCQueue, slist_base_elimination )
405 typedef base_hook_item< boost::intrusive::slist_base_hook<> > value_type;
406 struct traits : public
407 cds::intrusive::fcqueue::make_traits <
408 cds::intrusive::opt::disposer< disposer >
409 , cds::opt::enable_elimination < true >
410 , cds::opt::lock_type< std::mutex >
413 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>, traits > queue_type;
419 TEST_F( IntrusiveFCQueue, slist_member )
421 typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
422 typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
424 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
425 cds::intrusive::fcqueue::make_traits<
426 cds::intrusive::opt::disposer< disposer >
434 TEST_F( IntrusiveFCQueue, slist_member_elimination )
436 typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
437 typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
439 typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
440 cds::intrusive::fcqueue::make_traits<
441 cds::intrusive::opt::disposer< disposer >
442 ,cds::opt::enable_elimination< true >