Add Deque::removeLast
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Jul 2013 13:22:31 +0000 (13:22 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Jul 2013 13:22:31 +0000 (13:22 +0000)
https://bugs.webkit.org/show_bug.cgi?id=118466

Source/WTF:

Reviewed by Andreas Kling.

Deque can remove both the first and the last element efficiently.

Test: TestWebKitAPI/Tests/WTF/Deque.cpp

* wtf/Deque.h:
(WTF::::takeLast):
(WTF::::removeLast):

Tools:

Reviewed by Andreas Kling.

* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WTF/Deque.cpp: Added.
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@152449 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/Deque.h
Tools/ChangeLog
Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
Tools/TestWebKitAPI/Tests/WTF/Deque.cpp [new file with mode: 0644]

index 0749d6f..7b87101 100644 (file)
@@ -1,3 +1,18 @@
+2013-07-08  Antti Koivisto  <antti@apple.com>
+
+        Add Deque::removeLast
+        https://bugs.webkit.org/show_bug.cgi?id=118466
+
+        Reviewed by Andreas Kling.
+        
+        Deque can remove both the first and the last element efficiently.
+        
+        Test: TestWebKitAPI/Tests/WTF/Deque.cpp
+
+        * wtf/Deque.h:
+        (WTF::::takeLast):
+        (WTF::::removeLast):
+
 2013-07-08  Zoltan Arvai  <zarvai@inf.u-szeged.hu>
 
         [Qt][Windows] Buildfix after r152426.
index da52290..5350c7a 100644 (file)
@@ -79,10 +79,12 @@ namespace WTF {
 
         T& last() { ASSERT(m_start != m_end); return *(--end()); }
         const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
+        PassType takeLast();
 
         template<typename U> void append(const U&);
         template<typename U> void prepend(const U&);
         void removeFirst();
+        void removeLast();
         void remove(iterator&);
         void remove(const_iterator&);
 
@@ -406,6 +408,14 @@ namespace WTF {
         return Pass::transfer(oldFirst);
     }
 
+    template<typename T, size_t inlineCapacity>
+    inline typename Deque<T, inlineCapacity>::PassType Deque<T, inlineCapacity>::takeLast()
+    {
+        T oldLast = Pass::transfer(last());
+        removeLast();
+        return Pass::transfer(oldLast);
+    }
+
     template<typename T, size_t inlineCapacity> template<typename U>
     inline void Deque<T, inlineCapacity>::append(const U& value)
     {
@@ -447,6 +457,20 @@ namespace WTF {
     }
 
     template<typename T, size_t inlineCapacity>
+    inline void Deque<T, inlineCapacity>::removeLast()
+    {
+        checkValidity();
+        invalidateIterators();
+        ASSERT(!isEmpty());
+        if (!m_end)
+            m_end = m_buffer.capacity() - 1;
+        else
+            --m_end;
+        TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
+        checkValidity();
+    }
+
+    template<typename T, size_t inlineCapacity>
     inline void Deque<T, inlineCapacity>::remove(iterator& it)
     {
         it.checkValidity();
index 70f26d6..282b478 100644 (file)
@@ -1,3 +1,14 @@
+2013-07-08  Antti Koivisto  <antti@apple.com>
+
+        Add Deque::removeLast
+        https://bugs.webkit.org/show_bug.cgi?id=118466
+
+        Reviewed by Andreas Kling.
+
+        * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+        * TestWebKitAPI/Tests/WTF/Deque.cpp: Added.
+        (TestWebKitAPI::TEST):
+
 2013-07-08  Brian Holt  <brian.holt@samsung.com>
 
         [GTK] Leak: GFile* leaking in beginDragWithFilesCallback
index 00cc89a..1bdb2c6 100644 (file)
                E194E1BB177E5145009C4D4E /* StopLoadingFromDidReceiveResponse.mm in Sources */ = {isa = PBXBuildFile; fileRef = E194E1BA177E5145009C4D4E /* StopLoadingFromDidReceiveResponse.mm */; };
                E194E1BD177E53C7009C4D4E /* StopLoadingFromDidReceiveResponse.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = E194E1BC177E534A009C4D4E /* StopLoadingFromDidReceiveResponse.html */; };
                E490296814E2E3A4002BEDD1 /* TypingStyleCrash.mm in Sources */ = {isa = PBXBuildFile; fileRef = E490296714E2E3A4002BEDD1 /* TypingStyleCrash.mm */; };
+               E4A757D4178AF1B100B5D7A4 /* Deque.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */; };
                F660AA0D15A5F061003A1243 /* GetInjectedBundleInitializationUserDataCallback.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F660AA0C15A5F061003A1243 /* GetInjectedBundleInitializationUserDataCallback.cpp */; };
                F660AA1115A5F631003A1243 /* GetInjectedBundleInitializationUserDataCallback_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F660AA0F15A5F624003A1243 /* GetInjectedBundleInitializationUserDataCallback_Bundle.cpp */; };
                F660AA1315A619C9003A1243 /* InjectedBundleInitializationUserDataCallbackWins.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F660AA1215A619C8003A1243 /* InjectedBundleInitializationUserDataCallbackWins.cpp */; };
                E194E1BA177E5145009C4D4E /* StopLoadingFromDidReceiveResponse.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = StopLoadingFromDidReceiveResponse.mm; sourceTree = "<group>"; };
                E194E1BC177E534A009C4D4E /* StopLoadingFromDidReceiveResponse.html */ = {isa = PBXFileReference; lastKnownFileType = text.html; path = StopLoadingFromDidReceiveResponse.html; sourceTree = "<group>"; };
                E490296714E2E3A4002BEDD1 /* TypingStyleCrash.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = TypingStyleCrash.mm; sourceTree = "<group>"; };
+               E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = Deque.cpp; path = WTF/Deque.cpp; sourceTree = "<group>"; };
                F3FC3EE213678B7300126A65 /* libgtest.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; path = libgtest.a; sourceTree = BUILT_PRODUCTS_DIR; };
                F660AA0C15A5F061003A1243 /* GetInjectedBundleInitializationUserDataCallback.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = GetInjectedBundleInitializationUserDataCallback.cpp; sourceTree = "<group>"; };
                F660AA0F15A5F624003A1243 /* GetInjectedBundleInitializationUserDataCallback_Bundle.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = GetInjectedBundleInitializationUserDataCallback_Bundle.cpp; sourceTree = "<group>"; };
                                26F1B44215CA434F00D1E4BF /* AtomicString.cpp */,
                                A7A966DA140ECCC8005EF9B4 /* CheckedArithmeticOperations.cpp */,
                                26A2C72E15E2E73C005B1A14 /* CString.cpp */,
