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_ITERABLE_LIST_H
32 #define CDSUNIT_LIST_TEST_ITERABLE_LIST_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
39 class iterable_list_test : public fixture
54 item( int key, int val )
73 bool operator ()( const T& v1, const T& v2 ) const
75 return v1.key() < v2.key();
79 bool operator ()( const T& v1, const Q& v2 ) const
85 bool operator ()( const Q& v1, const T& v2 ) const
93 int operator ()( const T& v1, const T& v2 ) const
95 if ( v1.key() < v2.key())
97 return v1.key() > v2.key() ? 1 : 0;
100 template <typename Q>
101 int operator ()( const T& v1, const Q& v2 ) const
105 return v1.key() > v2 ? 1 : 0;
108 template <typename Q>
109 int operator ()( const Q& v1, const T& v2 ) const
113 return v1 > v2.key() ? 1 : 0;
131 template <typename T1, typename T2>
132 bool operator()( T1 const& t1, T2 const& t2 ) const
134 return t1.nKey < t2.nKey;
139 template <typename List>
140 void test_common( List& l )
142 // Precondition: list is empty
143 // Postcondition: list is empty
145 static const size_t nSize = 20;
146 typedef typename List::value_type value_type;
147 value_type arr[nSize];
149 for ( size_t i = 0; i < nSize; ++i ) {
150 arr[i].nKey = static_cast<int>(i);
151 arr[i].nVal = arr[i].nKey * 10;
153 shuffle( arr, arr + nSize );
155 ASSERT_TRUE( l.empty());
156 ASSERT_CONTAINER_SIZE( l, 0 );
159 for ( auto const& i : arr ) {
160 EXPECT_FALSE( l.contains( i ));
161 EXPECT_FALSE( l.contains( i.nKey ));
162 EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less()));
163 EXPECT_TRUE( l.find( i ) == l.end());
164 EXPECT_FALSE( l.find( i, []( value_type&, value_type const&) {} ));
165 EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} ));
166 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} ));
167 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less()) == l.end());
169 switch ( i.nKey % 5 ) {
171 EXPECT_TRUE( l.insert( i.nKey ));
172 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
173 EXPECT_EQ( n.nVal, key * 2 );
175 EXPECT_FALSE( l.insert( i.nKey ));
178 EXPECT_TRUE( l.insert( i, []( value_type& n ) {
181 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
182 EXPECT_EQ( n.nVal, key * 3 );
184 EXPECT_FALSE( l.insert( i ));
187 EXPECT_TRUE( l.emplace( i.nKey, i.nKey * 100 ));
188 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
189 EXPECT_EQ( n.nVal, key * 100 );
191 EXPECT_FALSE( l.insert( i ));
195 auto pair = l.update( i.nKey, []( value_type& n, value_type* old) {
196 EXPECT_TRUE( old == nullptr );
199 EXPECT_FALSE( pair.first );
200 EXPECT_FALSE( pair.second );
202 pair = l.update( i.nKey, []( value_type& n, value_type* old ) {
203 EXPECT_TRUE( old == nullptr );
206 EXPECT_TRUE( pair.first );
207 EXPECT_TRUE( pair.second );
209 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
210 EXPECT_EQ( n.nVal, key * 3 );
212 EXPECT_FALSE( l.insert( i ));
217 auto pair = l.upsert( i.nKey, false );
218 EXPECT_FALSE( pair.first );
219 EXPECT_FALSE( pair.second );
221 pair = l.upsert( i.nKey );
222 EXPECT_TRUE( pair.first );
223 EXPECT_TRUE( pair.second );
225 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
226 EXPECT_EQ( n.nVal, key * 2 );
228 EXPECT_FALSE( l.insert( i ));
233 EXPECT_TRUE( l.contains( i ));
234 EXPECT_TRUE( l.contains( i.nKey ));
235 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
236 EXPECT_TRUE( l.find( i, []( value_type& n, value_type const& arg ) {
237 EXPECT_EQ( arg.nKey, n.nKey );
240 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
241 EXPECT_EQ( key, n.nKey );
242 EXPECT_EQ( n.nKey, n.nVal );
245 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& n, other_item const& key ) {
246 EXPECT_EQ( key.nKey, n.nKey );
247 EXPECT_EQ( n.nKey * 5, n.nVal );
249 ASSERT_FALSE( l.find( i ) == l.end());
250 EXPECT_EQ( l.find( i.nKey )->nKey, i.nKey );
251 ASSERT_FALSE( l.find_with( other_item( i.nKey ), other_less()) == l.end());
252 EXPECT_EQ( l.find_with( other_item( i.nKey ), other_less())->nKey, i.nKey );
254 auto pair = l.upsert( i.nKey, false );
255 EXPECT_TRUE( pair.first );
256 EXPECT_FALSE( pair.second );
258 pair = l.update( i.nKey, []( value_type& n, value_type* old ) {
259 ASSERT_FALSE( old == nullptr );
260 EXPECT_EQ( old->nKey, n.nKey );
261 EXPECT_EQ( old->nKey * 2, n.nVal );
262 n.nVal = old->nKey * 3;
264 EXPECT_TRUE( pair.first );
265 EXPECT_FALSE( pair.second );
267 EXPECT_FALSE( l.empty());
270 ASSERT_FALSE( l.empty());
271 EXPECT_CONTAINER_SIZE( l, nSize );
274 for ( auto const&i : arr ) {
275 ASSERT_FALSE( l.find( i.nKey ) == l.end());
276 EXPECT_EQ( l.find( i.nKey )->nKey, i.nKey );
277 ASSERT_FALSE( l.find_with( other_item( i.nKey ), other_less()) == l.end());
278 EXPECT_EQ( l.find_with( other_item( i.nKey ), other_less())->nKey, i.nKey );
280 switch ( i.nKey % 4 ) {
282 EXPECT_TRUE( l.erase( i.nKey ));
285 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less()));
288 EXPECT_TRUE( l.erase( i, [ &i ]( value_type const& n ) {
289 EXPECT_EQ( n.nKey, i.nKey );
290 EXPECT_EQ( n.nKey * 3, n.nVal );
294 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), [ &i ]( value_type const& n) {
295 EXPECT_EQ( n.nKey, i.nKey );
296 EXPECT_EQ( n.nKey * 3, n.nVal );
300 EXPECT_FALSE( l.contains( i ));
301 EXPECT_FALSE( l.contains( i.nKey ));
302 EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less()));
303 EXPECT_FALSE( l.find( i, []( value_type&, value_type const&) {} ));
304 EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} ));
305 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} ));
306 EXPECT_TRUE( l.find( i ) == l.end());
307 EXPECT_TRUE( l.find( i.nKey ) == l.end());
308 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less()) == l.end());
311 ASSERT_TRUE( l.empty());
312 EXPECT_CONTAINER_SIZE( l, 0 );
315 for ( auto& i : arr )
316 EXPECT_TRUE( l.insert( i ));
318 ASSERT_FALSE( l.empty());
319 EXPECT_CONTAINER_SIZE( l, nSize );
323 ASSERT_TRUE( l.empty());
324 EXPECT_CONTAINER_SIZE( l, 0 );
326 // empty list iterator test
329 EXPECT_TRUE( l.begin() == l.end());
330 EXPECT_TRUE( l.cbegin() == l.cend());
331 EXPECT_TRUE( cl.begin() == cl.end());
332 EXPECT_TRUE( l.begin() == l.cend());
333 EXPECT_TRUE( cl.begin() == l.end());
337 template <typename List>
338 void test_ordered_iterator( List& l )
340 // Precondition: list is empty
341 // Postcondition: list is empty
343 static const size_t nSize = 20;
344 typedef typename List::value_type value_type;
345 value_type arr[nSize];
347 for ( size_t i = 0; i < nSize; ++i ) {
348 arr[i].nKey = static_cast<int>(i);
349 arr[i].nVal = arr[i].nKey;
351 shuffle( arr, arr + nSize );
353 ASSERT_TRUE( l.empty());
354 ASSERT_CONTAINER_SIZE( l, 0 );
356 for ( auto& i : arr )
357 EXPECT_TRUE( l.insert( i ));
360 for ( auto& it : l ) {
361 EXPECT_EQ( key, it.nKey );
362 EXPECT_EQ( it.nVal, it.nKey );
363 it.nVal = it.nKey * 10;
366 EXPECT_EQ( static_cast<size_t>(key), nSize );
369 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
370 EXPECT_EQ( key, it->nKey );
371 EXPECT_EQ( key, (*it).nKey );
372 EXPECT_EQ( it->nKey * 10, it->nVal );
375 EXPECT_EQ( static_cast<size_t>(key), nSize );
378 for ( auto it = l.begin(); it != l.end(); ++it ) {
379 EXPECT_EQ( key, it->nKey );
380 EXPECT_EQ( key, (*it).nKey );
381 EXPECT_EQ( it->nKey * 10, it->nVal );
382 it->nVal = it->nKey * 2;
385 EXPECT_EQ( static_cast<size_t>(key), nSize );
389 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
390 EXPECT_EQ( key, it->nKey );
391 EXPECT_EQ( key, (*it).nKey );
392 EXPECT_EQ( it->nKey * 2, it->nVal );
395 EXPECT_EQ( static_cast<size_t>(key), nSize );
398 ASSERT_TRUE( l.empty());
399 EXPECT_CONTAINER_SIZE( l, 0 );
403 } // namespace cds_test
405 #endif // CDSUNIT_LIST_TEST_ITERABLE_LIST_H