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 )
96 struct hash_accessor {
97 int operator()( int_item const& v ) const
103 struct simple_item_counter {
106 simple_item_counter()
125 operator size_t() const
132 int operator ()( int lhs, int rhs ) const
136 return lhs > rhs ? 1 : 0;
142 template <typename T>
143 void operator ()( T * p )
153 // Precondition: set is empty
154 // Postcondition: set is empty
156 ASSERT_TRUE( s.empty());
157 ASSERT_CONTAINER_SIZE( s, 0 );
158 size_t const nSetSize = std::max( s.head_size() * 2, static_cast<size_t>(100));
160 typedef typename Set::value_type value_type;
162 std::vector< value_type > data;
163 std::vector< size_t> indices;
164 data.reserve( nSetSize );
165 indices.reserve( nSetSize );
166 for ( size_t key = 0; key < nSetSize; ++key ) {
167 data.push_back( value_type( static_cast<int>( key )));
168 indices.push_back( key );
170 shuffle( indices.begin(), indices.end());
173 for ( auto idx : indices ) {
174 auto& i = data[ idx ];
176 ASSERT_FALSE( s.contains( i.nKey ));
177 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
179 std::pair<bool, bool> updResult;
181 updResult = s.update( i, false );
182 EXPECT_FALSE( updResult.first );
183 EXPECT_FALSE( updResult.second );
185 switch ( i.key() % 3 ) {
187 ASSERT_TRUE( s.insert( i ));
188 ASSERT_FALSE( s.insert( i ));
189 updResult = s.update( i, false );
190 EXPECT_TRUE( updResult.first );
191 EXPECT_FALSE( updResult.second );
194 EXPECT_EQ( i.nInsertCount, 0u );
195 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ));
196 EXPECT_EQ( i.nInsertCount, 1u );
197 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ));
198 EXPECT_EQ( i.nInsertCount, 1u );
202 updResult = s.update( i );
203 EXPECT_TRUE( updResult.first );
204 EXPECT_TRUE( updResult.second );
208 ASSERT_TRUE( s.contains( i.nKey ));
209 EXPECT_EQ( i.nFindCount, 0u );
210 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ));
211 EXPECT_EQ( i.nFindCount, 1u );
213 ASSERT_FALSE( s.empty());
214 ASSERT_CONTAINER_SIZE( s, nSetSize );
216 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
218 // get_level_statistics
220 std::vector< typename Set::level_statistics > level_stat;
221 s.get_level_statistics( level_stat );
222 EXPECT_GT( level_stat.size(), 0u );
226 shuffle( indices.begin(), indices.end());
227 for ( auto idx : indices ) {
228 auto& i = data[ idx ];
230 ASSERT_TRUE( s.contains( i.nKey ));
231 EXPECT_EQ( i.nFindCount, 0u );
232 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ));
233 EXPECT_EQ( i.nFindCount, 1u );
236 switch ( i.key() % 3 ) {
238 ASSERT_FALSE( s.unlink( v ));
239 ASSERT_TRUE( s.unlink( i ));
240 ASSERT_FALSE( s.unlink( i ));
243 ASSERT_TRUE( s.erase( i.key()));
244 ASSERT_FALSE( s.erase( i.key()) );
247 EXPECT_EQ( i.nEraseCount, 0u );
248 ASSERT_TRUE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
249 EXPECT_EQ( i.nEraseCount, 1u );
250 ASSERT_FALSE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
251 EXPECT_EQ( i.nEraseCount, 1u );
255 ASSERT_FALSE( s.contains( i.nKey ));
256 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ));
258 ASSERT_TRUE( s.empty());
259 ASSERT_CONTAINER_SIZE( s, 0 );
261 // Force retiring cycle
262 Set::gc::force_dispose();
263 for ( auto& i : data ) {
264 EXPECT_EQ( i.nDisposeCount, 1u );
268 for ( auto& i : data ) {
270 ASSERT_TRUE( s.insert( i ));
272 ASSERT_FALSE( s.empty());
273 ASSERT_CONTAINER_SIZE( s, nSetSize );
275 // Forward iterator test
276 for ( auto it = s.begin(); it != s.end(); ++it ) {
279 for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
280 EXPECT_EQ( it->nFindCount, 1u );
283 // Reverse iterator test
284 for ( auto it = s.rbegin(); it != s.rend(); ++it ) {
287 for ( auto it = s.crbegin(); it != s.crend(); ++it ) {
288 EXPECT_EQ( it->nFindCount, 2u );
291 for ( auto& i : data ) {
292 EXPECT_EQ( i.nFindCount, 2u );
298 ASSERT_TRUE( s.empty());
299 ASSERT_CONTAINER_SIZE( s, 0u );
300 ASSERT_TRUE( s.begin() == s.end());
301 ASSERT_TRUE( s.cbegin() == s.cend());
303 // Force retiring cycle
304 Set::gc::force_dispose();
305 for ( auto& i : data ) {
306 EXPECT_EQ( i.nDisposeCount, 1u );
311 } // namespace cds_test
313 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_FELDMAN_HASHSET_H