Home | History | Annotate | Download | only in wtf 
      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
    317