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_TREE_TEST_INTRUSIVE_TREE_H
32 #define CDSUNIT_TREE_TEST_INTRUSIVE_TREE_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
37 #include <cds/opt/hash.h>
38 // forward declaration
39 namespace cds { namespace intrusive {}}
43 namespace ci = cds::intrusive;
45 class intrusive_tree: public fixture
48 static size_t const kSize = 1000;
52 unsigned int nDisposeCount ; // count of disposer calling
53 unsigned int nFindCount ; // count of find-functor calling
54 unsigned int nUpdateNewCount;
55 unsigned int nUpdateCount;
56 mutable unsigned int nEraseCount;
65 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
119 explicit member_int_item( int key )
124 member_int_item(int key, int val)
129 member_int_item(member_int_item const& v )
143 template <typename T>
144 void operator()( key_type& key, T const& val ) const
150 struct simple_item_counter {
153 simple_item_counter()
172 operator size_t() const
179 template <typename T>
182 bool operator ()(T const& v1, T const& v2 ) const
184 return v1.key() < v2.key();
187 bool operator()( T const& lhs, int rhs ) const
189 return lhs.key() < rhs;
192 bool operator()( int lhs, T const& rhs ) const
194 return lhs < rhs.key();
197 bool operator()( int lhs, int rhs ) const
203 template <typename T>
206 int operator ()(T const& v1, T const& v2 ) const
208 if ( v1.key() < v2.key() )
210 return v1.key() > v2.key() ? 1 : 0;
213 int operator()( T const& lhs, int rhs ) const
215 if ( lhs.key() < rhs )
217 return lhs.key() > rhs ? 1 : 0;
220 int operator()( int lhs, T const& rhs ) const
222 if ( lhs < rhs.key() )
224 return lhs > rhs.key() ? 1 : 0;
227 int operator()( int lhs, int rhs ) const
231 return lhs > rhs ? 1 : 0;
238 explicit other_item( int k )
249 template <typename Q, typename T>
250 bool operator()( Q const& lhs, T const& rhs ) const
252 return lhs.key() < rhs.key();
255 template <typename Q>
256 bool operator()( Q const& lhs, int rhs ) const
258 return lhs.key() < rhs;
261 template <typename T>
262 bool operator()( int lhs, T const& rhs ) const
264 return lhs < rhs.key();
270 template <typename T>
271 void operator ()( T * p )
278 template <class Tree>
281 // Precondition: tree is empty
282 // Postcondition: tree is empty
284 ASSERT_TRUE( t.empty() );
285 ASSERT_CONTAINER_SIZE( t, 0 );
286 size_t const nTreeSize = kSize;
288 typedef typename Tree::value_type value_type;
290 std::vector< value_type > data;
291 std::vector< size_t > indices;
292 data.reserve( kSize );
293 indices.reserve( kSize );
294 for ( size_t key = 0; key < kSize; ++key ) {
295 data.push_back( value_type( static_cast<int>( key )));
296 indices.push_back( key );
298 shuffle( indices.begin(), indices.end() );
301 for ( auto idx : indices ) {
302 auto& i = data[ idx ];
304 ASSERT_FALSE( t.contains( i.nKey ));
305 ASSERT_FALSE( t.contains( i ));
306 ASSERT_FALSE( t.contains( other_item( i.key()), other_less()));
307 ASSERT_FALSE( t.find( i.nKey, []( value_type&, int ) {} ));
308 ASSERT_FALSE( t.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
310 std::pair<bool, bool> updResult;
312 updResult = t.update( i, []( bool bNew, value_type&, value_type& )
314 ASSERT_TRUE( false );
316 EXPECT_FALSE( updResult.first );
317 EXPECT_FALSE( updResult.second );
319 switch ( i.key() % 3 ) {
321 ASSERT_TRUE( t.insert( i ));
322 ASSERT_FALSE( t.insert( i ));
323 updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg)
325 EXPECT_FALSE( bNew );
326 EXPECT_EQ( &val, &arg );
328 EXPECT_TRUE( updResult.first );
329 EXPECT_FALSE( updResult.second );
332 EXPECT_EQ( i.nUpdateNewCount, 0 );
333 ASSERT_TRUE( t.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
334 EXPECT_EQ( i.nUpdateNewCount, 1 );
335 ASSERT_FALSE( t.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
336 EXPECT_EQ( i.nUpdateNewCount, 1 );
337 i.nUpdateNewCount = 0;
340 updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
342 EXPECT_TRUE( false );
344 EXPECT_FALSE( updResult.first );
345 EXPECT_FALSE( updResult.second );
347 EXPECT_EQ( i.nUpdateNewCount, 0 );
348 updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
351 EXPECT_EQ( &val, &arg );
352 ++val.nUpdateNewCount;
354 EXPECT_TRUE( updResult.first );
355 EXPECT_TRUE( updResult.second );
356 EXPECT_EQ( i.nUpdateNewCount, 1 );
357 i.nUpdateNewCount = 0;
359 EXPECT_EQ( i.nUpdateCount, 0 );
360 updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
362 EXPECT_FALSE( bNew );
363 EXPECT_EQ( &val, &arg );
366 EXPECT_TRUE( updResult.first );
367 EXPECT_FALSE( updResult.second );
368 EXPECT_EQ( i.nUpdateCount, 1 );
374 ASSERT_TRUE( t.contains( i.nKey ) );
375 ASSERT_TRUE( t.contains( i ) );
376 ASSERT_TRUE( t.contains( other_item( i.key() ), other_less()));
377 EXPECT_EQ( i.nFindCount, 0 );
378 ASSERT_TRUE( t.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
379 EXPECT_EQ( i.nFindCount, 1 );
380 ASSERT_TRUE( t.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
381 EXPECT_EQ( i.nFindCount, 2 );
382 ASSERT_TRUE( t.find( i, []( value_type& v, value_type& ) { ++v.nFindCount; } ) );
383 EXPECT_EQ( i.nFindCount, 3 );
385 ASSERT_FALSE( t.empty() );
386 ASSERT_CONTAINER_SIZE( t, nTreeSize );
388 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
391 shuffle( indices.begin(), indices.end() );
392 for ( auto idx : indices ) {
393 auto& i = data[ idx ];
395 ASSERT_TRUE( t.contains( i.nKey ) );
396 ASSERT_TRUE( t.contains( i ) );
397 ASSERT_TRUE( t.contains( other_item( i.key() ), other_less() ) );
398 EXPECT_EQ( i.nFindCount, 0 );
399 ASSERT_TRUE( t.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
400 EXPECT_EQ( i.nFindCount, 1 );
401 ASSERT_TRUE( t.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
402 EXPECT_EQ( i.nFindCount, 2 );
405 switch ( i.key() % 6 ) {
407 ASSERT_FALSE( t.unlink( v ));
408 ASSERT_TRUE( t.unlink( i ));
409 ASSERT_FALSE( t.unlink( i ) );
412 ASSERT_TRUE( t.erase( i.key()));
413 ASSERT_FALSE( t.erase( i.key() ) );
416 ASSERT_TRUE( t.erase( v ));
417 ASSERT_FALSE( t.erase( v ) );
420 ASSERT_TRUE( t.erase_with( other_item( i.key()), other_less()));
421 ASSERT_FALSE( t.erase_with( other_item( i.key() ), other_less() ) );
424 EXPECT_EQ( i.nEraseCount, 0 );
425 ASSERT_TRUE( t.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
426 EXPECT_EQ( i.nEraseCount, 1 );
427 ASSERT_FALSE( t.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
428 EXPECT_EQ( i.nEraseCount, 1 );
431 EXPECT_EQ( i.nEraseCount, 0 );
432 ASSERT_TRUE( t.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
433 EXPECT_EQ( i.nEraseCount, 1 );
434 ASSERT_FALSE( t.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
435 EXPECT_EQ( i.nEraseCount, 1 );
439 ASSERT_FALSE( t.contains( i.nKey ));
440 ASSERT_FALSE( t.contains( i ));
441 ASSERT_FALSE( t.contains( other_item( i.key()), other_less()));
442 ASSERT_FALSE( t.find( i.nKey, []( value_type&, int ) {} ));
443 ASSERT_FALSE( t.find( i, []( value_type&, value_type const& ) {} ));
444 ASSERT_FALSE( t.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
446 ASSERT_TRUE( t.empty() );
447 ASSERT_CONTAINER_SIZE( t, 0 );
449 // Force retiring cycle
450 Tree::gc::force_dispose();
451 for ( auto& i : data ) {
452 EXPECT_EQ( i.nDisposeCount, 1 );
456 for ( auto idx : indices ) {
459 ASSERT_TRUE( t.insert( i ));
461 ASSERT_FALSE( t.empty() );
462 ASSERT_CONTAINER_SIZE( t, nTreeSize );
467 ASSERT_TRUE( t.empty());
468 ASSERT_CONTAINER_SIZE( t, 0 );
470 // Force retiring cycle
471 Tree::gc::force_dispose();
472 for ( auto& i : data ) {
473 EXPECT_EQ( i.nDisposeCount, 1 );
478 } // namespace cds_test
480 #endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_TREE_H