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_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;
49 template <typename Map>
52 // Precondition: map is empty
53 // Postcondition: map is empty
55 ASSERT_TRUE( m.empty() );
56 ASSERT_CONTAINER_SIZE( m, 0 );
58 typedef typename Map::value_type map_pair;
59 size_t const kkSize = kSize;
61 std::vector<key_type> arrKeys;
62 for ( int i = 0; i < static_cast<int>(kkSize); ++i )
63 arrKeys.push_back( key_type( i ) );
64 shuffle( arrKeys.begin(), arrKeys.end() );
66 std::vector< value_type > arrVals;
67 for ( size_t i = 0; i < kkSize; ++i ) {
69 val.nVal = static_cast<int>(i);
70 val.strVal = std::to_string( i );
71 arrVals.push_back( val );
75 for ( auto const& i : arrKeys ) {
76 value_type const& val( arrVals.at( i.nKey ) );
78 ASSERT_FALSE( m.contains( i.nKey ) );
79 ASSERT_FALSE( m.contains( i ) );
80 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
83 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
87 std::pair< bool, bool > updResult;
89 switch ( i.nKey % 16 ) {
91 ASSERT_TRUE( m.insert( i ) );
92 ASSERT_FALSE( m.insert( i ) );
93 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
94 v.second.nVal = v.first.nKey;
95 v.second.strVal = std::to_string( v.first.nKey );
99 ASSERT_TRUE( m.insert( i.nKey ) );
100 ASSERT_FALSE( m.insert( i.nKey ) );
101 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
102 v.second.nVal = v.first.nKey;
103 v.second.strVal = std::to_string( v.first.nKey );
107 ASSERT_TRUE( m.insert( std::to_string( i.nKey ) ) );
108 ASSERT_FALSE( m.insert( std::to_string( i.nKey ) ) );
109 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
110 v.second.nVal = v.first.nKey;
111 v.second.strVal = std::to_string( v.first.nKey );
115 ASSERT_TRUE( m.insert( i, val ) );
116 ASSERT_FALSE( m.insert( i, val ) );
119 ASSERT_TRUE( m.insert( i.nKey, val.strVal ) );
120 ASSERT_FALSE( m.insert( i.nKey, val.strVal ) );
123 ASSERT_TRUE( m.insert( val.strVal, i.nKey ) );
124 ASSERT_FALSE( m.insert( val.strVal, i.nKey ) );
127 ASSERT_TRUE( m.insert_with( i, []( map_pair& v ) {
128 v.second.nVal = v.first.nKey;
129 v.second.strVal = std::to_string( v.first.nKey );
131 ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
132 EXPECT_TRUE( false );
136 ASSERT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
137 v.second.nVal = v.first.nKey;
138 v.second.strVal = std::to_string( v.first.nKey );
140 ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
141 EXPECT_TRUE( false );
145 ASSERT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
146 v.second.nVal = v.first.nKey;
147 v.second.strVal = std::to_string( v.first.nKey );
149 ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
150 EXPECT_TRUE( false );
154 updResult = m.update( i.nKey, []( map_pair&, map_pair* ) {
155 EXPECT_TRUE( false );
157 ASSERT_FALSE( updResult.first );
158 ASSERT_FALSE( updResult.second );
160 updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
161 EXPECT_TRUE( old == nullptr );
162 v.second.nVal = v.first.nKey;
164 ASSERT_TRUE( updResult.first );
165 ASSERT_TRUE( updResult.second );
167 updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
168 ASSERT_FALSE( old == nullptr );
169 EXPECT_EQ( v.first.nKey, old->second.nVal );
170 v.second.nVal = old->second.nVal;
171 v.second.strVal = std::to_string( v.second.nVal );
173 ASSERT_TRUE( updResult.first );
174 ASSERT_FALSE( updResult.second );
177 updResult = m.update( i, []( map_pair&, map_pair* ) {
178 EXPECT_TRUE( false );
180 ASSERT_FALSE( updResult.first );
181 ASSERT_FALSE( updResult.second );
183 updResult = m.update( i, []( map_pair& v, map_pair* old ) {
184 EXPECT_TRUE( old == nullptr );
185 v.second.nVal = v.first.nKey;
187 ASSERT_TRUE( updResult.first );
188 ASSERT_TRUE( updResult.second );
190 updResult = m.update( i, []( map_pair& v, map_pair* old ) {
191 ASSERT_FALSE( old == nullptr );
192 EXPECT_EQ( v.first.nKey, old->second.nVal );
193 v.second.nVal = old->second.nVal;
194 v.second.strVal = std::to_string( v.second.nVal );
196 ASSERT_TRUE( updResult.first );
197 ASSERT_FALSE( updResult.second );
200 updResult = m.update( val.strVal, []( map_pair&, map_pair* ) {
201 EXPECT_TRUE( false );
203 ASSERT_FALSE( updResult.first );
204 ASSERT_FALSE( updResult.second );
206 updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
207 EXPECT_TRUE( old == nullptr );
208 v.second.nVal = v.first.nKey;
210 ASSERT_TRUE( updResult.first );
211 ASSERT_TRUE( updResult.second );
213 updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
214 ASSERT_FALSE( old == nullptr );
215 EXPECT_EQ( v.first.nKey, old->second.nVal );
216 v.second.nVal = old->second.nVal;
217 v.second.strVal = std::to_string( v.second.nVal );
219 ASSERT_TRUE( updResult.first );
220 ASSERT_FALSE( updResult.second );
223 ASSERT_TRUE( m.emplace( i.nKey ) );
224 ASSERT_FALSE( m.emplace( i.nKey ) );
225 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
226 v.second.nVal = v.first.nKey;
227 v.second.strVal = std::to_string( v.first.nKey );
231 ASSERT_TRUE( m.emplace( i, i.nKey ) );
232 ASSERT_FALSE( m.emplace( i, i.nKey ) );
236 std::string str = val.strVal;
237 ASSERT_TRUE( m.emplace( i, std::move( str ) ) );
238 ASSERT_TRUE( str.empty() );
240 ASSERT_FALSE( m.emplace( i, std::move( str ) ) );
241 ASSERT_TRUE( str.empty() );
246 std::string str = val.strVal;
247 ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str ) ) );
248 ASSERT_TRUE( str.empty() );
250 ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str ) ) );
251 ASSERT_TRUE( str.empty() );
256 ASSERT_TRUE( m.contains( i.nKey ) );
257 ASSERT_TRUE( m.contains( i ) );
258 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
259 EXPECT_EQ( v.first.nKey, v.second.nVal );
260 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
262 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
263 EXPECT_EQ( v.first.nKey, v.second.nVal );
264 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
267 ASSERT_FALSE( m.empty() );
268 ASSERT_CONTAINER_SIZE( m, kkSize );
269 ASSERT_FALSE( m.begin() == m.end() );
270 ASSERT_FALSE( m.cbegin() == m.cend() );
272 shuffle( arrKeys.begin(), arrKeys.end() );
275 std::vector< typename Map::level_statistics > vect;
276 m.get_level_statistics( vect );
280 for ( auto const& i : arrKeys ) {
281 value_type const& val( arrVals.at( i.nKey ) );
283 ASSERT_TRUE( m.contains( i.nKey ) );
284 ASSERT_TRUE( m.contains( val.strVal ) );
285 ASSERT_TRUE( m.contains( i ) );
286 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
287 EXPECT_EQ( v.first.nKey, v.second.nVal );
288 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
290 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
291 EXPECT_EQ( v.first.nKey, v.second.nVal );
292 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
295 switch ( i.nKey % 6 ) {
297 ASSERT_TRUE( m.erase( i ) );
298 ASSERT_FALSE( m.erase( i ) );
301 ASSERT_TRUE( m.erase( i.nKey ) );
302 ASSERT_FALSE( m.erase( i.nKey ) );
305 ASSERT_TRUE( m.erase( val.strVal ) );
306 ASSERT_FALSE( m.erase( val.strVal ) );
309 ASSERT_TRUE( m.erase( i, []( map_pair& v ) {
310 EXPECT_EQ( v.first.nKey, v.second.nVal );
311 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
313 ASSERT_FALSE( m.erase( i, []( map_pair& ) {
314 EXPECT_TRUE( false );
318 ASSERT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
319 EXPECT_EQ( v.first.nKey, v.second.nVal );
320 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
322 ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
323 EXPECT_TRUE( false );
327 ASSERT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
328 EXPECT_EQ( v.first.nKey, v.second.nVal );
329 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
331 ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
332 EXPECT_TRUE( false );
337 ASSERT_FALSE( m.contains( i.nKey ) );
338 ASSERT_FALSE( m.contains( i ) );
339 ASSERT_FALSE( m.contains( val.strVal ) );
340 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
341 ASSERT_TRUE( false );
343 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
344 EXPECT_TRUE( false );
347 ASSERT_TRUE( m.empty() );
348 ASSERT_CONTAINER_SIZE( m, 0 );
350 ASSERT_TRUE( m.begin() == m.end() );
351 ASSERT_TRUE( m.cbegin() == m.cend() );
354 for ( auto const& i : arrKeys )
355 ASSERT_TRUE( m.insert( i ) );
357 ASSERT_FALSE( m.empty() );
358 ASSERT_CONTAINER_SIZE( m, kkSize );
362 ASSERT_TRUE( m.empty() );
363 ASSERT_CONTAINER_SIZE( m, 0 );
367 } // namespace cds_test
369 #endif // CDSUNIT_MAP_TEST_FELDMAN_HASHMAP_H