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_LIST_NOGC_H
32 #define CDSUNIT_LIST_TEST_LIST_NOGC_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
39 class list_nogc : 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>
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_TRUE( l.contains( i ) == l.end());
161 EXPECT_TRUE( l.contains( i.nKey ) == l.end());
162 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()) == l.end());
164 switch ( i.nKey & 3 ) {
167 auto it = l.insert( i.nKey );
168 EXPECT_FALSE( it == l.end());
169 EXPECT_EQ( it->nKey, i.nKey );
170 EXPECT_EQ( it->nVal, it->nKey * 2 );
171 it = l.contains( i.nKey );
172 EXPECT_FALSE( it == l.end());
173 EXPECT_EQ( it->nKey, i.nKey );
174 EXPECT_EQ( it->nVal, it->nKey * 2 );
175 it = l.insert( i.nKey );
176 EXPECT_TRUE( it == l.end());
181 auto it = l.insert( i );
182 EXPECT_FALSE( it == l.end());
183 EXPECT_EQ( it->nKey, i.nKey );
184 EXPECT_EQ( it->nVal, i.nVal );
185 it = l.contains( i );
186 EXPECT_FALSE( it == l.end());
187 EXPECT_EQ( it->nKey, i.nKey );
188 EXPECT_EQ( it->nVal, i.nVal );
190 EXPECT_TRUE( it == l.end());
195 auto it = l.emplace( i.nKey, i.nKey * 100 );
196 EXPECT_FALSE( it == l.end());
197 EXPECT_EQ( it->nKey, i.nKey );
198 EXPECT_EQ( it->nVal, i.nKey * 100 );
199 it = l.contains( other_item( i.nKey ), other_less());
200 EXPECT_FALSE( it == l.end());
201 EXPECT_EQ( it->nKey, i.nKey );
202 EXPECT_EQ( it->nVal, i.nKey * 100 );
203 it = l.emplace( i.nKey, i.nKey * 50 );
204 EXPECT_TRUE( it == l.end());
209 auto pair = l.update( i.nKey, false );
210 EXPECT_TRUE( pair.first == l.end());
211 EXPECT_FALSE( pair.second );
213 pair = l.update( i.nKey );
214 EXPECT_FALSE( pair.first == l.end());
215 EXPECT_TRUE( pair.second );
216 pair.first->nVal = i.nKey * 3;
217 EXPECT_EQ( pair.first->nKey, i.nKey );
219 auto it = l.contains( other_item( i.nKey ), other_less());
220 EXPECT_FALSE( it == l.end());
221 EXPECT_TRUE( it == pair.first );
222 EXPECT_EQ( it->nKey, i.nKey );
223 EXPECT_EQ( it->nVal, i.nKey * 3 );
225 pair = l.update( i.nKey, false );
226 EXPECT_FALSE( pair.first == l.end());
227 EXPECT_TRUE( pair.first == it );
228 EXPECT_FALSE( pair.second );
229 EXPECT_EQ( pair.first->nKey, i.nKey );
230 pair.first->nVal = i.nKey * 5;
232 it = l.contains( other_item( i.nKey ), other_less());
233 EXPECT_FALSE( it == l.end());
234 EXPECT_TRUE( it == pair.first );
235 EXPECT_EQ( it->nKey, i.nKey );
236 EXPECT_EQ( it->nVal, i.nKey * 5 );
241 EXPECT_TRUE( l.contains( i ) != l.end());
242 EXPECT_TRUE( l.contains( i.nKey ) != l.end());
243 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()) != l.end());
245 EXPECT_FALSE( l.empty());
248 ASSERT_FALSE( l.empty());
249 EXPECT_CONTAINER_SIZE( l, nSize );
253 ASSERT_TRUE( l.empty());
254 EXPECT_CONTAINER_SIZE( l, 0 );
256 // empty list iterator test
259 EXPECT_TRUE( l.begin() == l.end());
260 EXPECT_TRUE( l.cbegin() == l.cend());
261 EXPECT_TRUE( cl.begin() == cl.end());
262 EXPECT_TRUE( l.begin() == l.cend());
263 EXPECT_TRUE( cl.begin() == l.end());
267 template <typename List>
268 void test_ordered_iterator( List& l )
270 // Precondition: list is empty
271 // Postcondition: list is empty
273 static const size_t nSize = 20;
274 typedef typename List::value_type value_type;
275 value_type arr[nSize];
277 for ( size_t i = 0; i < nSize; ++i ) {
278 arr[i].nKey = static_cast<int>(i);
279 arr[i].nVal = arr[i].nKey;
281 shuffle( arr, arr + nSize );
283 ASSERT_TRUE( l.empty());
284 ASSERT_CONTAINER_SIZE( l, 0 );
286 for ( auto& i : arr )
287 EXPECT_TRUE( l.insert( i ) != l.end());
290 for ( auto& it : l ) {
291 EXPECT_EQ( key, it.nKey );
292 EXPECT_EQ( it.nVal, it.nKey );
293 it.nVal = it.nKey * 10;
296 EXPECT_EQ( static_cast<size_t>(key), nSize );
299 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
300 EXPECT_EQ( key, it->nKey );
301 EXPECT_EQ( key, (*it).nKey );
302 EXPECT_EQ( it->nKey * 10, it->nVal );
305 EXPECT_EQ( static_cast<size_t>(key), nSize );
308 for ( auto it = l.begin(); it != l.end(); ++it ) {
309 EXPECT_EQ( key, it->nKey );
310 EXPECT_EQ( key, (*it).nKey );
311 EXPECT_EQ( it->nKey * 10, it->nVal );
312 it->nVal = it->nKey * 2;
315 EXPECT_EQ( static_cast<size_t>(key), nSize );
319 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
320 EXPECT_EQ( key, it->nKey );
321 EXPECT_EQ( key, (*it).nKey );
322 EXPECT_EQ( it->nKey * 2, it->nVal );
325 EXPECT_EQ( static_cast<size_t>(key), nSize );
328 ASSERT_TRUE( l.empty());
329 EXPECT_CONTAINER_SIZE( l, 0 );
333 } // namespace cds_test
335 #endif // CDSUNIT_LIST_TEST_LIST_NOGC_H