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_TREE_SET_H
32 #define CDSUNIT_SET_TEST_TREE_SET_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
37 // forward declaration
38 namespace cds { namespace container {}}
42 class container_tree_set : public fixture
45 static size_t const kSize = 1000;
49 unsigned int nFindCount;
50 unsigned int nUpdateNewCount;
51 unsigned int nUpdateCount;
52 mutable unsigned int nEraseCount;
61 memset( this, 0, sizeof( *this ) );
68 explicit other_item( int k )
78 struct int_item: public stat
89 explicit int_item( int k )
95 explicit int_item( Q const& src )
100 int_item( int_item const& src )
103 , strVal( src.strVal )
106 int_item( int_item&& src )
109 , strVal( std::move( src.strVal ) )
112 int_item( int k, std::string&& s )
115 , strVal( std::move( s ) )
118 explicit int_item( other_item const& s )
120 , nVal( s.key() * 2 )
131 template <typename T>
132 void operator()( int& key, T const& val ) const
138 struct simple_item_counter {
141 simple_item_counter()
160 operator size_t() const
169 bool operator ()( int_item const& v1, int_item const& v2 ) const
171 return v1.key() < v2.key();
174 bool operator()( int lhs, int rhs ) const
179 template <typename Q>
180 bool operator ()( int_item const& v1, const Q& v2 ) const
182 return v1.key() < v2;
185 template <typename Q>
186 bool operator ()( const Q& v1, int_item const& v2 ) const
188 return v1 < v2.key();
193 int operator ()( int_item const& v1, int_item const& v2 ) const
195 if ( v1.key() < v2.key() )
197 return v1.key() > v2.key() ? 1 : 0;
200 int operator()( int lhs, int rhs ) const
205 template <typename T>
206 int operator ()( T const& v1, int v2 ) const
210 return v1.key() > v2 ? 1 : 0;
213 template <typename T>
214 int operator ()( int v1, T const& v2 ) const
218 return v1 > v2.key() ? 1 : 0;
223 template <typename Q, typename T>
224 bool operator()( Q const& lhs, T const& rhs ) const
226 return lhs.key() < rhs.key();
229 bool operator()( int lhs, other_item const& rhs ) const
231 return lhs < rhs.key();
234 bool operator()( other_item const& lhs, int rhs ) const
236 return lhs.key() < rhs;
241 template <typename Set>
244 // Precondition: set is empty
245 // Postcondition: set is empty
247 ASSERT_TRUE( s.empty() );
248 ASSERT_CONTAINER_SIZE( s, 0 );
249 size_t const nSetSize = kSize;
251 typedef typename Set::value_type value_type;
253 std::vector< value_type > data;
254 std::vector< size_t> indices;
255 data.reserve( kSize );
256 indices.reserve( kSize );
257 for ( size_t key = 0; key < kSize; ++key ) {
258 data.push_back( value_type( static_cast<int>(key) ) );
259 indices.push_back( key );
261 shuffle( indices.begin(), indices.end() );
264 for ( auto idx : indices ) {
267 ASSERT_FALSE( s.contains( i.nKey ) );
268 ASSERT_FALSE( s.contains( i ) );
269 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
270 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
271 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
272 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
274 std::pair<bool, bool> updResult;
277 updResult = s.update( i.key(), []( bool bNew, value_type&, int )
279 ASSERT_TRUE( false );
281 EXPECT_FALSE( updResult.first );
282 EXPECT_FALSE( updResult.second );
286 ASSERT_TRUE( s.insert( i ));
287 ASSERT_FALSE( s.insert( i ));
288 updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg)
290 EXPECT_FALSE( bNew );
291 EXPECT_EQ( val.key(), arg.key() );
293 EXPECT_TRUE( updResult.first );
294 EXPECT_FALSE( updResult.second );
297 ASSERT_TRUE( s.insert( i.key() ));
298 ASSERT_FALSE( s.insert( i.key() ));
299 updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg)
301 EXPECT_FALSE( bNew );
302 EXPECT_EQ( val.key(), arg );
304 EXPECT_TRUE( updResult.first );
305 EXPECT_FALSE( updResult.second );
308 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
309 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
310 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
312 EXPECT_EQ( v.key(), key );
313 EXPECT_EQ( v.nFindCount, 1 );
317 ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
318 ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
319 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
321 EXPECT_EQ( v.key(), key );
322 EXPECT_EQ( v.nFindCount, 1 );
326 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
329 EXPECT_EQ( v.key(), arg.key() );
332 EXPECT_TRUE( updResult.first );
333 EXPECT_TRUE( updResult.second );
335 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
337 EXPECT_FALSE( bNew );
338 EXPECT_EQ( v.key(), arg.key() );
341 EXPECT_TRUE( updResult.first );
342 EXPECT_FALSE( updResult.second );
344 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
346 EXPECT_EQ( v.key(), key );
347 EXPECT_EQ( v.nUpdateNewCount, 2 );
351 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
354 EXPECT_EQ( v.key(), arg );
357 EXPECT_TRUE( updResult.first );
358 EXPECT_TRUE( updResult.second );
360 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
362 EXPECT_FALSE( bNew );
363 EXPECT_EQ( v.key(), arg );
366 EXPECT_TRUE( updResult.first );
367 EXPECT_FALSE( updResult.second );
369 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
371 EXPECT_EQ( v.key(), arg.key() );
372 EXPECT_EQ( v.nUpdateNewCount, 2 );
376 ASSERT_TRUE( s.emplace( i.key()));
377 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
379 EXPECT_EQ( v.key(), arg.key() );
380 EXPECT_EQ( v.nVal, arg.nVal );
385 ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
386 EXPECT_TRUE( str.empty());
387 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
389 EXPECT_EQ( v.key(), arg.key() );
390 EXPECT_EQ( v.nVal, arg.nVal );
391 EXPECT_EQ( v.strVal, std::string( "Hello!" ));
395 // forgot anything?..
396 ASSERT_TRUE( false );
399 ASSERT_TRUE( s.contains( i.nKey ) );
400 ASSERT_TRUE( s.contains( i ) );
401 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
402 ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) );
403 ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) );
404 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type&, other_item const& ) {} ) );
407 ASSERT_FALSE( s.empty() );
408 ASSERT_CONTAINER_SIZE( s, nSetSize );
410 ASSERT_TRUE( s.check_consistency());
413 shuffle( indices.begin(), indices.end() );
414 for ( auto idx : indices ) {
417 ASSERT_TRUE( s.contains( i.nKey ) );
418 ASSERT_TRUE( s.contains( i ) );
419 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
420 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int )
424 ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& )
426 EXPECT_EQ( ++v.nFindCount, 2 );
428 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& )
430 EXPECT_EQ( ++v.nFindCount, 3 );
433 int nKey = i.key() - 1;
436 ASSERT_TRUE( s.erase( i.key()));
437 ASSERT_FALSE( s.erase( i.key()));
440 ASSERT_TRUE( s.erase( i ));
441 ASSERT_FALSE( s.erase( i ));
444 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
445 ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
448 ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
452 EXPECT_EQ( i.key(), nKey );
455 ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
459 EXPECT_EQ( i.key(), nKey + 1 );
462 ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v )
466 EXPECT_EQ( i.key(), nKey );
469 ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v )
473 EXPECT_EQ( i.key(), nKey + 1 );
476 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
480 EXPECT_EQ( i.key(), nKey );
483 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
487 EXPECT_EQ( i.key(), nKey + 1 );
491 ASSERT_FALSE( s.contains( i.nKey ) );
492 ASSERT_FALSE( s.contains( i ) );
493 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
494 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
495 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
496 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
498 ASSERT_TRUE( s.empty() );
499 ASSERT_CONTAINER_SIZE( s, 0 );
503 for ( auto& i : data ) {
504 ASSERT_TRUE( s.insert( i ) );
507 ASSERT_FALSE( s.empty() );
508 ASSERT_CONTAINER_SIZE( s, nSetSize );
512 ASSERT_TRUE( s.empty() );
513 ASSERT_CONTAINER_SIZE( s, 0 );
517 } // namespace cds_test
519 #endif // CDSUNIT_SET_TEST_TREE_SET_H