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_SET_TEST_FELDMAN_HASHSET_H
32 #define CDSUNIT_SET_TEST_FELDMAN_HASHSET_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
37 #include <cds/opt/hash.h>
39 // forward declaration
40 namespace cds { namespace container {}}
41 namespace co = cds::opt;
42 namespace cc = cds::container;
46 class feldman_hashset : public fixture
49 static size_t const kSize = 1000;
53 unsigned int nFindCount;
54 unsigned int nUpdateNewCount;
55 unsigned int nUpdateCount;
64 memset( this, 0, sizeof( *this ));
71 explicit other_item( int k )
81 struct int_item: public stat
92 explicit int_item( int k )
98 explicit int_item( Q const& src )
103 int_item( int_item const& src )
106 , strVal( src.strVal )
109 int_item( int_item&& src )
112 , strVal( std::move( src.strVal ))
115 int_item( int k, std::string&& s )
118 , strVal( std::move( s ))
121 explicit int_item( other_item const& s )
123 , nVal( s.key() * 2 )
144 key_val( int key, int val )
149 key_val( key_val const& v )
160 struct int_item2: public key_val, public stat
167 explicit int_item2( int key )
171 int_item2( int key, int val )
172 : key_val( key, val )
175 int_item2( int_item2 const& v )
181 int_item2( int_item2&& v )
184 , strVal( std::move( v.strVal ))
187 int_item2( int k, std::string&& s )
188 : key_val( k, k * 2 )
189 , strVal( std::move( s ))
192 explicit int_item2( other_item const& s )
193 : key_val( s.key(), s.key() * 2 )
199 int operator()( int_item const& i ) const
204 int operator()( other_item const& i ) const
209 int operator()( int i ) const
216 key_val const& operator()( int_item2 const& i ) const
221 key_val operator()( other_item const& i ) const
223 return key_val( i.key());
226 key_val operator()( int i ) const
232 struct simple_item_counter {
235 simple_item_counter()
254 operator size_t() const
262 int operator ()( int v1, int v2 ) const
266 return v1 > v2 ? 1 : 0;
271 int operator ()( key_val const& v1, key_val const& v2 ) const
273 if ( v1.key() < v2.key())
275 return v1.key() > v2.key() ? 1 : 0;
280 template <typename Q, typename T>
281 bool operator()( Q const& lhs, T const& rhs ) const
283 return lhs.key() < rhs.key();
288 template <typename Set>
291 // Precondition: set is empty
292 // Postcondition: set is empty
294 ASSERT_TRUE( s.empty());
295 ASSERT_CONTAINER_SIZE( s, 0 );
296 size_t const nSetSize = kSize;
298 typedef typename Set::value_type value_type;
300 std::vector< value_type > data;
301 std::vector< size_t> indices;
302 data.reserve( kSize );
303 indices.reserve( kSize );
304 for ( size_t key = 0; key < kSize; ++key ) {
305 data.push_back( value_type( static_cast<int>(key)));
306 indices.push_back( key );
308 shuffle( indices.begin(), indices.end());
311 for ( auto idx : indices ) {
314 ASSERT_FALSE( s.contains( i.nKey ));
315 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
317 std::pair<bool, bool> updResult;
320 updResult = s.update( i.key(), []( value_type&, value_type * )
322 ASSERT_TRUE( false );
324 EXPECT_FALSE( updResult.first );
325 EXPECT_FALSE( updResult.second );
329 ASSERT_TRUE( s.insert( i ));
330 ASSERT_FALSE( s.insert( i ));
331 updResult = s.update( i, []( value_type& val, value_type * prev )
333 ASSERT_TRUE( prev != nullptr );
334 EXPECT_EQ( val.key(), prev->key());
336 EXPECT_TRUE( updResult.first );
337 EXPECT_FALSE( updResult.second );
340 ASSERT_TRUE( s.insert( i.key()));
341 ASSERT_FALSE( s.insert( i.key()));
342 updResult = s.update( i.key(), []( value_type& val, value_type * prev )
344 ASSERT_TRUE( prev != nullptr );
345 EXPECT_EQ( val.key(), prev->key());
347 EXPECT_TRUE( updResult.first );
348 EXPECT_FALSE( updResult.second );
351 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
352 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
353 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
355 EXPECT_EQ( v.nFindCount, 1u );
359 ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
360 ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
361 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
363 EXPECT_EQ( v.nFindCount, 1u );
367 updResult = s.update( i, []( value_type& v, value_type * prev )
369 EXPECT_TRUE( prev == nullptr );
372 EXPECT_TRUE( updResult.first );
373 EXPECT_TRUE( updResult.second );
375 updResult = s.update( i, []( value_type& v, value_type * prev )
377 ASSERT_TRUE( prev != nullptr );
378 EXPECT_EQ( prev->nUpdateNewCount, 1u );
379 EXPECT_EQ( v.key(), prev->key());
382 EXPECT_TRUE( updResult.first );
383 EXPECT_FALSE( updResult.second );
385 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
387 EXPECT_EQ( v.nUpdateCount, 1u );
388 EXPECT_EQ( v.nUpdateNewCount, 0u );
392 updResult = s.update( i.key(), []( value_type& v, value_type * prev )
394 EXPECT_TRUE( prev == nullptr );
397 EXPECT_TRUE( updResult.first );
398 EXPECT_TRUE( updResult.second );
400 updResult = s.update( i.key(), []( value_type& v, value_type * prev )
402 ASSERT_TRUE( prev != nullptr );
403 EXPECT_EQ( v.key(), prev->key());
404 EXPECT_EQ( prev->nUpdateNewCount, 1u );
405 EXPECT_EQ( v.nUpdateNewCount, 0u );
408 EXPECT_TRUE( updResult.first );
409 EXPECT_FALSE( updResult.second );
411 ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
413 EXPECT_EQ( v.nUpdateNewCount, 1u );
417 ASSERT_TRUE( s.emplace( i.key()));
418 ASSERT_TRUE( s.contains( i.key()));
422 ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
423 EXPECT_TRUE( str.empty());
424 ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
426 EXPECT_EQ( v.strVal, std::string( "Hello!" ));
430 // forgot anything?..
431 ASSERT_TRUE( false );
434 ASSERT_TRUE( s.contains( i.nKey ));
435 ASSERT_TRUE( s.find( i.nKey, []( value_type& ) {} ));
438 ASSERT_FALSE( s.empty());
439 ASSERT_CONTAINER_SIZE( s, nSetSize );
442 shuffle( indices.begin(), indices.end());
443 for ( auto idx : indices ) {
446 ASSERT_TRUE( s.contains( i.nKey ));
447 ASSERT_TRUE( s.find( i.nKey, []( value_type& v )
452 int nKey = i.key() - 1;
455 ASSERT_TRUE( s.erase( i.key()));
456 ASSERT_FALSE( s.erase( i.key()));
459 ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
461 EXPECT_EQ( v.nFindCount, 1u );
464 EXPECT_EQ( i.key(), nKey );
467 ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
471 EXPECT_EQ( i.key(), nKey + 1 );
475 ASSERT_FALSE( s.contains( i.nKey ));
476 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ));
478 ASSERT_TRUE( s.empty());
479 ASSERT_CONTAINER_SIZE( s, 0u );
483 for ( auto& i : data ) {
484 ASSERT_TRUE( s.insert( i ));
488 typename Set::stat const& statistics = s.statistics();
489 CDS_UNUSED( statistics );
491 std::vector< typename Set::level_statistics > lstat;
492 s.get_level_statistics( lstat );
493 EXPECT_EQ( lstat[0].node_capacity, s.head_size());
494 for ( size_t i = 1; i < lstat.size(); ++i ) {
495 EXPECT_EQ( lstat[i].node_capacity, s.array_node_size());
499 ASSERT_FALSE( s.empty());
500 ASSERT_CONTAINER_SIZE( s, nSetSize );
504 ASSERT_TRUE( s.empty());
505 ASSERT_CONTAINER_SIZE( s, 0u );
507 ASSERT_TRUE( s.begin() == s.end());
508 ASSERT_TRUE( s.cbegin() == s.cend());
509 ASSERT_TRUE( s.rbegin() == s.rend());
510 ASSERT_TRUE( s.crbegin() == s.crend());
514 } // namespace cds_test
516 #endif // CDSUNIT_SET_TEST_FELDMAN_HASHSET_H