3 #ifndef CDSTEST_HDR_INTRUSIVE_MULTILEVEL_HASHSET_H
4 #define CDSTEST_HDR_INTRUSIVE_MULTILEVEL_HASHSET_H
6 #include "cppunit/cppunit_proxy.h"
10 namespace intrusive {}
15 namespace ci = cds::intrusive;
16 namespace co = cds::opt;
18 class IntrusiveMultiLevelHashSetHdrTest: public CppUnitMini::TestCase
20 template <typename Hash>
23 unsigned int nDisposeCount ; // count of disposer calling
25 unsigned int nInsertCall;
26 unsigned int nFindCall;
27 unsigned int nEraseCall;
28 mutable unsigned int nIteratorCall;
39 template <typename Hash>
42 Hash const& operator()( Item<Hash> const& i ) const
48 struct item_disposer {
49 template <typename Hash>
50 void operator()( Item<Hash> * p )
62 hash128(size_t l, size_t h) : lo(l), hi(h) {}
65 hash128 operator()( size_t n ) const
67 return hash128( std::hash<size_t>()( n ), std::hash<size_t>()( ~n ));
69 hash128 operator()( hash128 const& n ) const
71 return hash128( std::hash<size_t>()( n.lo ), std::hash<size_t>()( ~n.hi ));
76 bool operator()( hash128 const& lhs, hash128 const& rhs ) const
78 if ( lhs.hi != rhs.hi )
79 return lhs.hi < rhs.hi;
80 return lhs.lo < rhs.lo;
85 int operator()( hash128 const& lhs, hash128 const& rhs ) const
87 if ( lhs.hi != rhs.hi )
88 return lhs.hi < rhs.hi ? -1 : 1;
89 return lhs.lo < rhs.lo ? -1 : lhs.lo == rhs.lo ? 0 : 1;
95 template <typename Set, typename Hash>
96 void test_hp( size_t nHeadBits, size_t nArrayBits )
98 typedef typename Set::hash_type hash_type;
99 typedef typename Set::value_type value_type;
103 size_t const arrCapacity = 1000;
104 std::vector< value_type > arrValue;
105 arrValue.reserve( arrCapacity );
106 for ( size_t i = 0; i < arrCapacity; ++i ) {
107 arrValue.emplace_back( value_type() );
108 arrValue.back().hash = hasher( i );
110 CPPUNIT_ASSERT( arrValue.size() == arrCapacity );
112 Set s( nHeadBits, nArrayBits );
113 CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size());
114 CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits));
115 CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits));
118 CPPUNIT_ASSERT(s.size() == 0 );
119 CPPUNIT_ASSERT(s.empty() );
120 for ( auto& el : arrValue ) {
121 CPPUNIT_ASSERT( s.insert( el ));
122 CPPUNIT_ASSERT(s.contains( el.hash ));
124 CPPUNIT_ASSERT(s.size() == arrCapacity );
125 for ( auto& el : arrValue ) {
126 CPPUNIT_ASSERT(s.contains( el.hash ));
127 CPPUNIT_ASSERT( !s.insert( el ) );
129 CPPUNIT_ASSERT(s.size() == arrCapacity );
130 CPPUNIT_ASSERT( !s.empty() );
134 typedef typename Set::iterator iterator;
135 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it )
136 ++(it->nIteratorCall);
137 for ( auto& el : arrValue ) {
138 CPPUNIT_ASSERT( el.nIteratorCall == 1 );
139 el.nIteratorCall = 0;
144 // Const iterator test
145 for ( typename Set::const_iterator it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it )
146 (*it).nIteratorCall += 1;
147 for ( auto& el : arrValue ) {
148 CPPUNIT_ASSERT( el.nIteratorCall == 1 );
149 el.nIteratorCall = 0;
154 // Reverse iterator test
155 for ( typename Set::reverse_iterator it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it )
156 it->nIteratorCall += 1;
157 for ( auto& el : arrValue ) {
158 CPPUNIT_ASSERT( el.nIteratorCall == 1 );
159 el.nIteratorCall = 0;
164 // Reverse const iterator test
165 for ( typename Set::const_reverse_iterator it = s.crbegin(), itEnd = s.crend(); it != itEnd; ++it ) {
166 (*it).nIteratorCall += 1;
169 for ( auto& el : arrValue ) {
170 CPPUNIT_ASSERT( el.nIteratorCall == 1 );
171 el.nIteratorCall = 0;
175 // update() exists test
176 for ( auto& el : arrValue ) {
178 std::tie(bOp, bInsert) = s.update( el, false );
179 CPPUNIT_ASSERT( bOp );
180 CPPUNIT_ASSERT( !bInsert );
181 CPPUNIT_ASSERT( el.nFindCall == 0 );
182 CPPUNIT_ASSERT(s.find(el.hash, [](value_type& v) { v.nFindCall++; } ));
183 CPPUNIT_ASSERT( el.nFindCall == 1 );
187 CPPUNIT_ASSERT(s.size() == arrCapacity );
188 for ( auto const& el : arrValue ) {
189 CPPUNIT_ASSERT(s.unlink( el ));
190 CPPUNIT_ASSERT(!s.contains( el.hash ));
192 CPPUNIT_ASSERT(s.size() == 0 );
193 Set::gc::force_dispose();
194 for ( auto const& el : arrValue ) {
195 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
199 for ( auto& el : arrValue )
200 el.hash = hasher( el.hash );
203 CPPUNIT_ASSERT(s.size() == 0 );
204 for ( auto& el : arrValue ) {
205 CPPUNIT_ASSERT( s.insert( el, []( value_type& v ) { ++v.nInsertCall; } ));
206 CPPUNIT_ASSERT(s.contains( el.hash ));
207 CPPUNIT_ASSERT( el.nInsertCall == 1 );
209 CPPUNIT_ASSERT(s.size() == arrCapacity );
210 for ( auto& el : arrValue ) {
211 CPPUNIT_ASSERT(s.contains( el.hash ));
212 CPPUNIT_ASSERT( !s.insert( el ) );
214 CPPUNIT_ASSERT(s.size() == arrCapacity );
215 CPPUNIT_ASSERT( !s.empty() );
217 for ( auto& el : arrValue )
218 el.nDisposeCount = 0;
221 CPPUNIT_ASSERT(s.size() == 0 );
222 Set::gc::force_dispose();
223 for ( auto const& el : arrValue ) {
224 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
228 for ( auto& el : arrValue )
229 el.hash = hasher( el.hash );
232 for ( auto& el : arrValue ) {
234 std::tie(bOp, bInsert) = s.update( el, false );
235 CPPUNIT_ASSERT( !bOp );
236 CPPUNIT_ASSERT( !bInsert );
237 CPPUNIT_ASSERT( !s.contains( el.hash ));
239 std::tie(bOp, bInsert) = s.update( el, true );
240 CPPUNIT_ASSERT( bOp );
241 CPPUNIT_ASSERT( bInsert );
242 CPPUNIT_ASSERT( s.contains( el.hash ));
244 CPPUNIT_ASSERT(s.size() == arrCapacity );
247 for ( auto& el : arrValue ) {
248 el.nDisposeCount = 0;
249 CPPUNIT_ASSERT( s.contains( el.hash ));
250 CPPUNIT_ASSERT(s.erase( el.hash ));
251 CPPUNIT_ASSERT( !s.contains( el.hash ));
252 CPPUNIT_ASSERT( !s.erase( el.hash ));
254 CPPUNIT_ASSERT(s.size() == 0 );
255 Set::gc::force_dispose();
256 for ( auto& el : arrValue ) {
257 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
258 CPPUNIT_ASSERT(s.insert( el ));
261 // erase with functor, get() test
262 for ( auto& el : arrValue ) {
263 el.nDisposeCount = 0;
264 CPPUNIT_ASSERT( s.contains( el.hash ) );
266 typename Set::guarded_ptr gp{ s.get( el.hash ) };
267 CPPUNIT_ASSERT( gp );
268 CPPUNIT_ASSERT( gp->nEraseCall == 0);
269 CPPUNIT_ASSERT(s.erase( gp->hash, []( value_type& i ) { ++i.nEraseCall; } ));
270 CPPUNIT_ASSERT( gp->nEraseCall == 1);
271 Set::gc::force_dispose();
272 CPPUNIT_ASSERT( gp->nDisposeCount == 0 );
274 CPPUNIT_ASSERT( !s.contains( el.hash ));
275 CPPUNIT_ASSERT( !s.erase( el.hash ));
276 CPPUNIT_ASSERT( el.nEraseCall == 1 );
277 Set::gc::force_dispose();
278 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
280 CPPUNIT_ASSERT(s.size() == 0 );
283 for ( auto& el : arrValue ) {
284 el.hash = hasher( el.hash );
285 el.nDisposeCount = 0;
287 std::tie(bOp, bInsert) = s.update( el );
288 CPPUNIT_ASSERT( bOp );
289 CPPUNIT_ASSERT( bInsert );
291 CPPUNIT_ASSERT(s.size() == arrCapacity );
294 for ( auto& el : arrValue ) {
295 CPPUNIT_ASSERT( s.contains( el.hash ) );
296 typename Set::guarded_ptr gp = s.extract( el.hash );
297 CPPUNIT_ASSERT( gp );
298 Set::gc::force_dispose();
299 CPPUNIT_ASSERT( el.nDisposeCount == 0 );
300 CPPUNIT_ASSERT( gp->nDisposeCount == 0 );
301 gp = s.get( el.hash );
302 CPPUNIT_ASSERT( !gp );
303 Set::gc::force_dispose();
304 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
305 CPPUNIT_ASSERT( !s.contains( el.hash ) );
307 CPPUNIT_ASSERT(s.size() == 0 );
308 CPPUNIT_ASSERT(s.empty() );
310 // erase with iterator
311 for ( auto& el : arrValue ) {
312 el.nDisposeCount = 0;
313 el.nIteratorCall = 0;
314 CPPUNIT_ASSERT(s.insert( el ));
316 for ( typename Set::iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
318 it->nIteratorCall = 1;
320 CPPUNIT_ASSERT(s.size() == 0 );
321 Set::gc::force_dispose();
322 for ( auto& el : arrValue ) {
323 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
324 CPPUNIT_ASSERT( el.nIteratorCall == 1 );
326 CPPUNIT_ASSERT(s.empty() );
328 CPPUNIT_MSG( s.statistics() );
332 void hp_stdhash_stat();
333 void hp_stdhash_5_3();
334 void hp_stdhash_5_3_stat();
336 void hp_hash128_stat();
337 void hp_hash128_4_3();
338 void hp_hash128_4_3_stat();
341 void dhp_stdhash_stat();
342 void dhp_stdhash_5_3();
343 void dhp_stdhash_5_3_stat();
345 void dhp_hash128_stat();
346 void dhp_hash128_4_3();
347 void dhp_hash128_4_3_stat();
349 CPPUNIT_TEST_SUITE(IntrusiveMultiLevelHashSetHdrTest)
350 CPPUNIT_TEST(hp_stdhash)
351 CPPUNIT_TEST(hp_stdhash_stat)
352 CPPUNIT_TEST(hp_stdhash_5_3)
353 CPPUNIT_TEST(hp_stdhash_5_3_stat)
354 CPPUNIT_TEST(hp_hash128)
355 CPPUNIT_TEST(hp_hash128_stat)
356 CPPUNIT_TEST(hp_hash128_4_3)
357 CPPUNIT_TEST(hp_hash128_4_3_stat)
359 CPPUNIT_TEST(dhp_stdhash)
360 CPPUNIT_TEST(dhp_stdhash_stat)
361 CPPUNIT_TEST(dhp_stdhash_5_3)
362 CPPUNIT_TEST(dhp_stdhash_5_3_stat)
363 CPPUNIT_TEST(dhp_hash128)
364 CPPUNIT_TEST(dhp_hash128_stat)
365 CPPUNIT_TEST(dhp_hash128_4_3)
366 CPPUNIT_TEST(dhp_hash128_4_3_stat)
367 CPPUNIT_TEST_SUITE_END()
371 #endif // #ifndef CDSTEST_HDR_INTRUSIVE_MULTILEVEL_HASHSET_H