2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_MAP_TEST_FELDMAN_HASHMAP_H
32 #define CDSUNIT_MAP_TEST_FELDMAN_HASHMAP_H
34 #include "test_map_data.h"
36 // forward declaration
37 namespace cds { namespace container {}}
38 namespace co = cds::opt;
39 namespace cc = cds::container;
43 class feldman_hashmap : public map_fixture
46 static size_t const kSize = 1000;
52 explicit key_type2( int n )
57 explicit key_type2( size_t n )
58 : nKey( static_cast<int>( n ))
59 , subkey( static_cast<uint16_t>( n ))
62 explicit key_type2( std::string const& str )
63 : nKey( std::stoi( str ))
67 key_type2( key_type2 const& s )
75 bool operator ()( key_type2 const& v1, key_type2 const& v2 ) const
77 return v1.nKey < v2.nKey;
80 bool operator ()( key_type2 const& v1, int v2 ) const
85 bool operator ()( int v1, key_type2 const& v2 ) const
90 bool operator ()( key_type2 const& v1, std::string const& v2 ) const
92 return v1.nKey < std::stoi( v2 );
95 bool operator ()( std::string const& v1, key_type2 const& v2 ) const
97 return std::stoi( v1 ) < v2.nKey;
102 int operator ()( key_type2 const& v1, key_type2 const& v2 ) const
104 if ( v1.nKey < v2.nKey )
106 return v1.nKey > v2.nKey ? 1 : 0;
109 int operator ()( key_type2 const& v1, int v2 ) const
113 return v1.nKey > v2 ? 1 : 0;
116 int operator ()( int v1, key_type2 const& v2 ) const
120 return v1 > v2.nKey ? 1 : 0;
123 int operator ()( key_type2 const& v1, std::string const& v2 ) const
125 int n2 = std::stoi( v2 );
128 return v1.nKey > n2 ? 1 : 0;
131 int operator ()( std::string const& v1, key_type2 const& v2 ) const
133 int n1 = std::stoi( v1 );
136 return n1 > v2.nKey ? 1 : 0;
141 key_type2 operator()( int i ) const
143 return key_type2( cds::opt::v::hash<int>()(i));
146 key_type2 operator()( std::string const& str ) const
148 return key_type2( cds::opt::v::hash<int>()(std::stoi( str )));
151 template <typename T>
152 key_type2 operator()( T const& i ) const
154 return key_type2( cds::opt::v::hash<int>()(i.nKey));
160 template <typename Map>
163 // Precondition: map is empty
164 // Postcondition: map is empty
166 ASSERT_TRUE( m.empty());
167 ASSERT_CONTAINER_SIZE( m, 0 );
169 typedef typename Map::key_type key_type;
170 typedef typename Map::mapped_type value_type;
171 typedef typename Map::value_type map_pair;
172 size_t const kkSize = kSize;
174 std::vector<key_type> arrKeys;
175 for ( int i = 0; i < static_cast<int>(kkSize); ++i )
176 arrKeys.push_back( key_type( i ));
177 shuffle( arrKeys.begin(), arrKeys.end());
179 std::vector< value_type > arrVals;
180 for ( size_t i = 0; i < kkSize; ++i ) {
182 val.nVal = static_cast<int>(i);
183 val.strVal = std::to_string( i );
184 arrVals.push_back( val );
188 for ( auto const& i : arrKeys ) {
189 value_type const& val( arrVals.at( i.nKey ));
191 ASSERT_FALSE( m.contains( i.nKey ));
192 ASSERT_FALSE( m.contains( i ));
193 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
194 ASSERT_TRUE( false );
196 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
197 EXPECT_TRUE( false );
200 std::pair< bool, bool > updResult;
202 switch ( i.nKey % 16 ) {
204 ASSERT_TRUE( m.insert( i ));
205 ASSERT_FALSE( m.insert( i ));
206 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
207 v.second.nVal = v.first.nKey;
208 v.second.strVal = std::to_string( v.first.nKey );
212 ASSERT_TRUE( m.insert( i.nKey ));
213 ASSERT_FALSE( m.insert( i.nKey ));
214 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
215 v.second.nVal = v.first.nKey;
216 v.second.strVal = std::to_string( v.first.nKey );
220 ASSERT_TRUE( m.insert( std::to_string( i.nKey )));
221 ASSERT_FALSE( m.insert( std::to_string( i.nKey )));
222 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
223 v.second.nVal = v.first.nKey;
224 v.second.strVal = std::to_string( v.first.nKey );
228 ASSERT_TRUE( m.insert( i, val ));
229 ASSERT_FALSE( m.insert( i, val ));
232 ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
233 ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
236 ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
237 ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
240 ASSERT_TRUE( m.insert_with( i, []( map_pair& v ) {
241 v.second.nVal = v.first.nKey;
242 v.second.strVal = std::to_string( v.first.nKey );
244 ASSERT_FALSE( m.insert_with( i, []( map_pair& ) {
245 EXPECT_TRUE( false );
249 ASSERT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
250 v.second.nVal = v.first.nKey;
251 v.second.strVal = std::to_string( v.first.nKey );
253 ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& ) {
254 EXPECT_TRUE( false );
258 ASSERT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
259 v.second.nVal = v.first.nKey;
260 v.second.strVal = std::to_string( v.first.nKey );
262 ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& ) {
263 EXPECT_TRUE( false );
267 updResult = m.update( i.nKey, []( map_pair&, map_pair* ) {
268 EXPECT_TRUE( false );
270 ASSERT_FALSE( updResult.first );
271 ASSERT_FALSE( updResult.second );
273 updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
274 EXPECT_TRUE( old == nullptr );
275 v.second.nVal = v.first.nKey;
277 ASSERT_TRUE( updResult.first );
278 ASSERT_TRUE( updResult.second );
280 updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
281 ASSERT_FALSE( old == nullptr );
282 EXPECT_EQ( v.first.nKey, old->second.nVal );
283 v.second.nVal = old->second.nVal;
284 v.second.strVal = std::to_string( v.second.nVal );
286 ASSERT_TRUE( updResult.first );
287 ASSERT_FALSE( updResult.second );
290 updResult = m.update( i, []( map_pair&, map_pair* ) {
291 EXPECT_TRUE( false );
293 ASSERT_FALSE( updResult.first );
294 ASSERT_FALSE( updResult.second );
296 updResult = m.update( i, []( map_pair& v, map_pair* old ) {
297 EXPECT_TRUE( old == nullptr );
298 v.second.nVal = v.first.nKey;
300 ASSERT_TRUE( updResult.first );
301 ASSERT_TRUE( updResult.second );
303 updResult = m.update( i, []( map_pair& v, map_pair* old ) {
304 ASSERT_FALSE( old == nullptr );
305 EXPECT_EQ( v.first.nKey, old->second.nVal );
306 v.second.nVal = old->second.nVal;
307 v.second.strVal = std::to_string( v.second.nVal );
309 ASSERT_TRUE( updResult.first );
310 ASSERT_FALSE( updResult.second );
313 updResult = m.update( val.strVal, []( map_pair&, map_pair* ) {
314 EXPECT_TRUE( false );
316 ASSERT_FALSE( updResult.first );
317 ASSERT_FALSE( updResult.second );
319 updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
320 EXPECT_TRUE( old == nullptr );
321 v.second.nVal = v.first.nKey;
323 ASSERT_TRUE( updResult.first );
324 ASSERT_TRUE( updResult.second );
326 updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
327 ASSERT_FALSE( old == nullptr );
328 EXPECT_EQ( v.first.nKey, old->second.nVal );
329 v.second.nVal = old->second.nVal;
330 v.second.strVal = std::to_string( v.second.nVal );
332 ASSERT_TRUE( updResult.first );
333 ASSERT_FALSE( updResult.second );
336 ASSERT_TRUE( m.emplace( i.nKey ));
337 ASSERT_FALSE( m.emplace( i.nKey ));
338 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
339 v.second.nVal = v.first.nKey;
340 v.second.strVal = std::to_string( v.first.nKey );
344 ASSERT_TRUE( m.emplace( i, i.nKey ));
345 ASSERT_FALSE( m.emplace( i, i.nKey ));
349 std::string str = val.strVal;
350 ASSERT_TRUE( m.emplace( i, std::move( str )));
351 ASSERT_TRUE( str.empty());
353 ASSERT_FALSE( m.emplace( i, std::move( str )));
354 ASSERT_TRUE( str.empty());
359 std::string str = val.strVal;
360 ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
361 ASSERT_TRUE( str.empty());
363 ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
364 ASSERT_TRUE( str.empty());
369 ASSERT_TRUE( m.contains( i.nKey ));
370 ASSERT_TRUE( m.contains( i ));
371 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
372 EXPECT_EQ( v.first.nKey, v.second.nVal );
373 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
375 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
376 EXPECT_EQ( v.first.nKey, v.second.nVal );
377 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
380 ASSERT_FALSE( m.empty());
381 ASSERT_CONTAINER_SIZE( m, kkSize );
382 ASSERT_FALSE( m.begin() == m.end());
383 ASSERT_FALSE( m.cbegin() == m.cend());
385 shuffle( arrKeys.begin(), arrKeys.end());
388 std::vector< typename Map::level_statistics > vect;
389 m.get_level_statistics( vect );
393 for ( auto const& i : arrKeys ) {
394 value_type const& val( arrVals.at( i.nKey ));
396 ASSERT_TRUE( m.contains( i.nKey ));
397 ASSERT_TRUE( m.contains( val.strVal ));
398 ASSERT_TRUE( m.contains( i ));
399 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
400 EXPECT_EQ( v.first.nKey, v.second.nVal );
401 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
403 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
404 EXPECT_EQ( v.first.nKey, v.second.nVal );
405 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
408 switch ( i.nKey % 6 ) {
410 ASSERT_TRUE( m.erase( i ));
411 ASSERT_FALSE( m.erase( i ));
414 ASSERT_TRUE( m.erase( i.nKey ));
415 ASSERT_FALSE( m.erase( i.nKey ));
418 ASSERT_TRUE( m.erase( val.strVal ));
419 ASSERT_FALSE( m.erase( val.strVal ));
422 ASSERT_TRUE( m.erase( i, []( map_pair& v ) {
423 EXPECT_EQ( v.first.nKey, v.second.nVal );
424 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
426 ASSERT_FALSE( m.erase( i, []( map_pair& ) {
427 EXPECT_TRUE( false );
431 ASSERT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
432 EXPECT_EQ( v.first.nKey, v.second.nVal );
433 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
435 ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
436 EXPECT_TRUE( false );
440 ASSERT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
441 EXPECT_EQ( v.first.nKey, v.second.nVal );
442 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
444 ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
445 EXPECT_TRUE( false );
450 ASSERT_FALSE( m.contains( i.nKey ));
451 ASSERT_FALSE( m.contains( i ));
452 ASSERT_FALSE( m.contains( val.strVal ));
453 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
454 ASSERT_TRUE( false );
456 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
457 EXPECT_TRUE( false );
460 ASSERT_TRUE( m.empty());
461 ASSERT_CONTAINER_SIZE( m, 0 );
463 ASSERT_TRUE( m.begin() == m.end());
464 ASSERT_TRUE( m.cbegin() == m.cend());
467 for ( auto const& i : arrKeys )
468 ASSERT_TRUE( m.insert( i ));
470 ASSERT_FALSE( m.empty());
471 ASSERT_CONTAINER_SIZE( m, kkSize );
475 ASSERT_TRUE( m.empty());
476 ASSERT_CONTAINER_SIZE( m, 0 );
480 } // namespace cds_test
482 #endif // CDSUNIT_MAP_TEST_FELDMAN_HASHMAP_H