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_ITERABLE_LIST_H
31 #define CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H
33 #include <cds_test/check_size.h>
34 #include <cds_test/fixture.h>
38 class intrusive_iterable_list : public fixture
43 int nUpdateExistsCall;
51 , nUpdateExistsCall( 0 )
63 stat& operator =( const stat& s )
65 memcpy( this, &s, sizeof( s ) );
80 item_type( int key, int val )
86 item_type( const item_type& v )
92 const int& key() const
97 item_type& operator=( item_type const& src )
104 item_type& operator=( item_type&& src )
112 template <typename T>
115 bool operator ()( const T& v1, const T& v2 ) const
117 return v1.key() < v2.key();
120 template <typename Q>
121 bool operator ()( const T& v1, const Q& v2 ) const
123 return v1.key() < v2;
126 template <typename Q>
127 bool operator ()( const Q& v1, const T& v2 ) const
129 return v1 < v2.key();
142 template <typename T, typename Q>
143 bool operator()( T const& i1, Q const& i2 ) const
145 return i1.nKey < i2.nKey;
149 template <typename T>
151 int operator ()( const T& v1, const T& v2 ) const
153 if ( v1.key() < v2.key() )
155 return v1.key() > v2.key() ? 1 : 0;
158 template <typename Q>
159 int operator ()( const T& v1, const Q& v2 ) const
163 return v1.key() > v2 ? 1 : 0;
166 template <typename Q>
167 int operator ()( const Q& v1, const T& v2 ) const
171 return v1 > v2.key() ? 1 : 0;
177 template <typename T>
178 void operator ()( T * p )
180 ++p->s.nDisposeCount;
184 struct update_functor
186 template <typename T>
187 void operator()( T& item, T * old )
190 ++item.s.nUpdateNewCall;
192 ++item.s.nUpdateExistsCall;
198 template <typename T, typename Q>
199 void operator ()( T& item, Q& /*val*/ )
207 template <typename T>
208 void operator()( T const& item )
215 template <typename List>
216 void test_common( List& l )
218 // Precondition: list is empty
219 // Postcondition: list is empty
221 static const size_t nSize = 20;
222 typedef typename List::value_type value_type;
223 value_type arr[ nSize ];
224 value_type arr2[ nSize ];
226 for ( size_t i = 0; i < nSize; ++i ) {
227 arr[i].nKey = static_cast<int>( i );
228 arr[i].nVal = arr[i].nKey * 10;
232 shuffle( arr, arr + nSize );
233 shuffle( arr2, arr2 + nSize );
235 ASSERT_TRUE( l.empty() );
236 ASSERT_CONTAINER_SIZE( l, 0 );
238 typedef typename List::iterator iterator;
241 for ( auto& i : arr ) {
242 EXPECT_FALSE( l.contains( i.nKey ));
243 EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less()));
244 EXPECT_FALSE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
245 EXPECT_EQ( i.s.nFindCall, 0 );
246 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
247 EXPECT_EQ( i.s.nFindCall, 0 );
249 switch ( i.nKey % 4 ) {
251 EXPECT_TRUE( l.insert( i ));
254 EXPECT_EQ( i.s.nInsertCall, 0 );
255 EXPECT_TRUE( l.insert( i, []( value_type& i ) { ++i.s.nInsertCall; } ));
256 EXPECT_EQ( i.s.nInsertCall, 1 );
260 std::pair<bool, bool> ret = l.update( i, []( value_type& i, value_type * old ) {
261 EXPECT_TRUE( old == nullptr );
262 EXPECT_EQ( i.s.nUpdateNewCall, 0 );
263 ++i.s.nUpdateNewCall;
265 EXPECT_EQ( i.s.nUpdateNewCall, 0 );
266 EXPECT_EQ( ret.first, false );
267 EXPECT_EQ( ret.second, false );
269 ret = l.update( i, []( value_type& i, value_type * old ) {
270 EXPECT_TRUE( old == nullptr );
271 EXPECT_EQ( i.s.nUpdateNewCall, 0 );
272 ++i.s.nUpdateNewCall;
274 EXPECT_EQ( i.s.nUpdateNewCall, 1 );
275 EXPECT_EQ( ret.first, true );
276 EXPECT_EQ( ret.second, true );
281 std::pair<bool, bool> ret = l.upsert( i, false );
282 EXPECT_EQ( ret.first, false );
283 EXPECT_EQ( ret.second, false );
286 EXPECT_EQ( ret.first, true );
287 EXPECT_EQ( ret.second, true );
292 EXPECT_TRUE( l.contains( i.nKey ));
293 EXPECT_TRUE( l.contains( i ));
294 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
295 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
296 EXPECT_EQ( i.s.nFindCall, 1 );
297 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
298 EXPECT_EQ( i.s.nFindCall, 2 );
299 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
300 EXPECT_EQ( i.s.nFindCall, 3 );
302 EXPECT_FALSE( l.insert( i ) );
303 ASSERT_FALSE( l.empty() );
305 int const ckey = i.nKey;
306 iterator it = l.find( ckey );
307 ASSERT_FALSE( it == l.end() );
308 EXPECT_EQ( it->nKey, i.nKey );
309 EXPECT_EQ( (*it).nVal, i.nVal );
310 check_ordered( it, l.end() );
312 it = l.find( i.nKey );
313 ASSERT_FALSE( it == l.end() );
314 EXPECT_EQ( it->nKey, i.nKey );
315 EXPECT_EQ( (*it).nVal, i.nVal );
316 check_ordered( it, l.end() );
318 it = l.find_with( other_item( i.nKey ), other_less() );
319 ASSERT_FALSE( it == l.end() );
320 EXPECT_EQ( it->nKey, i.nKey );
321 EXPECT_EQ( it->nVal, i.nVal );
322 check_ordered( it, l.end() );
325 ASSERT_CONTAINER_SIZE( l, nSize );
328 for ( auto const& i : arr ) {
329 EXPECT_TRUE( l.contains( i.nKey ));
330 EXPECT_TRUE( l.contains( i ));
331 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
332 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
333 EXPECT_EQ( i.s.nFindCall, 4 );
334 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
335 EXPECT_EQ( i.s.nFindCall, 5 );
336 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
337 EXPECT_EQ( i.s.nFindCall, 6 );
339 ASSERT_FALSE( l.empty() );
340 ASSERT_CONTAINER_SIZE( l, nSize );
342 // update existing test
343 for ( auto& i : arr2 ) {
344 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
345 std::pair<bool, bool> ret = l.update( i, update_functor() );
346 EXPECT_TRUE( ret.first );
347 EXPECT_FALSE( ret.second );
348 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
351 // update with the same value must be empty - no functor is called
352 for ( auto& i : arr2 ) {
353 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
354 std::pair<bool, bool> ret = l.update( i, update_functor() );
355 EXPECT_TRUE( ret.first );
356 EXPECT_FALSE( ret.second );
357 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
360 for ( auto& i : arr ) {
361 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
362 std::pair<bool, bool> ret = l.update( i, []( value_type& i, value_type * old ) {
363 EXPECT_FALSE( old == nullptr );
364 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
365 ++i.s.nUpdateExistsCall;
367 EXPECT_TRUE( ret.first );
368 EXPECT_FALSE( ret.second );
369 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
373 for ( auto const& i : arr ) {
375 EXPECT_TRUE( l.erase( i.nKey ));
377 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less() ));
379 EXPECT_FALSE( l.contains( i ));
381 EXPECT_TRUE( l.empty() );
382 EXPECT_CONTAINER_SIZE( l, 0 );
384 // Apply retired pointer to clean links
385 List::gc::force_dispose();
387 for ( auto const& i : arr )
388 EXPECT_EQ( i.s.nDisposeCount, 2 );
389 for ( auto const& i : arr2 )
390 EXPECT_EQ( i.s.nDisposeCount, 1 );
392 // erase with functor
393 for ( auto& i : arr ) {
394 int const updateNewCall = i.s.nUpdateNewCall;
395 std::pair<bool, bool> ret = l.update( i, update_functor(), false );
396 EXPECT_FALSE( ret.first );
397 EXPECT_FALSE( ret.second );
398 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall );
400 ret = l.update( i, update_functor(), true );
401 EXPECT_TRUE( ret.first );
402 EXPECT_TRUE( ret.second );
403 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall + 1 );
405 EXPECT_FALSE( l.empty() );
406 EXPECT_CONTAINER_SIZE( l, nSize );
408 for ( auto const& i : arr ) {
409 EXPECT_EQ( i.s.nEraseCall, 0 );
411 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
412 EXPECT_FALSE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
415 EXPECT_TRUE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
416 EXPECT_FALSE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
418 EXPECT_EQ( i.s.nEraseCall, 1 );
419 EXPECT_FALSE( l.contains( i.nKey ));
421 EXPECT_TRUE( l.empty() );
422 EXPECT_CONTAINER_SIZE( l, 0 );
424 // Apply retired pointer to clean links
425 List::gc::force_dispose();
427 for ( auto const& i : arr )
428 EXPECT_EQ( i.s.nDisposeCount, 3 );
431 for ( auto& i : arr )
432 EXPECT_TRUE( l.insert( i ));
434 EXPECT_FALSE( l.empty() );
435 EXPECT_CONTAINER_SIZE( l, nSize );
439 EXPECT_TRUE( l.empty() );
440 EXPECT_CONTAINER_SIZE( l, 0 );
442 // Apply retired pointer to clean links
443 List::gc::force_dispose();
444 for ( auto const& i : arr ) {
445 EXPECT_EQ( i.s.nDisposeCount, 4 );
446 EXPECT_FALSE( l.contains( i ));
450 for ( auto& i : arr )
451 EXPECT_TRUE( l.insert( i ) );
452 for ( auto& i : arr ) {
454 EXPECT_TRUE( l.contains( val ));
455 EXPECT_FALSE( l.unlink( val ));
456 EXPECT_TRUE( l.contains( val ) );
457 EXPECT_TRUE( l.unlink( i ));
458 EXPECT_FALSE( l.unlink( i ));
459 EXPECT_FALSE( l.contains( i ) );
461 EXPECT_TRUE( l.empty() );
462 EXPECT_CONTAINER_SIZE( l, 0 );
464 // Apply retired pointer to clean links
465 List::gc::force_dispose();
466 for ( auto const& i : arr ) {
467 EXPECT_EQ( i.s.nDisposeCount, 5 );
468 EXPECT_FALSE( l.contains( i ) );
471 // Iterators on empty list
474 auto itEnd = l.end();
475 auto cit = l.cbegin();
476 auto citEnd = l.cend();
478 EXPECT_TRUE( it == itEnd );
479 EXPECT_TRUE( it == cit );
480 EXPECT_TRUE( cit == citEnd );
485 EXPECT_TRUE( it == itEnd );
486 EXPECT_TRUE( it == cit );
487 EXPECT_TRUE( cit == citEnd );
491 template <typename List>
492 void test_ordered_iterator( List& l )
494 // Precondition: list is empty
495 // Postcondition: list is empty
497 static const size_t nSize = 20;
498 typedef typename List::value_type value_type;
499 value_type arr[nSize];
501 for ( size_t i = 0; i < nSize; ++i ) {
502 arr[i].nKey = static_cast<int>(i);
503 arr[i].nVal = arr[i].nKey * 10;
505 shuffle( arr, arr + nSize );
507 ASSERT_TRUE( l.empty() );
508 ASSERT_CONTAINER_SIZE( l, 0 );
510 for ( auto& i : arr )
511 EXPECT_TRUE( l.insert( i ) );
514 for ( auto it = l.begin(); it != l.end(); ++it ) {
515 EXPECT_EQ( it->nKey, key );
516 EXPECT_EQ( (*it).nKey, key );
521 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
522 EXPECT_EQ( it->nKey, key );
523 EXPECT_EQ( (*it).nKey, key );
528 List::gc::force_dispose();
529 for ( auto const& i : arr ) {
530 EXPECT_EQ( i.s.nDisposeCount, 1 );
531 EXPECT_FALSE( l.contains( i ) );
535 template <typename Iterator>
536 void check_ordered( Iterator first, Iterator last )
538 while ( first != last ) {
540 if ( ++it != last ) {
541 EXPECT_LT( first->nKey, it->nKey );
549 } // namespace cds_test
551 #endif // CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H