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 #include "wtf/Vector.h"
  28
  29 #include "wtf/HashSet.h"
  30 #include "wtf/OwnPtr.h"
  31 #include "wtf/PassOwnPtr.h"
  32 #include "wtf/text/WTFString.h"
  33 #include <gtest/gtest.h>
  34
  35 namespace WTF {
  36
  37 namespace {
  38
  39 TEST(VectorTest, Basic)
  40 {
  41     Vector<int> intVector;
  42     EXPECT_TRUE(intVector.isEmpty());
  43     EXPECT_EQ(0ul, intVector.size());
  44     EXPECT_EQ(0ul, intVector.capacity());
  45 }
  46
  47 TEST(VectorTest, Reverse)
  48 {
  49     Vector<int> intVector;
  50     intVector.append(10);
  51     intVector.append(11);
  52     intVector.append(12);
  53     intVector.append(13);
  54     intVector.reverse();
  55
  56     EXPECT_EQ(13, intVector[0]);
  57     EXPECT_EQ(12, intVector[1]);
  58     EXPECT_EQ(11, intVector[2]);
  59     EXPECT_EQ(10, intVector[3]);
  60
  61     intVector.append(9);
  62     intVector.reverse();
  63
  64     EXPECT_EQ(9, intVector[0]);
  65     EXPECT_EQ(10, intVector[1]);
  66     EXPECT_EQ(11, intVector[2]);
  67     EXPECT_EQ(12, intVector[3]);
  68     EXPECT_EQ(13, intVector[4]);
  69 }
  70
  71 TEST(VectorTest, Iterator)
  72 {
  73     Vector<int> intVector;
  74     intVector.append(10);
  75     intVector.append(11);
  76     intVector.append(12);
  77     intVector.append(13);
  78
  79     Vector<int>::iterator it = intVector.begin();
  80     Vector<int>::iterator end = intVector.end();
  81     EXPECT_TRUE(end != it);
  82
  83     EXPECT_EQ(10, *it);
  84     ++it;
  85     EXPECT_EQ(11, *it);
  86     ++it;
  87     EXPECT_EQ(12, *it);
  88     ++it;
  89     EXPECT_EQ(13, *it);
  90     ++it;
  91
  92     EXPECT_TRUE(end == it);
  93 }
  94
  95 TEST(VectorTest, ReverseIterator)
  96 {
  97     Vector<int> intVector;
  98     intVector.append(10);
  99     intVector.append(11);
 100     intVector.append(12);
 101     intVector.append(13);
 102
 103     Vector<int>::reverse_iterator it = intVector.rbegin();
 104     Vector<int>::reverse_iterator end = intVector.rend();
 105     EXPECT_TRUE(end != it);
 106
 107     EXPECT_EQ(13, *it);
 108     ++it;
 109     EXPECT_EQ(12, *it);
 110     ++it;
 111     EXPECT_EQ(11, *it);
 112     ++it;
 113     EXPECT_EQ(10, *it);
 114     ++it;
 115
 116     EXPECT_TRUE(end == it);
 117 }
 118
 119 class DestructCounter {
 120 public:
 121     explicit DestructCounter(int i, int* destructNumber)
 122         : m_i(i)
 123         , m_destructNumber(destructNumber)
 124     { }
 125
 126     ~DestructCounter() { ++(*m_destructNumber); }
 127     int get() const { return m_i; }
 128
 129 private:
 130     int m_i;
 131     int* m_destructNumber;
 132 };
 133
 134 typedef WTF::Vector<OwnPtr<DestructCounter>> OwnPtrVector;
 135
 136 TEST(VectorTest, OwnPtr)
 137 {
 138     int destructNumber = 0;
 139     OwnPtrVector vector;
 140     vector.append(adoptPtr(new DestructCounter(0, &destructNumber)));
 141     vector.append(adoptPtr(new DestructCounter(1, &destructNumber)));
 142     EXPECT_EQ(2u, vector.size());
 143
 144     OwnPtr<DestructCounter>& counter0 = vector.first();
 145     ASSERT_EQ(0, counter0->get());
 146     int counter1 = vector.last()->get();
 147     ASSERT_EQ(1, counter1);
 148     ASSERT_EQ(0, destructNumber);
 149
 150     size_t index = 0;
 151     for (OwnPtrVector::iterator iter = vector.begin(); iter != vector.end(); ++iter) {
 152         OwnPtr<DestructCounter>* refCounter = iter;
 153         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()->get()));
 154         EXPECT_EQ(index, static_cast<size_t>((*refCounter)->get()));
 155         index++;
 156     }
 157     EXPECT_EQ(0, destructNumber);
 158
 159     for (index = 0; index < vector.size(); index++) {
 160         OwnPtr<DestructCounter>& refCounter = vector[index];
 161         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
 162         index++;
 163     }
 164     EXPECT_EQ(0, destructNumber);
 165
 166     EXPECT_EQ(0, vector[0]->get());
 167     EXPECT_EQ(1, vector[1]->get());
 168     vector.remove(0);
 169     EXPECT_EQ(1, vector[0]->get());
 170     EXPECT_EQ(1u, vector.size());
 171     EXPECT_EQ(1, destructNumber);
 172
 173     OwnPtr<DestructCounter> ownCounter1 = vector[0].release();
 174     vector.remove(0);
 175     ASSERT_EQ(counter1, ownCounter1->get());
 176     ASSERT_EQ(0u, vector.size());
 177     ASSERT_EQ(1, destructNumber);
 178
 179     ownCounter1.clear();
 180     EXPECT_EQ(2, destructNumber);
 181
 182     size_t count = 1025;
 183     destructNumber = 0;
 184     for (size_t i = 0; i < count; i++)
 185         vector.prepend(adoptPtr(new DestructCounter(i, &destructNumber)));
 186
 187     // Vector relocation must not destruct OwnPtr element.
 188     EXPECT_EQ(0, destructNumber);
 189     EXPECT_EQ(count, vector.size());
 190
 191     OwnPtrVector copyVector;
 192     vector.swap(copyVector);
 193     EXPECT_EQ(0, destructNumber);
 194     EXPECT_EQ(count, copyVector.size());
 195     EXPECT_EQ(0u, vector.size());
 196
 197     copyVector.clear();
 198     EXPECT_EQ(count, static_cast<size_t>(destructNumber));
 199 }
 200
 201 // WrappedInt class will fail if it was memmoved or memcpyed.
 202 static HashSet<void*> constructedWrappedInts;
 203 class WrappedInt {
 204 public:
 205     WrappedInt(int i = 0)
 206         : m_originalThisPtr(this)
 207         , m_i(i)
 208     {
 209         constructedWrappedInts.add(this);
 210     }
 211
 212     WrappedInt(const WrappedInt& other)
 213         : m_originalThisPtr(this)
 214         , m_i(other.m_i)
 215     {
 216         constructedWrappedInts.add(this);
 217     }
 218
 219     WrappedInt& operator=(const WrappedInt& other)
 220     {
 221         m_i = other.m_i;
 222         return *this;
 223     }
 224
 225     ~WrappedInt()
 226     {
 227         EXPECT_EQ(m_originalThisPtr, this);
 228         EXPECT_TRUE(constructedWrappedInts.contains(this));
 229         constructedWrappedInts.remove(this);
 230     }
 231
 232     int get() const { return m_i; }
 233
 234 private:
 235     void* m_originalThisPtr;
 236     int m_i;
 237 };
 238
 239 TEST(VectorTest, SwapWithInlineCapacity)
 240 {
 241     const size_t inlineCapacity = 2;
 242     Vector<WrappedInt, inlineCapacity> vectorA;
 243     vectorA.append(WrappedInt(1));
 244     Vector<WrappedInt, inlineCapacity> vectorB;
 245     vectorB.append(WrappedInt(2));
 246
 247     EXPECT_EQ(vectorA.size(), vectorB.size());
 248     vectorA.swap(vectorB);
 249
 250     EXPECT_EQ(1u, vectorA.size());
 251     EXPECT_EQ(2, vectorA.at(0).get());
 252     EXPECT_EQ(1u, vectorB.size());
 253     EXPECT_EQ(1, vectorB.at(0).get());
 254
 255     vectorA.append(WrappedInt(3));
 256
 257     EXPECT_GT(vectorA.size(), vectorB.size());
 258     vectorA.swap(vectorB);
 259
 260     EXPECT_EQ(1u, vectorA.size());
 261     EXPECT_EQ(1, vectorA.at(0).get());
 262     EXPECT_EQ(2u, vectorB.size());
 263     EXPECT_EQ(2, vectorB.at(0).get());
 264     EXPECT_EQ(3, vectorB.at(1).get());
 265
 266     EXPECT_LT(vectorA.size(), vectorB.size());
 267     vectorA.swap(vectorB);
 268
 269     EXPECT_EQ(2u, vectorA.size());
 270     EXPECT_EQ(2, vectorA.at(0).get());
 271     EXPECT_EQ(3, vectorA.at(1).get());
 272     EXPECT_EQ(1u, vectorB.size());
 273     EXPECT_EQ(1, vectorB.at(0).get());
 274
 275     vectorA.append(WrappedInt(4));
 276     EXPECT_GT(vectorA.size(), inlineCapacity);
 277     vectorA.swap(vectorB);
 278
 279     EXPECT_EQ(1u, vectorA.size());
 280     EXPECT_EQ(1, vectorA.at(0).get());
 281     EXPECT_EQ(3u, vectorB.size());
 282     EXPECT_EQ(2, vectorB.at(0).get());
 283     EXPECT_EQ(3, vectorB.at(1).get());
 284     EXPECT_EQ(4, vectorB.at(2).get());
 285
 286     vectorB.swap(vectorA);
 287 }
 288
 289 #if defined(ANNOTATE_CONTIGUOUS_CONTAINER)
 290 TEST(VectorTest, ContainerAnnotations)
 291 {
 292     Vector<int> vectorA;
 293     vectorA.append(10);
 294     vectorA.reserveCapacity(32);
 295
 296     volatile int* intPointerA = vectorA.data();
 297     EXPECT_DEATH(intPointerA[1] = 11, "container-overflow");
 298     vectorA.append(11);
 299     intPointerA[1] = 11;
 300     EXPECT_DEATH(intPointerA[2] = 12, "container-overflow");
 301     EXPECT_DEATH((void)intPointerA[2], "container-overflow");
 302     vectorA.shrinkToFit();
 303     vectorA.reserveCapacity(16);
 304     intPointerA = vectorA.data();
 305     EXPECT_DEATH((void)intPointerA[2], "container-overflow");
 306
 307     Vector<int> vectorB(vectorA);
 308     vectorB.reserveCapacity(16);
 309     volatile int* intPointerB = vectorB.data();
 310     EXPECT_DEATH((void)intPointerB[2], "container-overflow");
 311
 312     Vector<int> vectorC((Vector<int>(vectorA)));
 313     volatile int* intPointerC = vectorC.data();
 314     EXPECT_DEATH((void)intPointerC[2], "container-overflow");
 315     vectorC.append(13);
 316     vectorC.swap(vectorB);
 317
 318     volatile int* intPointerB2 = vectorB.data();
 319     volatile int* intPointerC2 = vectorC.data();
 320     intPointerB2[2] = 13;
 321     EXPECT_DEATH((void)intPointerB2[3], "container-overflow");
 322     EXPECT_DEATH((void)intPointerC2[2], "container-overflow");
 323
 324     vectorB = vectorC;
 325     volatile int* intPointerB3 = vectorB.data();
 326     EXPECT_DEATH((void)intPointerB3[2], "container-overflow");
 327 }
 328 #endif // defined(ANNOTATE_CONTIGUOUS_CONTAINER)
 329
 330 class Comparable {
 331 };
 332 bool operator==(const Comparable& a, const Comparable& b) { return true; }
 333
 334 template<typename T> void compare()
 335 {
 336     EXPECT_TRUE(Vector<T>() == Vector<T>());
 337     EXPECT_FALSE(Vector<T>(1) == Vector<T>(0));
 338     EXPECT_FALSE(Vector<T>() == Vector<T>(1));
 339     EXPECT_TRUE(Vector<T>(1) == Vector<T>(1));
 340
 341     Vector<T, 1> vectorWithInlineCapacity;
 342     EXPECT_TRUE(vectorWithInlineCapacity == Vector<T>());
 343     EXPECT_FALSE(vectorWithInlineCapacity == Vector<T>(1));
 344 }
 345
 346 TEST(VectorTest, Compare)
 347 {
 348     compare<int>();
 349     compare<Comparable>();
 350     compare<WTF::String>();
 351 }
 352
 353 } // anonymous namespace
 354
 355 } // namespace WTF