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 cc = cds::container;
45 namespace co = cds::opt;
47 class container_set : public fixture
50 static size_t const kSize = 100;
54 unsigned int nFindCount;
55 unsigned int nUpdateNewCount;
56 unsigned int nUpdateCount;
57 mutable unsigned int nEraseCount;
66 memset( this, 0, sizeof( *this ) );
73 explicit other_item( int k )
94 explicit int_item( int k )
100 explicit int_item( Q const& src )
105 int_item( int_item const& src )
108 , strVal( src.strVal )
111 int_item( int_item&& src )
114 , strVal( std::move( src.strVal ) )
117 int_item( int k, std::string&& s )
120 , strVal( std::move( s ) )
123 explicit int_item( other_item const& s )
125 , nVal( s.key() * 2 )
135 size_t operator()( int i ) const
137 return co::v::hash<int>()(i);
139 template <typename Item>
140 size_t operator()( const Item& i ) const
142 return (*this)(i.key());
146 struct simple_item_counter {
149 simple_item_counter()
168 operator size_t() const
177 bool operator ()( int_item const& v1, int_item const& v2 ) const
179 return v1.key() < v2.key();
182 template <typename Q>
183 bool operator ()( int_item const& v1, const Q& v2 ) const
185 return v1.key() < v2;
188 template <typename Q>
189 bool operator ()( const Q& v1, int_item const& v2 ) const
191 return v1 < v2.key();
196 int operator ()( int_item const& v1, int_item const& v2 ) const
198 if ( v1.key() < v2.key() )
200 return v1.key() > v2.key() ? 1 : 0;
203 template <typename T, typename Q>
204 int operator ()( T const& v1, const Q& v2 ) const
208 return v1.key() > v2 ? 1 : 0;
211 template <typename T, typename Q>
212 int operator ()( const Q& v1, T const& v2 ) const
216 return v1 > v2.key() ? 1 : 0;
221 template <typename Q, typename T>
222 bool operator()( Q const& lhs, T const& rhs ) const
224 return lhs.key() < rhs.key();
229 template <typename Set>
232 // Precondition: set is empty
233 // Postcondition: set is empty
235 ASSERT_TRUE( s.empty() );
236 ASSERT_CONTAINER_SIZE( s, 0 );
237 size_t const nSetSize = kSize;
239 typedef typename Set::value_type value_type;
241 std::vector< value_type > data;
242 std::vector< size_t> indices;
243 data.reserve( kSize );
244 indices.reserve( kSize );
245 for ( size_t key = 0; key < kSize; ++key ) {
246 data.push_back( value_type( static_cast<int>(key) ) );
247 indices.push_back( key );
249 shuffle( indices.begin(), indices.end() );
252 for ( auto idx : indices ) {
255 ASSERT_FALSE( s.contains( i.nKey ) );
256 ASSERT_FALSE( s.contains( i ) );
257 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
258 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
259 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
260 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
262 std::pair<bool, bool> updResult;
265 updResult = s.update( i.key(), []( bool bNew, value_type&, int )
267 ASSERT_TRUE( false );
269 EXPECT_FALSE( updResult.first );
270 EXPECT_FALSE( updResult.second );
274 ASSERT_TRUE( s.insert( i ));
275 ASSERT_FALSE( s.insert( i ));
276 updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg)
278 EXPECT_FALSE( bNew );
279 EXPECT_EQ( &val, &arg );
281 EXPECT_TRUE( updResult.first );
282 EXPECT_FALSE( updResult.second );
285 ASSERT_TRUE( s.insert( i.key() ));
286 ASSERT_FALSE( s.insert( i.key() ));
287 updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg)
289 EXPECT_FALSE( bNew );
290 EXPECT_EQ( &val, &arg );
292 EXPECT_TRUE( updResult.first );
293 EXPECT_FALSE( updResult.second );
296 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
297 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
298 ASSERT_TRUE( s.find( i.nKey, []( value_type const& V, int key )
300 EXPECT_EQ( v.key(), key );
301 EXPECT_EQ( v.nFindCount, 1 );
305 ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
306 ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
307 ASSERT_TRUE( s.find( i.nKey, []( value_type const& V, int key )
309 EXPECT_EQ( v.key(), key );
310 EXPECT_EQ( v.nFindCount, 1 );
314 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
317 EXPECT_EQ( v.key(), arg.key() );
320 EXPECT_TRUE( updResult.first );
321 EXPECT_TRUE( updResult.second );
323 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
326 EXPECT_EQ( v.key(), arg.key() );
329 EXPECT_TRUE( updResult.first );
330 EXPECT_FALSE( updResult.second );
332 ASSERT_TRUE( s.find( i.nKey, []( value_type const& V, int key )
334 EXPECT_EQ( v.key(), key );
335 EXPECT_EQ( v.nFindCount, 2 );
339 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
342 EXPECT_EQ( v.key(), arg );
345 EXPECT_TRUE( updResult.first );
346 EXPECT_TRUE( updResult.second );
348 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
351 EXPECT_EQ( v.key(), arg );
354 EXPECT_TRUE( updResult.first );
355 EXPECT_FALSE( updResult.second );
357 ASSERT_TRUE( s.find( i, []( value_type const& V, value_type const& arg )
359 EXPECT_EQ( v.key(), arg.key() );
360 EXPECT_EQ( v.nFindCount, 2 );
364 ASSERT_TRUE( s.emplace( i.key()));
365 ASSERT_TRUE( s.find( i, []( value_type const& V, value_type const& arg )
367 EXPECT_EQ( v.key(), arg.key() );
368 EXPECT_EQ( v.nVal, arg.nVal );
373 ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
374 EXPECT_TRUE( str.empty());
375 ASSERT_TRUE( s.find( i, []( value_type const& V, value_type const& arg )
377 EXPECT_EQ( v.key(), arg.key() );
378 EXPECT_EQ( v.nVal, arg.nVal );
379 EXPECT_EQ( v.strVal, std::string( "Hello!" ));
383 // forgot anything?..
384 ASSERT_TRUE( false );
387 ASSERT_TRUE( s.contains( i.nKey ) );
388 ASSERT_TRUE( s.contains( i ) );
389 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
390 ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) );
391 ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) );
392 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type&, other_item const& ) {} ) );
395 ASSERT_FALSE( s.empty() );
396 ASSERT_CONTAINER_SIZE( s, nSetSize );
399 shuffle( indices.begin(), indices.end() );
400 for ( auto idx : indices ) {
403 ASSERT_TRUE( s.contains( i.nKey ) );
404 ASSERT_TRUE( s.contains( i ) );
405 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
406 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int )
410 ASSERT_TRUE( s.find( i, []( value_type& v, int )
412 EXPECT_EQ( ++v.nFindCount, 2 );
414 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& )
416 EXPECT_EQ( ++v.nFindCount, 3 );
418 EXPECT_EQ( i.nFindCount, 2 );
420 int nKey = i.key() - 1;
423 ASSERT_TRUE( s.erase( i.key()));
424 ASSERT_FALSE( s.erase( i.key()));
427 ASSERT_TRUE( s.erase( i ));
428 ASSERT_FALSE( s.erase( i ));
431 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
432 ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
435 ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
439 EXPECT_EQ( i.key(), nKey );
442 ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
446 EXPECT_EQ( i.key(), nKey + 1 );
449 ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v )
453 EXPECT_EQ( i.key(), nKey );
456 ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v )
460 EXPECT_EQ( i.key(), nKey + 1 );
463 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
467 EXPECT_EQ( i.key(), nKey );
470 ASSERT_FALSE( s.erase( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
474 EXPECT_EQ( i.key(), nKey + 1 );
478 ASSERT_FALSE( s.contains( i.nKey ) );
479 ASSERT_FALSE( s.contains( i ) );
480 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
481 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
482 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
483 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
485 ASSERT_TRUE( s.empty() );
486 ASSERT_CONTAINER_SIZE( s, 0 );
490 for ( auto& i : data ) {
491 ASSERT_TRUE( s.insert( i ) );
494 ASSERT_FALSE( s.empty() );
495 ASSERT_CONTAINER_SIZE( s, nSetSize );
499 ASSERT_TRUE( s.empty() );
500 ASSERT_CONTAINER_SIZE( s, 0 );
502 ASSERT_TRUE( s.begin() == s.end() );
503 ASSERT_TRUE( s.cbegin() == s.cend() );
507 } // namespace cds_test
509 #endif // CDSUNIT_SET_TEST_SET_H