+                               E4A757D3178AEA5B00B5D7A4 /* Deque.cpp */,
                                1AA9E55714980A9900001A8A /* Functional.cpp */,
                                0BCD833414857CE400EA2003 /* HashMap.cpp */,
                                26B2DFF815BDE599004F691D /* HashSet.cpp */,
                                37A6895F148A9B50005100FA /* SubresourceErrorCrash.mm in Sources */,
                                C081224513FC19EC00DC39AE /* SyntheticBackingScaleFactorWindow.m in Sources */,
                                0BCD856A1485C98B00EA2003 /* TemporaryChange.cpp in Sources */,
+                               E4A757D4178AF1B100B5D7A4 /* Deque.cpp in Sources */,
                                29AB8AA4164C7A9300D49BEC /* TestBrowsingContextLoadDelegate.mm in Sources */,
                                BC131AA9117131FC00B69727 /* TestsController.cpp in Sources */,
                                E490296814E2E3A4002BEDD1 /* TypingStyleCrash.mm in Sources */,
diff --git a/Tools/TestWebKitAPI/Tests/WTF/Deque.cpp b/Tools/TestWebKitAPI/Tests/WTF/Deque.cpp
new file mode 100644 (file)
index 0000000..26a815a
--- /dev/null
@@ -0,0 +1,106 @@
+/*
+ * Copyright (C) 2011 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include <wtf/Deque.h>
+
+namespace TestWebKitAPI {
+
+TEST(WTF, DequeIterator)
+{
+    Deque<int> deque;
+    deque.append(11);
+    deque.prepend(10);
+    deque.append(12);
+    deque.append(13);
+
+    Deque<int>::iterator it = deque.begin();
+    Deque<int>::iterator end = deque.end();
+    EXPECT_TRUE(end != it);
+
+    EXPECT_EQ(10, *it);
+    ++it;
+    EXPECT_EQ(11, *it);
+    ++it;
+    EXPECT_EQ(12, *it);
+    ++it;
+    EXPECT_EQ(13, *it);
+    ++it;
+
+    EXPECT_TRUE(end == it);
+}
+
+TEST(WTF, DequeReverseIterator)
+{
+    Deque<int> deque;
+    deque.append(11);
+    deque.prepend(10);
+    deque.append(12);
+    deque.append(13);
+
+    Deque<int>::reverse_iterator it = deque.rbegin();
+    Deque<int>::reverse_iterator end = deque.rend();
+    EXPECT_TRUE(end != it);
+
+    EXPECT_EQ(13, *it);
+    ++it;
+    EXPECT_EQ(12, *it);
+    ++it;
+    EXPECT_EQ(11, *it);
+    ++it;
+    EXPECT_EQ(10, *it);
+    ++it;
+
+    EXPECT_TRUE(end == it);
+}
+
+TEST(WTF, DequeRemove)
+{
+    Deque<int> deque;
+    deque.append(11);
+    deque.prepend(10);
+    deque.append(12);
+    deque.append(13);
+
+    EXPECT_EQ(10, deque.first());
+    EXPECT_EQ(13, deque.last());
+
+    deque.removeLast();
+    EXPECT_EQ(10, deque.first());
+    EXPECT_EQ(12, deque.last());
+
+    deque.removeFirst();
+    EXPECT_EQ(11, deque.first());
+    EXPECT_EQ(12, deque.last());
+
+    deque.removeFirst();
+    EXPECT_EQ(12, deque.first());
+    EXPECT_EQ(12, deque.last());
+
+    deque.removeLast();
+    EXPECT_TRUE(deque.isEmpty());
+}
+
+} // namespace TestWebKitAPI