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.
31 #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H
32 #define CDSUNIT_SET_TEST_INTRUSIVE_SET_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
37 #include <cds/opt/hash.h>
39 // forward declaration
40 namespace cds { namespace intrusive {}}
44 namespace ci = cds::intrusive;
45 namespace co = cds::opt;
47 class intrusive_set: public fixture
50 static size_t const kSize = 1000;
54 unsigned int nDisposeCount ; // count of disposer calling
55 unsigned int nFindCount ; // count of find-functor calling
56 unsigned int nUpdateNewCount;
57 unsigned int nUpdateCount;
58 mutable unsigned int nEraseCount;
67 memset( this, 0, sizeof( *this ) );
71 template <typename Node>
83 explicit base_int_item( int key )
88 base_int_item(int key, int val)
93 base_int_item( base_int_item const& v )
106 template <typename Node>
107 struct member_int_item: public stat
109 typedef Node member_type;
121 explicit member_int_item( int key )
126 member_int_item(int key, int val)
131 member_int_item(member_int_item const& v )
144 size_t operator()( int i ) const
146 return co::v::hash<int>()( i );
148 template <typename Item>
149 size_t operator()( const Item& i ) const
151 return (*this)( i.key() );
154 typedef hash_int hash1;
156 struct hash2: private hash1
158 typedef hash1 base_class;
160 size_t operator()( int i ) const
162 size_t h = ~(base_class::operator()( i ));
163 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
165 template <typename Item>
166 size_t operator()( const Item& i ) const
168 size_t h = ~(base_class::operator()( i ));
169 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
173 struct simple_item_counter {
176 simple_item_counter()
195 operator size_t() const
202 template <typename T>
205 bool operator ()(const T& v1, const T& v2 ) const
207 return v1.key() < v2.key();
210 bool operator ()(const T& v1, int v2 ) const
212 return v1.key() < v2;
215 bool operator ()(int v1, const T& v2 ) const
217 return v1 < v2.key();
220 bool operator()( int v1, int v2 ) const
226 template <typename T>
228 int operator ()(const T& v1, const T& v2 ) const
230 if ( v1.key() < v2.key() )
232 return v1.key() > v2.key() ? 1 : 0;
235 template <typename Q>
236 int operator ()(const T& v1, const Q& v2 ) const
240 return v1.key() > v2 ? 1 : 0;
243 template <typename Q>
244 int operator ()(const Q& v1, const T& v2 ) const
248 return v1 > v2.key() ? 1 : 0;
252 template <typename T>
254 int operator ()( const T& v1, const T& v2 ) const
256 return v1.key() == v2.key();
259 template <typename Q>
260 int operator ()( const T& v1, const Q& v2 ) const
262 return v1.key() == v2;
265 template <typename Q>
266 int operator ()( const Q& v1, const T& v2 ) const
268 return v1 == v2.key();
275 explicit other_item( int k )
286 template <typename T>
287 bool operator()( other_item const& lhs, T const& rhs ) const
289 return lhs.key() < rhs.key();
292 template <typename T>
293 bool operator()( T const& lhs, other_item const& rhs ) const
295 return lhs.key() < rhs.key();
298 bool operator()( other_item const& lhs, int rhs ) const
300 return lhs.key() < rhs;
303 bool operator()( int lhs, other_item const& rhs ) const
305 return lhs < rhs.key();
309 struct other_equal_to {
310 template <typename Q, typename T>
311 bool operator()( Q const& lhs, T const& rhs ) const
313 return lhs.key() == rhs.key();
319 template <typename T>
320 void operator ()( T * p )
327 template <typename Set>
328 void test( Set& s, std::vector< typename Set::value_type >& data )
330 test_< true >( s, data );
333 template <bool Sorted, class Set>
334 void test_( Set& s, std::vector< typename Set::value_type >& data )
336 // Precondition: set is empty
337 // Postcondition: set is empty
339 ASSERT_TRUE( s.empty() );
340 ASSERT_CONTAINER_SIZE( s, 0 );
342 typedef typename Set::value_type value_type;
343 typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate;
344 size_t const nSetSize = kSize;
346 std::vector< size_t> indices;
347 data.reserve( kSize );
348 indices.reserve( kSize );
349 for ( size_t key = 0; key < kSize; ++key ) {
350 data.push_back( value_type( static_cast<int>( key )));
351 indices.push_back( key );
353 shuffle( indices.begin(), indices.end() );
356 for ( auto idx : indices ) {
357 auto& i = data[ idx ];
359 ASSERT_FALSE( s.contains( i.nKey ));
360 ASSERT_FALSE( s.contains( i ));
361 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
362 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
363 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
365 std::pair<bool, bool> updResult;
367 updResult = s.update( i, []( bool bNew, value_type&, value_type& )
369 ASSERT_TRUE( false );
371 EXPECT_FALSE( updResult.first );
372 EXPECT_FALSE( updResult.second );
374 switch ( i.key() % 3 ) {
376 ASSERT_TRUE( s.insert( i ));
377 ASSERT_FALSE( s.insert( i ));
378 updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg)
380 EXPECT_FALSE( bNew );
381 EXPECT_EQ( &val, &arg );
383 EXPECT_TRUE( updResult.first );
384 EXPECT_FALSE( updResult.second );
387 EXPECT_EQ( i.nUpdateNewCount, 0 );
388 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
389 EXPECT_EQ( i.nUpdateNewCount, 1 );
390 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
391 EXPECT_EQ( i.nUpdateNewCount, 1 );
392 i.nUpdateNewCount = 0;
395 updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg )
398 EXPECT_EQ( &val, &arg );
400 EXPECT_TRUE( updResult.first );
401 EXPECT_TRUE( updResult.second );
405 ASSERT_TRUE( s.contains( i.nKey ) );
406 ASSERT_TRUE( s.contains( i ) );
407 ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate()));
408 EXPECT_EQ( i.nFindCount, 0 );
409 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
410 EXPECT_EQ( i.nFindCount, 1 );
411 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
412 EXPECT_EQ( i.nFindCount, 2 );
414 ASSERT_FALSE( s.empty() );
415 ASSERT_CONTAINER_SIZE( s, nSetSize );
417 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
420 shuffle( indices.begin(), indices.end() );
421 for ( auto idx : indices ) {
422 auto& i = data[ idx ];
424 ASSERT_TRUE( s.contains( i.nKey ) );
425 ASSERT_TRUE( s.contains( i ) );
426 ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate() ) );
427 EXPECT_EQ( i.nFindCount, 0 );
428 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
429 EXPECT_EQ( i.nFindCount, 1 );
430 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
431 EXPECT_EQ( i.nFindCount, 2 );
434 switch ( i.key() % 6 ) {
436 ASSERT_FALSE( s.unlink( v ));
437 ASSERT_TRUE( s.unlink( i ));
438 ASSERT_FALSE( s.unlink( i ) );
441 ASSERT_TRUE( s.erase( i.key()));
442 ASSERT_FALSE( s.erase( i.key() ) );
445 ASSERT_TRUE( s.erase( v ));
446 ASSERT_FALSE( s.erase( v ) );
449 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate()));
450 ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_predicate() ) );
453 EXPECT_EQ( i.nEraseCount, 0 );
454 ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
455 EXPECT_EQ( i.nEraseCount, 1 );
456 ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
457 EXPECT_EQ( i.nEraseCount, 1 );
460 EXPECT_EQ( i.nEraseCount, 0 );
461 ASSERT_TRUE( s.erase_with( other_item( i.key() ), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
462 EXPECT_EQ( i.nEraseCount, 1 );
463 ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
464 EXPECT_EQ( i.nEraseCount, 1 );
468 ASSERT_FALSE( s.contains( i.nKey ));
469 ASSERT_FALSE( s.contains( i ));
470 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
471 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
472 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
474 ASSERT_TRUE( s.empty() );
475 ASSERT_CONTAINER_SIZE( s, 0 );
478 for ( auto& i : data ) {
480 ASSERT_TRUE( s.insert( i ));
482 ASSERT_FALSE( s.empty() );
483 ASSERT_CONTAINER_SIZE( s, nSetSize );
487 ASSERT_TRUE( s.empty() );
488 ASSERT_CONTAINER_SIZE( s, 0 );
491 for ( auto& i : data ) {
493 ASSERT_TRUE( s.insert( i ) );
495 ASSERT_FALSE( s.empty() );
496 ASSERT_CONTAINER_SIZE( s, nSetSize );
498 s.clear_and_dispose( mock_disposer() );
500 ASSERT_TRUE( s.empty() );
501 ASSERT_CONTAINER_SIZE( s, 0 );
502 for ( auto& i : data ) {
503 EXPECT_EQ( i.nDisposeCount, 1 );
509 } // namespace cds_test
511 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H