Title: [93039] trunk/Source
- Revision
- 93039
- Author
- r...@webkit.org
- Date
- 2011-08-15 04:59:22 -0700 (Mon, 15 Aug 2011)
Log Message
Patch by Oliver Varga <varga.oli...@stud.u-szeged.hu> on 2011-08-15
Reviewed by Nikolas Zimmermann.
Speed up SVGSMILElement::findInstanceTime.
https://bugs.webkit.org/show_bug.cgi?id=61025
Source/_javascript_Core:
Add a new parameter to StdlibExtras.h::binarySerarch function
to also handle cases when the array does not contain the key value.
This is needed for an svg function.
* wtf/StdLibExtras.h:
(WTF::binarySearch):
Source/WebCore:
Replace the linear search to binary search on ordered list because
the previous searches from the beginning was not efficient.
Out of index error fixed by Renata Hodovan.
No new tests this is only a performance tweak.
* svg/animation/SVGSMILElement.cpp:
(WebCore::extractTimeFromVector):
(WebCore::SVGSMILElement::findInstanceTime):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (93038 => 93039)
--- trunk/Source/_javascript_Core/ChangeLog 2011-08-15 11:02:10 UTC (rev 93038)
+++ trunk/Source/_javascript_Core/ChangeLog 2011-08-15 11:59:22 UTC (rev 93039)
@@ -1,3 +1,17 @@
+2011-08-15 Oliver Varga <varga.oli...@stud.u-szeged.hu>
+
+ Reviewed by Nikolas Zimmermann.
+
+ Speed up SVGSMILElement::findInstanceTime.
+ https://bugs.webkit.org/show_bug.cgi?id=61025
+
+ Add a new parameter to StdlibExtras.h::binarySerarch function
+ to also handle cases when the array does not contain the key value.
+ This is needed for an svg function.
+
+ * wtf/StdLibExtras.h:
+ (WTF::binarySearch):
+
2011-08-13 Sam Weinig <s...@webkit.org>
Add back 0xbbadbeef to CRASH to allow for old habits
Modified: trunk/Source/_javascript_Core/wtf/StdLibExtras.h (93038 => 93039)
--- trunk/Source/_javascript_Core/wtf/StdLibExtras.h 2011-08-15 11:02:10 UTC (rev 93038)
+++ trunk/Source/_javascript_Core/wtf/StdLibExtras.h 2011-08-15 11:59:22 UTC (rev 93039)
@@ -123,19 +123,23 @@
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)
+inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
{
- // 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.
+ // 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.
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];
@@ -149,13 +153,18 @@
array += (pos + 1);
}
- // 'size' should never reach zero.
- ASSERT(size);
+ // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
+ if (mode == KeyMustBePresentInArray)
+ ASSERT(size);
}
-
- // 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]));
+
+ // 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]));
+ }
+
return &array[0];
}
Modified: trunk/Source/WebCore/ChangeLog (93038 => 93039)
--- trunk/Source/WebCore/ChangeLog 2011-08-15 11:02:10 UTC (rev 93038)
+++ trunk/Source/WebCore/ChangeLog 2011-08-15 11:59:22 UTC (rev 93039)
@@ -1,3 +1,20 @@
+2011-08-15 Oliver Varga <varga.oli...@stud.u-szeged.hu>
+
+ Reviewed by Nikolas Zimmermann.
+
+ Speed up SVGSMILElement::findInstanceTime.
+ https://bugs.webkit.org/show_bug.cgi?id=61025
+
+ Replace the linear search to binary search on ordered list because
+ the previous searches from the beginning was not efficient.
+ Out of index error fixed by Renata Hodovan.
+
+ No new tests this is only a performance tweak.
+
+ * svg/animation/SVGSMILElement.cpp:
+ (WebCore::extractTimeFromVector):
+ (WebCore::SVGSMILElement::findInstanceTime):
+
2011-08-15 Hayato Ito <hay...@chromium.org>
Implement proper handling of focusin/focusout events in regard to shadow DOM boundaries.
Modified: trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp (93038 => 93039)
--- trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2011-08-15 11:02:10 UTC (rev 93038)
+++ trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2011-08-15 11:59:22 UTC (rev 93039)
@@ -616,25 +616,52 @@
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;
- 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;
+ 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();
}
- return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
+
+ while (indexOfResult < sizeOfList - 1 && list[indexOfResult] == list[indexOfResult + 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];
}
SMILTime SVGSMILElement::repeatingDuration() const
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
http://lists.webkit.org/mailman/listinfo.cgi/webkit-changes
