Fix <https://bugs.webkit.org/show_bug.cgi?id=24876>.
authormrowe@apple.com <mrowe@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 27 Mar 2009 21:34:03 +0000 (21:34 +0000)
committermrowe@apple.com <mrowe@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 27 Mar 2009 21:34:03 +0000 (21:34 +0000)
Bug 24876: fast/forms/select-max-length.html times out in debug builds due to HTMLSelectElement::setLength being O(N^2)

Reviewed by Sam Weinig.

* html/HTMLSelectElement.cpp:
(WebCore::HTMLSelectElement::setLength): Repeatedly calling remove to remove elements causes us to recalculate the list
items after each node is removed, leading to O(N^2) behaviour.  By inlining the batch removal in to setLength we can avoid
this gratuitous recalcuation.

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

WebCore/ChangeLog
WebCore/html/HTMLSelectElement.cpp

index 2a8e9b0..52d7fb8 100644 (file)
@@ -1,3 +1,15 @@
+2009-03-27  Mark Rowe  <mrowe@apple.com>
+
+        Reviewed by Sam Weinig.
+
+        Fix <https://bugs.webkit.org/show_bug.cgi?id=24876>.
+        Bug 24876: fast/forms/select-max-length.html times out in debug builds due to HTMLSelectElement::setLength being O(N^2)
+
+        * html/HTMLSelectElement.cpp:
+        (WebCore::HTMLSelectElement::setLength): Repeatedly calling remove to remove elements causes us to recalculate the list
+        items after each node is removed, leading to O(N^2) behaviour.  By inlining the batch removal in to setLength we can avoid
+        this gratuitous recalcuation.
+
 2009-03-27  Dirk Schulze  <krit@webkit.org>
 
         Reviewed by Eric Seidel.
index 78c80c2..541c359 100644 (file)
@@ -1064,10 +1064,18 @@ void HTMLSelectElement::setLength(unsigned newLen, ExceptionCode& ec)
             if (ec)
                 break;
         } while (++diff);
+    } else {
+        const Vector<HTMLElement*>& items = listItems();
+
+        size_t optionIndex = 0;
+        for (size_t listIndex = 0; listIndex < items.size(); listIndex++) {
+            if (items[listIndex]->hasLocalName(optionTag) && optionIndex++ >= newLen) {
+                Element *item = items[listIndex];
+                ASSERT(item->parentNode());
+                item->parentNode()->removeChild(item, ec);
+            }
+        }
     }
-    else // remove elements
-        while (diff-- > 0)
-            remove(newLen);
 }
 
 void HTMLSelectElement::scrollToSelection()