REGRESSION(r195417): many tests crash
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jan 2016 21:37:56 +0000 (21:37 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jan 2016 21:37:56 +0000 (21:37 +0000)
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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@195420 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/RangeSet.h
Source/WTF/wtf/StdLibExtras.h

index a4d986d..e85433b 100644 (file)
@@ -1,5 +1,26 @@
 2016-01-21  Filip Pizlo  <fpizlo@apple.com>
 
+        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):
+
+2016-01-21  Filip Pizlo  <fpizlo@apple.com>
+
         B3 should have load elimination
         https://bugs.webkit.org/show_bug.cgi?id=153288
 
index 56ecf4b..75471ad 100644 (file)
@@ -92,15 +92,8 @@ public:
             return false;
         
         unsigned index = findRange(range);
-        if (index + 1 < m_ranges.size()
-            && subsumesNonEmpty(m_ranges[index + 1], range))
-            return true;
-        if (index < m_ranges.size()
-            && subsumesNonEmpty(m_ranges[index], range))
-            return true;
-        if (static_cast<unsigned>(index - 1) < m_ranges.size()
-            && subsumesNonEmpty(m_ranges[index - 1], range))
-            return true;
+        if (index != UINT_MAX)
+            return subsumesNonEmpty(m_ranges[index], range);
         return false;
     }
 
@@ -109,17 +102,7 @@ public:
         if (range.begin() == range.end())
             return false;
         
-        unsigned index = findRange(range);
-        if (index + 1 < m_ranges.size()
-            && overlapsNonEmpty(m_ranges[index + 1], range))
-            return true;
-        if (index < m_ranges.size()
-            && overlapsNonEmpty(m_ranges[index], range))
-            return true;
-        if (static_cast<unsigned>(index - 1) < m_ranges.size()
-            && overlapsNonEmpty(m_ranges[index - 1], range))
-            return true;
-        return false;
+        return findRange(range) != UINT_MAX;
     }
 
     void clear()
@@ -191,14 +174,13 @@ private:
     {
         const_cast<RangeSet*>(this)->compact();
 
-        const Range* found = approximateBinarySearch<const Range, Type>(
-            m_ranges, m_ranges.size(), range.begin(), [&] (const Range* range) -> Type {
-                return range->begin();
-            });
-        if (!found)
-            return UINT_MAX;
-
-        return found - m_ranges.begin();
+        // FIXME: Once we start using this in anger, we will want this to be a binary search.
+        for (unsigned i = 0; i < m_ranges.size(); ++i) {
+            if (overlapsNonEmpty(m_ranges[i], range))
+                return i;
+        }
+        
+        return UINT_MAX;
     }
     
     Vector<Range, 8> m_ranges;
index 861b804..d872097 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
+ * Copyright (C) 2008 Apple Inc. All Rights Reserved.
  * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
  *
  * Redistribution and use in source and binary forms, with or without
@@ -212,7 +212,7 @@ inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType
         ASSERT(mode != KeyMustBePresentInArray || size);
     }
     
-    if (mode != KeyMustBePresentInArray && !size)
+    if (mode == KeyMightNotBePresentInArray && !size)
         return 0;
     
     ArrayElementType* result = &array[offset];
@@ -230,38 +230,38 @@ inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType
 
 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 {
     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
 }
 
 // Return zero if the element is not found.
 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 {
     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
 }
 
 // Return the element that is either to the left, or the right, of where the element would have been found.
 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 {
     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
 }
 
 // Variants of the above that use const.
 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 {
     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
 }
 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 {
     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
 }
 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 {
     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
 }