⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 195420 in webkit


Ignore:
Timestamp:
Jan 21, 2016, 1:37:56 PM (11 years ago)
Author:
fpizlo@apple.com
Message:

REGRESSION(r195417): many tests crash
​https://bugs.webkit.org/show_bug.cgi?id=153316

Reviewed by Saam Barati.

This rolls out the StdLibExtras.h change, and simplifies RangeSet to not use binary search.
That's fine for now, since B3 doesn't stress RangeSet enough right now.

  • wtf/RangeSet.h:

(WTF::RangeSet::contains):
(WTF::RangeSet::overlaps):
(WTF::RangeSet::clear):
(WTF::RangeSet::findRange):

  • wtf/StdLibExtras.h:

(WTF::binarySearchImpl):
(WTF::binarySearch):
(WTF::tryBinarySearch):
(WTF::approximateBinarySearch):

Location:
trunk/Source/WTF
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r195417 r195420  
     12016-01-21  Filip Pizlo  <fpizlo@apple.com>
     2
     3        REGRESSION(r195417): many tests crash
     4        https://bugs.webkit.org/show_bug.cgi?id=153316
     5
     6        Reviewed by Saam Barati.
     7
     8        This rolls out the StdLibExtras.h change, and simplifies RangeSet to not use binary search.
     9        That's fine for now, since B3 doesn't stress RangeSet enough right now.
     10
     11        * wtf/RangeSet.h:
     12        (WTF::RangeSet::contains):
     13        (WTF::RangeSet::overlaps):
     14        (WTF::RangeSet::clear):
     15        (WTF::RangeSet::findRange):
     16        * wtf/StdLibExtras.h:
     17        (WTF::binarySearchImpl):
     18        (WTF::binarySearch):
     19        (WTF::tryBinarySearch):
     20        (WTF::approximateBinarySearch):
     21
    1222016-01-21  Filip Pizlo  <fpizlo@apple.com>
    223

  • trunk/Source/WTF/wtf/RangeSet.h

    r195417 r195420  
    9393       
    9494        unsigned index = findRange(range);
    95         if (index + 1 < m_ranges.size()
    96             && subsumesNonEmpty(m_ranges[index + 1], range))
    97             return true;
    98         if (index < m_ranges.size()
    99             && subsumesNonEmpty(m_ranges[index], range))
    100             return true;
    101         if (static_cast<unsigned>(index - 1) < m_ranges.size()
    102             && subsumesNonEmpty(m_ranges[index - 1], range))
    103             return true;
     95        if (index != UINT_MAX)
     96            return subsumesNonEmpty(m_ranges[index], range);
    10497        return false;
    10598    }
    … …  
    110103            return false;
    111104       
    112         unsigned index = findRange(range);
    113         if (index + 1 < m_ranges.size()
    114             && overlapsNonEmpty(m_ranges[index + 1], range))
    115             return true;
    116         if (index < m_ranges.size()
    117             && overlapsNonEmpty(m_ranges[index], range))
    118             return true;
    119         if (static_cast<unsigned>(index - 1) < m_ranges.size()
    120             && overlapsNonEmpty(m_ranges[index - 1], range))
    121             return true;
    122         return false;
     105        return findRange(range) != UINT_MAX;
    123106    }
    124107
    … …  
    192175        const_cast<RangeSet*>(this)->compact();
    193176
    194         const Range* found = approximateBinarySearch<const Range, Type>(
    195             m_ranges, m_ranges.size(), range.begin(), [&] (const Range* range) -> Type {
    196                 return range->begin();
    197             });
    198         if (!found)
    199             return UINT_MAX;
    200 
    201         return found - m_ranges.begin();
     177        // FIXME: Once we start using this in anger, we will want this to be a binary search.
     178        for (unsigned i = 0; i < m_ranges.size(); ++i) {
     179            if (overlapsNonEmpty(m_ranges[i], range))
     180                return i;
     181        }
     182       
     183        return UINT_MAX;
    202184    }
    203185   

  • trunk/Source/WTF/wtf/StdLibExtras.h

    r195417 r195420  
    11/*
    2  * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
     2 * Copyright (C) 2008 Apple Inc. All Rights Reserved.
    33 * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
    44 *
    … …  
    213213    }
    214214   
    215     if (mode != KeyMustBePresentInArray && !size)
     215    if (mode == KeyMightNotBePresentInArray && !size)
    216216        return 0;
    217217   
    … …  
    231231// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
    232232template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    233 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
     233inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
    234234{
    235235    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
    … …  
    238238// Return zero if the element is not found.
    239239template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    240 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
     240inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
    241241{
    242242    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
    … …  
    245245// Return the element that is either to the left, or the right, of where the element would have been found.
    246246template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    247 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
     247inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
    248248{
    249249    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
    … …  
    252252// Variants of the above that use const.
    253253template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    254 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
     254inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
    255255{
    256256    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
    257257}
    258258template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    259 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
     259inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
    260260{
    261261    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
    262262}
    263263template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
    264 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
     264inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
    265265{
    266266    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
Note: See TracChangeset for help on using the changeset viewer.