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
38 namespace android {
39 using std::string;
40 using std::vector;
41 static const size_t kExponentialFactor = 2;
testConstructorInt()42 bool 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
testConstructorString()73 bool 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
84 typedef enum { ONE = 10, TWO} TestEnum;
85
testConstructorClass()86 bool 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
testConstructorRepeat()103 bool 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
testConstructorIterator()139 bool 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
testReserve()178 bool 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
testPushBack()247 bool 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
testPopBack()293 bool 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
testResize()333 bool 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
testSwap()394 bool 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
testIterators()413 bool 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
testCtorDtorForNonPod()460 bool 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
testEraseElt()500 bool 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
testEraseRange()563 bool 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.
testAt()645 bool 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
main(int argc,char ** argv)654 int 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