1//Has to be first for StackAllocator swap overload to be taken
2//into account (at least using GCC 4.0.1)
3#include "stack_allocator.h"
4
5#include <list>
6#include <algorithm>
7#include <functional>
8
9#include "cppunit/cppunit_proxy.h"
10
11#if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)
12using namespace std;
13#endif
14
15//
16// TestCase class
17//
18class ListTest : public CPPUNIT_NS::TestCase
19{
20  CPPUNIT_TEST_SUITE(ListTest);
21  CPPUNIT_TEST(list1);
22  CPPUNIT_TEST(list2);
23  CPPUNIT_TEST(list3);
24  CPPUNIT_TEST(list4);
25  CPPUNIT_TEST(erase);
26  CPPUNIT_TEST(resize);
27  CPPUNIT_TEST(push_back);
28  CPPUNIT_TEST(push_front);
29  CPPUNIT_TEST(allocator_with_state);
30  CPPUNIT_TEST(swap);
31  CPPUNIT_TEST(adl);
32  //CPPUNIT_TEST(const_list);
33  CPPUNIT_TEST_SUITE_END();
34
35protected:
36  void list1();
37  void list2();
38  void list3();
39  void list4();
40  void erase();
41  void resize();
42  void push_back();
43  void push_front();
44  void allocator_with_state();
45  void swap();
46  void adl();
47  //void const_list();
48};
49
50CPPUNIT_TEST_SUITE_REGISTRATION(ListTest);
51
52//
53// tests implementation
54//
55void ListTest::list1()
56{
57  int array1 [] = { 9, 16, 36 };
58  int array2 [] = { 1, 4 };
59
60  list<int> l1(array1, array1 + 3);
61  list<int> l2(array2, array2 + 2);
62  list<int>::iterator i1 = l1.begin();
63  list<int>::iterator i2 = l2.begin();
64  list<int>::const_iterator ci(i1);
65  list<int>::const_iterator ci1(ci);
66  l1.splice(i1, l2);
67  i1 = l1.begin();
68  CPPUNIT_ASSERT( *i1++ == 1 );
69  CPPUNIT_ASSERT( *i1++ == 4 );
70  CPPUNIT_ASSERT( *i1++ == 9 );
71  CPPUNIT_ASSERT( *i1++ == 16 );
72  CPPUNIT_ASSERT( *i1++ == 36 );
73
74#if defined (STLPORT) && \
75   (!defined (_STLP_DEBUG) || (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL))
76  CPPUNIT_ASSERT( i2 == l1.begin() );
77#endif
78
79  //Default construct check (_STLP_DEF_CONST_PLCT_NEW_BUG)
80  list<int> l(2);
81  i1 = l.begin();
82  CPPUNIT_ASSERT( *(i1++) == 0 );
83  CPPUNIT_ASSERT( *i1 == 0 );
84#if 0
85  //A small compilation time check to be activated from time to time,
86  //compilation should fail.
87  {
88    list<char>::iterator l_char_ite;
89    list<int>::iterator l_int_ite;
90    CPPUNIT_ASSERT( l_char_ite != l_int_ite );
91  }
92#endif
93}
94
95void ListTest::list2()
96{
97  int array1 [] = { 1, 16 };
98  int array2 [] = { 4, 9 };
99
100  list<int> l1(array1, array1 + 2);
101  list<int> l2(array2, array2 + 2);
102  list<int>::iterator i = l1.begin();
103  i++;
104  l1.splice(i, l2, l2.begin(), l2.end());
105  i = l1.begin();
106  CPPUNIT_ASSERT(*i++==1);
107  CPPUNIT_ASSERT(*i++==4);
108  CPPUNIT_ASSERT(*i++==9);
109  CPPUNIT_ASSERT(*i++==16);
110}
111
112void ListTest::list3()
113{
114  char array [] = { 'x', 'l', 'x', 't', 's', 's' };
115
116  list<char> str(array, array + 6);
117  list<char>::iterator i;
118
119  str.reverse();
120  i = str.begin();
121  CPPUNIT_ASSERT(*i++=='s');
122  CPPUNIT_ASSERT(*i++=='s');
123  CPPUNIT_ASSERT(*i++=='t');
124  CPPUNIT_ASSERT(*i++=='x');
125  CPPUNIT_ASSERT(*i++=='l');
126  CPPUNIT_ASSERT(*i++=='x');
127
128  str.remove('x');
129  i = str.begin();
130  CPPUNIT_ASSERT(*i++=='s');
131  CPPUNIT_ASSERT(*i++=='s');
132  CPPUNIT_ASSERT(*i++=='t');
133  CPPUNIT_ASSERT(*i++=='l');
134
135  str.unique();
136  i = str.begin();
137  CPPUNIT_ASSERT(*i++=='s');
138  CPPUNIT_ASSERT(*i++=='t');
139  CPPUNIT_ASSERT(*i++=='l');
140
141  str.sort();
142  i = str.begin();
143  CPPUNIT_ASSERT(*i++=='l');
144  CPPUNIT_ASSERT(*i++=='s');
145  CPPUNIT_ASSERT(*i++=='t');
146}
147
148void ListTest::list4()
149{
150  int array1 [] = { 1, 3, 6, 7 };
151  int array2 [] = { 2, 4 };
152
153  list<int> l1(array1, array1 + 4);
154  list<int> l2(array2, array2 + 2);
155  l1.merge(l2);
156  list<int>::iterator i = l1.begin();
157  CPPUNIT_ASSERT(*i++==1);
158  CPPUNIT_ASSERT(*i++==2);
159  CPPUNIT_ASSERT(*i++==3);
160  CPPUNIT_ASSERT(*i++==4);
161  CPPUNIT_ASSERT(*i++==6);
162  CPPUNIT_ASSERT(*i++==7);
163
164  //We use distance to avoid a simple call to an internal counter
165  CPPUNIT_ASSERT(distance(l1.begin(), l1.end()) == 6);
166  CPPUNIT_ASSERT(distance(l2.begin(), l2.end()) == 0);
167
168  l1.swap(l2);
169
170  CPPUNIT_ASSERT(distance(l1.begin(), l1.end()) == 0);
171  CPPUNIT_ASSERT(distance(l2.begin(), l2.end()) == 6);
172}
173
174void ListTest::erase()
175{
176  list<int> l;
177  l.push_back( 1 );
178  l.erase(l.begin());
179  CPPUNIT_ASSERT( l.empty() );
180
181  int array[] = { 0, 1, 2, 3 };
182  l.assign(array, array + 4);
183  list<int>::iterator lit;
184  lit = l.erase(l.begin());
185  CPPUNIT_ASSERT( *lit == 1 );
186
187  lit = l.erase(l.begin(), --l.end());
188  CPPUNIT_ASSERT( *lit == 3 );
189
190  l.clear();
191  CPPUNIT_ASSERT( l.empty() );
192}
193
194
195void ListTest::resize()
196{
197  {
198    list<int> l;
199    l.resize(5, 1);
200
201    size_t i;
202    list<int>::iterator lit(l.begin());
203    for (i = 0; i < 5; ++i) {
204      CPPUNIT_ASSERT( lit != l.end() );
205      CPPUNIT_ASSERT( *(lit++) == 1 );
206    }
207    CPPUNIT_ASSERT( lit == l.end() );
208
209    l.resize(3);
210    lit = l.begin();
211    for (i = 0; i < 3; ++i) {
212      CPPUNIT_ASSERT( lit != l.end() );
213      CPPUNIT_ASSERT( *(lit++) == 1 );
214    }
215    CPPUNIT_ASSERT( lit == l.end() );
216  }
217
218  {
219    list<int> l;
220    l.resize(5);
221
222    size_t i;
223    list<int>::iterator lit(l.begin());
224    for (i = 0; i < 5; ++i) {
225      CPPUNIT_ASSERT( lit != l.end() );
226      CPPUNIT_ASSERT( *(lit++) == 0 );
227    }
228    CPPUNIT_ASSERT( lit == l.end() );
229  }
230}
231
232void ListTest::push_back()
233{
234  list<int> l;
235  l.push_back( 1 );
236  l.push_back( 2 );
237  l.push_back( 3 );
238
239  list<int>::reverse_iterator r = l.rbegin();
240
241  CPPUNIT_ASSERT( *r == 3 );
242  l.push_back( 4 );
243  /*
244   * Following lines are commented, because ones show standard contradiction
245   * (24.4.1 and 23.2.2.3); but present behaviour is valid, 24.4.1, paragraphs 1 and 2,
246   * 24.4.1.3.3 and 23.1 paragraph 9 (Table 66). The 24.4.1 is more common rule,
247   * so it has preference under 23.2.2.3, by my opinion.
248   *
249   *      - ptr
250   */
251  // CPPUNIT_ASSERT( *r == 3 );
252  // ++r;
253  // CPPUNIT_ASSERT( *r == 2 );
254}
255
256void ListTest::push_front()
257{
258  list<int> l;
259  l.push_back( 1 );
260  l.push_back( 2 );
261  l.push_back( 3 );
262
263  list<int>::iterator i = l.begin();
264
265  CPPUNIT_ASSERT( *i == 1 );
266  l.push_front( 0 );
267  CPPUNIT_ASSERT( *i == 1 );
268  ++i;
269  CPPUNIT_ASSERT( *i == 2 );
270}
271
272void ListTest::allocator_with_state()
273{
274  char buf1[1024];
275  StackAllocator<int> stack1(buf1, buf1 + sizeof(buf1));
276
277  char buf2[1024];
278  StackAllocator<int> stack2(buf2, buf2 + sizeof(buf2));
279
280  typedef list<int, StackAllocator<int> > ListInt;
281  {
282    //Swap with both list non empty
283    ListInt lint1(10, 0, stack1);
284    ListInt lint1Cpy(lint1);
285
286    ListInt lint2(10, 1, stack2);
287    ListInt lint2Cpy(lint2);
288
289    lint1.swap(lint2);
290
291    CPPUNIT_ASSERT( lint1.get_allocator().swaped() );
292    CPPUNIT_ASSERT( lint2.get_allocator().swaped() );
293
294    CPPUNIT_ASSERT( lint1 == lint2Cpy );
295    CPPUNIT_ASSERT( lint2 == lint1Cpy );
296    CPPUNIT_ASSERT( lint1.get_allocator() == stack2 );
297    CPPUNIT_ASSERT( lint2.get_allocator() == stack1 );
298  }
299  CPPUNIT_CHECK( stack1.ok() );
300  CPPUNIT_CHECK( stack2.ok() );
301  stack1.reset(); stack2.reset();
302
303  {
304    //Swap with empty calle list
305    ListInt lint1(10, 0, stack1);
306    ListInt lint1Cpy(lint1);
307
308    ListInt lint2(stack2);
309    ListInt lint2Cpy(lint2);
310
311    lint1.swap(lint2);
312
313    CPPUNIT_ASSERT( lint1.get_allocator().swaped() );
314    CPPUNIT_ASSERT( lint2.get_allocator().swaped() );
315
316    CPPUNIT_ASSERT( lint1 == lint2Cpy );
317    CPPUNIT_ASSERT( lint2 == lint1Cpy );
318    CPPUNIT_ASSERT( lint1.get_allocator() == stack2 );
319    CPPUNIT_ASSERT( lint2.get_allocator() == stack1 );
320  }
321  CPPUNIT_CHECK( stack1.ok() );
322  CPPUNIT_CHECK( stack2.ok() );
323  stack1.reset(); stack2.reset();
324
325  {
326    //Swap with empty caller list
327    ListInt lint1(stack1);
328    ListInt lint1Cpy(lint1);
329
330    ListInt lint2(10, 0, stack2);
331    ListInt lint2Cpy(lint2);
332
333    lint1.swap(lint2);
334
335    CPPUNIT_ASSERT( lint1.get_allocator().swaped() );
336    CPPUNIT_ASSERT( lint2.get_allocator().swaped() );
337
338    CPPUNIT_ASSERT( lint1 == lint2Cpy );
339    CPPUNIT_ASSERT( lint2 == lint1Cpy );
340    CPPUNIT_ASSERT( lint1.get_allocator() == stack2 );
341    CPPUNIT_ASSERT( lint2.get_allocator() == stack1 );
342  }
343  CPPUNIT_CHECK( stack1.ok() );
344  CPPUNIT_CHECK( stack2.ok() );
345  stack1.reset(); stack2.reset();
346
347  {
348    ListInt lint1(10, 0, stack1);
349    ListInt lint2(10, 1, stack2);
350
351    lint1.splice(lint1.begin(), lint2);
352    CPPUNIT_ASSERT( lint1.size() == 20 );
353    CPPUNIT_ASSERT( lint2.empty() );
354  }
355  CPPUNIT_CHECK( stack1.ok() );
356  CPPUNIT_CHECK( stack2.ok() );
357  stack1.reset(); stack2.reset();
358
359  {
360    ListInt lint1(10, 0, stack1);
361    ListInt lint2(10, 1, stack2);
362
363    lint1.splice(lint1.begin(), lint2, lint2.begin());
364    CPPUNIT_ASSERT( lint1.size() == 11 );
365    CPPUNIT_ASSERT( lint2.size() == 9 );
366  }
367  CPPUNIT_CHECK( stack1.ok() );
368  CPPUNIT_CHECK( stack2.ok() );
369  stack1.reset(); stack2.reset();
370
371  {
372    ListInt lint1(10, 0, stack1);
373    ListInt lint2(10, 1, stack2);
374
375    ListInt::iterator lit(lint2.begin());
376    advance(lit, 5);
377    lint1.splice(lint1.begin(), lint2, lint2.begin(), lit);
378    CPPUNIT_ASSERT( lint1.size() == 15 );
379    CPPUNIT_ASSERT( lint2.size() == 5 );
380  }
381  CPPUNIT_CHECK( stack1.ok() );
382  CPPUNIT_CHECK( stack2.ok() );
383  stack1.reset(); stack2.reset();
384
385  {
386    ListInt lint1(10, 0, stack1);
387    ListInt lint2(10, 1, stack2);
388
389    ListInt lintref(stack2);
390    lintref.insert(lintref.begin(), 10, 1);
391    lintref.insert(lintref.begin(), 10, 0);
392
393    lint1.merge(lint2);
394    CPPUNIT_ASSERT( lint1.size() == 20 );
395    CPPUNIT_ASSERT( lint1 == lintref );
396    CPPUNIT_ASSERT( lint2.empty() );
397  }
398  CPPUNIT_CHECK( stack1.ok() );
399  CPPUNIT_CHECK( stack2.ok() );
400
401#if defined (STLPORT) && !defined (_STLP_NO_MEMBER_TEMPLATES) && \
402    (!defined (_MSC_VER) || (_MSC_VER >= 1300))
403  {
404    //This is a compile time test.
405    //We check that sort implementation is correct when list is instanciated
406    //with an allocator that do not have a default constructor.
407    ListInt lint1(10, 0, stack1);
408    lint1.sort();
409    lint1.sort(greater<int>());
410  }
411#endif
412}
413
414/*
415void ListTest::const_list()
416{
417  list<const int> cint_list;
418  cint_list.push_back(1);
419  cint_list.push_front(2);
420}
421*/
422void ListTest::swap()
423{
424  list<int> lst1;
425  list<int> lst2;
426
427  lst1.push_back(1);
428  lst2.push_back(2);
429
430  lst1.swap( lst2 );
431
432  CPPUNIT_CHECK( lst1.front() == 2 );
433  CPPUNIT_CHECK( lst2.front() == 1 );
434  CPPUNIT_CHECK( lst1.size() == 1 );
435  CPPUNIT_CHECK( lst2.size() == 1 );
436
437  lst1.pop_front();
438  lst2.pop_front();
439
440  CPPUNIT_CHECK( lst1.empty() );
441  CPPUNIT_CHECK( lst2.empty() );
442}
443
444namespace foo {
445  class bar {};
446
447  template <class _It>
448  size_t distance(_It, _It);
449}
450
451void ListTest::adl()
452{
453  list<foo::bar> lbar;
454  CPPUNIT_ASSERT( lbar.size() == 0);
455}
456
457#if !defined (STLPORT) || \
458    !defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
459/* Simple compilation test: Check that nested types like iterator
460 * can be access even if type used to instanciate container is not
461 * yet completely defined.
462 */
463class IncompleteClass
464{
465  list<IncompleteClass> instances;
466  typedef list<IncompleteClass>::iterator it;
467};
468#endif
469