Modified: trunk/Source/_javascript_Core/ChangeLog (90811 => 90812)
--- trunk/Source/_javascript_Core/ChangeLog 2011-07-12 10:14:30 UTC (rev 90811)
+++ trunk/Source/_javascript_Core/ChangeLog 2011-07-12 12:39:52 UTC (rev 90812)
@@ -1,3 +1,15 @@
+2011-07-12 Adam Roben <[email protected]>
+
+ Unreviewed, rolling out r90811.
+ http://trac.webkit.org/changeset/90811
+ https://bugs.webkit.org/show_bug.cgi?id=61025
+
+ Several svg tests failing assertions beneath
+ SVGSMILElement::findInstanceTime
+
+ * wtf/StdLibExtras.h:
+ (WTF::binarySearch):
+
2011-07-12 Oliver Varga <[email protected]>
Reviewed by Nikolas Zimmermann.
Modified: trunk/Source/_javascript_Core/wtf/StdLibExtras.h (90811 => 90812)
--- trunk/Source/_javascript_Core/wtf/StdLibExtras.h 2011-07-12 10:14:30 UTC (rev 90811)
+++ trunk/Source/_javascript_Core/wtf/StdLibExtras.h 2011-07-12 12:39:52 UTC (rev 90812)
@@ -123,23 +123,19 @@
return (x + remainderMask) & ~remainderMask;
}
-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)
return &array[pos];
@@ -153,18 +149,13 @@
array += (pos + 1);
}
- // 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];
}
Modified: trunk/Source/WebCore/ChangeLog (90811 => 90812)
--- trunk/Source/WebCore/ChangeLog 2011-07-12 10:14:30 UTC (rev 90811)
+++ trunk/Source/WebCore/ChangeLog 2011-07-12 12:39:52 UTC (rev 90812)
@@ -1,3 +1,15 @@
+2011-07-12 Adam Roben <[email protected]>
+
+ Unreviewed, rolling out r90811.
+ http://trac.webkit.org/changeset/90811
+ https://bugs.webkit.org/show_bug.cgi?id=61025
+
+ Several svg tests failing assertions beneath
+ SVGSMILElement::findInstanceTime
+
+ * svg/animation/SVGSMILElement.cpp:
+ (WebCore::SVGSMILElement::findInstanceTime):
+
2011-07-12 Oliver Varga <[email protected]>
Reviewed by Nikolas Zimmermann.
Modified: trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp (90811 => 90812)
--- trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2011-07-12 10:14:30 UTC (rev 90811)
+++ trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2011-07-12 12:39:52 UTC (rev 90812)
@@ -616,54 +616,25 @@
endListChanged(eventTime);
}
-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();
+ 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;
}
-
- if (sizeOfList > 1) {
- 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];
+ return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
}
SMILTime SVGSMILElement::repeatingDuration() const
