Diff
Modified: trunk/Source/WTF/ChangeLog (137187 => 137188)
--- trunk/Source/WTF/ChangeLog 2012-12-10 19:14:45 UTC (rev 137187)
+++ trunk/Source/WTF/ChangeLog 2012-12-10 19:26:30 UTC (rev 137188)
@@ -1,3 +1,27 @@
+2012-12-10 Benjamin Poulain <[email protected]>
+
+ Add convenience methods to use ListHashSet for a LRU cache
+ https://bugs.webkit.org/show_bug.cgi?id=104499
+
+ Reviewed by Sam Weinig.
+
+ ListHashSet is a great abstract data type to implement caches.
+ Unfortunately, the class was missing methods to do that easily and
+ efficiently. This patch fixes that.
+
+ The names appendOrMoveToLast() and prependOrMoveToFirst() were chosen
+ in favor of append()/prepend() to ensure they are not used in place of
+ add() by accident.
+
+ * wtf/ListHashSet.h:
+ (ListHashSet):
+ (WTF::::removeFirst):
+ (WTF::::appendOrMoveToLast):
+ (WTF::::prependOrMoveToFirst):
+ (WTF::::unlink):
+ (WTF::::unlinkAndDelete):
+ (WTF::::prependNode):
+
2012-12-10 Eric Carlson <[email protected]>
Add support for in-band text tracks to Mac port
Modified: trunk/Source/WTF/wtf/ListHashSet.h (137187 => 137188)
--- trunk/Source/WTF/wtf/ListHashSet.h 2012-12-10 19:14:45 UTC (rev 137187)
+++ trunk/Source/WTF/wtf/ListHashSet.h 2012-12-10 19:26:30 UTC (rev 137188)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
* Copyright (C) 2011, Benjamin Poulain <[email protected]>
*
* This library is free software; you can redistribute it and/or
@@ -38,10 +38,6 @@
// guaranteed safe against mutation of the ListHashSet, except for
// removal of the item currently pointed to by a given iterator.
- // In theory it would be possible to add prepend, insertAfter
- // and an append that moves the element to the end even if already present,
- // but unclear yet if these are needed.
-
template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
template<typename Value, size_t inlineCapacity, typename HashFunctions>
@@ -112,6 +108,7 @@
ValueType& first();
const ValueType& first() const;
+ void removeFirst();
ValueType& last();
const ValueType& last() const;
@@ -134,6 +131,14 @@
// and a bool that is true if an new entry was added.
AddResult add(const ValueType&);
+ // Add the value to the end of the collection. If the value was already in
+ // the list, it is moved to the end.
+ AddResult appendOrMoveToLast(const ValueType&);
+
+ // Add the value to the beginning of the collection. If the value was already in
+ // the list, it is moved to the beginning.
+ AddResult prependOrMoveToFirst(const ValueType&);
+
AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue);
AddResult insertBefore(iterator, const ValueType&);
@@ -142,8 +147,10 @@
void clear();
private:
+ void unlink(Node*);
void unlinkAndDelete(Node*);
void appendNode(Node*);
+ void prependNode(Node*);
void insertNodeBefore(Node* beforeNode, Node* newNode);
void deleteAllNodes();
@@ -629,6 +636,14 @@
}
template<typename T, size_t inlineCapacity, typename U>
+ inline void ListHashSet<T, inlineCapacity, U>::removeFirst()
+ {
+ ASSERT(!isEmpty());
+ m_impl.remove(m_head);
+ unlinkAndDelete(m_head);
+ }
+
+ template<typename T, size_t inlineCapacity, typename U>
inline const T& ListHashSet<T, inlineCapacity, U>::first() const
{
ASSERT(!isEmpty());
@@ -724,6 +739,28 @@
}
template<typename T, size_t inlineCapacity, typename U>
+ typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType &value)
+ {
+ typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
+ Node* node = *result.iterator;
+ if (!result.isNewEntry)
+ unlink(node);
+ appendNode(node);
+ return AddResult(makeIterator(*result.iterator), result.isNewEntry);
+ }
+
+ template<typename T, size_t inlineCapacity, typename U>
+ typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType &value)
+ {
+ typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
+ Node* node = *result.iterator;
+ if (!result.isNewEntry)
+ unlink(node);
+ prependNode(node);
+ return AddResult(makeIterator(*result.iterator), result.isNewEntry);
+ }
+
+ template<typename T, size_t inlineCapacity, typename U>
typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue)
{
typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get());
@@ -763,7 +800,7 @@
}
template<typename T, size_t inlineCapacity, typename U>
- void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
+ void ListHashSet<T, inlineCapacity, U>::unlink(Node* node)
{
if (!node->m_prev) {
ASSERT(node == m_head);
@@ -780,7 +817,12 @@
ASSERT(node != m_tail);
node->m_next->m_prev = node->m_prev;
}
+ }
+ template<typename T, size_t inlineCapacity, typename U>
+ void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
+ {
+ unlink(node);
node->destroy(m_allocator.get());
}
@@ -802,6 +844,20 @@
}
template<typename T, size_t inlineCapacity, typename U>
+ void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node)
+ {
+ node->m_prev = 0;
+ node->m_next = m_head;
+
+ if (m_head)
+ m_head->m_prev = node;
+ else
+ m_tail = node;
+
+ m_head = node;
+ }
+
+ template<typename T, size_t inlineCapacity, typename U>
void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
{
if (!beforeNode)
Modified: trunk/Tools/ChangeLog (137187 => 137188)
--- trunk/Tools/ChangeLog 2012-12-10 19:14:45 UTC (rev 137187)
+++ trunk/Tools/ChangeLog 2012-12-10 19:26:30 UTC (rev 137188)
@@ -1,3 +1,20 @@
+2012-12-10 Benjamin Poulain <[email protected]>
+
+ Add convenience methods to use ListHashSet for a LRU cache
+ https://bugs.webkit.org/show_bug.cgi?id=104499
+
+ Reviewed by Sam Weinig.
+
+ Test the new methods added to ListHashSet.
+
+ * TestWebKitAPI/CMakeLists.txt:
+ * TestWebKitAPI/GNUmakefile.am:
+ * TestWebKitAPI/TestWebKitAPI.gypi:
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+ * TestWebKitAPI/Tests/WTF/ListHashSet.cpp: Added.
+ (TestWebKitAPI):
+ (TestWebKitAPI::TEST):
+
2012-12-10 Dirk Pranke <[email protected]>
webkit-patch print-expectations doesn't work right for platforms w/ shared expectations
Modified: trunk/Tools/TestWebKitAPI/CMakeLists.txt (137187 => 137188)
--- trunk/Tools/TestWebKitAPI/CMakeLists.txt 2012-12-10 19:14:45 UTC (rev 137187)
+++ trunk/Tools/TestWebKitAPI/CMakeLists.txt 2012-12-10 19:26:30 UTC (rev 137188)
@@ -73,6 +73,7 @@
${TESTWEBKITAPI_DIR}/Tests/WTF/Functional.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/HashMap.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/IntegerToStringConversion.cpp
+ ${TESTWEBKITAPI_DIR}/Tests/WTF/ListHashSet.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/MathExtras.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/MetaAllocator.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/MemoryInstrumentationTest.cpp
Modified: trunk/Tools/TestWebKitAPI/GNUmakefile.am (137187 => 137188)
--- trunk/Tools/TestWebKitAPI/GNUmakefile.am 2012-12-10 19:14:45 UTC (rev 137187)
+++ trunk/Tools/TestWebKitAPI/GNUmakefile.am 2012-12-10 19:26:30 UTC (rev 137188)
@@ -52,6 +52,7 @@
Tools/TestWebKitAPI/Tests/WTF/Functional.cpp \
Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp \
Tools/TestWebKitAPI/Tests/WTF/IntegerToStringConversion.cpp \
+ Tools/TestWebKitAPI/Tests/WTF/ListHashSet.cpp \
Tools/TestWebKitAPI/Tests/WTF/MathExtras.cpp \
Tools/TestWebKitAPI/Tests/WTF/MediaTime.cpp \
Tools/TestWebKitAPI/Tests/WTF/RedBlackTree.cpp \
Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.gypi (137187 => 137188)
--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.gypi 2012-12-10 19:14:45 UTC (rev 137187)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.gypi 2012-12-10 19:26:30 UTC (rev 137188)
@@ -36,6 +36,8 @@
'Tests/WTF/CString.cpp',
'Tests/WTF/Functional.cpp',
'Tests/WTF/HashMap.cpp',
+ 'Tests/WTF/HashSet.cpp',
+ 'Tests/WTF/ListHashSet.cpp',
'Tests/WTF/MathExtras.cpp',
'Tests/WTF/MediaTime.cpp',
'Tests/WTF/MemoryInstrumentationTest.cpp',
Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (137187 => 137188)
--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2012-12-10 19:14:45 UTC (rev 137187)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2012-12-10 19:26:30 UTC (rev 137188)
@@ -23,6 +23,7 @@
1ADBEFE3130C6AA100D61D19 /* simple-accelerated-compositing.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1ADBEFBC130C6A0100D61D19 /* simple-accelerated-compositing.html */; };
1AEDE22613E5E7E700E62FE8 /* InjectedBundleControllerMac.mm in Sources */ = {isa = PBXBuildFile; fileRef = 1AEDE22413E5E7A000E62FE8 /* InjectedBundleControllerMac.mm */; };
261516D615B0E60500A2C201 /* SetAndUpdateCacheModel.mm in Sources */ = {isa = PBXBuildFile; fileRef = 261516D515B0E60500A2C201 /* SetAndUpdateCacheModel.mm */; };
+ 26300B1816755CD90066886D /* ListHashSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26300B1716755CD90066886D /* ListHashSet.cpp */; };
265AF55015D1E48A00B0CB4A /* WTFString.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 265AF54F15D1E48A00B0CB4A /* WTFString.cpp */; };
266FAFD315E5775200F61D5B /* IntegerToStringConversion.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 266FAFD215E5775200F61D5B /* IntegerToStringConversion.cpp */; };
26A2C72F15E2E73C005B1A14 /* CString.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26A2C72E15E2E73C005B1A14 /* CString.cpp */; };
@@ -267,6 +268,7 @@
1ADBEFBC130C6A0100D61D19 /* simple-accelerated-compositing.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "simple-accelerated-compositing.html"; sourceTree = "<group>"; };
1AEDE22413E5E7A000E62FE8 /* InjectedBundleControllerMac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = InjectedBundleControllerMac.mm; sourceTree = "<group>"; };
261516D515B0E60500A2C201 /* SetAndUpdateCacheModel.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = SetAndUpdateCacheModel.mm; sourceTree = "<group>"; };
+ 26300B1716755CD90066886D /* ListHashSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ListHashSet.cpp; path = WTF/ListHashSet.cpp; sourceTree = "<group>"; };
265AF54F15D1E48A00B0CB4A /* WTFString.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = WTFString.cpp; path = WTF/WTFString.cpp; sourceTree = "<group>"; };
266FAFD215E5775200F61D5B /* IntegerToStringConversion.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = IntegerToStringConversion.cpp; path = WTF/IntegerToStringConversion.cpp; sourceTree = "<group>"; };
26A2C72E15E2E73C005B1A14 /* CString.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = CString.cpp; path = WTF/CString.cpp; sourceTree = "<group>"; };
@@ -666,6 +668,7 @@
1AA9E55714980A9900001A8A /* Functional.cpp */,
0BCD833414857CE400EA2003 /* HashMap.cpp */,
26B2DFF815BDE599004F691D /* HashSet.cpp */,
+ 26300B1716755CD90066886D /* ListHashSet.cpp */,
B4039F9C15E6D8B3007255D6 /* MathExtras.cpp */,
14F3B11215E45EAB00210069 /* SaturatedArithmeticOperations.cpp */,
266FAFD215E5775200F61D5B /* IntegerToStringConversion.cpp */,
@@ -959,6 +962,7 @@
C0ADBE7C12FCA4D000D2C129 /* _javascript_Test.cpp in Sources */,
C081224213FC172400DC39AE /* _javascript_TestMac.mm in Sources */,
440A1D3914A0103A008A66F2 /* KURL.cpp in Sources */,
+ 26300B1816755CD90066886D /* ListHashSet.cpp in Sources */,
52CB47411448FB9300873995 /* LoadAlternateHTMLStringWithNonDirectoryURL.cpp in Sources */,
33DC8911141953A300747EF7 /* LoadCanceledNoServerRedirectCallback.cpp in Sources */,
BC131A9B1171316900B69727 /* main.mm in Sources */,
Added: trunk/Tools/TestWebKitAPI/Tests/WTF/ListHashSet.cpp (0 => 137188)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/ListHashSet.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/ListHashSet.cpp 2012-12-10 19:26:30 UTC (rev 137188)
@@ -0,0 +1,173 @@
+/*
+ * Copyright (C) 2012 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/ListHashSet.h>
+
+namespace TestWebKitAPI {
+
+TEST(WTF, ListHashSetRemoveFirst)
+{
+ ListHashSet<int> list;
+ list.add(1);
+ list.add(2);
+ list.add(3);
+
+ ASSERT_EQ(1, list.first());
+
+ list.removeFirst();
+ ASSERT_EQ(2, list.first());
+
+ list.removeFirst();
+ ASSERT_EQ(3, list.first());
+
+ list.removeFirst();
+ ASSERT_TRUE(list.isEmpty());
+}
+
+TEST(WTF, ListHashSetAppendOrMoveToLastNewItems)
+{
+ ListHashSet<int> list;
+ ListHashSet<int>::AddResult result = list.appendOrMoveToLast(1);
+ ASSERT_TRUE(result.isNewEntry);
+ result = list.add(2);
+ ASSERT_TRUE(result.isNewEntry);
+ result = list.appendOrMoveToLast(3);
+ ASSERT_TRUE(result.isNewEntry);
+
+ ASSERT_EQ(list.size(), 3);
+
+ // The list should be in order 1, 2, 3.
+ ListHashSet<int>::iterator iterator = list.begin();
+ ASSERT_EQ(1, *iterator);
+ ++iterator;
+ ASSERT_EQ(2, *iterator);
+ ++iterator;
+ ASSERT_EQ(3, *iterator);
+ ++iterator;
+}
+
+TEST(WTF, ListHashSetAppendOrMoveToLastWithDuplicates)
+{
+ ListHashSet<int> list;
+
+ // Add a single element twice.
+ ListHashSet<int>::AddResult result = list.add(1);
+ ASSERT_TRUE(result.isNewEntry);
+ result = list.appendOrMoveToLast(1);
+ ASSERT_FALSE(result.isNewEntry);
+ ASSERT_EQ(1, list.size());
+
+ list.add(2);
+ list.add(3);
+ ASSERT_EQ(3, list.size());
+
+ // Appending 2 move it to the end.
+ ASSERT_EQ(3, list.last());
+ result = list.appendOrMoveToLast(2);
+ ASSERT_FALSE(result.isNewEntry);
+ ASSERT_EQ(2, list.last());
+
+ // Inverse the list by moving each element to end end.
+ result = list.appendOrMoveToLast(3);
+ ASSERT_FALSE(result.isNewEntry);
+ result = list.appendOrMoveToLast(2);
+ ASSERT_FALSE(result.isNewEntry);
+ result = list.appendOrMoveToLast(1);
+ ASSERT_FALSE(result.isNewEntry);
+ ASSERT_EQ(3, list.size());
+
+ ListHashSet<int>::iterator iterator = list.begin();
+ ASSERT_EQ(3, *iterator);
+ ++iterator;
+ ASSERT_EQ(2, *iterator);
+ ++iterator;
+ ASSERT_EQ(1, *iterator);
+ ++iterator;
+}
+
+TEST(WTF, ListHashSetPrependOrMoveToLastNewItems)
+{
+ ListHashSet<int> list;
+ ListHashSet<int>::AddResult result = list.prependOrMoveToFirst(1);
+ ASSERT_TRUE(result.isNewEntry);
+ result = list.add(2);
+ ASSERT_TRUE(result.isNewEntry);
+ result = list.prependOrMoveToFirst(3);
+ ASSERT_TRUE(result.isNewEntry);
+
+ ASSERT_EQ(list.size(), 3);
+
+ // The list should be in order 3, 1, 2.
+ ListHashSet<int>::iterator iterator = list.begin();
+ ASSERT_EQ(3, *iterator);
+ ++iterator;
+ ASSERT_EQ(1, *iterator);
+ ++iterator;
+ ASSERT_EQ(2, *iterator);
+ ++iterator;
+}
+
+TEST(WTF, ListHashSetPrependOrMoveToLastWithDuplicates)
+{
+ ListHashSet<int> list;
+
+ // Add a single element twice.
+ ListHashSet<int>::AddResult result = list.add(1);
+ ASSERT_TRUE(result.isNewEntry);
+ result = list.prependOrMoveToFirst(1);
+ ASSERT_FALSE(result.isNewEntry);
+ ASSERT_EQ(1, list.size());
+
+ list.add(2);
+ list.add(3);
+ ASSERT_EQ(3, list.size());
+
+ // Prepending 2 move it to the beginning.
+ ASSERT_EQ(1, list.first());
+ result = list.prependOrMoveToFirst(2);
+ ASSERT_FALSE(result.isNewEntry);
+ ASSERT_EQ(2, list.first());
+
+ // Inverse the list by moving each element to the first position.
+ result = list.prependOrMoveToFirst(1);
+ ASSERT_FALSE(result.isNewEntry);
+ result = list.prependOrMoveToFirst(2);
+ ASSERT_FALSE(result.isNewEntry);
+ result = list.prependOrMoveToFirst(3);
+ ASSERT_FALSE(result.isNewEntry);
+ ASSERT_EQ(3, list.size());
+
+ ListHashSet<int>::iterator iterator = list.begin();
+ ASSERT_EQ(3, *iterator);
+ ++iterator;
+ ASSERT_EQ(2, *iterator);
+ ++iterator;
+ ASSERT_EQ(1, *iterator);
+ ++iterator;
+}
+
+} // namespace TestWebKitAPI
