src/third_party/WebKit/Source/wtf/VectorTest.cpp

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27
  28 #include "wtf/HashSet.h"
  29 #include "wtf/OwnPtr.h"
  30 #include "wtf/PassOwnPtr.h"
  31 #include "wtf/Vector.h"
  32 #include <gtest/gtest.h>
  33
  34 namespace {
  35
  36 TEST(VectorTest, Basic)
  37 {
  38     Vector<int> intVector;
  39     EXPECT_TRUE(intVector.isEmpty());
  40     EXPECT_EQ(0ul, intVector.size());
  41     EXPECT_EQ(0ul, intVector.capacity());
  42 }
  43
  44 TEST(VectorTest, Reverse)
  45 {
  46     Vector<int> intVector;
  47     intVector.append(10);
  48     intVector.append(11);
  49     intVector.append(12);
  50     intVector.append(13);
  51     intVector.reverse();
  52
  53     EXPECT_EQ(13, intVector[0]);
  54     EXPECT_EQ(12, intVector[1]);
  55     EXPECT_EQ(11, intVector[2]);
  56     EXPECT_EQ(10, intVector[3]);
  57
  58     intVector.append(9);
  59     intVector.reverse();
  60
  61     EXPECT_EQ(9, intVector[0]);
  62     EXPECT_EQ(10, intVector[1]);
  63     EXPECT_EQ(11, intVector[2]);
  64     EXPECT_EQ(12, intVector[3]);
  65     EXPECT_EQ(13, intVector[4]);
  66 }
  67
  68 TEST(VectorTest, Iterator)
  69 {
  70     Vector<int> intVector;
  71     intVector.append(10);
  72     intVector.append(11);
  73     intVector.append(12);
  74     intVector.append(13);
  75
  76     Vector<int>::iterator it = intVector.begin();
  77     Vector<int>::iterator end = intVector.end();
  78     EXPECT_TRUE(end != it);
  79
  80     EXPECT_EQ(10, *it);
  81     ++it;
  82     EXPECT_EQ(11, *it);
  83     ++it;
  84     EXPECT_EQ(12, *it);
  85     ++it;
  86     EXPECT_EQ(13, *it);
  87     ++it;
  88
  89     EXPECT_TRUE(end == it);
  90 }
  91
  92 TEST(VectorTest, ReverseIterator)
  93 {
  94     Vector<int> intVector;
  95     intVector.append(10);
  96     intVector.append(11);
  97     intVector.append(12);
  98     intVector.append(13);
  99
 100     Vector<int>::reverse_iterator it = intVector.rbegin();
 101     Vector<int>::reverse_iterator end = intVector.rend();
 102     EXPECT_TRUE(end != it);
 103
 104     EXPECT_EQ(13, *it);
 105     ++it;
 106     EXPECT_EQ(12, *it);
 107     ++it;
 108     EXPECT_EQ(11, *it);
 109     ++it;
 110     EXPECT_EQ(10, *it);
 111     ++it;
 112
 113     EXPECT_TRUE(end == it);
 114 }
 115
 116 class DestructCounter {
 117 public:
 118     explicit DestructCounter(int i, int* destructNumber)
 119         : m_i(i)
 120         , m_destructNumber(destructNumber)
 121     { }
 122
 123     ~DestructCounter() { ++(*m_destructNumber); }
 124     int get() const { return m_i; }
 125
 126 private:
 127     int m_i;
 128     int* m_destructNumber;
 129 };
 130
 131 typedef WTF::Vector<OwnPtr<DestructCounter> > OwnPtrVector;
 132
 133 TEST(VectorTest, OwnPtr)
 134 {
 135     int destructNumber = 0;
 136     OwnPtrVector vector;
 137     vector.append(adoptPtr(new DestructCounter(0, &destructNumber)));
 138     vector.append(adoptPtr(new DestructCounter(1, &destructNumber)));
 139     EXPECT_EQ(2u, vector.size());
 140
 141     OwnPtr<DestructCounter>& counter0 = vector.first();
 142     ASSERT_EQ(0, counter0->get());
 143     int counter1 = vector.last()->get();
 144     ASSERT_EQ(1, counter1);
 145     ASSERT_EQ(0, destructNumber);
 146
 147     size_t index = 0;
 148     for (OwnPtrVector::iterator iter = vector.begin(); iter != vector.end(); ++iter) {
 149         OwnPtr<DestructCounter>* refCounter = iter;
 150         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()->get()));
 151         EXPECT_EQ(index, static_cast<size_t>((*refCounter)->get()));
 152         index++;
 153     }
 154     EXPECT_EQ(0, destructNumber);
 155
 156     for (index = 0; index < vector.size(); index++) {
 157         OwnPtr<DestructCounter>& refCounter = vector[index];
 158         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
 159         index++;
 160     }
 161     EXPECT_EQ(0, destructNumber);
 162
 163     EXPECT_EQ(0, vector[0]->get());
 164     EXPECT_EQ(1, vector[1]->get());
 165     vector.remove(0);
 166     EXPECT_EQ(1, vector[0]->get());
 167     EXPECT_EQ(1u, vector.size());
 168     EXPECT_EQ(1, destructNumber);
 169
 170     OwnPtr<DestructCounter> ownCounter1 = vector[0].release();
 171     vector.remove(0);
 172     ASSERT_EQ(counter1, ownCounter1->get());
 173     ASSERT_EQ(0u, vector.size());
 174     ASSERT_EQ(1, destructNumber);
 175
 176     ownCounter1.clear();
 177     EXPECT_EQ(2, destructNumber);
 178
 179     size_t count = 1025;
 180     destructNumber = 0;
 181     for (size_t i = 0; i < count; i++)
 182         vector.prepend(adoptPtr(new DestructCounter(i, &destructNumber)));
 183
 184     // Vector relocation must not destruct OwnPtr element.
 185     EXPECT_EQ(0, destructNumber);
 186     EXPECT_EQ(count, vector.size());
 187
 188     OwnPtrVector copyVector;
 189     vector.swap(copyVector);
 190     EXPECT_EQ(0, destructNumber);
 191     EXPECT_EQ(count, copyVector.size());
 192     EXPECT_EQ(0u, vector.size());
 193
 194     copyVector.clear();
 195     EXPECT_EQ(count, static_cast<size_t>(destructNumber));
 196 }
 197
 198 // WrappedInt class will fail if it was memmoved or memcpyed.
 199 static HashSet<void*> constructedWrappedInts;
 200 class WrappedInt {
 201 public:
 202     WrappedInt(int i = 0)
 203         : m_originalThisPtr(this)
 204         , m_i(i)
 205     {
 206         constructedWrappedInts.add(this);
 207     }
 208
 209     WrappedInt(const WrappedInt& other)
 210         : m_originalThisPtr(this)
 211         , m_i(other.m_i)
 212     {
 213         constructedWrappedInts.add(this);
 214     }
 215
 216     WrappedInt& operator=(const WrappedInt& other)
 217     {
 218         m_i = other.m_i;
 219         return *this;
 220     }
 221
 222     ~WrappedInt()
 223     {
 224         EXPECT_EQ(m_originalThisPtr, this);
 225         EXPECT_TRUE(constructedWrappedInts.contains(this));
 226         constructedWrappedInts.remove(this);
 227     }
 228
 229     int get() const { return m_i; }
 230
 231 private:
 232     void* m_originalThisPtr;
 233     int m_i;
 234 };
 235
 236 TEST(VectorTest, SwapWithInlineCapacity)
 237 {
 238     const size_t inlineCapacity = 2;
 239     Vector<WrappedInt, inlineCapacity> vectorA;
 240     vectorA.append(WrappedInt(1));
 241     Vector<WrappedInt, inlineCapacity> vectorB;
 242     vectorB.append(WrappedInt(2));
 243
 244     EXPECT_EQ(vectorA.size(), vectorB.size());
 245     vectorA.swap(vectorB);
 246
 247     EXPECT_EQ(1u, vectorA.size());
 248     EXPECT_EQ(2, vectorA.at(0).get());
 249     EXPECT_EQ(1u, vectorB.size());
 250     EXPECT_EQ(1, vectorB.at(0).get());
 251
 252     vectorA.append(WrappedInt(3));
 253
 254     EXPECT_GT(vectorA.size(), vectorB.size());
 255     vectorA.swap(vectorB);
 256
 257     EXPECT_EQ(1u, vectorA.size());
 258     EXPECT_EQ(1, vectorA.at(0).get());
 259     EXPECT_EQ(2u, vectorB.size());
 260     EXPECT_EQ(2, vectorB.at(0).get());
 261     EXPECT_EQ(3, vectorB.at(1).get());
 262
 263     EXPECT_LT(vectorA.size(), vectorB.size());
 264     vectorA.swap(vectorB);
 265
 266     EXPECT_EQ(2u, vectorA.size());
 267     EXPECT_EQ(2, vectorA.at(0).get());
 268     EXPECT_EQ(3, vectorA.at(1).get());
 269     EXPECT_EQ(1u, vectorB.size());
 270     EXPECT_EQ(1, vectorB.at(0).get());
 271
 272     vectorA.append(WrappedInt(4));
 273     EXPECT_GT(vectorA.size(), inlineCapacity);
 274     vectorA.swap(vectorB);
 275
 276     EXPECT_EQ(1u, vectorA.size());
 277     EXPECT_EQ(1, vectorA.at(0).get());
 278     EXPECT_EQ(3u, vectorB.size());
 279     EXPECT_EQ(2, vectorB.at(0).get());
 280     EXPECT_EQ(3, vectorB.at(1).get());
 281     EXPECT_EQ(4, vectorB.at(2).get());
 282
 283     vectorB.swap(vectorA);
 284 }
 285
 286 } // namespace