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.
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_TRUE( l.find( i.nKey ) == l.end());
246 EXPECT_EQ( i.s.nFindCall, 0 );
247 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
248 EXPECT_EQ( i.s.nFindCall, 0 );
250 switch ( i.nKey % 4 ) {
252 EXPECT_TRUE( l.insert( i ));
255 EXPECT_EQ( i.s.nInsertCall, 0 );
256 EXPECT_TRUE( l.insert( i, []( value_type& v ) { ++v.s.nInsertCall; } ));
257 EXPECT_EQ( i.s.nInsertCall, 1 );
261 std::pair<bool, bool> ret = l.update( i, []( value_type& v, value_type * old ) {
262 EXPECT_TRUE( old == nullptr );
263 EXPECT_EQ( v.s.nUpdateNewCall, 0 );
264 ++v.s.nUpdateNewCall;
266 EXPECT_EQ( i.s.nUpdateNewCall, 0 );
267 EXPECT_EQ( ret.first, false );
268 EXPECT_EQ( ret.second, false );
270 ret = l.update( i, []( value_type& v, value_type * old ) {
271 EXPECT_TRUE( old == nullptr );
272 EXPECT_EQ( v.s.nUpdateNewCall, 0 );
273 ++v.s.nUpdateNewCall;
275 EXPECT_EQ( i.s.nUpdateNewCall, 1 );
276 EXPECT_EQ( ret.first, true );
277 EXPECT_EQ( ret.second, true );
282 std::pair<bool, bool> ret = l.upsert( i, false );
283 EXPECT_EQ( ret.first, false );
284 EXPECT_EQ( ret.second, false );
287 EXPECT_EQ( ret.first, true );
288 EXPECT_EQ( ret.second, true );
293 EXPECT_TRUE( l.contains( i.nKey ));
294 EXPECT_TRUE( l.contains( i ));
295 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
296 EXPECT_FALSE( l.find( i.nKey ) == l.end());
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 int const ckey = i.nKey;
308 iterator it = l.find( ckey );
309 ASSERT_FALSE( it == l.end());
310 EXPECT_EQ( it->nKey, i.nKey );
311 EXPECT_EQ( (*it).nVal, i.nVal );
312 check_ordered( it, l.end());
314 it = l.find( i.nKey );
315 ASSERT_FALSE( it == l.end());
316 EXPECT_EQ( it->nKey, i.nKey );
317 EXPECT_EQ( (*it).nVal, i.nVal );
318 check_ordered( it, l.end());
320 it = l.find_with( other_item( i.nKey ), other_less());
321 ASSERT_FALSE( it == l.end());
322 EXPECT_EQ( it->nKey, i.nKey );
323 EXPECT_EQ( it->nVal, i.nVal );
324 check_ordered( it, l.end());
327 ASSERT_CONTAINER_SIZE( l, nSize );
330 for ( auto const& i : arr ) {
331 EXPECT_TRUE( l.contains( i.nKey ));
332 EXPECT_TRUE( l.contains( i ));
333 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
334 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
335 EXPECT_EQ( i.s.nFindCall, 4 );
336 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
337 EXPECT_EQ( i.s.nFindCall, 5 );
338 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
339 EXPECT_EQ( i.s.nFindCall, 6 );
341 ASSERT_FALSE( l.empty());
342 ASSERT_CONTAINER_SIZE( l, nSize );
344 // update existing test
345 for ( auto& i : arr2 ) {
346 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
347 std::pair<bool, bool> ret = l.update( i, update_functor());
348 EXPECT_TRUE( ret.first );
349 EXPECT_FALSE( ret.second );
350 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
353 // update with the same value must be empty - no functor is called
354 for ( auto& i : arr2 ) {
355 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
356 std::pair<bool, bool> ret = l.update( i, update_functor());
357 EXPECT_TRUE( ret.first );
358 EXPECT_FALSE( ret.second );
359 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
362 // Apply retired pointer to clean links
363 List::gc::force_dispose();
365 for ( auto& i : arr ) {
366 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
367 std::pair<bool, bool> ret = l.update( i, []( value_type& v, value_type * old ) {
368 EXPECT_FALSE( old == nullptr );
369 EXPECT_EQ( v.s.nUpdateExistsCall, 0 );
370 ++v.s.nUpdateExistsCall;
372 EXPECT_TRUE( ret.first );
373 EXPECT_FALSE( ret.second );
374 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
378 for ( auto const& i : arr ) {
380 EXPECT_TRUE( l.erase( i.nKey ));
382 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less()));
384 EXPECT_FALSE( l.contains( i ));
386 EXPECT_TRUE( l.empty());
387 EXPECT_CONTAINER_SIZE( l, 0 );
389 // Apply retired pointer to clean links
390 List::gc::force_dispose();
392 for ( auto const& i : arr )
393 EXPECT_EQ( i.s.nDisposeCount, 2 );
394 for ( auto const& i : arr2 )
395 EXPECT_EQ( i.s.nDisposeCount, 1 );
397 // erase with functor
398 for ( auto& i : arr ) {
399 int const updateNewCall = i.s.nUpdateNewCall;
400 std::pair<bool, bool> ret = l.update( i, update_functor(), false );
401 EXPECT_FALSE( ret.first );
402 EXPECT_FALSE( ret.second );
403 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall );
405 ret = l.update( i, update_functor(), true );
406 EXPECT_TRUE( ret.first );
407 EXPECT_TRUE( ret.second );
408 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall + 1 );
410 EXPECT_FALSE( l.empty());
411 EXPECT_CONTAINER_SIZE( l, nSize );
413 for ( auto const& i : arr ) {
414 EXPECT_EQ( i.s.nEraseCall, 0 );
416 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
417 EXPECT_FALSE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
420 EXPECT_TRUE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
421 EXPECT_FALSE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
423 EXPECT_EQ( i.s.nEraseCall, 1 );
424 EXPECT_FALSE( l.contains( i.nKey ));
426 EXPECT_TRUE( l.empty());
427 EXPECT_CONTAINER_SIZE( l, 0 );
429 // Apply retired pointer to clean links
430 List::gc::force_dispose();
432 for ( auto const& i : arr )
433 EXPECT_EQ( i.s.nDisposeCount, 3 );
436 for ( auto& i : arr )
437 EXPECT_TRUE( l.insert( i ));
439 EXPECT_FALSE( l.empty());
440 EXPECT_CONTAINER_SIZE( l, nSize );
444 EXPECT_TRUE( l.empty());
445 EXPECT_CONTAINER_SIZE( l, 0 );
447 // Apply retired pointer to clean links
448 List::gc::force_dispose();
449 for ( auto const& i : arr ) {
450 EXPECT_EQ( i.s.nDisposeCount, 4 );
451 EXPECT_FALSE( l.contains( i ));
455 for ( auto& i : arr )
456 EXPECT_TRUE( l.insert( i ));
457 for ( auto& i : arr ) {
459 EXPECT_TRUE( l.contains( val ));
460 EXPECT_FALSE( l.unlink( val ));
461 EXPECT_TRUE( l.contains( val ));
462 EXPECT_TRUE( l.unlink( i ));
463 EXPECT_FALSE( l.unlink( i ));
464 EXPECT_FALSE( l.contains( i ));
466 EXPECT_TRUE( l.empty());
467 EXPECT_CONTAINER_SIZE( l, 0 );
469 // Apply retired pointer to clean links
470 List::gc::force_dispose();
471 for ( auto const& i : arr ) {
472 EXPECT_EQ( i.s.nDisposeCount, 5 );
473 EXPECT_FALSE( l.contains( i ));
476 // Iterators on empty list
479 auto itEnd = l.end();
480 auto cit = l.cbegin();
481 auto citEnd = l.cend();
483 EXPECT_TRUE( it == itEnd );
484 EXPECT_TRUE( it == cit );
485 EXPECT_TRUE( cit == citEnd );
490 EXPECT_TRUE( it == itEnd );
491 EXPECT_TRUE( it == cit );
492 EXPECT_TRUE( cit == citEnd );
496 template <typename List>
497 void test_ordered_iterator( List& l )
499 // Precondition: list is empty
500 // Postcondition: list is empty
502 static const size_t nSize = 20;
503 typedef typename List::value_type value_type;
504 value_type arr[nSize];
506 for ( size_t i = 0; i < nSize; ++i ) {
507 arr[i].nKey = static_cast<int>(i);
508 arr[i].nVal = arr[i].nKey * 10;
510 shuffle( arr, arr + nSize );
512 ASSERT_TRUE( l.empty());
513 ASSERT_CONTAINER_SIZE( l, 0 );
515 for ( auto& i : arr )
516 EXPECT_TRUE( l.insert( i ));
519 for ( auto it = l.begin(); it != l.end(); ++it ) {
520 EXPECT_EQ( it->nKey, key );
521 EXPECT_EQ( (*it).nKey, key );
526 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
527 EXPECT_EQ( it->nKey, key );
528 EXPECT_EQ( (*it).nKey, key );
534 for ( auto it = l.begin(); it != l.end(); ++it ) {
535 EXPECT_EQ( it->nKey, key );
536 EXPECT_EQ( ( *it ).nKey, key );
538 EXPECT_TRUE( l.erase_at( it ) );
540 EXPECT_EQ( it->nKey, key );
541 EXPECT_EQ( ( *it ).nKey, key );
543 EXPECT_FALSE( l.erase_at( it ) );
546 EXPECT_TRUE( l.empty() );
547 EXPECT_CONTAINER_SIZE( l, 0 );
549 List::gc::force_dispose();
550 for ( auto const& i : arr ) {
551 EXPECT_EQ( i.s.nDisposeCount, 1 );
552 EXPECT_FALSE( l.contains( i ));
556 template <typename Iterator>
557 void check_ordered( Iterator first, Iterator last )
559 while ( first != last ) {
561 if ( ++it != last ) {
562 EXPECT_LT( first->nKey, it->nKey );
570 } // namespace cds_test
572 #endif // CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H