2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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.
30 #ifndef CDSUNIT_LIST_TEST_INTRUSIVE_LIST_NOGC_H
31 #define CDSUNIT_LIST_TEST_INTRUSIVE_LIST_NOGC_H
33 #include <cds_test/check_size.h>
34 #include <cds_test/fixture.h>
38 class intrusive_list_nogc : public fixture
43 int nUpdateExistsCall;
49 , nUpdateExistsCall( 0 )
59 stat& operator =( const stat& s )
61 memcpy( this, &s, sizeof( s ) );
66 template <typename Node>
67 struct base_item : public Node
77 base_item( int key, int val )
83 base_item( const base_item& v )
89 const int& key() const
94 base_item& operator=( base_item const& src )
101 base_item& operator=( base_item&& src )
109 template <typename Node>
120 member_item( int key, int val )
126 member_item( const member_item& v )
132 const int& key() const
137 member_item& operator =( member_item const& src )
144 member_item& operator=( member_item&& src )
152 template <typename T>
155 bool operator ()( const T& v1, const T& v2 ) const
157 return v1.key() < v2.key();
160 template <typename Q>
161 bool operator ()( const T& v1, const Q& v2 ) const
163 return v1.key() < v2;
166 template <typename Q>
167 bool operator ()( const Q& v1, const T& v2 ) const
169 return v1 < v2.key();
182 template <typename T, typename Q>
183 bool operator()( T const& i1, Q const& i2 ) const
185 return i1.nKey < i2.nKey;
189 template <typename T>
191 int operator ()( const T& v1, const T& v2 ) const
193 if ( v1.key() < v2.key() )
195 return v1.key() > v2.key() ? 1 : 0;
198 template <typename Q>
199 int operator ()( const T& v1, const Q& v2 ) const
203 return v1.key() > v2 ? 1 : 0;
206 template <typename Q>
207 int operator ()( const Q& v1, const T& v2 ) const
211 return v1 > v2.key() ? 1 : 0;
217 template <typename T>
218 void operator ()( T * p )
220 ++p->s.nDisposeCount;
224 struct mock_disposer2
226 template <typename T>
227 void operator ()( T * p )
229 p->s.nDisposeCount += 10;
233 struct update_functor
235 template <typename T>
236 void operator ()( bool bNew, T& item, T& /*val*/ )
239 ++item.s.nUpdateNewCall;
241 ++item.s.nUpdateExistsCall;
247 template <typename T, typename Q>
248 void operator ()( T& item, Q& /*val*/ )
256 template <typename T>
257 void operator()( T const& item )
264 template <typename List>
265 void test_common( List& l )
267 // Precondition: list is empty
268 // Postcondition: list is empty
270 static const size_t nSize = 20;
271 typedef typename List::value_type value_type;
272 value_type arr[ nSize ];
274 for ( size_t i = 0; i < nSize; ++i ) {
275 arr[i].nKey = static_cast<int>( i );
276 arr[i].nVal = arr[i].nKey * 10;
278 shuffle( arr, arr + nSize );
280 ASSERT_TRUE( l.empty() );
281 ASSERT_CONTAINER_SIZE( l, 0 );
284 for ( auto& i : arr ) {
285 EXPECT_FALSE( l.contains( i.nKey ));
286 EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less()));
287 EXPECT_FALSE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
288 EXPECT_EQ( i.s.nFindCall, 0 );
289 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
290 EXPECT_EQ( i.s.nFindCall, 0 );
292 EXPECT_TRUE( l.insert( i ));
294 EXPECT_TRUE( l.contains( i.nKey ));
295 EXPECT_TRUE( l.contains( i ));
296 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
297 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
298 EXPECT_EQ( i.s.nFindCall, 1 );
299 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
300 EXPECT_EQ( i.s.nFindCall, 2 );
301 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
302 EXPECT_EQ( i.s.nFindCall, 3 );
304 EXPECT_FALSE( l.insert( i ) );
305 ASSERT_FALSE( l.empty() );
307 ASSERT_CONTAINER_SIZE( l, nSize );
310 for ( auto const& i : arr ) {
311 EXPECT_TRUE( l.contains( i.nKey ));
312 EXPECT_TRUE( l.contains( i ));
313 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
314 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
315 EXPECT_EQ( i.s.nFindCall, 4 );
316 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
317 EXPECT_EQ( i.s.nFindCall, 5 );
318 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
319 EXPECT_EQ( i.s.nFindCall, 6 );
321 ASSERT_FALSE( l.empty() );
322 ASSERT_CONTAINER_SIZE( l, nSize );
324 // update existing test
325 for ( auto& i : arr ) {
326 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
327 std::pair<bool, bool> ret = l.update( i, update_functor() );
328 EXPECT_TRUE( ret.first );
329 EXPECT_FALSE( ret.second );
330 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
332 ret = l.update( i, []( bool bNew, value_type& i, value_type& arg ) {
333 EXPECT_FALSE( bNew );
334 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
335 EXPECT_TRUE( &i == &arg );
336 ++i.s.nUpdateExistsCall;
338 EXPECT_TRUE( ret.first );
339 EXPECT_FALSE( ret.second );
340 EXPECT_EQ( i.s.nUpdateExistsCall, 2 );
345 EXPECT_TRUE( l.empty() );
346 EXPECT_CONTAINER_SIZE( l, 0 );
348 // Apply retired pointer to clean links
349 List::gc::force_dispose();
350 for ( auto const& i : arr ) {
351 EXPECT_EQ( i.s.nDisposeCount, 1 );
352 EXPECT_FALSE( l.contains( i ) );
356 for ( auto& i : arr ) {
357 std::pair<bool, bool> ret = l.update( i, update_functor(), false );
358 EXPECT_FALSE( ret.first );
359 EXPECT_FALSE( ret.second );
361 ret = l.update( i, update_functor(), true );
362 EXPECT_TRUE( ret.first );
363 EXPECT_TRUE( ret.second );
364 EXPECT_EQ( i.s.nUpdateNewCall, 1 );
367 EXPECT_FALSE( l.empty() );
368 EXPECT_CONTAINER_SIZE( l, nSize );
370 l.clear( mock_disposer2());
372 EXPECT_TRUE( l.empty() );
373 EXPECT_CONTAINER_SIZE( l, 0 );
375 // Apply retired pointer to clean links
376 List::gc::force_dispose();
377 for ( auto const& i : arr ) {
378 EXPECT_EQ( i.s.nDisposeCount, 11 );
379 EXPECT_FALSE( l.contains( i ));
382 // Iterators on empty list
385 auto itEnd = l.end();
386 auto cit = l.cbegin();
387 auto citEnd = l.cend();
389 EXPECT_TRUE( it == itEnd );
390 EXPECT_TRUE( it == cit );
391 EXPECT_TRUE( cit == citEnd );
396 EXPECT_TRUE( it == itEnd );
397 EXPECT_TRUE( it == cit );
398 EXPECT_TRUE( cit == citEnd );
402 template <typename List>
403 void test_ordered_iterator( List& l )
405 // Precondition: list is empty
406 // Postcondition: list is empty
408 static const size_t nSize = 20;
409 typedef typename List::value_type value_type;
410 value_type arr[nSize];
412 for ( size_t i = 0; i < nSize; ++i ) {
413 arr[i].nKey = static_cast<int>(i);
414 arr[i].nVal = arr[i].nKey * 10;
416 shuffle( arr, arr + nSize );
418 ASSERT_TRUE( l.empty() );
419 ASSERT_CONTAINER_SIZE( l, 0 );
421 for ( auto& i : arr )
422 EXPECT_TRUE( l.insert( i ) );
425 for ( auto it = l.begin(); it != l.end(); ++it ) {
426 EXPECT_EQ( it->nKey, key );
427 EXPECT_EQ( (*it).nKey, key );
432 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
433 EXPECT_EQ( it->nKey, key );
434 EXPECT_EQ( (*it).nKey, key );
439 List::gc::force_dispose();
440 for ( auto const& i : arr ) {
441 EXPECT_EQ( i.s.nDisposeCount, 1 );
442 EXPECT_FALSE( l.contains( i ) );
446 template <typename List>
447 void test_unordered_iterator( List& l )
449 // Precondition: list is empty
450 // Postcondition: list is empty
452 static const size_t nSize = 20;
453 typedef typename List::value_type value_type;
454 value_type arr[nSize];
456 for ( size_t i = 0; i < nSize; ++i ) {
457 arr[i].nKey = static_cast<int>(i);
458 arr[i].nVal = arr[i].nKey * 10;
460 shuffle( arr, arr + nSize );
462 ASSERT_TRUE( l.empty() );
463 ASSERT_CONTAINER_SIZE( l, 0 );
465 for ( auto& i : arr )
466 EXPECT_TRUE( l.insert( i ) );
469 for ( auto it = l.begin(); it != l.end(); ++it, ++idx ) {
470 ASSERT_LT( idx, nSize );
471 EXPECT_EQ( it->nKey, arr[idx].nKey );
472 EXPECT_EQ( (*it).nKey, arr[idx].nKey );
476 for ( auto it = l.cbegin(); it != l.cend(); ++it, ++idx ) {
477 ASSERT_LT( idx, nSize );
478 EXPECT_EQ( it->nKey, arr[idx].nKey );
479 EXPECT_EQ( (*it).nKey, arr[idx].nKey );
484 List::gc::force_dispose();
485 for ( auto const& i : arr ) {
486 EXPECT_EQ( i.s.nDisposeCount, 1 );
487 EXPECT_FALSE( l.contains( i ) );
492 } // namespace cds_test
494 #endif // CDSUNIT_LIST_TEST_INTRUSIVE_LIST_NOGC_H