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 <deque>
6 #include <algorithm>
7 #if !defined (STLPORT) || defined (_STLP_USE_EXCEPTIONS)
8 # include <stdexcept>
9 #endif
10 
11 #include "cppunit/cppunit_proxy.h"
12 
13 #if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)
14 using namespace std;
15 #endif
16 
17 //
18 // TestCase class
19 //
20 class DequeTest : public CPPUNIT_NS::TestCase
21 {
22   CPPUNIT_TEST_SUITE(DequeTest);
23   CPPUNIT_TEST(deque1);
24   CPPUNIT_TEST(at);
25   CPPUNIT_TEST(insert);
26   CPPUNIT_TEST(erase);
27   CPPUNIT_TEST(auto_ref);
28   CPPUNIT_TEST(allocator_with_state);
29 #if defined (STLPORT) && defined (_STLP_NO_MEMBER_TEMPLATES)
30   CPPUNIT_IGNORE;
31 #endif
32   CPPUNIT_TEST(optimizations_check);
33   CPPUNIT_TEST_SUITE_END();
34 
35 protected:
36   void deque1();
37   void insert();
38   void erase();
39   void at();
40   void auto_ref();
41   void allocator_with_state();
42   void optimizations_check();
43 };
44 
45 CPPUNIT_TEST_SUITE_REGISTRATION(DequeTest);
46 
47 //
48 // tests implementation
49 //
50 void DequeTest::deque1()
51 {
52   deque<int> d;
53   d.push_back(4);
54   d.push_back(9);
55   d.push_back(16);
56   d.push_front(1);
57 
58   CPPUNIT_ASSERT( d[0] == 1 );
59   CPPUNIT_ASSERT( d[1] == 4 );
60   CPPUNIT_ASSERT( d[2] == 9 );
61   CPPUNIT_ASSERT( d[3] == 16 );
62 
63   d.pop_front();
64   d[2] = 25;
65 
66   CPPUNIT_ASSERT( d[0] == 4 );
67   CPPUNIT_ASSERT( d[1] == 9 );
68   CPPUNIT_ASSERT( d[2] == 25 );
69 
70   //Some compile time tests:
71   deque<int>::iterator dit = d.begin();
72   deque<int>::const_iterator cdit(d.begin());
73   CPPUNIT_ASSERT( (dit - cdit) == 0 );
74   CPPUNIT_ASSERT( (cdit - dit) == 0 );
75   CPPUNIT_ASSERT( (dit - dit) == 0 );
76   CPPUNIT_ASSERT( (cdit - cdit) == 0 );
77   CPPUNIT_ASSERT(!((dit < cdit) || (dit > cdit) || (dit != cdit) || !(dit <= cdit) || !(dit >= cdit)));
78 }
79 
80 void DequeTest::insert()
81 {
82   deque<int> d;
83   d.push_back(0);
84   d.push_back(1);
85   d.push_back(2);
86   CPPUNIT_ASSERT( d.size() == 3 );
87 
88   deque<int>::iterator dit;
89 
90   //Insertion before begin:
91   dit = d.insert(d.begin(), 3);
92   CPPUNIT_ASSERT( dit != d.end() );
93   CPPUNIT_CHECK( *dit == 3 );
94   CPPUNIT_ASSERT( d.size() == 4 );
95   CPPUNIT_ASSERT( d[0] == 3 );
96 
97   //Insertion after begin:
98   dit = d.insert(d.begin() + 1, 4);
99   CPPUNIT_ASSERT( dit != d.end() );
100   CPPUNIT_CHECK( *dit == 4 );
101   CPPUNIT_ASSERT( d.size() == 5 );
102   CPPUNIT_ASSERT( d[1] == 4 );
103 
104   //Insertion at end:
105   dit = d.insert(d.end(), 5);
106   CPPUNIT_ASSERT( dit != d.end() );
107   CPPUNIT_CHECK( *dit == 5 );
108   CPPUNIT_ASSERT( d.size() == 6 );
109   CPPUNIT_ASSERT( d[5] == 5 );
110 
111   //Insertion before last element:
112   dit = d.insert(d.end() - 1, 6);
113   CPPUNIT_ASSERT( dit != d.end() );
114   CPPUNIT_CHECK( *dit == 6 );
115   CPPUNIT_ASSERT( d.size() == 7 );
116   CPPUNIT_ASSERT( d[5] == 6 );
117 
118   //Insertion of several elements before begin
119   d.insert(d.begin(), 2, 7);
120   CPPUNIT_ASSERT( d.size() == 9 );
121   CPPUNIT_ASSERT( d[0] == 7 );
122   CPPUNIT_ASSERT( d[1] == 7 );
123 
124   //Insertion of several elements after begin
125   //There is more elements to insert than elements before insertion position
126   d.insert(d.begin() + 1, 2, 8);
127   CPPUNIT_ASSERT( d.size() == 11 );
128   CPPUNIT_ASSERT( d[1] == 8 );
129   CPPUNIT_ASSERT( d[2] == 8 );
130 
131   //There is less elements to insert than elements before insertion position
132   d.insert(d.begin() + 3, 2, 9);
133   CPPUNIT_ASSERT( d.size() == 13 );
134   CPPUNIT_ASSERT( d[3] == 9 );
135   CPPUNIT_ASSERT( d[4] == 9 );
136 
137   //Insertion of several elements at end:
138   d.insert(d.end(), 2, 10);
139   CPPUNIT_ASSERT( d.size() == 15 );
140   CPPUNIT_ASSERT( d[14] == 10 );
141   CPPUNIT_ASSERT( d[13] == 10 );
142 
143   //Insertion of several elements before last:
144   //There is more elements to insert than elements after insertion position
145   d.insert(d.end() - 1, 2, 11);
146   CPPUNIT_ASSERT( d.size() == 17 );
147   CPPUNIT_ASSERT( d[15] == 11 );
148   CPPUNIT_ASSERT( d[14] == 11 );
149 
150   //There is less elements to insert than elements after insertion position
151   d.insert(d.end() - 3, 2, 12);
152   CPPUNIT_ASSERT( d.size() == 19 );
153   CPPUNIT_ASSERT( d[15] == 12 );
154   CPPUNIT_ASSERT( d[14] == 12 );
155 }
156 
157 void DequeTest::at() {
158   deque<int> d;
159   deque<int> const& cd = d;
160 
161   d.push_back(10);
162   CPPUNIT_ASSERT( d.at(0) == 10 );
163   d.at(0) = 20;
164   CPPUNIT_ASSERT( cd.at(0) == 20 );
165 
166 #if !defined (STLPORT) || defined (_STLP_USE_EXCEPTIONS)
167   for (;;) {
168     try {
169       d.at(1) = 20;
170       CPPUNIT_ASSERT(false);
171     }
172     catch (out_of_range const&) {
173       return;
174     }
175     catch (...) {
176       CPPUNIT_ASSERT(false);
177     }
178   }
179 #endif
180 }
181 
182 void DequeTest::auto_ref()
183 {
184   int i;
185   deque<int> ref;
186   for (i = 0; i < 5; ++i) {
187     ref.push_back(i);
188   }
189 
190   deque<deque<int> > d_d_int(1, ref);
191   d_d_int.push_back(d_d_int[0]);
192   d_d_int.push_back(ref);
193   d_d_int.push_back(d_d_int[0]);
194   d_d_int.push_back(d_d_int[0]);
195   d_d_int.push_back(ref);
196 
197   for (i = 0; i < 5; ++i) {
198     CPPUNIT_ASSERT( d_d_int[i] == ref );
199   }
200 }
201 
202 void DequeTest::allocator_with_state()
203 {
204   char buf1[1024];
205   StackAllocator<int> stack1(buf1, buf1 + sizeof(buf1));
206 
207   char buf2[1024];
208   StackAllocator<int> stack2(buf2, buf2 + sizeof(buf2));
209 
210   {
211     typedef deque<int, StackAllocator<int> > DequeInt;
212     DequeInt dint1(10, 0, stack1);
213     DequeInt dint1Cpy(dint1);
214 
215     DequeInt dint2(10, 1, stack2);
216     DequeInt dint2Cpy(dint2);
217 
218     dint1.swap(dint2);
219 
220     CPPUNIT_ASSERT( dint1.get_allocator().swaped() );
221     CPPUNIT_ASSERT( dint2.get_allocator().swaped() );
222 
223     CPPUNIT_ASSERT( dint1 == dint2Cpy );
224     CPPUNIT_ASSERT( dint2 == dint1Cpy );
225     CPPUNIT_ASSERT( dint1.get_allocator() == stack2 );
226     CPPUNIT_ASSERT( dint2.get_allocator() == stack1 );
227   }
228   CPPUNIT_ASSERT( stack1.ok() );
229   CPPUNIT_ASSERT( stack2.ok() );
230 }
231 
232 struct Point {
233   int x, y;
234 };
235 
236 struct PointEx : public Point {
237   PointEx() : builtFromBase(false) {}
238   PointEx(const Point&) : builtFromBase(true) {}
239 
240   bool builtFromBase;
241 };
242 
243 #if defined (STLPORT)
244 #  if defined (_STLP_USE_NAMESPACES)
245 namespace std {
246 #  endif
247   _STLP_TEMPLATE_NULL
248   struct __type_traits<PointEx> {
249     typedef __false_type has_trivial_default_constructor;
250     typedef __true_type has_trivial_copy_constructor;
251     typedef __true_type has_trivial_assignment_operator;
252     typedef __true_type has_trivial_destructor;
253     typedef __true_type is_POD_type;
254   };
255 #  if defined (_STLP_USE_NAMESPACES)
256 }
257 #  endif
258 #endif
259 
260 //This test check that deque implementation do not over optimize
261 //operation as PointEx copy constructor is trivial
262 void DequeTest::optimizations_check()
263 {
264 #if !defined (STLPORT) || !defined (_STLP_NO_MEMBER_TEMPLATES)
265   deque<Point> d1(1);
266   CPPUNIT_ASSERT( d1.size() == 1 );
267 
268   deque<PointEx> d2(d1.begin(), d1.end());
269   CPPUNIT_ASSERT( d2.size() == 1 );
270   CPPUNIT_ASSERT( d2[0].builtFromBase == true );
271 
272   d2.insert(d2.end(), d1.begin(), d1.end());
273   CPPUNIT_ASSERT( d2.size() == 2 );
274   CPPUNIT_ASSERT( d2[1].builtFromBase == true );
275 #endif
276 }
277 
278 void DequeTest::erase()
279 {
280   deque<int> dint;
281   dint.push_back(3);
282   dint.push_front(2);
283   dint.push_back(4);
284   dint.push_front(1);
285   dint.push_back(5);
286   dint.push_front(0);
287   dint.push_back(6);
288 
289   deque<int>::iterator it(dint.begin() + 1);
290   CPPUNIT_ASSERT( *it == 1 );
291 
292   dint.erase(dint.begin());
293   CPPUNIT_ASSERT( *it == 1 );
294 
295   it = dint.end() - 2;
296   CPPUNIT_ASSERT( *it == 5 );
297 
298   dint.erase(dint.end() - 1);
299   CPPUNIT_ASSERT( *it == 5 );
300 
301   dint.push_back(6);
302   dint.push_front(0);
303 
304   it = dint.begin() + 2;
305   CPPUNIT_ASSERT( *it == 2 );
306 
307   dint.erase(dint.begin(), dint.begin() + 2);
308   CPPUNIT_ASSERT( *it == 2 );
309 
310   it = dint.end() - 3;
311   CPPUNIT_ASSERT( *it == 4 );
312 
313   dint.erase(dint.end() - 2, dint.end());
314   CPPUNIT_ASSERT( *it == 4 );
315 }
316 
317 #if (!defined (STLPORT) || \
318     (!defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION))) && \
319      (!defined (_MSC_VER) || (_MSC_VER > 1400)) && \
320      (!defined(__GNUC__) || (__GNUC__ < 4) || (__GNUC_MINOR__ < 3))
321 /* Simple compilation test: Check that nested types like iterator
322  * can be access even if type used to instanciate container is not
323  * yet completely defined.
324  */
325 class IncompleteClass
326 {
327   deque<IncompleteClass> instances;
328   typedef deque<IncompleteClass>::size_type size;
329 };
330 #endif
331