Attachment 60757 Details for Bug 41778 – Patch

[patch] Patch

bug-41778-20100707111316.patch (text/plain), 6.19 KB, created by Adam Barth on 2010-07-07 11:13:17 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Adam Barth

Created: 2010-07-07 11:13:17 PDT

Size: 6.19 KB

patch

obsolete

>Index: JavaScriptCore/ChangeLog
>===================================================================
>--- JavaScriptCore/ChangeLog	(revision 62683)
>+++ JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,16 @@
>+2010-07-07  Adam Barth  <abarth@webkit.org>
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        Add reverseFind to Vector and deploy in HTML5 parser
>+        https://bugs.webkit.org/show_bug.cgi?id=41778
>+
>+        This method seems generally useful.  I'm slightly surprised we don't
>+        have it already.
>+
>+        * wtf/Vector.h:
>+        (WTF::::reverseFind):
>+
> 2010-07-07  Darin Adler  <darin@apple.com>
> 
>         Reviewed by Adam Barth.
>Index: JavaScriptCore/wtf/Vector.h
>===================================================================
>--- JavaScriptCore/wtf/Vector.h	(revision 62679)
>+++ JavaScriptCore/wtf/Vector.h	(working copy)
>@@ -557,6 +557,7 @@ namespace WTF {
>         const T& last() const { return at(size() - 1); }
> 
>         template<typename U> size_t find(const U&) const;
>+        template<typename U> size_t reverseFind(const U&) const;
> 
>         void shrink(size_t size);
>         void grow(size_t size);
>@@ -744,6 +745,18 @@ namespace WTF {
>     }
> 
>     template<typename T, size_t inlineCapacity>
>+    template<typename U>
>+    size_t Vector<T, inlineCapacity>::reverseFind(const U& value) const
>+    {
>+        for (size_t i = 1; i <= size(); ++i) {
>+            const size_t index = size() - i;
>+            if (at(index) == value)
>+                return index;
>+        }
>+        return notFound;
>+    }
>+
>+    template<typename T, size_t inlineCapacity>
>     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
>     {
>         if (size() > newSize)
>Index: WebCore/ChangeLog
>===================================================================
>--- WebCore/ChangeLog	(revision 62683)
>+++ WebCore/ChangeLog	(working copy)
>@@ -1,3 +1,26 @@
>+2010-07-07  Adam Barth  <abarth@webkit.org>
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        Add reverseFind to Vector and deploy in HTML5 parser
>+        https://bugs.webkit.org/show_bug.cgi?id=41778
>+
>+        This patch moves reverseFind from begin an
>+        HTMLFormattingElementList-specific concept to begin a general Vector
>+        concept.  Also, instead of using Entry as the type for operator==, we
>+        now use elements directly.  The old code compiled because the Entry
>+        constructor wasn't explicit, which means we were churning refs on every
>+        comparison!
>+
>+        * html/HTMLFormattingElementList.cpp:
>+        (WebCore::HTMLFormattingElementList::find):
>+        (WebCore::HTMLFormattingElementList::bookmarkFor):
>+        (WebCore::HTMLFormattingElementList::insertAt):
>+        (WebCore::HTMLFormattingElementList::remove):
>+        * html/HTMLFormattingElementList.h:
>+        (WebCore::HTMLFormattingElementList::Entry::operator==):
>+        (WebCore::HTMLFormattingElementList::Entry::operator!=):
>+
> 2010-07-06  Simon Fraser  <simon.fraser@apple.com>
> 
>         Reviewed by Dan Bernstein.
>Index: WebCore/html/HTMLFormattingElementList.cpp
>===================================================================
>--- WebCore/html/HTMLFormattingElementList.cpp	(revision 62680)
>+++ WebCore/html/HTMLFormattingElementList.cpp	(working copy)
>@@ -58,7 +58,7 @@ bool HTMLFormattingElementList::contains
> 
> HTMLFormattingElementList::Entry* HTMLFormattingElementList::find(Element* element)
> {
>-    size_t index = findIndex(element);
>+    size_t index = m_entries.reverseFind(element);
>     if (index != notFound) {
>         // This is somewhat of a hack, and is why this method can't be const.
>         return &m_entries[index];
>@@ -68,7 +68,7 @@ HTMLFormattingElementList::Entry* HTMLFo
> 
> HTMLFormattingElementList::Bookmark HTMLFormattingElementList::bookmarkFor(Element* element)
> {
>-    size_t index = findIndex(element);
>+    size_t index = m_entries.reverseFind(element);
>     ASSERT(index != notFound);
>     Element* elementBefore = (index > 1) ? m_entries[index - 1].element() : 0;
>     Element* elementAfter = (index < m_entries.size() - 1) ? m_entries[index + 1].element() : 0;
>@@ -79,12 +79,12 @@ void HTMLFormattingElementList::insertAt
> {
>     size_t beforeIndex = notFound;
>     if (bookmark.elementBefore()) {
>-        beforeIndex = findIndex(bookmark.elementBefore());
>+        beforeIndex = m_entries.reverseFind(bookmark.elementBefore());
>         ASSERT(beforeIndex != notFound);
>     }
>     size_t afterIndex = notFound;
>     if (bookmark.elementAfter()) {
>-        afterIndex = findIndex(bookmark.elementAfter());
>+        afterIndex = m_entries.reverseFind(bookmark.elementAfter());
>         ASSERT(afterIndex != notFound);
>     }
> 
>@@ -109,7 +109,7 @@ void HTMLFormattingElementList::append(E
> 
> void HTMLFormattingElementList::remove(Element* element)
> {
>-    size_t index = findIndex(element);
>+    size_t index = m_entries.reverseFind(element);
>     if (index != notFound)
>         m_entries.remove(index);
> }
>Index: WebCore/html/HTMLFormattingElementList.h
>===================================================================
>--- WebCore/html/HTMLFormattingElementList.h	(revision 62681)
>+++ WebCore/html/HTMLFormattingElementList.h	(working copy)
>@@ -71,12 +71,10 @@ public:
>         void replaceElement(PassRefPtr<Element> element) { m_element = element; }
> 
>         // Needed for use with Vector.  These are super-hot and must be inline.
>-        bool operator==(const Entry& other) const { return m_element == other.m_element; }
>-        bool operator!=(const Entry& other) const { return m_element != other.m_element; }
>+        bool operator==(Element* element) const { return m_element == element; }
>+        bool operator!=(Element* element) const { return m_element != element; }
> 
>     private:
>-        friend class HTMLFormattingElementList;
>-
>         RefPtr<Element> m_element;
>     };
> 
>@@ -126,17 +124,6 @@ public:
> #endif
> 
> private:
>-    size_t findIndex(Element* element) const
>-    {
>-        ASSERT(element);
>-        // A reverse find is more efficient than Vector<T>::find
>-        for (size_t i = 1; i <= m_entries.size(); ++i) {
>-            size_t index = m_entries.size() - i;
>-            if (m_entries[index].m_element == element)
>-                return index;
>-        }
>-        return notFound;
>-    }
>     Vector<Entry> m_entries;
> };
>

Flags:

sam: review+
abarth: commit-queue+

Actions: View | Formatted Diff | Diff

Attachments on bug 41778: 60757