Revert "Use DoublyLinkedList instead of ListHashSet in DocumentState"
This reverts commit 252e8a49c9383eceebe0938a1e876f0b4ab5aa8e.
Reason for revert: Caused http://crbug.com/790739
Original change's description:
> Use DoublyLinkedList instead of ListHashSet in DocumentState
>
> The only operations carried out on form_controls_ are insertions, removals
> and iterating through the entire list. Insertion and removal can be done
> faster with a DoublyLinkedList.
>
> Since the nodes for the DoublyLinkedList are Oilpan objects, this CL
> introduces HeapDoublyLinkedList that uses Member for the head and tail
> pointers, and traces the pointers.
>
> This improves the performance of HTMLInputElement::InsertedInto and
> HTMLInputElement::RemovedFrom by ~15%.
>
> Bug:
> Change-Id: I5b4cd20737e0276bece2430edfb7ec9609690f04
> Reviewed-on: https://chromium-review.googlesource.com/758877
> Reviewed-by: Kentaro Hara <haraken@chromium.org>
> Reviewed-by: Keishi Hattori <keishi@chromium.org>
> Reviewed-by: Jeremy Roman <jbroman@chromium.org>
> Commit-Queue: Adithya Srinivasan <adithyas@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#517876}
Bug: 790739
TBR=jbroman@chromium.org,haraken@chromium.org,keishi@chromium.org,adithyas@chromium.org,lfg@chromium.org
Change-Id: I48ddedd7b356efa6b1f6f69c58e2022e9a0872f1
Reviewed-on: https://chromium-review.googlesource.com/802774
Commit-Queue: Kenneth Russell <kbr@chromium.org>
Reviewed-by: Kenneth Russell <kbr@chromium.org>
Reviewed-by: Kentaro Hara <haraken@chromium.org>
Cr-Commit-Position: refs/heads/master@{#520840}diff --git a/third_party/WebKit/Source/core/html/forms/FormController.cpp b/third_party/WebKit/Source/core/html/forms/FormController.cpp
index 535b3ce..3157e8d7 100644
--- a/third_party/WebKit/Source/core/html/forms/FormController.cpp
+++ b/third_party/WebKit/Source/core/html/forms/FormController.cpp
@@ -410,14 +410,14 @@
}
void DocumentState::AddControl(HTMLFormControlElementWithState* control) {
- DCHECK(!control->Next() && !control->Prev());
- form_controls_.Append(control);
+ auto result = form_controls_.insert(control);
+ DCHECK(result.is_new_entry);
}
void DocumentState::RemoveControl(HTMLFormControlElementWithState* control) {
- form_controls_.Remove(control);
- control->SetPrev(nullptr);
- control->SetNext(nullptr);
+ auto it = form_controls_.find(control);
+ CHECK(it != form_controls_.end());
+ form_controls_.erase(it);
}
static String FormStateSignature() {
@@ -433,8 +433,8 @@
FormKeyGenerator* key_generator = FormKeyGenerator::Create();
std::unique_ptr<SavedFormStateMap> state_map =
WTF::WrapUnique(new SavedFormStateMap);
- for (HTMLFormControlElementWithState* control = form_controls_.Head();
- control; control = control->Next()) {
+ for (const auto& form_control : form_controls_) {
+ HTMLFormControlElementWithState* control = form_control.Get();
DCHECK(control->isConnected());
if (!control->ShouldSaveAndRestoreFormControlState())
continue;
diff --git a/third_party/WebKit/Source/core/html/forms/FormController.h b/third_party/WebKit/Source/core/html/forms/FormController.h
index c21565d5..7ec8019 100644
--- a/third_party/WebKit/Source/core/html/forms/FormController.h
+++ b/third_party/WebKit/Source/core/html/forms/FormController.h
@@ -25,7 +25,6 @@
#include <memory>
#include "platform/heap/Handle.h"
-#include "platform/heap/HeapAllocator.h"
#include "platform/wtf/Allocator.h"
#include "platform/wtf/Forward.h"
#include "platform/wtf/ListHashSet.h"
@@ -92,8 +91,9 @@
Vector<String> ToStateVector();
private:
- using FormElementList = HeapDoublyLinkedList<HTMLFormControlElementWithState>;
- FormElementList form_controls_;
+ using FormElementListHashSet =
+ HeapListHashSet<Member<HTMLFormControlElementWithState>, 64>;
+ FormElementListHashSet form_controls_;
};
class FormController final : public GarbageCollectedFinalized<FormController> {
diff --git a/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.cpp b/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.cpp
index 740ae5a..b8dd24f 100644
--- a/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.cpp
+++ b/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.cpp
@@ -87,10 +87,4 @@
return true;
}
-void HTMLFormControlElementWithState::Trace(Visitor* visitor) {
- visitor->Trace(prev_);
- visitor->Trace(next_);
- HTMLFormControlElement::Trace(visitor);
-}
-
} // namespace blink
diff --git a/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.h b/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.h
index 0a4db72c..31320d6 100644
--- a/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.h
+++ b/third_party/WebKit/Source/core/html/forms/HTMLFormControlElementWithState.h
@@ -27,15 +27,13 @@
#include "core/CoreExport.h"
#include "core/html/forms/HTMLFormControlElement.h"
-#include "platform/wtf/DoublyLinkedList.h"
namespace blink {
class FormControlState;
class CORE_EXPORT HTMLFormControlElementWithState
- : public HTMLFormControlElement,
- public DoublyLinkedListNode<HTMLFormControlElementWithState> {
+ : public HTMLFormControlElement {
public:
~HTMLFormControlElementWithState() override;
@@ -48,8 +46,6 @@
virtual void RestoreFormControlState(const FormControlState&) {}
void NotifyFormStateChanged();
- void Trace(Visitor*) override;
-
protected:
HTMLFormControlElementWithState(const QualifiedName& tag_name, Document&);
@@ -57,15 +53,6 @@
InsertionNotificationRequest InsertedInto(ContainerNode*) override;
void RemovedFrom(ContainerNode*) override;
bool IsFormControlElementWithState() const final;
-
- private:
- // Pointers for DoublyLinkedListNode<HTMLFormControlElementWithState>. This
- // is used for adding an instance to a list of form controls stored in
- // DocumentState. Each instance is only added to its containing document's
- // DocumentState list.
- friend class WTF::DoublyLinkedListNode<HTMLFormControlElementWithState>;
- Member<HTMLFormControlElementWithState> prev_;
- Member<HTMLFormControlElementWithState> next_;
};
DEFINE_TYPE_CASTS(HTMLFormControlElementWithState,
diff --git a/third_party/WebKit/Source/platform/heap/HeapAllocator.h b/third_party/WebKit/Source/platform/heap/HeapAllocator.h
index 60af8f95..490e6b6 100644
--- a/third_party/WebKit/Source/platform/heap/HeapAllocator.h
+++ b/third_party/WebKit/Source/platform/heap/HeapAllocator.h
@@ -12,7 +12,6 @@
#include "platform/wtf/Allocator.h"
#include "platform/wtf/Assertions.h"
#include "platform/wtf/Deque.h"
-#include "platform/wtf/DoublyLinkedList.h"
#include "platform/wtf/HashCountedSet.h"
#include "platform/wtf/HashMap.h"
#include "platform/wtf/HashSet.h"
@@ -480,23 +479,6 @@
: Deque<T, inlineCapacity, HeapAllocator>(other) {}
};
-template <typename T>
-class HeapDoublyLinkedList : public DoublyLinkedList<T, Member<T>> {
- IS_GARBAGE_COLLECTED_TYPE();
- DISALLOW_NEW();
-
- public:
- HeapDoublyLinkedList() {
- static_assert(WTF::IsGarbageCollectedType<T>::value,
- "This should only be used for garbage collected types.");
- }
-
- void Trace(Visitor* visitor) {
- visitor->Trace(this->head_);
- visitor->Trace(this->tail_);
- }
-};
-
} // namespace blink
namespace WTF {
diff --git a/third_party/WebKit/Source/platform/heap/HeapTerminatedArray.h b/third_party/WebKit/Source/platform/heap/HeapTerminatedArray.h
index c422d31..5cd2ec8 100644
--- a/third_party/WebKit/Source/platform/heap/HeapTerminatedArray.h
+++ b/third_party/WebKit/Source/platform/heap/HeapTerminatedArray.h
@@ -59,6 +59,12 @@
friend class WTF::TerminatedArrayBuilder;
};
+template <typename T>
+class TraceEagerlyTrait<HeapTerminatedArray<T>> {
+ public:
+ static const bool value = TraceEagerlyTrait<T>::value;
+};
+
} // namespace blink
#endif // HeapTerminatedArray_h
diff --git a/third_party/WebKit/Source/platform/heap/HeapTest.cpp b/third_party/WebKit/Source/platform/heap/HeapTest.cpp
index d772ab8..99bf5dd8 100644
--- a/third_party/WebKit/Source/platform/heap/HeapTest.cpp
+++ b/third_party/WebKit/Source/platform/heap/HeapTest.cpp
@@ -6709,62 +6709,4 @@
EXPECT_TRUE(string.Impl()->HasOneRef());
}
-class DoublyLinkedListNodeImpl
- : public GarbageCollectedFinalized<DoublyLinkedListNodeImpl>,
- public DoublyLinkedListNode<DoublyLinkedListNodeImpl> {
- public:
- DoublyLinkedListNodeImpl() {}
- static DoublyLinkedListNodeImpl* Create() {
- return new DoublyLinkedListNodeImpl();
- }
-
- static int destructor_calls_;
- ~DoublyLinkedListNodeImpl() { ++destructor_calls_; }
-
- void Trace(Visitor* visitor) {
- visitor->Trace(prev_);
- visitor->Trace(next_);
- }
-
- private:
- friend class WTF::DoublyLinkedListNode<DoublyLinkedListNodeImpl>;
- Member<DoublyLinkedListNodeImpl> prev_;
- Member<DoublyLinkedListNodeImpl> next_;
-};
-
-int DoublyLinkedListNodeImpl::destructor_calls_ = 0;
-
-template <typename T>
-class HeapDoublyLinkedListContainer
- : public GarbageCollected<HeapDoublyLinkedListContainer<T>> {
- public:
- static HeapDoublyLinkedListContainer<T>* Create() {
- return new HeapDoublyLinkedListContainer<T>();
- }
- HeapDoublyLinkedListContainer<T>() {}
- HeapDoublyLinkedList<T> list_;
- void Trace(Visitor* visitor) { visitor->Trace(list_); }
-};
-
-TEST(HeapTest, HeapDoublyLinkedList) {
- Persistent<HeapDoublyLinkedListContainer<DoublyLinkedListNodeImpl>>
- container =
- HeapDoublyLinkedListContainer<DoublyLinkedListNodeImpl>::Create();
- DoublyLinkedListNodeImpl::destructor_calls_ = 0;
-
- container->list_.Append(DoublyLinkedListNodeImpl::Create());
- container->list_.Append(DoublyLinkedListNodeImpl::Create());
-
- PreciselyCollectGarbage();
- EXPECT_EQ(DoublyLinkedListNodeImpl::destructor_calls_, 0);
-
- container->list_.RemoveHead();
- PreciselyCollectGarbage();
- EXPECT_EQ(DoublyLinkedListNodeImpl::destructor_calls_, 1);
-
- container->list_.RemoveHead();
- PreciselyCollectGarbage();
- EXPECT_EQ(DoublyLinkedListNodeImpl::destructor_calls_, 2);
-}
-
} // namespace blink
diff --git a/third_party/WebKit/Source/platform/heap/TraceTraits.h b/third_party/WebKit/Source/platform/heap/TraceTraits.h
index f2464fe..899966d 100644
--- a/third_party/WebKit/Source/platform/heap/TraceTraits.h
+++ b/third_party/WebKit/Source/platform/heap/TraceTraits.h
@@ -27,10 +27,6 @@
template <typename T>
class CrossThreadWeakPersistent;
template <typename T>
-class HeapDoublyLinkedList;
-template <typename T>
-class HeapTerminatedArray;
-template <typename T>
class Member;
template <typename T>
class TraceEagerlyTrait;
@@ -438,20 +434,6 @@
static const bool value = TraceEagerlyTrait<T>::value;
};
-template <typename T>
-class TraceEagerlyTrait<HeapTerminatedArray<T>> {
- public:
- static const bool value = TraceEagerlyTrait<T>::value;
-};
-
-template <typename T>
-class TraceEagerlyTrait<HeapDoublyLinkedList<T>> {
- STATIC_ONLY(TraceEagerlyTrait);
-
- public:
- static const bool value = TraceEagerlyTrait<T>::value;
-};
-
template <typename ValueArg, size_t inlineCapacity>
class HeapListHashSetAllocator;
template <typename T, size_t inlineCapacity>
diff --git a/third_party/WebKit/Source/platform/wtf/DoublyLinkedList.h b/third_party/WebKit/Source/platform/wtf/DoublyLinkedList.h
index 4c2e9a0..5280f77 100644
--- a/third_party/WebKit/Source/platform/wtf/DoublyLinkedList.h
+++ b/third_party/WebKit/Source/platform/wtf/DoublyLinkedList.h
@@ -70,7 +70,7 @@
return static_cast<const T*>(this)->next_;
}
-template <typename T, typename PointerType = T*>
+template <typename T>
class DoublyLinkedList {
USING_FAST_MALLOC(DoublyLinkedList);
@@ -90,90 +90,83 @@
void Append(T*);
void Remove(T*);
- protected:
- PointerType head_;
- PointerType tail_;
+ private:
+ T* head_;
+ T* tail_;
DISALLOW_COPY_AND_ASSIGN(DoublyLinkedList);
};
-template <typename T, typename PointerType>
-inline DoublyLinkedList<T, PointerType>::DoublyLinkedList()
- : head_(nullptr), tail_(nullptr) {
- static_assert(
- !IsGarbageCollectedType<T>::value ||
- !std::is_same<PointerType, T*>::value,
- "Cannot use DoublyLinkedList<> with garbage collected types, use "
- "HeapDoublyLinkedList<> instead.");
-}
+template <typename T>
+inline DoublyLinkedList<T>::DoublyLinkedList() : head_(0), tail_(0) {}
-template <typename T, typename PointerType>
-inline bool DoublyLinkedList<T, PointerType>::IsEmpty() const {
+template <typename T>
+inline bool DoublyLinkedList<T>::IsEmpty() const {
return !head_;
}
-template <typename T, typename PointerType>
-inline size_t DoublyLinkedList<T, PointerType>::size() const {
+template <typename T>
+inline size_t DoublyLinkedList<T>::size() const {
size_t size = 0;
for (T* node = head_; node; node = node->Next())
++size;
return size;
}
-template <typename T, typename PointerType>
-inline void DoublyLinkedList<T, PointerType>::Clear() {
- head_ = nullptr;
- tail_ = nullptr;
+template <typename T>
+inline void DoublyLinkedList<T>::Clear() {
+ head_ = 0;
+ tail_ = 0;
}
-template <typename T, typename PointerType>
-inline T* DoublyLinkedList<T, PointerType>::Head() const {
+template <typename T>
+inline T* DoublyLinkedList<T>::Head() const {
return head_;
}
-template <typename T, typename PointerType>
-inline T* DoublyLinkedList<T, PointerType>::Tail() const {
+template <typename T>
+inline T* DoublyLinkedList<T>::Tail() const {
return tail_;
}
-template <typename T, typename PointerType>
-inline void DoublyLinkedList<T, PointerType>::Push(T* node) {
+template <typename T>
+inline void DoublyLinkedList<T>::Push(T* node) {
if (!head_) {
DCHECK(!tail_);
head_ = node;
tail_ = node;
- node->SetPrev(nullptr);
- node->SetNext(nullptr);
+ node->SetPrev(0);
+ node->SetNext(0);
return;
}
DCHECK(tail_);
head_->SetPrev(node);
node->SetNext(head_);
- node->SetPrev(nullptr);
+ node->SetPrev(0);
head_ = node;
}
-template <typename T, typename PointerType>
-inline void DoublyLinkedList<T, PointerType>::Append(T* node) {
+template <typename T>
+inline void DoublyLinkedList<T>::Append(T* node) {
if (!tail_) {
DCHECK(!head_);
head_ = node;
tail_ = node;
- node->SetPrev(nullptr);
- node->SetNext(nullptr);
+ node->SetPrev(0);
+ node->SetNext(0);
return;
}
DCHECK(head_);
tail_->SetNext(node);
node->SetPrev(tail_);
- node->SetNext(nullptr);
+ node->SetNext(0);
tail_ = node;
}
-template <typename T, typename PointerType>
-inline void DoublyLinkedList<T, PointerType>::Remove(T* node) {
+template <typename T>
+inline void DoublyLinkedList<T>::Remove(T* node) {
if (node->Prev()) {
DCHECK_NE(node, head_);
node->Prev()->SetNext(node->Next());
@@ -191,8 +184,8 @@
}
}
-template <typename T, typename PointerType>
-inline T* DoublyLinkedList<T, PointerType>::RemoveHead() {
+template <typename T>
+inline T* DoublyLinkedList<T>::RemoveHead() {
T* node = Head();
if (node)
Remove(node);
