Changeset 90812 in webkit
- Timestamp:
- Jul 12, 2011 5:39:52 AM (13 years ago)
- Location:
- trunk/Source
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/ChangeLog
r90811 r90812 1 2011-07-12 Adam Roben <aroben@apple.com> 2 3 Unreviewed, rolling out r90811. 4 http://trac.webkit.org/changeset/90811 5 https://bugs.webkit.org/show_bug.cgi?id=61025 6 7 Several svg tests failing assertions beneath 8 SVGSMILElement::findInstanceTime 9 10 * wtf/StdLibExtras.h: 11 (WTF::binarySearch): 12 1 13 2011-07-12 Oliver Varga <Varga.Oliver@stud.u-szeged.hu> 2 14 -
trunk/Source/JavaScriptCore/wtf/StdLibExtras.h
r90811 r90812 124 124 } 125 125 126 enum BinarySearchMode {127 KeyMustBePresentInArray,128 KeyMustNotBePresentInArray129 };130 131 126 // Binary search algorithm, calls extractKey on pre-sorted elements in array, 132 127 // compares result with key (KeyTypes should be comparable with '--', '<', '>'). 128 // Optimized for cases where the array contains the key, checked by assertions. 133 129 template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)> 134 inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key , BinarySearchMode mode = KeyMustBePresentInArray)130 inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key) 135 131 { 136 // The array must contain at least one element (pre-condition, array does con tain key).137 // If the array contains onlyone element, no need to do the comparison.132 // The array must contain at least one element (pre-condition, array does conatin key). 133 // If the array only contains one element, no need to do the comparison. 138 134 while (size > 1) { 139 135 // Pick an element to check, half way through the array, and read the value. 140 136 int pos = (size - 1) >> 1; 141 137 KeyType val = extractKey(&array[pos]); 142 138 143 139 // If the key matches, success! 144 140 if (val == key) … … 154 150 } 155 151 156 // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero. 157 if (mode == KeyMustBePresentInArray) 158 ASSERT(size); 152 // 'size' should never reach zero. 153 ASSERT(size); 159 154 } 160 161 // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point 162 // we've chopped down to one element, no need to check it matches 163 if (mode == KeyMustBePresentInArray) { 164 ASSERT(size == 1); 165 ASSERT(key == extractKey(&array[0])); 166 } 167 155 156 // If we reach this point we've chopped down to one element, no need to check it matches 157 ASSERT(size == 1); 158 ASSERT(key == extractKey(&array[0])); 168 159 return &array[0]; 169 160 } -
trunk/Source/WebCore/ChangeLog
r90811 r90812 1 2011-07-12 Adam Roben <aroben@apple.com> 2 3 Unreviewed, rolling out r90811. 4 http://trac.webkit.org/changeset/90811 5 https://bugs.webkit.org/show_bug.cgi?id=61025 6 7 Several svg tests failing assertions beneath 8 SVGSMILElement::findInstanceTime 9 10 * svg/animation/SVGSMILElement.cpp: 11 (WebCore::SVGSMILElement::findInstanceTime): 12 1 13 2011-07-12 Oliver Varga <Varga.Oliver@stud.u-szeged.hu> 2 14 -
trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp
r90811 r90812 617 617 } 618 618 619 inline SMILTime extractTimeFromVector(const SMILTime* position)620 {621 return *position;622 }623 624 619 SMILTime SVGSMILElement::findInstanceTime(BeginOrEnd beginOrEnd, SMILTime minimumTime, bool equalsMinimumOK) const 625 620 { 621 // FIXME: This searches from the beginning which is inefficient. The list is usually not long 622 // (one entry in common cases) but you can construct a case where it does grow. 626 623 const Vector<SMILTime>& list = beginOrEnd == Begin ? m_beginTimes : m_endTimes; 627 int sizeOfList = list.size(); 628 629 if (!sizeOfList) 630 return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite(); 631 632 const SMILTime* result = binarySearch<const SMILTime, SMILTime, extractTimeFromVector>(list.begin(), sizeOfList, minimumTime, WTF::KeyMustNotBePresentInArray); 633 int indexOfResult = result - list.begin(); 634 635 if (sizeOfList - 1 > indexOfResult && list[indexOfResult] < minimumTime) 636 ++indexOfResult; 637 638 ASSERT(indexOfResult < sizeOfList); 639 640 // "The special value "indefinite" does not yield an instance time in the begin list." 641 if (list[indexOfResult].isIndefinite() && beginOrEnd == Begin) 642 return SMILTime::unresolved(); 643 644 if (list[indexOfResult] < minimumTime) 645 return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite(); 646 647 // If the equals is NOT accepted, we have to find a bigger one. 648 if (list[indexOfResult] == minimumTime && !equalsMinimumOK) { 649 if (indexOfResult + 1 >= sizeOfList) 650 return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite(); 651 } 652 653 if (sizeOfList > 1) { 654 while (list[indexOfResult] == list[indexOfResult + 1] && indexOfResult < sizeOfList - 1) 655 ++indexOfResult; 656 } 657 658 if (list[indexOfResult] > minimumTime) 659 return list[indexOfResult]; 660 if (list[indexOfResult] == minimumTime) { 661 if (indexOfResult + 1 < sizeOfList - 1) 662 return list[indexOfResult + 1]; 663 return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite(); 664 } 665 666 return list[indexOfResult]; 624 for (unsigned n = 0; n < list.size(); ++n) { 625 SMILTime time = list[n]; 626 ASSERT(!time.isUnresolved()); 627 if (time.isIndefinite() && beginOrEnd == Begin) { 628 // "The special value "indefinite" does not yield an instance time in the begin list." 629 continue; 630 } 631 if (equalsMinimumOK) { 632 if (time >= minimumTime) 633 return time; 634 } else if (time > minimumTime) 635 return time; 636 } 637 return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite(); 667 638 } 668 639
Note: See TracChangeset
for help on using the changeset viewer.