Changeset 90117 in webkit

Timestamp:

Jun 30, 2011 7:11:21 AM (13 years ago)

Author:

commit-queue@webkit.org

Message:

2011-06-30 Sheriff Bot <​webkit.review.bot@gmail.com>

Unreviewed, rolling out r90102.
​http://trac.webkit.org/changeset/90102
​https://bugs.webkit.org/show_bug.cgi?id=63714

Lots of tests asserting beneath
SVGSMILElement::findInstanceTime (Requested by aroben on
#webkit).

• wtf/StdLibExtras.h: (WTF::binarySearch):

2011-06-30 Sheriff Bot <​webkit.review.bot@gmail.com>

Unreviewed, rolling out r90102.
​http://trac.webkit.org/changeset/90102
​https://bugs.webkit.org/show_bug.cgi?id=63714

Lots of tests asserting beneath
SVGSMILElement::findInstanceTime (Requested by aroben on
#webkit).

• svg/animation/SVGSMILElement.cpp: (WebCore::SVGSMILElement::findInstanceTime):

Location:

trunk/Source

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/wtf/StdLibExtras.h (modified) (2 diffs)
• WebCore/ChangeLog (modified) (1 diff)
• WebCore/svg/animation/SVGSMILElement.cpp (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2011-06-30  Sheriff Bot  <webkit.review.bot@gmail.com>
+
+        Unreviewed, rolling out r90102.
+        http://trac.webkit.org/changeset/90102
+        https://bugs.webkit.org/show_bug.cgi?id=63714
+
+        Lots of tests asserting beneath
+        SVGSMILElement::findInstanceTime (Requested by aroben on
+        #webkit).
+
+        * wtf/StdLibExtras.h:
+        (WTF::binarySearch):
+
 2011-06-30  Oliver Varga  <Varga.Oliver@stud.u-szeged.hu>
 

trunk/Source/JavaScriptCore/wtf/StdLibExtras.h

@@ -124 +124 @@
 }
 
-enum BinarySearchMode {
-    KeyMustBePresentInArray,
-    KeyMustNotBePresentInArray
-};
-
 // Binary search algorithm, calls extractKey on pre-sorted elements in array,
 // compares result with key (KeyTypes should be comparable with '--', '<', '>').
+// Optimized for cases where the array contains the key, checked by assertions.
 template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)>
-inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
+inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key)
 {
-    // The array must contain at least one element (pre-condition, array does contain key).
-    // If the array contains only one element, no need to do the comparison.
+    // The array must contain at least one element (pre-condition, array does conatin key).
+    // If the array only contains one element, no need to do the comparison.
     while (size > 1) {
         // Pick an element to check, half way through the array, and read the value.
         int pos = (size - 1) >> 1;
         KeyType val = extractKey(&array[pos]);
-
+        
         // If the key matches, success!
         if (val == key)
@@ -154 +150 @@
         }
 
-        // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
-        if (mode == KeyMustBePresentInArray)
-            ASSERT(size);
+        // 'size' should never reach zero.
+        ASSERT(size);
     }
-
-    // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
-    // we've chopped down to one element, no need to check it matches
-    if (mode == KeyMustBePresentInArray) {
-        ASSERT(size == 1);
-        ASSERT(key == extractKey(&array[0]));
-    }
-
+    
+    // If we reach this point we've chopped down to one element, no need to check it matches
+    ASSERT(size == 1);
+    ASSERT(key == extractKey(&array[0]));
     return &array[0];
 }

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2011-06-30  Sheriff Bot  <webkit.review.bot@gmail.com>
+
+        Unreviewed, rolling out r90102.
+        http://trac.webkit.org/changeset/90102
+        https://bugs.webkit.org/show_bug.cgi?id=63714
+
+        Lots of tests asserting beneath
+        SVGSMILElement::findInstanceTime (Requested by aroben on
+        #webkit).
+
+        * svg/animation/SVGSMILElement.cpp:
+        (WebCore::SVGSMILElement::findInstanceTime):
+
 2011-06-30  Andrey Kosyakov  <caseq@chromium.org>
 

trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp

@@ -617 +617 @@
 }
     
-inline SMILTime extractTimeFromVector(const SMILTime* position)
-{
-    return *position;
-}
-
 SMILTime SVGSMILElement::findInstanceTime(BeginOrEnd beginOrEnd, SMILTime minimumTime, bool equalsMinimumOK) const
 {
+    // FIXME: This searches from the beginning which is inefficient. The list is usually not long
+    // (one entry in common cases) but you can construct a case where it does grow.
     const Vector<SMILTime>& list = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
-    int sizeOfList = list.size();
-
-    if (!sizeOfList)
-        return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
-
-    const SMILTime* result = binarySearch<const SMILTime, SMILTime, extractTimeFromVector>(list.begin(), sizeOfList, minimumTime, WTF::KeyMustNotBePresentInArray);
-    int indexOfResult = result - list.begin();
-
-    if (sizeOfList - 1 > indexOfResult && list[indexOfResult] < minimumTime)
-        ++indexOfResult;
-
-    ASSERT(indexOfResult < sizeOfList);
-
-    // "The special value "indefinite" does not yield an instance time in the begin list."
-    if (list[indexOfResult].isIndefinite() && beginOrEnd == Begin)
-        return SMILTime::unresolved();
-
-    if (list[indexOfResult] < minimumTime)
-        return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
-
-    // If the equals is NOT accepted, we have to find a bigger one.
-    if (list[indexOfResult] == minimumTime && !equalsMinimumOK) {
-        if (indexOfResult + 1 >= sizeOfList)
-            return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
-    }
-
-    while (list[indexOfResult] == list[indexOfResult + 1] && indexOfResult < sizeOfList - 1)
-        ++indexOfResult;
-
-    if (list[indexOfResult] > minimumTime)
-        return list[indexOfResult];
-    if (list[indexOfResult] == minimumTime) {
-        if (indexOfResult + 1 < sizeOfList - 1)
-            return list[indexOfResult + 1];
-        return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
-    }
-
-    return list[indexOfResult];
+    for (unsigned n = 0; n < list.size(); ++n) {
+        SMILTime time = list[n];
+        ASSERT(!time.isUnresolved());
+        if (time.isIndefinite() && beginOrEnd == Begin) {
+            // "The special value "indefinite" does not yield an instance time in the begin list."
+            continue;
+        }
+        if (equalsMinimumOK) {
+            if (time >= minimumTime)
+                return time;
+        } else if (time > minimumTime)
+            return time;
+    }
+    return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
 }