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