3 #ifndef CDSTEST_HDR_CUCKOO_MAP_H
4 #define CDSTEST_HDR_CUCKOO_MAP_H
5 #include "size_check.h"
7 #include "cppunit/cppunit_proxy.h"
8 #include <cds/os/timer.h>
9 #include <cds/opt/hash.h>
10 #include <functional> // ref
11 #include <algorithm> // random_shuffle
13 namespace cds { namespace container {}}
16 using misc::check_size;
18 namespace cc = cds::container;
19 namespace co = cds::opt;
21 class CuckooMapHdrTest: public CppUnitMini::TestCase
37 value_type( value_type&& v )
41 value_type( value_type const& v )
45 value_type& operator=( value_type const& v )
52 typedef std::pair<key_type const, value_type> pair_type;
56 bool operator ()(int v1, int v2 ) const
63 int operator ()(int v1, int v2 ) const
67 return v1 > v2 ? 1 : 0;
72 bool operator ()(int v1, int v2 ) const
79 size_t operator()( int i ) const
81 return co::v::hash<int>()( i );
85 struct simple_item_counter {
107 operator size_t() const
113 template <typename Map>
114 struct insert_functor
116 typedef typename Map::value_type pair_type;
119 void operator()( pair_type& item )
121 item.second.m_val = item.first * 3;
125 void operator()( bool bNew, pair_type& item )
128 item.second.m_val = item.first * 2;
130 item.second.m_val = item.first * 5;
137 check_value( int nExpected )
138 : m_nExpected( nExpected )
141 template <typename T>
142 void operator ()( T& pair )
144 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
146 template <typename T, typename Q>
147 void operator ()( T& pair, Q )
149 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
153 struct extract_functor
156 void operator()( pair_type const& val )
158 *m_pVal = val.second.m_val;
164 void test_iter( Map& s)
166 typedef typename Map::iterator iterator;
167 typedef typename Map::const_iterator const_iterator;
169 const int nMaxCount = 500;
170 for ( int i = 0; i < nMaxCount; ++i ) {
171 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
175 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
176 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
177 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
178 it->second.m_val = it->first;
181 CPPUNIT_ASSERT( nCount == nMaxCount );
183 Map const& refSet = s;
185 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
186 CPPUNIT_ASSERT( it->first == it->second.m_val );
187 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
190 CPPUNIT_ASSERT( nCount == nMaxCount );
199 CPPUNIT_ASSERT( m.bucket_count() == 32 );
200 CPPUNIT_ASSERT( m.lock_count() == 32 );
202 test_cuckoo_with( m );
204 // Iterators is not yet supported for CuckooMap
206 //CPPUNIT_ASSERT( m.empty() );
207 //CPPUNIT_ASSERT( check_size( m, 0 ));
211 //*******************************************
212 // If erase_with && find_with are supported
214 void test_int_with( Map& m )
216 std::pair<bool, bool> ensureResult;
217 typedef typename std::conditional< Map::c_isSorted, less, equal >::type predicate;
220 CPPUNIT_ASSERT( m.empty() );
221 CPPUNIT_ASSERT( check_size( m, 0 ));
222 CPPUNIT_ASSERT( !m.find(25) );
223 CPPUNIT_ASSERT( m.insert( 25 ) ) ; // value = 0
224 CPPUNIT_ASSERT( m.find(25) );
225 CPPUNIT_ASSERT( !m.empty() );
226 CPPUNIT_ASSERT( check_size( m, 1 ));
227 CPPUNIT_ASSERT( m.find(25) );
229 CPPUNIT_ASSERT( !m.insert( 25 ) );
230 CPPUNIT_ASSERT( !m.empty() );
231 CPPUNIT_ASSERT( check_size( m, 1 ));
233 CPPUNIT_ASSERT( !m.find_with(10, predicate()) );
234 CPPUNIT_ASSERT( m.insert( 10, 10 ) );
235 CPPUNIT_ASSERT( !m.empty() );
236 CPPUNIT_ASSERT( check_size( m, 2 ));
237 CPPUNIT_ASSERT( m.find_with(10, predicate()) );
239 CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
240 CPPUNIT_ASSERT( !m.empty() );
241 CPPUNIT_ASSERT( check_size( m, 2 ));
243 CPPUNIT_ASSERT( !m.find(30) );
244 CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) ) ; // value = 90
245 CPPUNIT_ASSERT( !m.empty() );
246 CPPUNIT_ASSERT( check_size( m, 3 ));
247 CPPUNIT_ASSERT( m.find(30) );
249 CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
250 CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
251 CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
254 CPPUNIT_ASSERT( !m.find(27) );
255 ensureResult = m.ensure( 27, insert_functor<Map>() ) ; // value = 54
256 CPPUNIT_ASSERT( ensureResult.first );
257 CPPUNIT_ASSERT( ensureResult.second );
258 CPPUNIT_ASSERT( m.find(27) );
262 CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
264 CPPUNIT_ASSERT( m.find_with( 25, predicate(), std::ref(chk) ));
265 chk.m_nExpected = 90;
266 CPPUNIT_ASSERT( m.find( 30, std::ref(chk) ));
267 chk.m_nExpected = 54;
268 CPPUNIT_ASSERT( m.find( 27, std::ref(chk) ));
270 ensureResult = m.ensure( 10, insert_functor<Map>() ) ; // value = 50
271 CPPUNIT_ASSERT( ensureResult.first );
272 CPPUNIT_ASSERT( !ensureResult.second );
273 chk.m_nExpected = 50;
274 CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
277 CPPUNIT_ASSERT( !m.find(100) );
278 CPPUNIT_ASSERT( !m.erase( 100 )) ; // not found
280 CPPUNIT_ASSERT( m.find(25) );
281 CPPUNIT_ASSERT( check_size( m, 4 ));
282 CPPUNIT_ASSERT( m.erase( 25 ));
283 CPPUNIT_ASSERT( !m.empty() );
284 CPPUNIT_ASSERT( check_size( m, 3 ));
285 CPPUNIT_ASSERT( !m.find(25) );
286 CPPUNIT_ASSERT( !m.erase( 25 ));
288 CPPUNIT_ASSERT( !m.find(258) );
289 CPPUNIT_ASSERT( m.insert(258))
290 CPPUNIT_ASSERT( check_size( m, 4 ));
291 CPPUNIT_ASSERT( m.find_with(258, predicate()) );
292 CPPUNIT_ASSERT( m.erase_with( 258, predicate() ));
293 CPPUNIT_ASSERT( !m.empty() );
294 CPPUNIT_ASSERT( check_size( m, 3 ));
295 CPPUNIT_ASSERT( !m.find(258) );
296 CPPUNIT_ASSERT( !m.erase_with( 258, predicate() ));
302 CPPUNIT_ASSERT( !m.find(29) );
303 CPPUNIT_ASSERT( m.insert(29, 290))
304 CPPUNIT_ASSERT( m.erase_with( 29, predicate(), std::ref(ext)));
305 CPPUNIT_ASSERT( !m.empty() );
306 CPPUNIT_ASSERT( check_size( m, 3 ));
307 CPPUNIT_ASSERT( nVal == 290 );
309 CPPUNIT_ASSERT( !m.erase_with( 29, predicate(), std::ref( ext ) ) );
310 CPPUNIT_ASSERT( nVal == -1 );
312 CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
313 CPPUNIT_ASSERT( !m.empty() );
314 CPPUNIT_ASSERT( check_size( m, 2 ));
315 CPPUNIT_ASSERT( nVal == 90 );
317 CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
318 CPPUNIT_ASSERT( nVal == -1 );
321 CPPUNIT_ASSERT( m.empty() );
322 CPPUNIT_ASSERT( check_size( m, 0 ));
325 CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
326 CPPUNIT_ASSERT( m.emplace(137, 731)) ; // key = 137, val = 731
327 CPPUNIT_ASSERT( m.emplace( 149, value_type(941) )) ; // key = 149, val = 941
329 CPPUNIT_ASSERT( !m.empty() );
330 CPPUNIT_ASSERT( check_size( m, 3 ));
333 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
334 chk.m_nExpected = 731;
335 CPPUNIT_ASSERT( m.find_with( 137, predicate(), std::ref(chk) ));
336 chk.m_nExpected = 941;
337 CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
339 CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
341 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
342 CPPUNIT_ASSERT( !m.empty() );
343 CPPUNIT_ASSERT( check_size( m, 3 ));
346 CPPUNIT_ASSERT( m.empty() );
347 CPPUNIT_ASSERT( check_size( m, 0 ));
351 void test_cuckoo_with(Map& m)
353 cds::OS::Timer timer;
357 // Iterators is not yet supported
359 //CPPUNIT_ASSERT( m.empty() );
360 //CPPUNIT_ASSERT( check_size( m, 0 ));
364 CPPUNIT_ASSERT( m.empty() );
365 CPPUNIT_ASSERT( check_size( m, 0 ));
368 for ( int i = 0; i < 40000; i++ ) {
372 CPPUNIT_MSG( " Duration=" << timer.duration() );
375 void Cuckoo_striped_list();
376 void Cuckoo_striped_vector();
377 void Cuckoo_refinable_list();
378 void Cuckoo_refinable_vector();
380 CPPUNIT_TEST_SUITE(CuckooMapHdrTest)
381 CPPUNIT_TEST(Cuckoo_striped_list)
382 CPPUNIT_TEST(Cuckoo_striped_vector)
383 CPPUNIT_TEST(Cuckoo_refinable_list)
384 CPPUNIT_TEST(Cuckoo_refinable_vector)
385 CPPUNIT_TEST_SUITE_END()
390 #endif // #ifndef CDSTEST_HDR_CUCKOO_MAP_H