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_H
31 #define CDSUNIT_LIST_TEST_INTRUSIVE_LIST_H
33 #include <cds_test/check_size.h>
34 #include <cds_test/fixture.h>
38 class intrusive_list_common : public fixture
43 int nUpdateExistsCall;
51 , nUpdateExistsCall( 0 )
63 stat& operator =( const stat& s )
65 memcpy( this, &s, sizeof( s ) );
70 template <typename Node>
71 struct base_item : public Node
81 base_item( int key, int val )
87 base_item( const base_item& v )
93 const int& key() const
98 base_item& operator=( base_item const& src )
105 base_item& operator=( base_item&& src )
113 template <typename Node>
124 member_item( int key, int val )
130 member_item( const member_item& v )
136 const int& key() const
141 member_item& operator =( member_item const& src )
148 member_item& operator=( member_item&& src )
156 template <typename T>
159 bool operator ()( const T& v1, const T& v2 ) const
161 return v1.key() < v2.key();
164 template <typename Q>
165 bool operator ()( const T& v1, const Q& v2 ) const
167 return v1.key() < v2;
170 template <typename Q>
171 bool operator ()( const Q& v1, const T& v2 ) const
173 return v1 < v2.key();
186 template <typename T, typename Q>
187 bool operator()( T const& i1, Q const& i2 ) const
189 return i1.nKey < i2.nKey;
193 template <typename T>
195 int operator ()( const T& v1, const T& v2 ) const
197 if ( v1.key() < v2.key() )
199 return v1.key() > v2.key() ? 1 : 0;
202 template <typename Q>
203 int operator ()( const T& v1, const Q& v2 ) const
207 return v1.key() > v2 ? 1 : 0;
210 template <typename Q>
211 int operator ()( const Q& v1, const T& v2 ) const
215 return v1 > v2.key() ? 1 : 0;
221 template <typename T>
222 void operator ()( T * p )
224 ++p->s.nDisposeCount;
228 struct update_functor
230 template <typename T>
231 void operator ()( bool bNew, T& item, T& /*val*/ )
234 ++item.s.nUpdateNewCall;
236 ++item.s.nUpdateExistsCall;
242 template <typename T, typename Q>
243 void operator ()( T& item, Q& /*val*/ )
251 template <typename T>
252 void operator()( T const& item )
259 template <typename List>
260 void test_common( List& l )
262 // Precondition: list is empty
263 // Postcondition: list is empty
265 static const size_t nSize = 20;
266 typedef typename List::value_type value_type;
267 value_type arr[ nSize ];
269 for ( size_t i = 0; i < nSize; ++i ) {
270 arr[i].nKey = static_cast<int>( i );
271 arr[i].nVal = arr[i].nKey * 10;
273 shuffle( arr, arr + nSize );
275 ASSERT_TRUE( l.empty() );
276 ASSERT_CONTAINER_SIZE( l, 0 );
279 for ( auto& i : arr ) {
280 EXPECT_FALSE( l.contains( i.nKey ));
281 EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less()));
282 EXPECT_FALSE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
283 EXPECT_EQ( i.s.nFindCall, 0 );
284 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
285 EXPECT_EQ( i.s.nFindCall, 0 );
288 EXPECT_TRUE( l.insert( i ));
290 EXPECT_EQ( i.s.nInsertCall, 0 );
291 EXPECT_TRUE( l.insert( i, []( value_type& i ) { ++i.s.nInsertCall; } ));
292 EXPECT_EQ( i.s.nInsertCall, 1 );
295 EXPECT_TRUE( l.contains( i.nKey ));
296 EXPECT_TRUE( l.contains( i ));
297 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
298 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
299 EXPECT_EQ( i.s.nFindCall, 1 );
300 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
301 EXPECT_EQ( i.s.nFindCall, 2 );
302 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
303 EXPECT_EQ( i.s.nFindCall, 3 );
305 EXPECT_FALSE( l.insert( i ) );
306 ASSERT_FALSE( l.empty() );
308 ASSERT_CONTAINER_SIZE( l, nSize );
311 for ( auto const& i : arr ) {
312 EXPECT_TRUE( l.contains( i.nKey ));
313 EXPECT_TRUE( l.contains( i ));
314 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
315 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
316 EXPECT_EQ( i.s.nFindCall, 4 );
317 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
318 EXPECT_EQ( i.s.nFindCall, 5 );
319 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
320 EXPECT_EQ( i.s.nFindCall, 6 );
322 ASSERT_FALSE( l.empty() );
323 ASSERT_CONTAINER_SIZE( l, nSize );
325 // update existing test
326 for ( auto& i : arr ) {
327 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
328 std::pair<bool, bool> ret = l.update( i, update_functor() );
329 EXPECT_TRUE( ret.first );
330 EXPECT_FALSE( ret.second );
331 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
333 ret = l.update( i, []( bool bNew, value_type& i, value_type& arg ) {
334 EXPECT_FALSE( bNew );
335 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
336 EXPECT_TRUE( &i == &arg );
337 ++i.s.nUpdateExistsCall;
339 EXPECT_TRUE( ret.first );
340 EXPECT_FALSE( ret.second );
341 EXPECT_EQ( i.s.nUpdateExistsCall, 2 );
345 for ( auto const& i : arr ) {
347 EXPECT_TRUE( l.erase( i.nKey ));
349 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less() ));
351 EXPECT_FALSE( l.contains( i ));
353 EXPECT_TRUE( l.empty() );
354 EXPECT_CONTAINER_SIZE( l, 0 );
356 // Apply retired pointer to clean links
357 List::gc::force_dispose();
359 for ( auto const& i : arr )
360 EXPECT_EQ( i.s.nDisposeCount, 1 );
362 // erase with functor
363 for ( auto& i : arr ) {
364 std::pair<bool, bool> ret = l.update( i, update_functor(), false );
365 EXPECT_FALSE( ret.first );
366 EXPECT_FALSE( ret.second );
368 ret = l.update( i, update_functor(), true );
369 EXPECT_TRUE( ret.first );
370 EXPECT_TRUE( ret.second );
371 EXPECT_EQ( i.s.nUpdateNewCall, 1 );
373 EXPECT_FALSE( l.empty() );
374 EXPECT_CONTAINER_SIZE( l, nSize );
376 for ( auto const& i : arr ) {
377 EXPECT_EQ( i.s.nEraseCall, 0 );
379 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
380 EXPECT_FALSE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
383 EXPECT_TRUE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
384 EXPECT_FALSE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
386 EXPECT_EQ( i.s.nEraseCall, 1 );
387 EXPECT_FALSE( l.contains( i.nKey ));
389 EXPECT_TRUE( l.empty() );
390 EXPECT_CONTAINER_SIZE( l, 0 );
392 // Apply retired pointer to clean links
393 List::gc::force_dispose();
395 for ( auto const& i : arr )
396 EXPECT_EQ( i.s.nDisposeCount, 2 );
399 for ( auto& i : arr )
400 EXPECT_TRUE( l.insert( i ));
402 EXPECT_FALSE( l.empty() );
403 EXPECT_CONTAINER_SIZE( l, nSize );
407 EXPECT_TRUE( l.empty() );
408 EXPECT_CONTAINER_SIZE( l, 0 );
410 // Apply retired pointer to clean links
411 List::gc::force_dispose();
412 for ( auto const& i : arr ) {
413 EXPECT_EQ( i.s.nDisposeCount, 3 );
414 EXPECT_FALSE( l.contains( i ));
418 for ( auto& i : arr )
419 EXPECT_TRUE( l.insert( i ) );
420 for ( auto& i : arr ) {
422 EXPECT_TRUE( l.contains( val ));
423 EXPECT_FALSE( l.unlink( val ));
424 EXPECT_TRUE( l.contains( val ) );
425 EXPECT_TRUE( l.unlink( i ));
426 EXPECT_FALSE( l.unlink( i ));
427 EXPECT_FALSE( l.contains( i ) );
429 EXPECT_TRUE( l.empty() );
430 EXPECT_CONTAINER_SIZE( l, 0 );
432 // Apply retired pointer to clean links
433 List::gc::force_dispose();
434 for ( auto const& i : arr ) {
435 EXPECT_EQ( i.s.nDisposeCount, 4 );
436 EXPECT_FALSE( l.contains( i ) );
439 // Iterators on empty list
442 auto itEnd = l.end();
443 auto cit = l.cbegin();
444 auto citEnd = l.cend();
446 EXPECT_TRUE( it == itEnd );
447 EXPECT_TRUE( it == cit );
448 EXPECT_TRUE( cit == citEnd );
453 EXPECT_TRUE( it == itEnd );
454 EXPECT_TRUE( it == cit );
455 EXPECT_TRUE( cit == citEnd );
459 template <typename List>
460 void test_ordered_iterator( List& l )
462 // Precondition: list is empty
463 // Postcondition: list is empty
465 static const size_t nSize = 20;
466 typedef typename List::value_type value_type;
467 value_type arr[nSize];
469 for ( size_t i = 0; i < nSize; ++i ) {
470 arr[i].nKey = static_cast<int>(i);
471 arr[i].nVal = arr[i].nKey * 10;
473 shuffle( arr, arr + nSize );
475 ASSERT_TRUE( l.empty() );
476 ASSERT_CONTAINER_SIZE( l, 0 );
478 for ( auto& i : arr )
479 EXPECT_TRUE( l.insert( i ) );
482 for ( auto it = l.begin(); it != l.end(); ++it ) {
483 EXPECT_EQ( it->nKey, key );
484 EXPECT_EQ( (*it).nKey, key );
489 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
490 EXPECT_EQ( it->nKey, key );
491 EXPECT_EQ( (*it).nKey, key );
496 List::gc::force_dispose();
497 for ( auto const& i : arr ) {
498 EXPECT_EQ( i.s.nDisposeCount, 1 );
499 EXPECT_FALSE( l.contains( i ) );
504 } // namespace cds_test
506 #endif // CDSUNIT_LIST_TEST_INTRUSIVE_LIST_H