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_SET_H
32 #define CDSUNIT_SET_TEST_SET_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
37 #include <cds/opt/hash.h>
38 #include <functional> // ref
40 // forward declaration
41 namespace cds { namespace container {}}
44 namespace co = cds::opt;
46 class container_set : public fixture
49 static size_t const kSize = 1000;
53 unsigned int nFindCount;
54 unsigned int nUpdateNewCount;
55 unsigned int nUpdateCount;
56 mutable unsigned int nEraseCount;
65 memset( this, 0, sizeof( *this ) );
72 explicit other_item( int k )
82 struct int_item: public stat
93 explicit int_item( int k )
99 explicit int_item( Q const& src )
104 int_item( int_item const& src )
107 , strVal( src.strVal )
110 int_item( int_item&& src )
113 , strVal( std::move( src.strVal ) )
116 int_item( int k, std::string&& s )
119 , strVal( std::move( s ) )
122 explicit int_item( other_item const& s )
124 , nVal( s.key() * 2 )
134 size_t operator()( int i ) const
136 return co::v::hash<int>()(i);
138 template <typename Item>
139 size_t operator()( const Item& i ) const
141 return (*this)(i.key());
145 struct simple_item_counter {
148 simple_item_counter()
167 operator size_t() const
176 bool operator ()( int_item const& v1, int_item const& v2 ) const
178 return v1.key() < v2.key();
181 template <typename Q>
182 bool operator ()( int_item const& v1, const Q& v2 ) const
184 return v1.key() < v2;
187 template <typename Q>
188 bool operator ()( const Q& v1, int_item const& v2 ) const
190 return v1 < v2.key();
195 int operator ()( int_item const& v1, int_item const& v2 ) const
197 if ( v1.key() < v2.key() )
199 return v1.key() > v2.key() ? 1 : 0;
202 template <typename T>
203 int operator ()( T const& v1, int v2 ) const
207 return v1.key() > v2 ? 1 : 0;
210 template <typename T>
211 int operator ()( int v1, T const& v2 ) const
215 return v1 > v2.key() ? 1 : 0;
220 template <typename Q, typename T>
221 bool operator()( Q const& lhs, T const& rhs ) const
223 return lhs.key() < rhs.key();
228 template <typename Set>
231 // Precondition: set is empty
232 // Postcondition: set is empty
234 ASSERT_TRUE( s.empty() );
235 ASSERT_CONTAINER_SIZE( s, 0 );
236 size_t const nSetSize = kSize;
238 typedef typename Set::value_type value_type;
240 std::vector< value_type > data;
241 std::vector< size_t> indices;
242 data.reserve( kSize );
243 indices.reserve( kSize );
244 for ( size_t key = 0; key < kSize; ++key ) {
245 data.push_back( value_type( static_cast<int>(key) ) );
246 indices.push_back( key );
248 shuffle( indices.begin(), indices.end() );
251 for ( auto idx : indices ) {
254 ASSERT_FALSE( s.contains( i.nKey ) );
255 ASSERT_FALSE( s.contains( i ) );
256 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
257 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
258 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
259 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
261 std::pair<bool, bool> updResult;
264 updResult = s.update( i.key(), []( bool bNew, value_type&, int )
266 ASSERT_TRUE( false );
268 EXPECT_FALSE( updResult.first );
269 EXPECT_FALSE( updResult.second );
273 ASSERT_TRUE( s.insert( i ));
274 ASSERT_FALSE( s.insert( i ));
275 updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg)
277 EXPECT_FALSE( bNew );
278 EXPECT_EQ( val.key(), arg.key() );
280 EXPECT_TRUE( updResult.first );
281 EXPECT_FALSE( updResult.second );
284 ASSERT_TRUE( s.insert( i.key() ));
285 ASSERT_FALSE( s.insert( i.key() ));
286 updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg)
288 EXPECT_FALSE( bNew );
289 EXPECT_EQ( val.key(), arg );
291 EXPECT_TRUE( updResult.first );
292 EXPECT_FALSE( updResult.second );
295 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
296 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
297 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
299 EXPECT_EQ( v.key(), key );
300 EXPECT_EQ( v.nFindCount, 1 );
304 ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
305 ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
306 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
308 EXPECT_EQ( v.key(), key );
309 EXPECT_EQ( v.nFindCount, 1 );
313 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
316 EXPECT_EQ( v.key(), arg.key() );
319 EXPECT_TRUE( updResult.first );
320 EXPECT_TRUE( updResult.second );
322 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
324 EXPECT_FALSE( bNew );
325 EXPECT_EQ( v.key(), arg.key() );
328 EXPECT_TRUE( updResult.first );
329 EXPECT_FALSE( updResult.second );
331 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
333 EXPECT_EQ( v.key(), key );
334 EXPECT_EQ( v.nUpdateNewCount, 2 );
338 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
341 EXPECT_EQ( v.key(), arg );
344 EXPECT_TRUE( updResult.first );
345 EXPECT_TRUE( updResult.second );
347 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
349 EXPECT_FALSE( bNew );
350 EXPECT_EQ( v.key(), arg );
353 EXPECT_TRUE( updResult.first );
354 EXPECT_FALSE( updResult.second );
356 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
358 EXPECT_EQ( v.key(), arg.key() );
359 EXPECT_EQ( v.nUpdateNewCount, 2 );
363 ASSERT_TRUE( s.emplace( i.key()));
364 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
366 EXPECT_EQ( v.key(), arg.key() );
367 EXPECT_EQ( v.nVal, arg.nVal );
372 ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
373 EXPECT_TRUE( str.empty());
374 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
376 EXPECT_EQ( v.key(), arg.key() );
377 EXPECT_EQ( v.nVal, arg.nVal );
378 EXPECT_EQ( v.strVal, std::string( "Hello!" ));
382 // forgot anything?..
383 ASSERT_TRUE( false );
386 ASSERT_TRUE( s.contains( i.nKey ) );
387 ASSERT_TRUE( s.contains( i ) );
388 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
389 ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) );
390 ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) );
391 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type&, other_item const& ) {} ) );
394 ASSERT_FALSE( s.empty() );
395 ASSERT_CONTAINER_SIZE( s, nSetSize );
398 shuffle( indices.begin(), indices.end() );
399 for ( auto idx : indices ) {
402 ASSERT_TRUE( s.contains( i.nKey ) );
403 ASSERT_TRUE( s.contains( i ) );
404 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
405 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int )
409 ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& )
411 EXPECT_EQ( ++v.nFindCount, 2 );
413 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& )
415 EXPECT_EQ( ++v.nFindCount, 3 );
418 int nKey = i.key() - 1;
421 ASSERT_TRUE( s.erase( i.key()));
422 ASSERT_FALSE( s.erase( i.key()));
425 ASSERT_TRUE( s.erase( i ));
426 ASSERT_FALSE( s.erase( i ));
429 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
430 ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
433 ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
437 EXPECT_EQ( i.key(), nKey );
440 ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
444 EXPECT_EQ( i.key(), nKey + 1 );
447 ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v )
451 EXPECT_EQ( i.key(), nKey );
454 ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v )
458 EXPECT_EQ( i.key(), nKey + 1 );
461 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
465 EXPECT_EQ( i.key(), nKey );
468 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
472 EXPECT_EQ( i.key(), nKey + 1 );
476 ASSERT_FALSE( s.contains( i.nKey ) );
477 ASSERT_FALSE( s.contains( i ) );
478 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
479 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
480 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
481 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
483 ASSERT_TRUE( s.empty() );
484 ASSERT_CONTAINER_SIZE( s, 0 );
488 for ( auto& i : data ) {
489 ASSERT_TRUE( s.insert( i ) );
492 ASSERT_FALSE( s.empty() );
493 ASSERT_CONTAINER_SIZE( s, nSetSize );
497 ASSERT_TRUE( s.empty() );
498 ASSERT_CONTAINER_SIZE( s, 0 );
500 ASSERT_TRUE( s.begin() == s.end() );
501 ASSERT_TRUE( s.cbegin() == s.cend() );
505 } // namespace cds_test
507 #endif // CDSUNIT_SET_TEST_SET_H