Line data    Source code

       1             : // Copyright 2017 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/detachable-vector.h"
       6             : 
       7             : #include "testing/gtest/include/gtest/gtest.h"
       8             : 
       9             : namespace v8 {
      10             : namespace internal {
      11             : 
      12       15443 : TEST(DetachableVector, ConstructIsEmpty) {
      13             :   DetachableVector<int> v;
      14             : 
      15           1 :   size_t empty_size = 0;
      16           2 :   EXPECT_EQ(empty_size, v.size());
      17             :   EXPECT_TRUE(v.empty());
      18           1 : }
      19             : 
      20       15443 : TEST(DetachableVector, PushAddsElement) {
      21           1 :   DetachableVector<int> v;
      22             : 
      23           1 :   v.push_back(1);
      24             : 
      25           2 :   EXPECT_EQ(1, v.front());
      26           2 :   EXPECT_EQ(1, v.back());
      27           2 :   EXPECT_EQ(1, v.at(0));
      28           1 :   size_t one_size = 1;
      29           2 :   EXPECT_EQ(one_size, v.size());
      30           2 :   EXPECT_FALSE(v.empty());
      31           1 : }
      32             : 
      33       15443 : TEST(DetachableVector, AfterFreeIsEmpty) {
      34           1 :   DetachableVector<int> v;
      35             : 
      36           1 :   v.push_back(1);
      37             :   v.free();
      38             : 
      39           1 :   size_t empty_size = 0;
      40           2 :   EXPECT_EQ(empty_size, v.size());
      41           1 :   EXPECT_TRUE(v.empty());
      42           1 : }
      43             : 
      44             : // This test relies on ASAN to detect leaks and double-frees.
      45       15443 : TEST(DetachableVector, DetachLeaksBackingStore) {
      46           1 :   DetachableVector<int> v;
      47           1 :   DetachableVector<int> v2;
      48             : 
      49           1 :   size_t one_size = 1;
      50             :   EXPECT_TRUE(v2.empty());
      51             : 
      52             :   // Force allocation of the backing store.
      53           1 :   v.push_back(1);
      54             :   // Bit-copy the data structure.
      55             :   memcpy(&v2, &v, sizeof(DetachableVector<int>));
      56             :   // The backing store should be leaked here - free was not called.
      57             :   v.detach();
      58             : 
      59             :   // We have transferred the backing store to the second vector.
      60           2 :   EXPECT_EQ(one_size, v2.size());
      61           1 :   EXPECT_TRUE(v.empty());
      62             : 
      63             :   // The destructor of v2 will release the backing store.
      64           1 : }
      65             : 
      66       15443 : TEST(DetachableVector, PushAndPopWithReallocation) {
      67           1 :   DetachableVector<size_t> v;
      68           1 :   const size_t kMinimumCapacity = DetachableVector<size_t>::kMinimumCapacity;
      69             : 
      70           2 :   EXPECT_EQ(0u, v.capacity());
      71           2 :   EXPECT_EQ(0u, v.size());
      72           1 :   v.push_back(0);
      73           2 :   EXPECT_EQ(kMinimumCapacity, v.capacity());
      74           2 :   EXPECT_EQ(1u, v.size());
      75             : 
      76             :   // Push values until the reallocation happens.
      77           9 :   for (size_t i = 1; i <= kMinimumCapacity; ++i) {
      78           8 :     v.push_back(i);
      79             :   }
      80           2 :   EXPECT_EQ(2 * kMinimumCapacity, v.capacity());
      81           2 :   EXPECT_EQ(kMinimumCapacity + 1, v.size());
      82             : 
      83           1 :   EXPECT_EQ(kMinimumCapacity, v.back());
      84             :   v.pop_back();
      85             : 
      86           1 :   v.push_back(100);
      87           2 :   EXPECT_EQ(100u, v.back());
      88             :   v.pop_back();
      89           2 :   EXPECT_EQ(kMinimumCapacity - 1, v.back());
      90           1 : }
      91             : 
      92       15443 : TEST(DetachableVector, ShrinkToFit) {
      93           1 :   DetachableVector<size_t> v;
      94           1 :   const size_t kMinimumCapacity = DetachableVector<size_t>::kMinimumCapacity;
      95             : 
      96             :   // shrink_to_fit doesn't affect the empty capacity DetachableVector.
      97           2 :   EXPECT_EQ(0u, v.capacity());
      98           1 :   v.shrink_to_fit();
      99           2 :   EXPECT_EQ(0u, v.capacity());
     100             : 
     101             :   // Do not shrink the buffer if it's smaller than kMinimumCapacity.
     102           1 :   v.push_back(0);
     103           2 :   EXPECT_EQ(kMinimumCapacity, v.capacity());
     104           1 :   v.shrink_to_fit();
     105           2 :   EXPECT_EQ(kMinimumCapacity, v.capacity());
     106             : 
     107             :   // Fill items to |v| until the buffer grows twice.
     108          17 :   for (size_t i = 0; i < 2 * kMinimumCapacity; ++i) {
     109          16 :     v.push_back(i);
     110             :   }
     111           2 :   EXPECT_EQ(2 * kMinimumCapacity + 1, v.size());
     112           2 :   EXPECT_EQ(4 * kMinimumCapacity, v.capacity());
     113             : 
     114             :   // Do not shrink the buffer if the number of unused slots is not large enough.
     115           1 :   v.shrink_to_fit();
     116           2 :   EXPECT_EQ(2 * kMinimumCapacity + 1, v.size());
     117           2 :   EXPECT_EQ(4 * kMinimumCapacity, v.capacity());
     118             : 
     119             :   v.pop_back();
     120             :   v.pop_back();
     121           1 :   v.shrink_to_fit();
     122           2 :   EXPECT_EQ(2 * kMinimumCapacity - 1, v.size());
     123           2 :   EXPECT_EQ(2 * kMinimumCapacity - 1, v.capacity());
     124           1 : }
     125             : 
     126             : }  // namespace internal
     127        9264 : }  // namespace v8