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_LIST_NOGC_H
32 #define CDSUNIT_LIST_TEST_KV_LIST_NOGC_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
39 class kv_list_nogc : public fixture
46 explicit key_type( int n )
50 key_type( key_type const& s )
54 key_type( key_type&& s )
68 explicit value_type( int n )
75 bool operator()( key_type const& lhs, key_type const& rhs ) const
77 return lhs.key < rhs.key;
80 bool operator()( key_type const& lhs, int rhs ) const
85 bool operator()( int lhs, key_type const& rhs ) const
91 bool operator ()( T const& v1, T const& v2 ) const
93 return v1.key < v2.key;
99 int operator()( key_type const& lhs, key_type const& rhs ) const
101 return lhs.key - rhs.key;
104 int operator()( key_type const& lhs, int rhs ) const
106 return lhs.key - rhs;
109 int operator()( int lhs, key_type const& rhs ) const
111 return lhs - rhs.key;
114 template <typename T>
115 int operator ()( T const& lhs, T const& rhs ) const
117 return lhs.key - rhs.key;
135 template <typename T1, typename T2>
136 bool operator()( T1 const& t1, T2 const& t2 ) const
138 return t1.key < t2.key;
143 template <typename List>
146 // Precondition: list is empty
147 // Postcondition: list is empty
149 static const size_t nSize = 20;
150 typedef typename List::value_type list_value_type;
158 for ( size_t i = 0; i < nSize; ++i ) {
159 arr[i].key = static_cast<int>(i) + 1;
160 arr[i].val = arr[i].key * 10;
162 shuffle( arr, arr + nSize );
164 ASSERT_TRUE( l.empty());
165 ASSERT_CONTAINER_SIZE( l, 0 );
168 for ( key_val const& i : arr ) {
169 EXPECT_TRUE( l.contains( i.key ) == l.end());
170 EXPECT_TRUE( l.contains( key_type( i.key )) == l.end());
171 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) == l.end());
173 switch ( i.key % 5 ) {
176 auto it = l.insert( i.key );
177 ASSERT_FALSE( it == l.end());
178 EXPECT_EQ( it->first.key, i.key );
179 EXPECT_EQ( it->second.val, 0 );
180 it = l.contains( i.key );
181 EXPECT_FALSE( it == l.end());
182 EXPECT_EQ( it->first.key, i.key );
183 EXPECT_EQ( it->second.val, 0 );
184 it = l.insert( i.key );
185 EXPECT_TRUE( it == l.end());
190 auto it = l.insert( i.key, i.val );
191 ASSERT_FALSE( it == l.end());
192 EXPECT_EQ( it->first.key, i.key );
193 EXPECT_EQ( it->second.val, i.val );
194 it = l.contains( key_type( i.key ));
195 EXPECT_FALSE( it == l.end());
196 EXPECT_EQ( it->first.key, i.key );
197 EXPECT_EQ( it->second.val, i.val );
198 it = l.insert( key_type( i.key ), i.val );
199 EXPECT_TRUE( it == l.end());
204 auto it = l.emplace( i.key, i.key * 100 );
205 ASSERT_FALSE( it == l.end());
206 EXPECT_EQ( it->first.key, i.key );
207 EXPECT_EQ( it->second.val, i.key * 100 );
208 it = l.contains( other_key( i.key ), other_less());
209 ASSERT_FALSE( it == l.end());
210 EXPECT_EQ( it->first.key, i.key );
211 EXPECT_EQ( it->second.val, i.key * 100 );
212 it = l.emplace( i.key, i.key * 50 );
213 EXPECT_TRUE( it == l.end());
218 auto pair = l.update( i.key, false );
219 EXPECT_TRUE( pair.first == l.end());
220 EXPECT_FALSE( pair.second );
222 pair = l.update( i.key );
223 ASSERT_FALSE( pair.first == l.end());
224 EXPECT_TRUE( pair.second );
225 pair.first->second.val = i.key * 3;
227 auto it = l.contains( other_key( i.key ), other_less());
228 ASSERT_FALSE( it == l.end());
229 EXPECT_TRUE( it == pair.first );
230 EXPECT_EQ( it->first.key, i.key );
231 EXPECT_EQ( it->second.val, i.key * 3 );
233 pair = l.update( i.key, false );
234 ASSERT_FALSE( pair.first == l.end());
235 EXPECT_TRUE( pair.first == it );
236 EXPECT_FALSE( pair.second );
237 EXPECT_EQ( pair.first->first.key, i.key );
238 pair.first->second.val = i.key * 5;
240 it = l.contains( other_key( i.key ), other_less());
241 ASSERT_FALSE( it == l.end());
242 EXPECT_TRUE( it == pair.first );
243 EXPECT_EQ( it->first.key, i.key );
244 EXPECT_EQ( it->second.val, i.key * 5 );
249 auto it = l.insert_with( key_type( i.key ), [&i]( list_value_type& n ) {
250 EXPECT_EQ( i.key, n.first.key );
251 n.second.val = n.first.key * 7;
253 ASSERT_FALSE( it == l.end());
254 EXPECT_EQ( it->first.key, i.key );
255 EXPECT_EQ( it->second.val, i.key * 7 );
256 it = l.contains( i.key );
257 ASSERT_FALSE( it == l.end());
258 EXPECT_EQ( it->first.key, i.key );
259 EXPECT_EQ( it->second.val, i.key * 7 );
260 it = l.insert_with( i.key, []( list_value_type& ) {
261 EXPECT_TRUE( false );
263 EXPECT_TRUE( it == l.end());
268 EXPECT_TRUE( l.contains( i.key ) != l.end());
269 EXPECT_TRUE( l.contains( key_type( i.key )) != l.end());
270 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) != l.end());
272 EXPECT_FALSE( l.empty());
275 ASSERT_FALSE( l.empty());
276 EXPECT_CONTAINER_SIZE( l, nSize );
280 ASSERT_TRUE( l.empty());
281 EXPECT_CONTAINER_SIZE( l, 0 );
283 // empty list iterator test
286 EXPECT_TRUE( l.begin() == l.end());
287 EXPECT_TRUE( l.cbegin() == l.cend());
288 EXPECT_TRUE( cl.begin() == cl.end());
289 EXPECT_TRUE( l.begin() == l.cend());
290 EXPECT_TRUE( cl.begin() == l.end());
294 template <typename List>
295 void test_ordered_iterator( List& l )
297 // Precondition: list is empty
298 // Postcondition: list is empty
300 static const size_t nSize = 20;
308 for ( size_t i = 0; i < nSize; ++i ) {
309 arr[i].key = static_cast<int>(i);
310 arr[i].val = arr[i].key;
312 shuffle( arr, arr + nSize );
314 ASSERT_TRUE( l.empty());
315 ASSERT_CONTAINER_SIZE( l, 0 );
317 for ( auto& i : arr )
318 EXPECT_TRUE( l.insert( i.key, i.val ) != l.end());
321 for ( auto& it : l ) {
322 EXPECT_EQ( key, it.first.key );
323 EXPECT_EQ( it.second.val, it.first.key );
324 it.second.val = it.first.key * 10;
327 EXPECT_EQ( static_cast<size_t>(key), nSize );
330 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
331 EXPECT_EQ( key, it->first.key );
332 EXPECT_EQ( key, (*it).first.key );
333 EXPECT_EQ( it->first.key * 10, it->second.val );
336 EXPECT_EQ( static_cast<size_t>(key), nSize );
339 for ( auto it = l.begin(); it != l.end(); ++it ) {
340 EXPECT_EQ( key, it->first.key );
341 EXPECT_EQ( it->first.key * 10, it->second.val );
342 it->second.val = it->first.key * 2;
345 EXPECT_EQ( static_cast<size_t>(key), nSize );
349 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
350 EXPECT_EQ( key, it->first.key );
351 EXPECT_EQ( it->first.key * 2, it->second.val );
354 EXPECT_EQ( static_cast<size_t>(key), nSize );
357 ASSERT_TRUE( l.empty());
358 EXPECT_CONTAINER_SIZE( l, 0 );
362 } // namespace cds_test
364 #endif // CDSUNIT_LIST_TEST_KV_LIST_NOGC_H