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_INTRUSIVE_FELDMAN_HASHSET_H
32 #define CDSUNIT_SET_TEST_INTRUSIVE_FELDMAN_HASHSET_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 intrusive {}}
42 namespace ci = cds::intrusive;
45 class intrusive_feldman_hashset: public fixture
50 unsigned int nDisposeCount; // count of disposer calling
51 unsigned int nFindCount; // count of find-functor calling
52 unsigned int nInsertCount;
53 mutable unsigned int nEraseCount;
62 memset( this, 0, sizeof( *this ));
66 struct int_item: public stat
74 explicit int_item( int key )
79 int_item( int key, int val )
84 int_item( int_item const& v )
108 key_val( int key, int val )
113 key_val( key_val const& v )
124 struct int_item2: public key_val, public stat
129 explicit int_item2( int key )
133 int_item2( int key, int val )
134 : key_val( key, val )
137 int_item2( int_item2 const& v )
143 struct hash_accessor {
144 int operator()( int_item const& v ) const
150 struct hash_accessor2 {
151 key_val const& operator()( int_item2 const& v ) const
157 struct simple_item_counter {
160 simple_item_counter()
179 operator size_t() const
186 int operator ()( int lhs, int rhs ) const
190 return lhs > rhs ? 1 : 0;
195 int operator ()( key_val const& lhs, key_val const& rhs ) const
197 if ( lhs.key() < rhs.key())
199 return lhs.key() > rhs.key() ? 1 : 0;
205 template <typename T>
206 void operator ()( T * p )
216 // Precondition: set is empty
217 // Postcondition: set is empty
219 ASSERT_TRUE( s.empty());
220 ASSERT_CONTAINER_SIZE( s, 0 );
221 size_t const nSetSize = std::max( s.head_size() * 2, static_cast<size_t>(100));
223 typedef typename Set::value_type value_type;
225 std::vector< value_type > data;
226 std::vector< size_t> indices;
227 data.reserve( nSetSize );
228 indices.reserve( nSetSize );
229 for ( size_t key = 0; key < nSetSize; ++key ) {
230 data.push_back( value_type( static_cast<int>( key )));
231 indices.push_back( key );
233 shuffle( indices.begin(), indices.end());
236 for ( auto idx : indices ) {
237 auto& i = data[ idx ];
239 ASSERT_FALSE( s.contains( i.nKey ));
240 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
242 std::pair<bool, bool> updResult;
244 updResult = s.update( i, false );
245 EXPECT_FALSE( updResult.first );
246 EXPECT_FALSE( updResult.second );
248 switch ( i.key() % 3 ) {
250 ASSERT_TRUE( s.insert( i ));
251 ASSERT_FALSE( s.insert( i ));
252 updResult = s.update( i, false );
253 EXPECT_TRUE( updResult.first );
254 EXPECT_FALSE( updResult.second );
257 EXPECT_EQ( i.nInsertCount, 0u );
258 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ));
259 EXPECT_EQ( i.nInsertCount, 1u );
260 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ));
261 EXPECT_EQ( i.nInsertCount, 1u );
265 updResult = s.update( i );
266 EXPECT_TRUE( updResult.first );
267 EXPECT_TRUE( updResult.second );
271 ASSERT_TRUE( s.contains( i.nKey ));
272 EXPECT_EQ( i.nFindCount, 0u );
273 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ));
274 EXPECT_EQ( i.nFindCount, 1u );
276 ASSERT_FALSE( s.empty());
277 ASSERT_CONTAINER_SIZE( s, nSetSize );
279 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
281 // get_level_statistics
283 std::vector< typename Set::level_statistics > level_stat;
284 s.get_level_statistics( level_stat );
285 EXPECT_GT( level_stat.size(), 0u );
289 shuffle( indices.begin(), indices.end());
290 for ( auto idx : indices ) {
291 auto& i = data[ idx ];
293 ASSERT_TRUE( s.contains( i.nKey ));
294 EXPECT_EQ( i.nFindCount, 0u );
295 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ));
296 EXPECT_EQ( i.nFindCount, 1u );
299 switch ( i.key() % 3 ) {
301 ASSERT_FALSE( s.unlink( v ));
302 ASSERT_TRUE( s.unlink( i ));
303 ASSERT_FALSE( s.unlink( i ));
306 ASSERT_TRUE( s.erase( i.key()));
307 ASSERT_FALSE( s.erase( i.key()));
310 EXPECT_EQ( i.nEraseCount, 0u );
311 ASSERT_TRUE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
312 EXPECT_EQ( i.nEraseCount, 1u );
313 ASSERT_FALSE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
314 EXPECT_EQ( i.nEraseCount, 1u );
318 ASSERT_FALSE( s.contains( i.nKey ));
319 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ));
321 ASSERT_TRUE( s.empty());
322 ASSERT_CONTAINER_SIZE( s, 0 );
324 // Force retiring cycle
325 Set::gc::force_dispose();
326 for ( auto& i : data ) {
327 EXPECT_EQ( i.nDisposeCount, 1u );
331 for ( auto& i : data ) {
333 ASSERT_TRUE( s.insert( i ));
335 ASSERT_FALSE( s.empty());
336 ASSERT_CONTAINER_SIZE( s, nSetSize );
338 // Forward iterator test
339 for ( auto it = s.begin(); it != s.end(); ++it ) {
342 for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
343 EXPECT_EQ( it->nFindCount, 1u );
346 // Reverse iterator test
347 for ( auto it = s.rbegin(); it != s.rend(); ++it ) {
350 for ( auto it = s.crbegin(); it != s.crend(); ++it ) {
351 EXPECT_EQ( it->nFindCount, 2u );
354 for ( auto& i : data ) {
355 EXPECT_EQ( i.nFindCount, 2u );
361 ASSERT_TRUE( s.empty());
362 ASSERT_CONTAINER_SIZE( s, 0u );
363 ASSERT_TRUE( s.begin() == s.end());
364 ASSERT_TRUE( s.cbegin() == s.cend());
366 // Force retiring cycle
367 Set::gc::force_dispose();
368 for ( auto& i : data ) {
369 EXPECT_EQ( i.nDisposeCount, 1u );
374 } // namespace cds_test
376 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_FELDMAN_HASHSET_H