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::value_type list_value_type;
168 for ( size_t i = 0; i < nSize; ++i ) {
169 arr[i].key = static_cast<int>(i) + 1;
170 arr[i].val = arr[i].key * 10;
172 shuffle( arr, arr + nSize );
174 ASSERT_TRUE( l.empty());
175 ASSERT_CONTAINER_SIZE( l, 0 );
178 for ( auto const& i : arr ) {
179 EXPECT_FALSE( l.contains( i.key ));
180 EXPECT_FALSE( l.contains( key_type( i.key )));
181 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
182 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
183 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
184 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
185 EXPECT_TRUE( l.find( i.key ) == l.end());
186 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less()) == l.end());
188 switch ( i.key % 6 ) {
190 EXPECT_TRUE( l.insert( i.key ));
191 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
192 EXPECT_EQ( n.second.val, 0 );
194 EXPECT_FALSE( l.insert( i.key ));
198 EXPECT_TRUE( l.insert( i.key, i.val ));
199 EXPECT_TRUE( l.find( key_type(i.key), []( list_value_type& n ) {
200 EXPECT_EQ( n.second.val, n.first.nKey * 10 );
202 EXPECT_FALSE( l.insert( key_type( i.key )));
206 EXPECT_TRUE( l.insert_with( i.key, []( list_value_type& n ) {
207 n.second.val = n.first.nKey * 2;
209 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
210 EXPECT_EQ( n.second.val, n.first.key() * 2 );
212 EXPECT_FALSE( l.insert_with( i.key, []( list_value_type& n ) {
213 n.second.val = n.first.nKey * 3;
215 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
216 EXPECT_EQ( n.second.val, n.first.key() * 2 );
223 EXPECT_TRUE( l.emplace( std::move(k), i.key * 100 ));
224 EXPECT_EQ( k.key(), 0 );
225 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
226 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
229 EXPECT_FALSE( l.emplace( std::move( k ), i.key ));
230 //EXPECT_EQ( k.key(), i.key ); // ???
231 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
232 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
239 auto pair = l.update( i.key, []( list_value_type&, list_value_type* ) {
240 ASSERT_TRUE( false );
242 EXPECT_FALSE( pair.first );
243 EXPECT_FALSE( pair.second );
245 pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) {
246 EXPECT_TRUE( old == nullptr );
247 n.second.val = n.first.nKey * 3;
249 EXPECT_TRUE( pair.first );
250 EXPECT_TRUE( pair.second );
252 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
253 EXPECT_EQ( n.second.val, n.first.key() * 3 );
256 pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) {
257 EXPECT_FALSE( old == nullptr );
258 n.second.val = n.first.nKey * 5;
260 EXPECT_TRUE( pair.first );
261 EXPECT_FALSE( pair.second );
263 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
264 EXPECT_EQ( n.second.val, n.first.key() * 5 );
270 auto ret = l.upsert( i.key, i.val, false );
271 EXPECT_FALSE( ret.first );
272 EXPECT_FALSE( ret.second );
273 EXPECT_FALSE( l.contains( i.key ));
275 ret = l.upsert( i.key, i.val );
276 EXPECT_TRUE( ret.first );
277 EXPECT_TRUE( ret.second );
278 EXPECT_TRUE( l.contains( i.key ));
280 ret = l.upsert( i.key, i.key * 12 );
281 EXPECT_TRUE( ret.first );
282 EXPECT_FALSE( ret.second );
283 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
284 EXPECT_EQ( n.second.val, n.first.key() * 12 );
290 EXPECT_TRUE( l.contains( i.key ));
291 EXPECT_TRUE( l.contains( list_key_type(i.key)));
292 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()));
293 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
294 n.second.val = n.first.nKey;
296 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
297 EXPECT_EQ( n.first.nKey, n.second.val );
298 n.second.val = n.first.nKey * 5;
300 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& n ) {
301 EXPECT_EQ( n.first.nKey * 5, n.second.val );
304 auto pair = l.update( i.key, []( list_value_type& n, list_value_type* old ) {
305 ASSERT_FALSE( old == nullptr );
306 EXPECT_EQ( n.first.nKey * 5, old->second.val );
307 n.second.val = n.first.nKey * 3;
309 EXPECT_TRUE( pair.first );
310 EXPECT_FALSE( pair.second );
312 EXPECT_FALSE( l.find( i.key ) == l.end());
313 EXPECT_EQ( l.find( i.key )->first.nKey, i.key );
314 EXPECT_EQ( l.find( i.key )->second.val, i.key * 3 );
315 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less()) == l.end());
316 EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->first.nKey, i.key );
317 EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->second.val, i.key * 3 );
319 EXPECT_FALSE( l.empty());
322 ASSERT_FALSE( l.empty());
323 EXPECT_CONTAINER_SIZE( l, nSize );
326 for ( auto const&i : arr ) {
327 switch ( i.key % 4 ) {
329 EXPECT_TRUE( l.erase( i.key ));
332 EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less()));
335 EXPECT_TRUE( l.erase( i.key, [ &i ]( list_value_type const& n ) {
336 EXPECT_EQ( n.first.nKey, i.key );
337 EXPECT_EQ( n.first.nKey * 3, n.second.val );
341 EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less(), [ &i ]( list_value_type const& n) {
342 EXPECT_EQ( n.first.nKey, i.key );
343 EXPECT_EQ( n.first.nKey * 3, n.second.val );
347 EXPECT_FALSE( l.contains( i.key ));
348 EXPECT_FALSE( l.contains( key_type( i.key )));
349 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
350 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
351 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
352 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
355 ASSERT_TRUE( l.empty());
356 EXPECT_CONTAINER_SIZE( l, 0 );
359 for ( auto& i : arr )
360 EXPECT_TRUE( l.insert( i.key, i.val ));
362 ASSERT_FALSE( l.empty());
363 EXPECT_CONTAINER_SIZE( l, nSize );
367 ASSERT_TRUE( l.empty());
368 EXPECT_CONTAINER_SIZE( l, 0 );
370 // empty list iterator test
373 EXPECT_TRUE( l.begin() == l.end());
374 EXPECT_TRUE( l.cbegin() == l.cend());
375 EXPECT_TRUE( cl.begin() == cl.end());
376 EXPECT_TRUE( l.begin() == l.cend());
377 EXPECT_TRUE( cl.begin() == l.end());
381 template <typename List>
382 void test_ordered_iterator( List& l )
384 // Precondition: list is empty
385 // Postcondition: list is empty
387 static const size_t nSize = 20;
394 for ( size_t i = 0; i < nSize; ++i ) {
395 arr[i].key = static_cast<int>(i);
396 arr[i].val = arr[i].key;
398 shuffle( arr, arr + nSize );
400 ASSERT_TRUE( l.empty());
401 ASSERT_CONTAINER_SIZE( l, 0 );
403 for ( auto& i : arr )
404 EXPECT_TRUE( l.insert( i.key, i.val ));
407 for ( auto& it : l ) {
408 EXPECT_EQ( key, it.first.key());
409 EXPECT_EQ( it.second.val, it.first.key());
410 it.second.val = it.first.key() * 10;
413 EXPECT_EQ( static_cast<size_t>(key), nSize );
416 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
417 EXPECT_EQ( key, it->first.key());
418 EXPECT_EQ( it->first.key() * 10, it->second.val );
421 EXPECT_EQ( static_cast<size_t>(key), nSize );
424 for ( auto it = l.begin(); it != l.end(); ++it ) {
425 EXPECT_EQ( key, it->first.key());
426 EXPECT_EQ( it->first.key() * 10, it->second.val );
427 it->second.val = it->first.key() * 2;
430 EXPECT_EQ( static_cast<size_t>(key), nSize );
434 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
435 EXPECT_EQ( key, it->first.nKey );
436 EXPECT_EQ( it->first.nKey * 2, it->second.val );
439 EXPECT_EQ( static_cast<size_t>(key), nSize );
442 ASSERT_TRUE( l.empty());
443 EXPECT_CONTAINER_SIZE( l, 0 );
447 } // namespace cds_test
449 #endif // CDSUNIT_LIST_TEST_KV_ITERABLE_LIST_H