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.
31 #ifndef CDSUNIT_STRIPED_SET_TEST_INTRUSIVE_SET_H
32 #define CDSUNIT_STRIPED_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 int operator ()( const T& v1, int v2 ) const
261 return v1.key() == v2;
264 int operator ()( int v1, const T& v2 ) const
266 return v1 == v2.key();
273 explicit other_item( int k )
284 template <typename T>
285 bool operator()( other_item const& lhs, T const& rhs ) const
287 return lhs.key() < rhs.key();
290 template <typename T>
291 bool operator()( T const& lhs, other_item const& rhs ) const
293 return lhs.key() < rhs.key();
296 bool operator()( other_item const& lhs, int rhs ) const
298 return lhs.key() < rhs;
301 bool operator()( int lhs, other_item const& rhs ) const
303 return lhs < rhs.key();
307 struct other_equal_to {
308 template <typename Q, typename T>
309 bool operator()( Q const& lhs, T const& rhs ) const
311 return lhs.key() == rhs.key();
317 template <typename T>
318 void operator ()( T * p )
325 template <typename Set>
326 void test( Set& s, std::vector< typename Set::value_type >& data )
328 test_< true >( s, data );
331 template <bool Sorted, class Set>
332 void test_( Set& s, std::vector< typename Set::value_type >& data )
334 // Precondition: set is empty
335 // Postcondition: set is empty
337 ASSERT_TRUE( s.empty());
338 ASSERT_CONTAINER_SIZE( s, 0 );
340 typedef typename Set::value_type value_type;
341 typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate;
342 size_t const nSetSize = kSize;
344 std::vector< size_t> indices;
345 data.reserve( kSize );
346 indices.reserve( kSize );
347 for ( size_t key = 0; key < kSize; ++key ) {
348 data.push_back( value_type( static_cast<int>( key )));
349 indices.push_back( key );
351 shuffle( indices.begin(), indices.end());
354 for ( auto idx : indices ) {
355 auto& i = data[ idx ];
357 ASSERT_FALSE( s.contains( i.nKey ));
358 ASSERT_FALSE( s.contains( i ));
359 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
360 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
361 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
363 std::pair<bool, bool> updResult;
365 updResult = s.update( i, []( bool /*bNew*/, value_type&, value_type& )
367 ASSERT_TRUE( false );
369 EXPECT_FALSE( updResult.first );
370 EXPECT_FALSE( updResult.second );
372 switch ( i.key() % 3 ) {
374 ASSERT_TRUE( s.insert( i ));
375 ASSERT_FALSE( s.insert( i ));
376 updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg)
378 EXPECT_FALSE( bNew );
379 EXPECT_EQ( &val, &arg );
381 EXPECT_TRUE( updResult.first );
382 EXPECT_FALSE( updResult.second );
385 EXPECT_EQ( i.nUpdateNewCount, 0u );
386 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
387 EXPECT_EQ( i.nUpdateNewCount, 1u );
388 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
389 EXPECT_EQ( i.nUpdateNewCount, 1u );
390 i.nUpdateNewCount = 0;
393 updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg )
396 EXPECT_EQ( &val, &arg );
398 EXPECT_TRUE( updResult.first );
399 EXPECT_TRUE( updResult.second );
403 ASSERT_TRUE( s.contains( i.nKey ));
404 ASSERT_TRUE( s.contains( i ));
405 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
406 EXPECT_EQ( i.nFindCount, 0u );
407 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
408 EXPECT_EQ( i.nFindCount, 1u );
409 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
410 EXPECT_EQ( i.nFindCount, 2u );
412 ASSERT_FALSE( s.empty());
413 ASSERT_CONTAINER_SIZE( s, nSetSize );
415 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
418 shuffle( indices.begin(), indices.end());
419 for ( auto idx : indices ) {
420 auto& i = data[ idx ];
422 ASSERT_TRUE( s.contains( i.nKey ));
423 ASSERT_TRUE( s.contains( i ));
424 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
425 EXPECT_EQ( i.nFindCount, 0u );
426 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
427 EXPECT_EQ( i.nFindCount, 1u );
428 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
429 EXPECT_EQ( i.nFindCount, 2u );
432 switch ( i.key() % 6 ) {
434 ASSERT_FALSE( s.unlink( v ));
435 ASSERT_TRUE( s.unlink( i ));
436 ASSERT_FALSE( s.unlink( i ));
439 ASSERT_TRUE( s.erase( i.key()));
440 ASSERT_FALSE( s.erase( i.key()));
443 ASSERT_TRUE( s.erase( v ));
444 ASSERT_FALSE( s.erase( v ));
447 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate()));
448 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate()));
451 EXPECT_EQ( i.nEraseCount, 0u );
452 ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
453 EXPECT_EQ( i.nEraseCount, 1u );
454 ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
455 EXPECT_EQ( i.nEraseCount, 1u );
458 EXPECT_EQ( i.nEraseCount, 0u );
459 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
460 EXPECT_EQ( i.nEraseCount, 1u );
461 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
462 EXPECT_EQ( i.nEraseCount, 1u );
466 ASSERT_FALSE( s.contains( i.nKey ));
467 ASSERT_FALSE( s.contains( i ));
468 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
469 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
470 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
472 ASSERT_TRUE( s.empty());
473 ASSERT_CONTAINER_SIZE( s, 0u );
476 for ( auto& i : data ) {
478 ASSERT_TRUE( s.insert( i ));
480 ASSERT_FALSE( s.empty());
481 ASSERT_CONTAINER_SIZE( s, nSetSize );
485 ASSERT_TRUE( s.empty());
486 ASSERT_CONTAINER_SIZE( s, 0u );
489 for ( auto& i : data ) {
491 ASSERT_TRUE( s.insert( i ));
493 ASSERT_FALSE( s.empty());
494 ASSERT_CONTAINER_SIZE( s, nSetSize );
496 s.clear_and_dispose( mock_disposer());
498 ASSERT_TRUE( s.empty());
499 ASSERT_CONTAINER_SIZE( s, 0 );
500 for ( auto& i : data ) {
501 EXPECT_EQ( i.nDisposeCount, 1u );
507 } // namespace cds_test
509 #endif // #ifndef CDSUNIT_STRIPED_SET_TEST_INTRUSIVE_SET_H