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_LIST_TEST_KV_ITERABLE_LIST_H
32 #define CDSUNIT_LIST_TEST_KV_ITERABLE_LIST_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
39 class kv_iterable_list : public fixture
46 explicit key_type( int n )
50 key_type( key_type const& s )
54 key_type( key_type&& s )
73 explicit value_type( int n )
80 bool operator()( key_type const& lhs, key_type const& rhs ) const
82 return lhs.key() < rhs.key();
85 bool operator()( key_type const& lhs, int rhs ) const
87 return lhs.key() < rhs;
90 bool operator()( int lhs, key_type const& rhs ) const
92 return lhs < rhs.key();
96 bool operator ()( T const& v1, T const& v2 ) const
98 return v1.key() < v2.key();
104 int operator()( key_type const& lhs, key_type const& rhs ) const
106 return lhs.key() - rhs.key();
109 int operator()( key_type const& lhs, int rhs ) const
111 return lhs.key() - rhs;
114 int operator()( int lhs, key_type const& rhs ) const
116 return lhs - rhs.key();
119 template <typename T>
120 int operator ()( T const& lhs, T const& rhs ) const
122 return lhs.key() - rhs.key();
145 template <typename T1, typename T2>
146 bool operator()( T1 const& t1, T2 const& t2 ) const
148 return t1.key() < t2.key();
153 template <typename List>
154 void test_common( List& l )
156 // Precondition: list is empty
157 // Postcondition: list is empty
159 static const size_t nSize = 20;
160 typedef typename List::key_type list_key_type;
161 typedef typename List::mapped_type list_mapped_type;
162 typedef typename List::value_type list_value_type;
169 for ( size_t i = 0; i < nSize; ++i ) {
170 arr[i].key = static_cast<int>(i) + 1;
171 arr[i].val = arr[i].key * 10;
173 shuffle( arr, arr + nSize );
175 ASSERT_TRUE( l.empty() );
176 ASSERT_CONTAINER_SIZE( l, 0 );
179 for ( auto const& i : arr ) {
180 EXPECT_FALSE( l.contains( i.key ));
181 EXPECT_FALSE( l.contains( key_type( i.key )));
182 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
183 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
184 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
185 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
186 EXPECT_TRUE( l.find( i.key ) == l.end() );
187 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less()) == l.end());
189 switch ( i.key % 6 ) {
191 EXPECT_TRUE( l.insert( i.key ));
192 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
193 EXPECT_EQ( n.second.val, 0 );
195 EXPECT_FALSE( l.insert( i.key ));
199 EXPECT_TRUE( l.insert( i.key, i.val ));
200 EXPECT_TRUE( l.find( key_type(i.key), []( list_value_type& n ) {
201 EXPECT_EQ( n.second.val, n.first.nKey * 10 );
203 EXPECT_FALSE( l.insert( key_type( i.key )));
207 EXPECT_TRUE( l.insert_with( i.key, []( list_value_type& n ) {
208 n.second.val = n.first.nKey * 2;
210 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
211 EXPECT_EQ( n.second.val, n.first.key() * 2 );
213 EXPECT_FALSE( l.insert_with( i.key, []( list_value_type& n ) {
214 n.second.val = n.first.nKey * 3;
216 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
217 EXPECT_EQ( n.second.val, n.first.key() * 2 );
224 EXPECT_TRUE( l.emplace( std::move(k), i.key * 100 ));
225 EXPECT_EQ( k.key(), 0 );
226 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
227 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
230 EXPECT_FALSE( l.emplace( std::move( k ), i.key ));
231 //EXPECT_EQ( k.key(), i.key ); // ???
232 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
233 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
240 auto pair = l.update( i.key, []( list_value_type& n, list_value_type* old ) {
241 ASSERT_TRUE( false );
243 EXPECT_FALSE( pair.first );
244 EXPECT_FALSE( pair.second );
246 pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) {
247 EXPECT_TRUE( old == nullptr );
248 n.second.val = n.first.nKey * 3;
250 EXPECT_TRUE( pair.first );
251 EXPECT_TRUE( pair.second );
253 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
254 EXPECT_EQ( n.second.val, n.first.key() * 3 );
257 pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) {
258 EXPECT_FALSE( old == nullptr );
259 n.second.val = n.first.nKey * 5;
261 EXPECT_TRUE( pair.first );
262 EXPECT_FALSE( pair.second );
264 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
265 EXPECT_EQ( n.second.val, n.first.key() * 5 );
271 auto ret = l.upsert( i.key, i.val, false );
272 EXPECT_FALSE( ret.first );
273 EXPECT_FALSE( ret.second );
274 EXPECT_FALSE( l.contains( i.key ));
276 ret = l.upsert( i.key, i.val );
277 EXPECT_TRUE( ret.first );
278 EXPECT_TRUE( ret.second );
279 EXPECT_TRUE( l.contains( i.key ) );
281 ret = l.upsert( i.key, i.val * 12 );
282 EXPECT_TRUE( ret.first );
283 EXPECT_FALSE( ret.second );
284 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
285 EXPECT_EQ( n.second.val, n.first.key() * 12 );
291 EXPECT_TRUE( l.contains( i.key ));
292 EXPECT_TRUE( l.contains( list_key_type(i.key)));
293 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()));
294 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
295 n.second.val = n.first.nKey;
297 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
298 EXPECT_EQ( n.first.nKey, n.second.val );
299 n.second.val = n.first.nKey * 5;
301 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& n ) {
302 EXPECT_EQ( n.first.nKey * 5, n.second.val );
305 auto pair = l.update( i.key, []( list_value_type& n, list_value_type* old ) {
306 EXPECT_FALSE( old == nullptr );
307 EXPECT_EQ( n.first.nKey * 5, n.second.val );
308 n.second.val = n.first.nKey * 3;
310 EXPECT_TRUE( pair.first );
311 EXPECT_FALSE( pair.second );
313 EXPECT_FALSE( l.find( i.key ) == l.end() );
314 EXPECT_EQ( l.find( i.key )->first.nKey, i.key );
315 EXPECT_EQ( l.find( i.key )->second.val, i.key * 3 );
316 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less() ) == l.end() );
317 EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->first.nKey, i.key );
318 EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->second.val, i.key * 3 );
320 EXPECT_FALSE( l.empty() );
323 ASSERT_FALSE( l.empty() );
324 EXPECT_CONTAINER_SIZE( l, nSize );
327 for ( auto const&i : arr ) {
328 switch ( i.key % 4 ) {
330 EXPECT_TRUE( l.erase( i.key ));
333 EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less()));
336 EXPECT_TRUE( l.erase( i.key, [ &i ]( list_value_type const& n ) {
337 EXPECT_EQ( n.first.nKey, i.key );
338 EXPECT_EQ( n.first.nKey * 3, n.second.val );
342 EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less(), [ &i ]( list_value_type const& n) {
343 EXPECT_EQ( n.first.nKey, i.key );
344 EXPECT_EQ( n.first.nKey * 3, n.second.val );
348 EXPECT_FALSE( l.contains( i.key ));
349 EXPECT_FALSE( l.contains( key_type( i.key )));
350 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
351 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
352 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
353 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
356 ASSERT_TRUE( l.empty() );
357 EXPECT_CONTAINER_SIZE( l, 0 );
360 for ( auto& i : arr )
361 EXPECT_TRUE( l.insert( i.key, i.val ));
363 ASSERT_FALSE( l.empty() );
364 EXPECT_CONTAINER_SIZE( l, nSize );
368 ASSERT_TRUE( l.empty() );
369 EXPECT_CONTAINER_SIZE( l, 0 );
371 // empty list iterator test
374 EXPECT_TRUE( l.begin() == l.end());
375 EXPECT_TRUE( l.cbegin() == l.cend());
376 EXPECT_TRUE( cl.begin() == cl.end());
377 EXPECT_TRUE( l.begin() == l.cend());
378 EXPECT_TRUE( cl.begin() == l.end());
382 template <typename List>
383 void test_ordered_iterator( List& l )
385 // Precondition: list is empty
386 // Postcondition: list is empty
388 static const size_t nSize = 20;
395 for ( size_t i = 0; i < nSize; ++i ) {
396 arr[i].key = static_cast<int>(i);
397 arr[i].val = arr[i].key;
399 shuffle( arr, arr + nSize );
401 ASSERT_TRUE( l.empty() );
402 ASSERT_CONTAINER_SIZE( l, 0 );
404 for ( auto& i : arr )
405 EXPECT_TRUE( l.insert( i.key, i.val ));
408 for ( auto& it : l ) {
409 EXPECT_EQ( key, it.first.key() );
410 EXPECT_EQ( it.second.val, it.first.key() );
411 it.second.val = it.first.key() * 10;
414 EXPECT_EQ( static_cast<size_t>(key), nSize );
417 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
418 EXPECT_EQ( key, it->first.key() );
419 EXPECT_EQ( it->first.key() * 10, it->second.val );
422 EXPECT_EQ( static_cast<size_t>(key), nSize );
425 for ( auto it = l.begin(); it != l.end(); ++it ) {
426 EXPECT_EQ( key, it->first.key() );
427 EXPECT_EQ( it->first.key() * 10, it->second.val );
428 it->second.val = it->first.key() * 2;
431 EXPECT_EQ( static_cast<size_t>(key), nSize );
435 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
436 EXPECT_EQ( key, it->first.nKey );
437 EXPECT_EQ( it->first.nKey * 2, it->second.val );
440 EXPECT_EQ( static_cast<size_t>(key), nSize );
443 ASSERT_TRUE( l.empty() );
444 EXPECT_CONTAINER_SIZE( l, 0 );
448 } // namespace cds_test
450 #endif // CDSUNIT_LIST_TEST_KV_ITERABLE_LIST_H