Changeset 90811 in webkit for trunk/Source/JavaScriptCore/wtf/StdLibExtras.h

Timestamp:

Jul 12, 2011, 3:14:30 AM (14 years ago)

Author:

[email protected]

Message:

Patch by Oliver Varga <​[email protected]> on 2011-07-12
Reviewed by Nikolas Zimmermann.

Speed up SVGSMILElement::findInstanceTime.
​https://bugs.webkit.org/show_bug.cgi?id=61025

Source/JavaScriptCore:

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):

File:

• trunk/Source/JavaScriptCore/wtf/StdLibExtras.h (modified) (2 diffs)

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)
+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)
@@ -150 +154 @@
         }
 
-        // '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];
 }