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_LIST_TEST_KV_LIST_H
32 #define CDSUNIT_LIST_TEST_KV_LIST_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
39 class kv_list_common : 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& ) {} ));
186 switch ( i.key % 5 ) {
188 EXPECT_TRUE( l.insert( i.key ));
189 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
190 EXPECT_EQ( n.second.val, 0 );
192 EXPECT_FALSE( l.insert( i.key ));
196 EXPECT_TRUE( l.insert( i.key, i.val ));
197 EXPECT_TRUE( l.find( key_type(i.key), []( list_value_type& n ) {
198 EXPECT_EQ( n.second.val, n.first.nKey * 10 );
200 EXPECT_FALSE( l.insert( key_type( i.key )));
204 EXPECT_TRUE( l.insert_with( i.key, []( list_value_type& n ) {
205 n.second.val = n.first.nKey * 2;
207 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
208 EXPECT_EQ( n.second.val, n.first.key() * 2 );
210 EXPECT_FALSE( l.insert_with( i.key, []( list_value_type& n ) {
211 n.second.val = n.first.nKey * 3;
213 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
214 EXPECT_EQ( n.second.val, n.first.key() * 2 );
221 EXPECT_TRUE( l.emplace( std::move(k), i.key * 100 ));
222 EXPECT_EQ( k.key(), 0 );
223 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
224 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
227 EXPECT_FALSE( l.emplace( std::move( k ), i.key ));
228 //EXPECT_EQ( k.key(), i.key ); // ???
229 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
230 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
236 auto pair = l.update( i.key, []( bool, list_value_type& ) {
237 ASSERT_TRUE( false );
239 EXPECT_FALSE( pair.first );
240 EXPECT_FALSE( pair.second );
242 pair = l.update( list_key_type(i.key), []( bool bNew, list_value_type& n ) {
244 n.second.val = n.first.nKey * 3;
246 EXPECT_TRUE( pair.first );
247 EXPECT_TRUE( pair.second );
249 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
250 EXPECT_EQ( n.second.val, n.first.key() * 3 );
253 pair = l.update( list_key_type(i.key), []( bool bNew, list_value_type& n ) {
254 EXPECT_FALSE( bNew );
255 n.second.val = n.first.nKey * 5;
257 EXPECT_TRUE( pair.first );
258 EXPECT_FALSE( pair.second );
260 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
261 EXPECT_EQ( n.second.val, n.first.key() * 5 );
267 EXPECT_TRUE( l.contains( i.key ));
268 EXPECT_TRUE( l.contains( list_key_type(i.key)));
269 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()));
270 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
271 n.second.val = n.first.nKey;
273 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
274 EXPECT_EQ( n.first.nKey, n.second.val );
275 n.second.val = n.first.nKey * 5;
277 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& n ) {
278 EXPECT_EQ( n.first.nKey * 5, n.second.val );
281 auto pair = l.update( i.key, []( bool bNew, list_value_type& n ) {
282 EXPECT_FALSE( bNew );
283 EXPECT_EQ( n.first.nKey * 5, n.second.val );
284 n.second.val = n.first.nKey * 3;
286 EXPECT_TRUE( pair.first );
287 EXPECT_FALSE( pair.second );
289 EXPECT_FALSE( l.empty());
292 ASSERT_FALSE( l.empty());
293 EXPECT_CONTAINER_SIZE( l, nSize );
296 for ( auto const&i : arr ) {
297 switch ( i.key & 3 ) {
299 EXPECT_TRUE( l.erase( i.key ));
302 EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less()));
305 EXPECT_TRUE( l.erase( i.key, [ &i ]( list_value_type const& n ) {
306 EXPECT_EQ( n.first.nKey, i.key );
307 EXPECT_EQ( n.first.nKey * 3, n.second.val );
311 EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less(), [ &i ]( list_value_type const& n) {
312 EXPECT_EQ( n.first.nKey, i.key );
313 EXPECT_EQ( n.first.nKey * 3, n.second.val );
317 EXPECT_FALSE( l.contains( i.key ));
318 EXPECT_FALSE( l.contains( key_type( i.key )));
319 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
320 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
321 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
322 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
325 ASSERT_TRUE( l.empty());
326 EXPECT_CONTAINER_SIZE( l, 0 );
329 for ( auto& i : arr )
330 EXPECT_TRUE( l.insert( i.key, i.val ));
332 ASSERT_FALSE( l.empty());
333 EXPECT_CONTAINER_SIZE( l, nSize );
337 ASSERT_TRUE( l.empty());
338 EXPECT_CONTAINER_SIZE( l, 0 );
340 // empty list iterator test
343 EXPECT_TRUE( l.begin() == l.end());
344 EXPECT_TRUE( l.cbegin() == l.cend());
345 EXPECT_TRUE( cl.begin() == cl.end());
346 EXPECT_TRUE( l.begin() == l.cend());
347 EXPECT_TRUE( cl.begin() == l.end());
351 template <typename List>
352 void test_ordered_iterator( List& l )
354 // Precondition: list is empty
355 // Postcondition: list is empty
357 static const size_t nSize = 20;
364 for ( size_t i = 0; i < nSize; ++i ) {
365 arr[i].key = static_cast<int>(i);
366 arr[i].val = arr[i].key;
368 shuffle( arr, arr + nSize );
370 ASSERT_TRUE( l.empty());
371 ASSERT_CONTAINER_SIZE( l, 0 );
373 for ( auto& i : arr )
374 EXPECT_TRUE( l.insert( i.key, i.val ));
377 for ( auto& it : l ) {
378 EXPECT_EQ( key, it.first.key());
379 EXPECT_EQ( it.second.val, it.first.key());
380 it.second.val = it.first.key() * 10;
383 EXPECT_EQ( static_cast<size_t>(key), nSize );
386 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
387 EXPECT_EQ( key, it->first.key());
388 EXPECT_EQ( it->first.key() * 10, it->second.val );
391 EXPECT_EQ( static_cast<size_t>(key), nSize );
394 for ( auto it = l.begin(); it != l.end(); ++it ) {
395 EXPECT_EQ( key, it->first.key());
396 EXPECT_EQ( it->first.key() * 10, it->second.val );
397 it->second.val = it->first.key() * 2;
400 EXPECT_EQ( static_cast<size_t>(key), nSize );
404 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
405 EXPECT_EQ( key, it->first.nKey );
406 EXPECT_EQ( it->first.nKey * 2, it->second.val );
409 EXPECT_EQ( static_cast<size_t>(key), nSize );
412 ASSERT_TRUE( l.empty());
413 EXPECT_CONTAINER_SIZE( l, 0 );
417 } // namespace cds_test
419 #endif // CDSUNIT_LIST_TEST_KV_LIST_H