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_LIST_H
32 #define CDSUNIT_LIST_TEST_LIST_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
39 class list_common : 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_FALSE( l.find( i, []( value_type&, value_type const&) {} ));
164 EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} ));
165 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} ));
167 switch ( i.nKey & 3 ) {
169 EXPECT_TRUE( l.insert( i.nKey ));
170 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
171 EXPECT_EQ( n.nVal, key * 2 );
173 EXPECT_FALSE( l.insert( i.nKey ));
176 EXPECT_TRUE( l.insert( i, []( value_type& n ) {
179 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
180 EXPECT_EQ( n.nVal, key * 3 );
182 EXPECT_FALSE( l.insert( i ));
185 EXPECT_TRUE( l.emplace( i.nKey, i.nKey * 100 ));
186 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
187 EXPECT_EQ( n.nVal, key * 100 );
189 EXPECT_FALSE( l.insert( i ));
193 auto pair = l.update( i.nKey, []( bool bNew, value_type& n, int key ) {
195 EXPECT_EQ( key, n.nKey );
198 EXPECT_FALSE( pair.first );
199 EXPECT_FALSE( pair.second );
201 pair = l.update( i.nKey, []( bool bNew, value_type& n, int key ) {
203 EXPECT_EQ( key, n.nKey );
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 EXPECT_TRUE( l.contains( i ));
218 EXPECT_TRUE( l.contains( i.nKey ));
219 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
220 EXPECT_TRUE( l.find( i, []( value_type& n, value_type const& arg ) {
221 EXPECT_EQ( arg.nKey, n.nKey );
224 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
225 EXPECT_EQ( key, n.nKey );
226 EXPECT_EQ( n.nKey, n.nVal );
229 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& n, other_item const& key ) {
230 EXPECT_EQ( key.nKey, n.nKey );
231 EXPECT_EQ( n.nKey * 5, n.nVal );
234 auto pair = l.update( i.nKey, []( bool bNew, value_type& n, int key ) {
235 EXPECT_FALSE( bNew );
236 EXPECT_EQ( key, n.nKey );
237 EXPECT_EQ( key * 5, n.nVal );
240 EXPECT_TRUE( pair.first );
241 EXPECT_FALSE( pair.second );
243 EXPECT_FALSE( l.empty() );
246 ASSERT_FALSE( l.empty() );
247 EXPECT_CONTAINER_SIZE( l, nSize );
250 for ( auto const&i : arr ) {
251 switch ( i.nKey & 3 ) {
253 EXPECT_TRUE( l.erase( i.nKey ));
256 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less()));
259 EXPECT_TRUE( l.erase( i, [ &i ]( value_type const& n ) {
260 EXPECT_EQ( n.nKey, i.nKey );
261 EXPECT_EQ( n.nKey * 3, n.nVal );
265 EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), [ &i ]( value_type const& n) {
266 EXPECT_EQ( n.nKey, i.nKey );
267 EXPECT_EQ( n.nKey * 3, n.nVal );
271 EXPECT_FALSE( l.contains( i ));
272 EXPECT_FALSE( l.contains( i.nKey ));
273 EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less()));
274 EXPECT_FALSE( l.find( i, []( value_type&, value_type const&) {} ));
275 EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} ));
276 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} ));
279 ASSERT_TRUE( l.empty() );
280 EXPECT_CONTAINER_SIZE( l, 0 );
283 for ( auto& i : arr )
284 EXPECT_TRUE( l.insert( i ));
286 ASSERT_FALSE( l.empty() );
287 EXPECT_CONTAINER_SIZE( l, nSize );
291 ASSERT_TRUE( l.empty() );
292 EXPECT_CONTAINER_SIZE( l, 0 );
294 // empty list iterator test
297 EXPECT_TRUE( l.begin() == l.end());
298 EXPECT_TRUE( l.cbegin() == l.cend());
299 EXPECT_TRUE( cl.begin() == cl.end());
300 EXPECT_TRUE( l.begin() == l.cend());
301 EXPECT_TRUE( cl.begin() == l.end());
305 template <typename List>
306 void test_ordered_iterator( List& l )
308 // Precondition: list is empty
309 // Postcondition: list is empty
311 static const size_t nSize = 20;
312 typedef typename List::value_type value_type;
313 value_type arr[nSize];
315 for ( size_t i = 0; i < nSize; ++i ) {
316 arr[i].nKey = static_cast<int>(i);
317 arr[i].nVal = arr[i].nKey;
319 shuffle( arr, arr + nSize );
321 ASSERT_TRUE( l.empty() );
322 ASSERT_CONTAINER_SIZE( l, 0 );
324 for ( auto& i : arr )
325 EXPECT_TRUE( l.insert( i ));
328 for ( auto& it : l ) {
329 EXPECT_EQ( key, it.nKey );
330 EXPECT_EQ( it.nVal, it.nKey );
331 it.nVal = it.nKey * 10;
334 EXPECT_EQ( static_cast<size_t>(key), nSize );
337 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
338 EXPECT_EQ( key, it->nKey );
339 EXPECT_EQ( key, (*it).nKey );
340 EXPECT_EQ( it->nKey * 10, it->nVal );
343 EXPECT_EQ( static_cast<size_t>(key), nSize );
346 for ( auto it = l.begin(); it != l.end(); ++it ) {
347 EXPECT_EQ( key, it->nKey );
348 EXPECT_EQ( key, (*it).nKey );
349 EXPECT_EQ( it->nKey * 10, it->nVal );
350 it->nVal = it->nKey * 2;
353 EXPECT_EQ( static_cast<size_t>(key), nSize );
357 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
358 EXPECT_EQ( key, it->nKey );
359 EXPECT_EQ( key, (*it).nKey );
360 EXPECT_EQ( it->nKey * 2, it->nVal );
363 EXPECT_EQ( static_cast<size_t>(key), nSize );
366 ASSERT_TRUE( l.empty() );
367 EXPECT_CONTAINER_SIZE( l, 0 );
371 } // namespace cds_test
373 #endif // CDSUNIT_LIST_TEST_LIST_H