Title: [195420] trunk/Source/WTF
Revision
195420
Author
fpi...@apple.com
Date
2016-01-21 13:37:56 -0800 (Thu, 21 Jan 2016)

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

Modified Paths

Diff

Modified: trunk/Source/WTF/ChangeLog (195419 => 195420)


--- trunk/Source/WTF/ChangeLog	2016-01-21 20:16:01 UTC (rev 195419)
+++ trunk/Source/WTF/ChangeLog	2016-01-21 21:37:56 UTC (rev 195420)
@@ -1,5 +1,26 @@
 2016-01-21  Filip Pizlo  <fpi...@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  <fpi...@apple.com>
+
         B3 should have load elimination
         https://bugs.webkit.org/show_bug.cgi?id=153288
 

Modified: trunk/Source/WTF/wtf/RangeSet.h (195419 => 195420)


--- trunk/Source/WTF/wtf/RangeSet.h	2016-01-21 20:16:01 UTC (rev 195419)
+++ trunk/Source/WTF/wtf/RangeSet.h	2016-01-21 21:37:56 UTC (rev 195420)
@@ -92,15 +92,8 @@
             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 @@
         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 @@
     {
         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;

Modified: trunk/Source/WTF/wtf/StdLibExtras.h (195419 => 195420)


--- trunk/Source/WTF/wtf/StdLibExtras.h	2016-01-21 20:16:01 UTC (rev 195419)
+++ trunk/Source/WTF/wtf/StdLibExtras.h	2016-01-21 21:37:56 UTC (rev 195420)
@@ -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 <par...@paroga.com>
  *
  * Redistribution and use in source and binary forms, with or without
@@ -212,7 +212,7 @@
         ASSERT(mode != KeyMustBePresentInArray || size);
     }
     
-    if (mode != KeyMustBePresentInArray && !size)
+    if (mode == KeyMightNotBePresentInArray && !size)
         return 0;
     
     ArrayElementType* result = &array[offset];
@@ -230,38 +230,38 @@
 
 // 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);
 }
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to