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() );
155 struct simple_item_counter {
158 simple_item_counter()
177 operator size_t() const
184 template <typename T>
187 bool operator ()(const T& v1, const T& v2 ) const
189 return v1.key() < v2.key();
192 template <typename Q>
193 bool operator ()(const T& v1, const Q& v2 ) const
195 return v1.key() < v2;
198 template <typename Q>
199 bool operator ()(const Q& v1, const T& v2 ) const
201 return v1 < v2.key();
205 template <typename T>
207 int operator ()(const T& v1, const T& v2 ) const
209 if ( v1.key() < v2.key() )
211 return v1.key() > v2.key() ? 1 : 0;
214 template <typename Q>
215 int operator ()(const T& v1, const Q& v2 ) const
219 return v1.key() > v2 ? 1 : 0;
222 template <typename Q>
223 int operator ()(const Q& v1, const T& v2 ) const
227 return v1 > v2.key() ? 1 : 0;
231 template <typename T>
233 int operator ()( const T& v1, const T& v2 ) const
235 return v1.key() == v2.key();
238 template <typename Q>
239 int operator ()( const T& v1, const Q& v2 ) const
241 return v1.key() == v2;
244 template <typename Q>
245 int operator ()( const Q& v1, const T& v2 ) const
247 return v1 == v2.key();
254 explicit other_item( int k )
265 template <typename Q, typename T>
266 bool operator()( Q const& lhs, T const& rhs ) const
268 return lhs.key() < rhs.key();
272 struct other_equal_to {
273 template <typename Q, typename T>
274 bool operator()( Q const& lhs, T const& rhs ) const
276 return lhs.key() == rhs.key();
282 template <typename T>
283 void operator ()( T * p )
290 template <typename Set>
296 template <bool Sorted, class Set>
299 // Precondition: set is empty
300 // Postcondition: set is empty
302 ASSERT_TRUE( s.empty() );
303 ASSERT_CONTAINER_SIZE( s, 0 );
305 typedef typename Set::value_type value_type;
306 typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate;
307 size_t const nSetSize = kSize;
309 std::vector< value_type > data;
310 std::vector< size_t> indices;
311 data.reserve( kSize );
312 indices.reserve( kSize );
313 for ( size_t key = 0; key < kSize; ++key ) {
314 data.push_back( value_type( static_cast<int>( key )));
315 indices.push_back( key );
317 shuffle( indices.begin(), indices.end() );
320 for ( auto idx : indices ) {
321 auto& i = data[ idx ];
323 ASSERT_FALSE( s.contains( i.nKey ));
324 ASSERT_FALSE( s.contains( i ));
325 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
326 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
327 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
329 std::pair<bool, bool> updResult;
331 updResult = s.update( i, []( bool bNew, value_type&, value_type& )
333 ASSERT_TRUE( false );
335 EXPECT_FALSE( updResult.first );
336 EXPECT_FALSE( updResult.second );
338 switch ( i.key() % 3 ) {
340 ASSERT_TRUE( s.insert( i ));
341 ASSERT_FALSE( s.insert( i ));
342 updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg)
344 EXPECT_FALSE( bNew );
345 EXPECT_EQ( &val, &arg );
347 EXPECT_TRUE( updResult.first );
348 EXPECT_FALSE( updResult.second );
351 EXPECT_EQ( i.nUpdateNewCount, 0 );
352 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
353 EXPECT_EQ( i.nUpdateNewCount, 1 );
354 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
355 EXPECT_EQ( i.nUpdateNewCount, 1 );
356 i.nUpdateNewCount = 0;
359 updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg )
362 EXPECT_EQ( &val, &arg );
364 EXPECT_TRUE( updResult.first );
365 EXPECT_TRUE( updResult.second );
369 ASSERT_TRUE( s.contains( i.nKey ) );
370 ASSERT_TRUE( s.contains( i ) );
371 ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate()));
372 EXPECT_EQ( i.nFindCount, 0 );
373 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
374 EXPECT_EQ( i.nFindCount, 1 );
375 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
376 EXPECT_EQ( i.nFindCount, 2 );
378 ASSERT_FALSE( s.empty() );
379 ASSERT_CONTAINER_SIZE( s, nSetSize );
381 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
384 shuffle( indices.begin(), indices.end() );
385 for ( auto idx : indices ) {
386 auto& i = data[ idx ];
388 ASSERT_TRUE( s.contains( i.nKey ) );
389 ASSERT_TRUE( s.contains( i ) );
390 ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate() ) );
391 EXPECT_EQ( i.nFindCount, 0 );
392 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
393 EXPECT_EQ( i.nFindCount, 1 );
394 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
395 EXPECT_EQ( i.nFindCount, 2 );
398 switch ( i.key() % 6 ) {
400 ASSERT_FALSE( s.unlink( v ));
401 ASSERT_TRUE( s.unlink( i ));
402 ASSERT_FALSE( s.unlink( i ) );
405 ASSERT_TRUE( s.erase( i.key()));
406 ASSERT_FALSE( s.erase( i.key() ) );
409 ASSERT_TRUE( s.erase( v ));
410 ASSERT_FALSE( s.erase( v ) );
413 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate()));
414 ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_predicate() ) );
417 EXPECT_EQ( i.nEraseCount, 0 );
418 ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
419 EXPECT_EQ( i.nEraseCount, 1 );
420 ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
421 EXPECT_EQ( i.nEraseCount, 1 );
424 EXPECT_EQ( i.nEraseCount, 0 );
425 ASSERT_TRUE( s.erase_with( other_item( i.key() ), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
426 EXPECT_EQ( i.nEraseCount, 1 );
427 ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
428 EXPECT_EQ( i.nEraseCount, 1 );
432 ASSERT_FALSE( s.contains( i.nKey ));
433 ASSERT_FALSE( s.contains( i ));
434 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
435 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
436 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
438 ASSERT_TRUE( s.empty() );
439 ASSERT_CONTAINER_SIZE( s, 0 );
442 for ( auto& i : data ) {
444 ASSERT_TRUE( s.insert( i ));
446 ASSERT_FALSE( s.empty() );
447 ASSERT_CONTAINER_SIZE( s, nSetSize );
451 ASSERT_TRUE( s.empty() );
452 ASSERT_CONTAINER_SIZE( s, 0 );
453 for ( auto& i : data ) {
454 EXPECT_EQ( i.nDisposeCount, 1 );
459 } // namespace cds_test
461 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H