src/third_party/WebKit/Source/wtf/DequeTest.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/Deque.h"
  29
  30 #include "wtf/HashSet.h"
  31 #include "wtf/OwnPtr.h"
  32 #include "wtf/PassOwnPtr.h"
  33 #include <gtest/gtest.h>
  34
  35 namespace {
  36
  37 TEST(DequeTest, Basic)
  38 {
  39     Deque<int> intDeque;
  40     EXPECT_TRUE(intDeque.isEmpty());
  41     EXPECT_EQ(0ul, intDeque.size());
  42 }
  43
  44 void checkNumberSequence(Deque<int>& deque, int from, int to, bool increment)
  45 {
  46     Deque<int>::iterator it = increment ? deque.begin() : deque.end();
  47     size_t index = increment ? 0 : deque.size();
  48     int step = from < to ? 1 : -1;
  49     for (int i = from; i != to + step; i += step) {
  50         if (!increment) {
  51             --it;
  52             --index;
  53         }
  54
  55         EXPECT_EQ(i, *it);
  56         EXPECT_EQ(i, deque[index]);
  57
  58         if (increment) {
  59             ++it;
  60             ++index;
  61         }
  62     }
  63     EXPECT_EQ(increment ? deque.end() : deque.begin(), it);
  64     EXPECT_EQ(increment ? deque.size() : 0, index);
  65 }
  66
  67 void checkNumberSequenceReverse(Deque<int>& deque, int from, int to, bool increment)
  68 {
  69     Deque<int>::reverse_iterator it = increment ? deque.rbegin() : deque.rend();
  70     size_t index = increment ? 0 : deque.size();
  71     int step = from < to ? 1 : -1;
  72     for (int i = from; i != to + step; i += step) {
  73         if (!increment) {
  74             --it;
  75             --index;
  76         }
  77
  78         EXPECT_EQ(i, *it);
  79         EXPECT_EQ(i, deque.at(deque.size() - 1 - index));
  80
  81         if (increment) {
  82             ++it;
  83             ++index;
  84         }
  85     }
  86     EXPECT_EQ(increment ? deque.rend() : deque.rbegin(), it);
  87     EXPECT_EQ(increment ? deque.size() : 0, index);
  88 }
  89
  90 TEST(DequeTest, Reverse)
  91 {
  92     Deque<int> intDeque;
  93     intDeque.append(10);
  94     intDeque.append(11);
  95     intDeque.append(12);
  96     intDeque.append(13);
  97
  98     checkNumberSequence(intDeque, 10, 13, true);
  99     checkNumberSequence(intDeque, 13, 10, false);
 100     checkNumberSequenceReverse(intDeque, 13, 10, true);
 101     checkNumberSequenceReverse(intDeque, 10, 13, false);
 102
 103     intDeque.append(14);
 104     intDeque.append(15);
 105     EXPECT_EQ(10, intDeque.takeFirst());
 106     EXPECT_EQ(15, intDeque.takeLast());
 107     checkNumberSequence(intDeque, 11, 14, true);
 108     checkNumberSequence(intDeque, 14, 11, false);
 109     checkNumberSequenceReverse(intDeque, 14, 11, true);
 110     checkNumberSequenceReverse(intDeque, 11, 14, false);
 111
 112     for (int i = 15; i < 200; ++i)
 113         intDeque.append(i);
 114     checkNumberSequence(intDeque, 11, 199, true);
 115     checkNumberSequence(intDeque, 199, 11, false);
 116     checkNumberSequenceReverse(intDeque, 199, 11, true);
 117     checkNumberSequenceReverse(intDeque, 11, 199, false);
 118
 119     for (int i = 0; i < 180; ++i) {
 120         EXPECT_EQ(i + 11, intDeque[0]);
 121         EXPECT_EQ(i + 11, intDeque.takeFirst());
 122     }
 123     checkNumberSequence(intDeque, 191, 199, true);
 124     checkNumberSequence(intDeque, 199, 191, false);
 125     checkNumberSequenceReverse(intDeque, 199, 191, true);
 126     checkNumberSequenceReverse(intDeque, 191, 199, false);
 127
 128     Deque<int> intDeque2;
 129     swap(intDeque, intDeque2);
 130
 131     checkNumberSequence(intDeque2, 191, 199, true);
 132     checkNumberSequence(intDeque2, 199, 191, false);
 133     checkNumberSequenceReverse(intDeque2, 199, 191, true);
 134     checkNumberSequenceReverse(intDeque2, 191, 199, false);
 135
 136     intDeque.swap(intDeque2);
 137
 138     checkNumberSequence(intDeque, 191, 199, true);
 139     checkNumberSequence(intDeque, 199, 191, false);
 140     checkNumberSequenceReverse(intDeque, 199, 191, true);
 141     checkNumberSequenceReverse(intDeque, 191, 199, false);
 142
 143     intDeque.swap(intDeque2);
 144
 145     checkNumberSequence(intDeque2, 191, 199, true);
 146     checkNumberSequence(intDeque2, 199, 191, false);
 147     checkNumberSequenceReverse(intDeque2, 199, 191, true);
 148     checkNumberSequenceReverse(intDeque2, 191, 199, false);
 149 }
 150
 151 class DestructCounter {
 152 public:
 153     explicit DestructCounter(int i, int* destructNumber)
 154         : m_i(i)
 155         , m_destructNumber(destructNumber)
 156     { }
 157
 158     ~DestructCounter() { ++(*m_destructNumber); }
 159     int get() const { return m_i; }
 160
 161 private:
 162     int m_i;
 163     int* m_destructNumber;
 164 };
 165
 166 typedef WTF::Deque<OwnPtr<DestructCounter> > OwnPtrDeque;
 167
 168 TEST(DequeTest, OwnPtr)
 169 {
 170     int destructNumber = 0;
 171     OwnPtrDeque deque;
 172     deque.append(adoptPtr(new DestructCounter(0, &destructNumber)));
 173     deque.append(adoptPtr(new DestructCounter(1, &destructNumber)));
 174     EXPECT_EQ(2u, deque.size());
 175
 176     OwnPtr<DestructCounter>& counter0 = deque.first();
 177     EXPECT_EQ(0, counter0->get());
 178     int counter1 = deque.last()->get();
 179     EXPECT_EQ(1, counter1);
 180     EXPECT_EQ(0, destructNumber);
 181
 182     size_t index = 0;
 183     for (OwnPtrDeque::iterator iter = deque.begin(); iter != deque.end(); ++iter) {
 184         OwnPtr<DestructCounter>& refCounter = *iter;
 185         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
 186         EXPECT_EQ(index, static_cast<size_t>((*refCounter).get()));
 187         index++;
 188     }
 189     EXPECT_EQ(0, destructNumber);
 190
 191     OwnPtrDeque::iterator it = deque.begin();
 192     for (index = 0; index < deque.size(); ++index) {
 193         OwnPtr<DestructCounter>& refCounter = *it;
 194         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
 195         index++;
 196         ++it;
 197     }
 198     EXPECT_EQ(0, destructNumber);
 199
 200     EXPECT_EQ(0, deque.first()->get());
 201     deque.removeFirst();
 202     EXPECT_EQ(1, deque.first()->get());
 203     EXPECT_EQ(1u, deque.size());
 204     EXPECT_EQ(1, destructNumber);
 205
 206     OwnPtr<DestructCounter> ownCounter1 = deque.first().release();
 207     deque.removeFirst();
 208     EXPECT_EQ(counter1, ownCounter1->get());
 209     EXPECT_EQ(0u, deque.size());
 210     EXPECT_EQ(1, destructNumber);
 211
 212     ownCounter1.clear();
 213     EXPECT_EQ(2, destructNumber);
 214
 215     size_t count = 1025;
 216     destructNumber = 0;
 217     for (size_t i = 0; i < count; ++i)
 218         deque.prepend(adoptPtr(new DestructCounter(i, &destructNumber)));
 219
 220     // Deque relocation must not destruct OwnPtr element.
 221     EXPECT_EQ(0, destructNumber);
 222     EXPECT_EQ(count, deque.size());
 223
 224     OwnPtrDeque copyDeque;
 225     deque.swap(copyDeque);
 226     EXPECT_EQ(0, destructNumber);
 227     EXPECT_EQ(count, copyDeque.size());
 228     EXPECT_EQ(0u, deque.size());
 229
 230     copyDeque.clear();
 231     EXPECT_EQ(count, static_cast<size_t>(destructNumber));
 232 }
 233
 234 // WrappedInt class will fail if it was memmoved or memcpyed.
 235 static HashSet<void*> constructedWrappedInts;
 236 class WrappedInt {
 237 public:
 238     WrappedInt(int i = 0)
 239         : m_originalThisPtr(this)
 240         , m_i(i)
 241     {
 242         constructedWrappedInts.add(this);
 243     }
 244
 245     WrappedInt(const WrappedInt& other)
 246         : m_originalThisPtr(this)
 247         , m_i(other.m_i)
 248     {
 249         constructedWrappedInts.add(this);
 250     }
 251
 252     WrappedInt& operator=(const WrappedInt& other)
 253     {
 254         m_i = other.m_i;
 255         return *this;
 256     }
 257
 258     ~WrappedInt()
 259     {
 260         EXPECT_EQ(m_originalThisPtr, this);
 261         EXPECT_TRUE(constructedWrappedInts.contains(this));
 262         constructedWrappedInts.remove(this);
 263     }
 264
 265     int get() const { return m_i; }
 266
 267 private:
 268     void* m_originalThisPtr;
 269     int m_i;
 270 };
 271
 272 TEST(DequeTest, SwapWithoutInlineCapacity)
 273 {
 274     Deque<WrappedInt> dequeA;
 275     dequeA.append(WrappedInt(1));
 276     Deque<WrappedInt> dequeB;
 277     dequeB.append(WrappedInt(2));
 278
 279     ASSERT_EQ(dequeA.size(), dequeB.size());
 280     dequeA.swap(dequeB);
 281
 282     ASSERT_EQ(1u, dequeA.size());
 283     EXPECT_EQ(2, dequeA.first().get());
 284     ASSERT_EQ(1u, dequeB.size());
 285     EXPECT_EQ(1, dequeB.first().get());
 286
 287     dequeA.append(WrappedInt(3));
 288
 289     ASSERT_GT(dequeA.size(), dequeB.size());
 290     dequeA.swap(dequeB);
 291
 292     ASSERT_EQ(1u, dequeA.size());
 293     EXPECT_EQ(1, dequeA.first().get());
 294     ASSERT_EQ(2u, dequeB.size());
 295     EXPECT_EQ(2, dequeB.first().get());
 296
 297     ASSERT_LT(dequeA.size(), dequeB.size());
 298     dequeA.swap(dequeB);
 299
 300     ASSERT_EQ(2u, dequeA.size());
 301     EXPECT_EQ(2, dequeA.first().get());
 302     ASSERT_EQ(1u, dequeB.size());
 303     EXPECT_EQ(1, dequeB.first().get());
 304
 305     dequeA.append(WrappedInt(4));
 306     dequeA.swap(dequeB);
 307
 308     ASSERT_EQ(1u, dequeA.size());
 309     EXPECT_EQ(1, dequeA.first().get());
 310     ASSERT_EQ(3u, dequeB.size());
 311     EXPECT_EQ(2, dequeB.first().get());
 312
 313     dequeB.swap(dequeA);
 314 }
 315
 316 } // namespace