2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_STRIPED_SET_TEST_SET_H
32 #define CDSUNIT_STRIPED_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;
70 memset( this, 0, sizeof( *this ));
73 void copy_stat( stat const& s )
75 memcpy( this, &s, sizeof( *this ));
82 explicit other_item( int k )
92 struct int_item: public stat
103 explicit int_item( int k )
108 template <typename Q>
109 explicit int_item( Q const& src )
114 int_item( int_item const& src )
118 , strVal( src.strVal )
121 int_item( int_item&& src )
125 , strVal( std::move( src.strVal ))
128 int_item( int k, std::string&& s )
131 , strVal( std::move( s ))
134 explicit int_item( other_item const& s )
136 , nVal( s.key() * 2 )
139 int_item& operator=( int_item const& src )
141 if ( &src != this ) {
150 int_item& operator=( int_item&& src )
152 if ( &src != this ) {
156 strVal = std::move( src.strVal );
168 size_t operator()( int i ) const
170 return co::v::hash<int>()(i);
172 template <typename Item>
173 size_t operator()( const Item& i ) const
175 return (*this)(i.key());
179 struct hash2: private hash1
181 typedef hash1 base_class;
183 size_t operator()( int i ) const
185 size_t h = ~(base_class::operator()( i ));
186 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
188 template <typename Item>
189 size_t operator()( const Item& i ) const
191 size_t h = ~(base_class::operator()( i ));
192 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
198 bool operator ()( int_item const& v1, int_item const& v2 ) const
200 return v1.key() < v2.key();
203 template <typename Q>
204 bool operator ()( int_item const& v1, const Q& v2 ) const
206 return v1.key() < v2;
209 template <typename Q>
210 bool operator ()( const Q& v1, int_item const& v2 ) const
212 return v1 < v2.key();
218 bool operator ()( int_item const& v1, int_item const& v2 ) const
220 return v1.key() == v2.key();
223 template <typename Q>
224 bool operator ()( int_item const& v1, const Q& v2 ) const
226 return v1.key() == v2;
229 template <typename Q>
230 bool operator ()( const Q& v1, int_item const& v2 ) const
232 return v1 == v2.key();
237 int operator ()( int_item const& v1, int_item const& v2 ) const
239 if ( v1.key() < v2.key())
241 return v1.key() > v2.key() ? 1 : 0;
244 template <typename T>
245 int operator ()( T const& v1, int v2 ) const
249 return v1.key() > v2 ? 1 : 0;
252 template <typename T>
253 int operator ()( int v1, T const& v2 ) const
257 return v1 > v2.key() ? 1 : 0;
262 template <typename Q, typename T>
263 bool operator()( Q const& lhs, T const& rhs ) const
265 return lhs.key() < rhs.key();
269 struct other_equal_to {
270 template <typename Q, typename T>
271 bool operator()( Q const& lhs, T const& rhs ) const
273 return lhs.key() == rhs.key();
278 template <typename Set>
284 template <bool Sorted, typename Set>
287 // Precondition: set is empty
288 // Postcondition: set is empty
290 ASSERT_TRUE( s.empty());
291 ASSERT_CONTAINER_SIZE( s, 0 );
292 size_t const nSetSize = kSize;
294 typedef typename Set::value_type value_type;
295 typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate;
297 std::vector< value_type > data;
298 std::vector< size_t> indices;
299 data.reserve( kSize );
300 indices.reserve( kSize );
301 for ( size_t key = 0; key < kSize; ++key ) {
302 data.push_back( value_type( static_cast<int>(key)));
303 indices.push_back( key );
305 shuffle( indices.begin(), indices.end());
308 for ( auto idx : indices ) {
311 ASSERT_FALSE( s.contains( i.nKey ));
312 ASSERT_FALSE( s.contains( i ));
313 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
314 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
315 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
316 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
318 std::pair<bool, bool> updResult;
321 updResult = s.update( i.key(), []( bool /*bNew*/, value_type&, int )
323 ASSERT_TRUE( false );
325 EXPECT_FALSE( updResult.first );
326 EXPECT_FALSE( updResult.second );
330 ASSERT_TRUE( s.insert( i ));
331 ASSERT_FALSE( s.insert( i ));
332 updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg)
334 EXPECT_FALSE( bNew );
335 EXPECT_EQ( val.key(), arg.key());
337 EXPECT_TRUE( updResult.first );
338 EXPECT_FALSE( updResult.second );
341 ASSERT_TRUE( s.insert( i.key()));
342 ASSERT_FALSE( s.insert( i.key()));
343 updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg)
345 EXPECT_FALSE( bNew );
346 EXPECT_EQ( val.key(), arg );
348 EXPECT_TRUE( updResult.first );
349 EXPECT_FALSE( updResult.second );
352 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
353 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
354 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
356 EXPECT_EQ( v.key(), key );
357 EXPECT_EQ( v.nFindCount, 1u );
361 ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
362 ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
363 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
365 EXPECT_EQ( v.key(), key );
366 EXPECT_EQ( v.nFindCount, 1u );
370 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
373 EXPECT_EQ( v.key(), arg.key());
376 EXPECT_TRUE( updResult.first );
377 EXPECT_TRUE( updResult.second );
379 updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
381 EXPECT_FALSE( bNew );
382 EXPECT_EQ( v.key(), arg.key());
385 EXPECT_TRUE( updResult.first );
386 EXPECT_FALSE( updResult.second );
388 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
390 EXPECT_EQ( v.key(), key );
391 EXPECT_EQ( v.nUpdateNewCount, 2u );
395 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
398 EXPECT_EQ( v.key(), arg );
401 EXPECT_TRUE( updResult.first );
402 EXPECT_TRUE( updResult.second );
404 updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
406 EXPECT_FALSE( bNew );
407 EXPECT_EQ( v.key(), arg );
410 EXPECT_TRUE( updResult.first );
411 EXPECT_FALSE( updResult.second );
413 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
415 EXPECT_EQ( v.key(), arg.key());
416 EXPECT_EQ( v.nUpdateNewCount, 2u );
420 ASSERT_TRUE( s.emplace( i.key()));
421 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
423 EXPECT_EQ( v.key(), arg.key());
424 EXPECT_EQ( v.nVal, arg.nVal );
429 ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
430 EXPECT_TRUE( str.empty());
431 ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
433 EXPECT_EQ( v.key(), arg.key());
434 EXPECT_EQ( v.nVal, arg.nVal );
435 EXPECT_EQ( v.strVal, std::string( "Hello!" ));
439 // forgot anything?..
440 ASSERT_TRUE( false );
443 ASSERT_TRUE( s.contains( i.nKey ));
444 ASSERT_TRUE( s.contains( i ));
445 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
446 ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ));
447 ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ));
448 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
451 ASSERT_FALSE( s.empty());
452 ASSERT_CONTAINER_SIZE( s, nSetSize );
455 shuffle( indices.begin(), indices.end());
456 for ( auto idx : indices ) {
459 ASSERT_TRUE( s.contains( i.nKey ));
460 ASSERT_TRUE( s.contains( i ));
461 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
462 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int )
466 ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& )
468 EXPECT_EQ( ++v.nFindCount, 2u );
470 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type& v, other_item const& )
472 EXPECT_EQ( ++v.nFindCount, 3u );
475 int nKey = i.key() - 1;
478 ASSERT_TRUE( s.erase( i.key()));
479 ASSERT_FALSE( s.erase( i.key()));
482 ASSERT_TRUE( s.erase( i ));
483 ASSERT_FALSE( s.erase( i ));
486 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate()));
487 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate()));
490 ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
494 EXPECT_EQ( i.key(), nKey );
497 ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
501 EXPECT_EQ( i.key(), nKey + 1 );
504 ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v )
508 EXPECT_EQ( i.key(), nKey );
511 ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v )
515 EXPECT_EQ( i.key(), nKey + 1 );
518 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate(), [&nKey]( value_type const& v )
522 EXPECT_EQ( i.key(), nKey );
525 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate(), [&nKey]( value_type const& v )
529 EXPECT_EQ( i.key(), nKey + 1 );
533 ASSERT_FALSE( s.contains( i.nKey ));
534 ASSERT_FALSE( s.contains( i ));
535 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
536 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
537 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
538 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
540 ASSERT_TRUE( s.empty());
541 ASSERT_CONTAINER_SIZE( s, 0u );
545 for ( auto& i : data ) {
546 ASSERT_TRUE( s.insert( i ));
549 ASSERT_FALSE( s.empty());
550 ASSERT_CONTAINER_SIZE( s, nSetSize );
554 ASSERT_TRUE( s.empty());
555 ASSERT_CONTAINER_SIZE( s, 0u );
559 } // namespace cds_test
561 #endif // CDSUNIT_STRIPED_SET_TEST_SET_H