1/*
2 * Copyright (C) 2009 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *  * Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 *  * Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in
12 *    the documentation and/or other materials provided with the
13 *    distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29#include "../include/vector"
30#ifndef ANDROID_ASTL_VECTOR__
31#error "Wrong header included!!"
32#endif
33#include <climits>
34#include <cstring>
35#include <string>
36#include "common.h"
37
38namespace android {
39using std::string;
40using std::vector;
41static const size_t kExponentialFactor = 2;
42bool testConstructorInt()
43{
44    {
45        vector<int> vec1;
46        EXPECT_TRUE(vec1.empty());
47        EXPECT_TRUE(vec1.size() == 0);
48        EXPECT_TRUE(vec1.capacity() == 0);
49    }
50    {
51        vector<int> vec2(100);
52        EXPECT_TRUE(!vec2.empty());
53        EXPECT_TRUE(vec2.size() == 100);
54        EXPECT_TRUE(vec2.capacity() == 100);
55        for (size_t i = 0; i < 100; ++i)
56        {
57            EXPECT_TRUE(vec2[i] == 0);
58        }
59    }
60    {
61        vector<int> vec3(200, 0xaa);
62        EXPECT_TRUE(!vec3.empty());
63        EXPECT_TRUE(vec3.size() == 200);
64        EXPECT_TRUE(vec3.capacity() == 200);
65        for (size_t i = 0; i < 200; ++i)
66        {
67            EXPECT_TRUE(vec3[i] == 0xaa);
68        }
69    }
70    return true;
71}
72
73bool testConstructorString()
74{
75    {
76        vector<string> vec1;
77        EXPECT_TRUE(vec1.empty());
78        EXPECT_TRUE(vec1.size() == 0);
79        EXPECT_TRUE(vec1.capacity() == 0);
80    }
81    return true;
82}
83
84typedef enum { ONE = 10, TWO} TestEnum;
85
86bool testConstructorClass()
87{
88    {
89        vector<B> vec1;
90        EXPECT_TRUE(vec1.empty());
91        EXPECT_TRUE(vec1.size() == 0);
92        EXPECT_TRUE(vec1.capacity() == 0);
93    }
94    {
95        vector<B> vec1(100);
96        EXPECT_TRUE(!vec1.empty());
97        EXPECT_TRUE(vec1.size() == 100);
98        EXPECT_TRUE(vec1.capacity() == 100);
99    }
100    return true;
101}
102
103bool testConstructorRepeat()
104{
105    {
106        const vector<int> vec1(100, 10);
107
108        for (int i = 0; i < 100; ++i)
109        {
110            EXPECT_TRUE(vec1[i] == 10);
111        }
112    }
113    {
114        const vector<float> vec2(100, 10.0f);
115
116        for (int i = 0; i < 100; ++i)
117        {
118            EXPECT_TRUE(vec2[i] == 10.0f);
119        }
120    }
121    {
122        const vector<TestEnum> vec3(100, ONE);
123
124        for (int i = 0; i < 100; ++i)
125        {
126            EXPECT_TRUE(vec3[i] == ONE);
127        }
128    }
129    {
130        const vector< A<B> > vec4;
131        const vector< A<B> > vec5(10, A<B>());
132
133        EXPECT_TRUE(vec4.size() == 0);
134        EXPECT_TRUE(vec5.size() == 10);
135    }
136    return true;
137}
138
139bool testConstructorIterator()
140{
141    {
142        vector<string> src;
143        EXPECT_TRUE(src.empty());
144        vector<string> dst(src.begin(), src.end());
145        EXPECT_TRUE(dst.empty());
146    }
147    {
148        vector<int> src;
149        EXPECT_TRUE(src.empty());
150        vector<int> dst(src.begin(), src.end());
151        EXPECT_TRUE(dst.empty());
152    }
153    {
154        vector<int> src;
155        src.push_back(10);
156        src.push_back(20);
157        src.push_back(30);
158        vector<int> dst(src.begin(), src.end());
159        EXPECT_TRUE(dst.size() == 3);
160        EXPECT_TRUE(dst[0] == 10);
161        EXPECT_TRUE(dst[1] == 20);
162        EXPECT_TRUE(dst[2] == 30);
163    }
164    {
165        vector<string> src;
166        src.push_back("str1");
167        src.push_back("str2");
168        src.push_back("str3");
169        vector<string> dst(src.begin(), src.end());
170        EXPECT_TRUE(dst.size() == 3);
171        EXPECT_TRUE(dst[0] == "str1");
172        EXPECT_TRUE(dst[1] == "str2");
173        EXPECT_TRUE(dst[2] == "str3");
174    }
175    return true;
176}
177
178bool testReserve()
179{
180    { // basic reserve + shrink.
181        vector<int> vec1(100, 10);
182
183        EXPECT_TRUE(vec1.capacity() == 100);
184        EXPECT_TRUE(vec1.reserve(200));
185        EXPECT_TRUE(vec1.capacity() == 200);
186        EXPECT_TRUE(vec1.size() == 100);
187
188        EXPECT_TRUE(vec1.reserve());
189        EXPECT_TRUE(vec1.capacity() == 100);
190        EXPECT_TRUE(vec1.size() == 100);
191    }
192    {
193        vector<int> vec2;
194
195        EXPECT_TRUE(vec2.capacity() == 0);
196        EXPECT_TRUE(vec2.reserve());
197        EXPECT_TRUE(vec2.capacity() == 0);
198
199        vec2.reserve(200);
200        EXPECT_TRUE(vec2.capacity() == 200);
201        vec2.reserve();
202        EXPECT_TRUE(vec2.capacity() == 0);
203        vec2.push_back(3);
204        vec2.reserve();
205        EXPECT_TRUE(vec2.capacity() == 1);
206    }
207    {
208        vector<int> vec3;
209
210        vec3.push_back(5);
211        vec3.reserve();
212        EXPECT_TRUE(vec3.capacity() == 1);
213        vec3.push_back(3);
214        EXPECT_TRUE(vec3.capacity() == kExponentialFactor);
215        while (vec3.size() < kExponentialFactor)
216            vec3.push_back(3);
217
218        EXPECT_TRUE(vec3.size() == kExponentialFactor);
219        EXPECT_TRUE(vec3.capacity() == kExponentialFactor);
220
221        // exp increment.
222        vec3.push_back(10);
223        EXPECT_TRUE(vec3.capacity() == kExponentialFactor * kExponentialFactor);
224    }
225    {
226        CopyCounter c;
227
228        c.mCount = 0;
229        vector<CopyCounter> vec4(100, c);
230        EXPECT_TRUE(c.mCount == 100);
231        // Growing does not do any copy via the copy assignement op.
232        vec4.reserve(1000);
233        EXPECT_TRUE(c.mCount == 200);
234        vec4.reserve(50); // reserving less than length is a nop.
235        EXPECT_TRUE(c.mCount == 200);
236    }
237    {
238        vector<unsigned short> vec5;
239
240        EXPECT_TRUE(!vec5.reserve(vec5.max_size() + 1));
241        EXPECT_TRUE(vec5.capacity() == 0);
242    }
243    return true;
244}
245
246
247bool testPushBack()
248{
249    {
250        vector<CtorDtorCounter> vec1;
251        CtorDtorCounter c;
252
253        c.reset();
254        for (int i = 0; i < 1000; ++i)
255        {
256            vec1.push_back(c);
257        }
258        EXPECT_TRUE(vec1.capacity() == 1024);
259        EXPECT_TRUE(vec1.size() == 1000);
260        // Assignment should not be used, but the constructor should.
261        EXPECT_TRUE(c.mAssignCount == 0);
262        // Copy constructor was been invoked for each new element
263        // pushed and when the capacity was increased.
264        EXPECT_TRUE(c.mCopyCtorCount > 1000);
265        EXPECT_TRUE(c.mCtorCount == 0);
266    }
267    {
268        vector<int> vec2;
269
270        vec2.push_back(10);
271        EXPECT_TRUE(vec2.front() == 10);
272        EXPECT_TRUE(vec2.back() == 10);
273        EXPECT_TRUE(vec2.size() == 1);
274        vec2.push_back(20);
275        EXPECT_TRUE(vec2.front() == 10);
276        EXPECT_TRUE(vec2.back() == 20);
277        EXPECT_TRUE(vec2.size() == 2);
278    }
279    // Push back an non-pod object.
280    {
281        string str = "a string";
282        vector<string> vec3;
283
284        vec3.push_back(str);
285        EXPECT_TRUE(vec3.size() == 1);
286        EXPECT_TRUE(vec3.front() == "a string");
287        EXPECT_TRUE(vec3.back() == "a string");
288    }
289    return true;
290}
291
292
293bool testPopBack()
294{
295    vector<int> vec1(10, 0xdeadbeef);;
296
297    EXPECT_TRUE(vec1.capacity() == 10);
298    EXPECT_TRUE(vec1.size() == 10);
299
300    for(size_t i = 10; i > 0; --i)
301    {
302        EXPECT_TRUE(vec1.capacity() == 10);
303        EXPECT_TRUE(vec1.size() == i);
304        vec1.pop_back();
305    }
306    EXPECT_TRUE(vec1.empty());
307    EXPECT_TRUE(vec1.begin() == vec1.end());
308    vec1.pop_back(); // pop_back on empty vector
309    EXPECT_TRUE(vec1.size() == 0);
310    EXPECT_TRUE(vec1.capacity() == 10);
311
312    vec1.clear();
313    vec1.pop_back(); // pop_back on empty vector
314    EXPECT_TRUE(vec1.size() == 0);
315    EXPECT_TRUE(vec1.capacity() == 0);
316    EXPECT_TRUE(vec1.begin() == vec1.end());
317    EXPECT_TRUE(vec1.begin().base() == NULL);
318
319    CtorDtorCounter instance;
320    vector<CtorDtorCounter> vec2(10, instance);
321
322    CtorDtorCounter::reset();
323    for (int i = 0; i < 10; ++i)
324    {
325        vec2.pop_back();
326    }
327    EXPECT_TRUE(vec2.size() == 0);
328    EXPECT_TRUE(CtorDtorCounter::mDtorCount == 10);
329    return true;
330}
331
332
333bool testResize()
334{
335    {
336        vector<int> vec1(10, 0xdeadbeef);
337        vec1.resize(0);
338        EXPECT_TRUE(vec1.capacity() == 10);
339        vec1.resize(5);
340        EXPECT_TRUE(vec1.capacity() == 10);
341        vec1.resize(10);
342        EXPECT_TRUE(vec1.capacity() == 10);
343        vec1.resize(11);
344        EXPECT_TRUE(vec1.capacity() == 11);
345        vec1.resize(100);
346        EXPECT_TRUE(vec1.capacity() == 100);
347        vec1.resize(10);
348        EXPECT_TRUE(vec1.capacity() == 100);
349    }
350    {
351        vector<B> vec1(10);
352        vec1.resize(0);
353        EXPECT_TRUE(vec1.capacity() == 10);
354        vec1.resize(5);
355        EXPECT_TRUE(vec1.capacity() == 10);
356        vec1.resize(10);
357        EXPECT_TRUE(vec1.capacity() == 10);
358        vec1.resize(11);
359        EXPECT_TRUE(vec1.capacity() == 11);
360        vec1.resize(100);
361        EXPECT_TRUE(vec1.capacity() == 100);
362        vec1.resize(10);
363        EXPECT_TRUE(vec1.capacity() == 100);
364    }
365    {
366        vector<CtorDtorCounter> vec;
367        CtorDtorCounter::reset();
368        vec.resize(10);
369        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 1);  // default arg.
370        EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == 10); // copied 10 times.
371
372        CtorDtorCounter::reset();
373        vec.resize(200);
374        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 1);  // default arg.
375        EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == 200);
376
377        CtorDtorCounter::reset();
378        vec.resize(199);
379        // the copy constructor should have been called once and the
380        // destructor twice (1 temp + 1 elt).
381        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 1);  // default arg.
382        EXPECT_TRUE(CtorDtorCounter::mDtorCount == 2);
383
384        CtorDtorCounter::reset();
385        vec.resize(0);
386        // the copy constructor should have been called once and the
387        // destructor twice (1 temp + 199 elts).
388        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 1);  // default arg.
389        EXPECT_TRUE(CtorDtorCounter::mDtorCount == 200);
390    }
391    return true;
392}
393
394bool testSwap()
395{
396    vector<int> vec1(100, 10);
397    vector<int> vec2;
398
399    vec1.swap(vec2);
400
401    EXPECT_TRUE(vec1.capacity() == 0);
402    EXPECT_TRUE(vec2.capacity() == 100);
403
404    EXPECT_TRUE(vec1.size() == 0);
405    EXPECT_TRUE(vec2.size() == 100);
406
407    EXPECT_TRUE(vec1.begin() == vec1.end());
408    EXPECT_TRUE(vec2.begin() != vec2.end());
409    return true;
410}
411
412
413bool testIterators()
414{
415    vector<int> vec1(10);
416
417    for (size_t i = 0; i < 10; ++i)
418    {
419        vec1[i] = i;
420    }
421
422    vector<int>::iterator i = vec1.begin();
423    for (int c = 0; i != vec1.end(); ++i, ++c)
424    {
425        EXPECT_TRUE(c == *i);
426    }
427
428    vector<int>::const_iterator j = vec1.begin();
429    for (int c = 0; j != vec1.end(); ++j, ++c)
430    {
431        EXPECT_TRUE(c == *j);
432    }
433
434    {
435        const vector<int> vec1(100, 10);
436
437        EXPECT_TRUE(vec1.end().operator-(100) == vec1.begin());
438        EXPECT_TRUE(vec1.end() - 100 == vec1.begin());
439
440        EXPECT_TRUE(100 + vec1.begin() == vec1.end());
441        EXPECT_TRUE(vec1.begin() + 100 == vec1.end());
442
443        EXPECT_TRUE(vec1.end() - vec1.begin() == 100);
444        EXPECT_TRUE(std::distance(vec1.begin(), vec1.end()) == 100);
445        EXPECT_TRUE(std::distance(vec1.end(), vec1.begin()) == -100);
446
447        for (vector<int>::const_iterator i = vec1.begin();
448             i != vec1.end(); ++i) {
449            EXPECT_TRUE(*i == 10);
450        }
451    }
452
453    {
454        const vector<int> vec2;
455        EXPECT_TRUE(vec2.begin() == vec2.end());
456    }
457    return true;
458}
459
460bool testCtorDtorForNonPod()
461{
462    {  // empty vector, no construction should happen.
463        CtorDtorCounter::reset();
464        vector<CtorDtorCounter> vec1;
465
466        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 0);
467        EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == 0);
468    }
469    EXPECT_TRUE(CtorDtorCounter::mDtorCount == 0);
470
471    {
472        CtorDtorCounter instance;
473        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 1);
474        CtorDtorCounter::reset();
475
476        vector<CtorDtorCounter> vec2(200, instance);
477
478        // 200 copies by assignement of the sample instance
479        EXPECT_TRUE(CtorDtorCounter::mAssignCount == 0);
480        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 0);
481        EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == 200);
482        EXPECT_TRUE(CtorDtorCounter::mDtorCount == 0);
483
484        CtorDtorCounter::reset();
485        vec2.reserve(400);
486
487        // 200 moves: 200 copies by copy constructor and 200 destructions.
488        EXPECT_TRUE(CtorDtorCounter::mCopyCtorCount == 200);
489        EXPECT_TRUE(CtorDtorCounter::mDtorCount == 200);
490        EXPECT_TRUE(CtorDtorCounter::mCtorCount == 0);
491        EXPECT_TRUE(CtorDtorCounter::mAssignCount == 0);
492
493        CtorDtorCounter::reset();
494    }
495    // 200 + 1 for the instance
496    EXPECT_TRUE(CtorDtorCounter::mDtorCount == 201);
497    return true;
498}
499
500bool testEraseElt()
501{
502    {
503        vector<B> empty;
504        vector<B>::iterator res = empty.erase(empty.end());
505        EXPECT_TRUE(res == empty.end());
506        EXPECT_TRUE(empty.empty());
507    }
508    {
509        vector<B> one;
510        one.push_back(B());
511        EXPECT_TRUE(!one.empty());
512
513        vector<B>::iterator res = one.erase(one.begin());
514        EXPECT_TRUE(res == one.end());
515
516        EXPECT_TRUE(one.begin() == one.end());
517        EXPECT_TRUE(one.empty());
518    }
519    {
520        vector<B> two;
521        two.push_back(B());
522        two.push_back(B());
523
524        vector<B>::iterator res = two.erase(two.begin());
525
526        EXPECT_TRUE(res == two.begin());
527        EXPECT_TRUE(res != two.end());
528
529        EXPECT_TRUE(two.begin() != two.end());
530        EXPECT_TRUE(two.size() == 1);
531    }
532    {
533        vector<int> vec;
534        for (int i = 0; i < 20; ++i) vec.push_back(i);
535        vector<int>::iterator pos;
536
537        pos = vec.erase(vec.begin() + 2);  // removes '2'
538        EXPECT_TRUE(*pos == 3);            // returns '3'
539
540        pos = vec.erase(vec.begin() + 18); // removes '19' now @ pos 18
541        EXPECT_TRUE(pos == vec.end());     // returns end()
542        EXPECT_TRUE(*(--pos) == 18);       // last one is now '18'
543    }
544    {
545        vector<std::string> vec;
546
547        vec.push_back("first");
548        vec.push_back("second");
549        vec.push_back("third");
550        vec.push_back("fourth");
551
552        vector<std::string>::iterator pos;
553        pos = vec.erase(vec.begin() + 1);  // removes 'second'
554        EXPECT_TRUE(vec.size() == 3);
555        EXPECT_TRUE(*pos == "third");
556        EXPECT_TRUE(vec[0] == "first");
557        EXPECT_TRUE(vec[1] == "third");
558        EXPECT_TRUE(vec[2] == "fourth");
559    }
560    return true;
561}
562
563bool testEraseRange()
564{
565    {
566        vector<B> empty;
567        vector<B>::iterator res = empty.erase(empty.begin(), empty.end());
568        EXPECT_TRUE(res == empty.end());
569        EXPECT_TRUE(empty.empty());
570        EXPECT_TRUE(empty.size() == 0);
571    }
572    {
573        vector<B> one;
574        one.push_back(B());
575        EXPECT_TRUE(!one.empty());
576
577        vector<B>::iterator res = one.erase(one.begin(), one.end());
578        EXPECT_TRUE(res == one.end());
579
580        EXPECT_TRUE(one.begin() == one.end());
581        EXPECT_TRUE(one.empty());
582    }
583    {
584        vector<B> two;
585        two.push_back(B());
586        two.push_back(B());
587
588        // erase the 1st one.
589        vector<B>::iterator res = two.erase(two.begin(), two.begin() + 1);
590
591        EXPECT_TRUE(res == two.begin());
592        EXPECT_TRUE(res != two.end());
593
594        EXPECT_TRUE(two.begin() != two.end());
595        EXPECT_TRUE(two.size() == 1);
596    }
597    {
598        vector<B> two;
599        two.push_back(B());
600        two.push_back(B());
601
602        // erase range is empty.
603        vector<B>::iterator res = two.erase(two.begin(), two.begin());
604
605        EXPECT_TRUE(res == two.begin());
606        EXPECT_TRUE(res != two.end());
607
608        EXPECT_TRUE(two.begin() != two.end());
609        EXPECT_TRUE(two.size() == 2);
610    }
611
612    {
613        vector<int> vec;
614        for (int i = 0; i < 20; ++i) vec.push_back(i);
615        vector<int>::iterator pos;
616
617        pos = vec.erase(vec.begin() + 2, vec.begin() + 3);  // removes '2'
618        EXPECT_TRUE(*pos == 3);                             // returns '3'
619
620        pos = vec.erase(vec.begin() + 18, vec.end()); // removes '19' now @ pos 18
621        EXPECT_TRUE(pos == vec.end());                // returns end()
622        EXPECT_TRUE(*(--pos) == 18);                  // last one is now '18'
623    }
624    {
625        vector<std::string> vec;
626
627        vec.push_back("first");
628        vec.push_back("second");
629        vec.push_back("third");
630        vec.push_back("fourth");
631
632        vector<std::string>::iterator pos;
633        pos = vec.erase(vec.begin() + 1, vec.begin() + 3);  // removes 'second' and third.
634        EXPECT_TRUE(vec.size() == 2);
635        EXPECT_TRUE(*pos == "fourth");
636        EXPECT_TRUE(vec[0] == "first");
637        EXPECT_TRUE(vec[1] == "fourth");
638        pos = vec.erase(vec.begin(), vec.end());  // clears the vector
639        EXPECT_TRUE(vec.empty());
640    }
641    return true;
642}
643
644// Valgrind should not barf when we access element out of bound.
645bool testAt() {
646    vector<int> vec;
647
648    vec.at(1000) = 0xdeadbeef;
649    EXPECT_TRUE(vec.at(1000) == 0xdeadbeef);
650    return true;
651}
652}  // namespace android
653
654int main(int argc, char **argv)
655{
656    FAIL_UNLESS(testConstructorInt);
657    FAIL_UNLESS(testConstructorString);
658    FAIL_UNLESS(testConstructorClass);
659    FAIL_UNLESS(testConstructorRepeat);
660    FAIL_UNLESS(testConstructorIterator);
661    FAIL_UNLESS(testReserve);
662    FAIL_UNLESS(testPushBack);
663    FAIL_UNLESS(testPopBack);
664    FAIL_UNLESS(testResize);
665    FAIL_UNLESS(testSwap);
666    FAIL_UNLESS(testIterators);
667    FAIL_UNLESS(testCtorDtorForNonPod);
668    FAIL_UNLESS(testEraseElt);
669    FAIL_UNLESS(testEraseRange);
670    FAIL_UNLESS(testAt);
671    return kPassed;
672}
673