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::key_type list_key_type;
151 typedef typename List::mapped_type list_mapped_type;
152 typedef typename List::value_type list_value_type;
160 for ( size_t i = 0; i < nSize; ++i ) {
161 arr[i].key = static_cast<int>(i) + 1;
162 arr[i].val = arr[i].key * 10;
164 shuffle( arr, arr + nSize );
166 ASSERT_TRUE( l.empty() );
167 ASSERT_CONTAINER_SIZE( l, 0 );
170 for ( auto const& i : arr ) {
171 EXPECT_TRUE( l.contains( i.key ) == l.end());
172 EXPECT_TRUE( l.contains( key_type( i.key )) == l.end());
173 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) == l.end());
175 switch ( i.key % 5 ) {
178 auto it = l.insert( i.key );
179 ASSERT_FALSE( it == l.end());
180 EXPECT_EQ( it->first.key, i.key );
181 EXPECT_EQ( it->second.val, 0 );
182 it = l.contains( i.key );
183 EXPECT_FALSE( it == l.end() );
184 EXPECT_EQ( it->first.key, i.key );
185 EXPECT_EQ( it->second.val, 0 );
186 it = l.insert( i.key );
187 EXPECT_TRUE( it == l.end() );
192 auto it = l.insert( i.key, i.val );
193 ASSERT_FALSE( it == l.end() );
194 EXPECT_EQ( it->first.key, i.key );
195 EXPECT_EQ( it->second.val, i.val );
196 it = l.contains( key_type( i.key ));
197 EXPECT_FALSE( it == l.end() );
198 EXPECT_EQ( it->first.key, i.key );
199 EXPECT_EQ( it->second.val, i.val );
200 it = l.insert( key_type( i.key ), i.val );
201 EXPECT_TRUE( it == l.end() );
206 auto it = l.emplace( i.key, i.key * 100 );
207 ASSERT_FALSE( it == l.end() );
208 EXPECT_EQ( it->first.key, i.key );
209 EXPECT_EQ( it->second.val, i.key * 100 );
210 it = l.contains( other_key( i.key ), other_less());
211 ASSERT_FALSE( it == l.end() );
212 EXPECT_EQ( it->first.key, i.key );
213 EXPECT_EQ( it->second.val, i.key * 100 );
214 it = l.emplace( i.key, i.key * 50 );
215 EXPECT_TRUE( it == l.end() );
220 auto pair = l.update( i.key, false );
221 EXPECT_TRUE( pair.first == l.end());
222 EXPECT_FALSE( pair.second );
224 pair = l.update( i.key );
225 ASSERT_FALSE( pair.first == l.end() );
226 EXPECT_TRUE( pair.second );
227 pair.first->second.val = i.key * 3;
229 auto it = l.contains( other_key( i.key ), other_less() );
230 ASSERT_FALSE( it == l.end() );
231 EXPECT_TRUE( it == pair.first );
232 EXPECT_EQ( it->first.key, i.key );
233 EXPECT_EQ( it->second.val, i.key * 3 );
235 pair = l.update( i.key, false );
236 ASSERT_FALSE( pair.first == l.end() );
237 EXPECT_TRUE( pair.first == it );
238 EXPECT_FALSE( pair.second );
239 EXPECT_EQ( pair.first->first.key, i.key );
240 pair.first->second.val = i.key * 5;
242 it = l.contains( other_key( i.key ), other_less() );
243 ASSERT_FALSE( it == l.end() );
244 EXPECT_TRUE( it == pair.first );
245 EXPECT_EQ( it->first.key, i.key );
246 EXPECT_EQ( it->second.val, i.key * 5 );
251 auto it = l.insert_with( key_type( i.key ), [&i]( list_value_type& n ) {
252 EXPECT_EQ( i.key, n.first.key );
253 n.second.val = n.first.key * 7;
255 ASSERT_FALSE( it == l.end() );
256 EXPECT_EQ( it->first.key, i.key );
257 EXPECT_EQ( it->second.val, i.key * 7 );
258 it = l.contains( i.key );
259 ASSERT_FALSE( it == l.end() );
260 EXPECT_EQ( it->first.key, i.key );
261 EXPECT_EQ( it->second.val, i.key * 7 );
262 it = l.insert_with( i.key, []( list_value_type& ) {
263 EXPECT_TRUE( false );
265 EXPECT_TRUE( it == l.end() );
270 EXPECT_TRUE( l.contains( i.key ) != l.end());
271 EXPECT_TRUE( l.contains( key_type( i.key )) != l.end());
272 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) != l.end());
274 EXPECT_FALSE( l.empty() );
277 ASSERT_FALSE( l.empty() );
278 EXPECT_CONTAINER_SIZE( l, nSize );
282 ASSERT_TRUE( l.empty() );
283 EXPECT_CONTAINER_SIZE( l, 0 );
285 // empty list iterator test
288 EXPECT_TRUE( l.begin() == l.end());
289 EXPECT_TRUE( l.cbegin() == l.cend());
290 EXPECT_TRUE( cl.begin() == cl.end());
291 EXPECT_TRUE( l.begin() == l.cend());
292 EXPECT_TRUE( cl.begin() == l.end());
296 template <typename List>
297 void test_ordered_iterator( List& l )
299 // Precondition: list is empty
300 // Postcondition: list is empty
302 static const size_t nSize = 20;
303 typedef typename List::key_type list_key_type;
304 typedef typename List::mapped_type list_mapped_type;
305 typedef typename List::value_type list_value_type;
313 for ( size_t i = 0; i < nSize; ++i ) {
314 arr[i].key = static_cast<int>(i);
315 arr[i].val = arr[i].key;
317 shuffle( arr, arr + nSize );
319 ASSERT_TRUE( l.empty() );
320 ASSERT_CONTAINER_SIZE( l, 0 );
322 for ( auto& i : arr )
323 EXPECT_TRUE( l.insert( i.key, i.val ) != l.end());
326 for ( auto& it : l ) {
327 EXPECT_EQ( key, it.first.key );
328 EXPECT_EQ( it.second.val, it.first.key );
329 it.second.val = it.first.key * 10;
332 EXPECT_EQ( static_cast<size_t>(key), nSize );
335 for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
336 EXPECT_EQ( key, it->first.key );
337 EXPECT_EQ( key, (*it).first.key );
338 EXPECT_EQ( it->first.key * 10, it->second.val );
341 EXPECT_EQ( static_cast<size_t>(key), nSize );
344 for ( auto it = l.begin(); it != l.end(); ++it ) {
345 EXPECT_EQ( key, it->first.key );
346 EXPECT_EQ( it->first.key * 10, it->second.val );
347 it->second.val = it->first.key * 2;
350 EXPECT_EQ( static_cast<size_t>(key), nSize );
354 for ( auto it = cl.begin(); it != cl.end(); ++it ) {
355 EXPECT_EQ( key, it->first.key );
356 EXPECT_EQ( it->first.key * 2, it->second.val );
359 EXPECT_EQ( static_cast<size_t>(key), nSize );
362 ASSERT_TRUE( l.empty() );
363 EXPECT_CONTAINER_SIZE( l, 0 );
367 } // namespace cds_test
369 #endif // CDSUNIT_LIST_TEST_KV_LIST_NOGC_H