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_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 )
133 int operator()( int_item const& i ) const
138 int operator()( other_item const& i ) const
143 int operator()( int i ) const
149 struct simple_item_counter {
152 simple_item_counter()
171 operator size_t() const
179 int operator ()( int v1, int v2 ) const
183 return v1 > v2 ? 1 : 0;
188 template <typename Q, typename T>
189 bool operator()( Q const& lhs, T const& rhs ) const
191 return lhs.key() < rhs.key();
196 template <typename Set>
199 // Precondition: set is empty
200 // Postcondition: set is empty
202 ASSERT_TRUE( s.empty());
203 ASSERT_CONTAINER_SIZE( s, 0 );
204 size_t const nSetSize = kSize;
206 typedef typename Set::value_type value_type;
208 std::vector< value_type > data;
209 std::vector< size_t> indices;
210 data.reserve( kSize );
211 indices.reserve( kSize );
212 for ( size_t key = 0; key < kSize; ++key ) {
213 data.push_back( value_type( static_cast<int>(key)));
214 indices.push_back( key );
216 shuffle( indices.begin(), indices.end());
219 for ( auto idx : indices ) {
222 ASSERT_FALSE( s.contains( i.nKey ));
223 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
225 std::pair<bool, bool> updResult;
228 updResult = s.update( i.key(), []( value_type&, value_type * )
230 ASSERT_TRUE( false );
232 EXPECT_FALSE( updResult.first );
233 EXPECT_FALSE( updResult.second );
237 ASSERT_TRUE( s.insert( i ));
238 ASSERT_FALSE( s.insert( i ));
239 updResult = s.update( i, []( value_type& val, value_type * prev )
241 ASSERT_TRUE( prev != nullptr );
242 EXPECT_EQ( val.key(), prev->key());
244 EXPECT_TRUE( updResult.first );
245 EXPECT_FALSE( updResult.second );
248 ASSERT_TRUE( s.insert( i.key()));
249 ASSERT_FALSE( s.insert( i.key()));
250 updResult = s.update( i.key(), []( value_type& val, value_type * prev )
252 ASSERT_TRUE( prev != nullptr );
253 EXPECT_EQ( val.key(), prev->key());
255 EXPECT_TRUE( updResult.first );
256 EXPECT_FALSE( updResult.second );
259 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
260 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
261 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
263 EXPECT_EQ( v.nFindCount, 1u );
267 ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
268 ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
269 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
271 EXPECT_EQ( v.nFindCount, 1u );
275 updResult = s.update( i, []( value_type& v, value_type * prev )
277 EXPECT_TRUE( prev == nullptr );
280 EXPECT_TRUE( updResult.first );
281 EXPECT_TRUE( updResult.second );
283 updResult = s.update( i, []( value_type& v, value_type * prev )
285 ASSERT_TRUE( prev != nullptr );
286 EXPECT_EQ( prev->nUpdateNewCount, 1u );
287 EXPECT_EQ( v.key(), prev->key());
290 EXPECT_TRUE( updResult.first );
291 EXPECT_FALSE( updResult.second );
293 ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
295 EXPECT_EQ( v.nUpdateCount, 1u );
296 EXPECT_EQ( v.nUpdateNewCount, 0u );
300 updResult = s.update( i.key(), []( value_type& v, value_type * prev )
302 EXPECT_TRUE( prev == nullptr );
305 EXPECT_TRUE( updResult.first );
306 EXPECT_TRUE( updResult.second );
308 updResult = s.update( i.key(), []( value_type& v, value_type * prev )
310 ASSERT_TRUE( prev != nullptr );
311 EXPECT_EQ( v.key(), prev->key());
312 EXPECT_EQ( prev->nUpdateNewCount, 1u );
313 EXPECT_EQ( v.nUpdateNewCount, 0u );
316 EXPECT_TRUE( updResult.first );
317 EXPECT_FALSE( updResult.second );
319 ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
321 EXPECT_EQ( v.nUpdateNewCount, 1u );
325 ASSERT_TRUE( s.emplace( i.key()));
326 ASSERT_TRUE( s.contains( i.key()));
330 ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
331 EXPECT_TRUE( str.empty());
332 ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
334 EXPECT_EQ( v.strVal, std::string( "Hello!" ));
338 // forgot anything?..
339 ASSERT_TRUE( false );
342 ASSERT_TRUE( s.contains( i.nKey ));
343 ASSERT_TRUE( s.find( i.nKey, []( value_type& ) {} ));
346 ASSERT_FALSE( s.empty());
347 ASSERT_CONTAINER_SIZE( s, nSetSize );
350 shuffle( indices.begin(), indices.end());
351 for ( auto idx : indices ) {
354 ASSERT_TRUE( s.contains( i.nKey ));
355 ASSERT_TRUE( s.find( i.nKey, []( value_type& v )
360 int nKey = i.key() - 1;
363 ASSERT_TRUE( s.erase( i.key()));
364 ASSERT_FALSE( s.erase( i.key()));
367 ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
369 EXPECT_EQ( v.nFindCount, 1u );
372 EXPECT_EQ( i.key(), nKey );
375 ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
379 EXPECT_EQ( i.key(), nKey + 1 );
383 ASSERT_FALSE( s.contains( i.nKey ));
384 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ));
386 ASSERT_TRUE( s.empty());
387 ASSERT_CONTAINER_SIZE( s, 0u );
391 for ( auto& i : data ) {
392 ASSERT_TRUE( s.insert( i ));
396 typename Set::stat const& statistics = s.statistics();
397 CDS_UNUSED( statistics );
399 std::vector< typename Set::level_statistics > lstat;
400 s.get_level_statistics( lstat );
401 EXPECT_EQ( lstat[0].node_capacity, s.head_size());
402 for ( size_t i = 1; i < lstat.size(); ++i ) {
403 EXPECT_EQ( lstat[i].node_capacity, s.array_node_size());
407 ASSERT_FALSE( s.empty());
408 ASSERT_CONTAINER_SIZE( s, nSetSize );
412 ASSERT_TRUE( s.empty());
413 ASSERT_CONTAINER_SIZE( s, 0u );
415 ASSERT_TRUE( s.begin() == s.end());
416 ASSERT_TRUE( s.cbegin() == s.cend());
417 ASSERT_TRUE( s.rbegin() == s.rend());
418 ASSERT_TRUE( s.crbegin() == s.crend());
422 } // namespace cds_test
424 #endif // CDSUNIT_SET_TEST_FELDMAN_HASHSET_H