<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[195420] trunk/Source/WTF</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/195420">195420</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-01-21 13:37:56 -0800 (Thu, 21 Jan 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>REGRESSION(<a href="http://trac.webkit.org/projects/webkit/changeset/195417">r195417</a>): 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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfRangeSeth">trunk/Source/WTF/wtf/RangeSet.h</a></li>
<li><a href="#trunkSourceWTFwtfStdLibExtrash">trunk/Source/WTF/wtf/StdLibExtras.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (195419 => 195420)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,5 +1,26 @@
</span><span class="cx"> 2016-01-21 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ 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>
+
</ins><span class="cx"> B3 should have load elimination
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=153288
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFwtfRangeSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/RangeSet.h (195419 => 195420)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -92,15 +92,8 @@
</span><span class="cx"> return false;
</span><span class="cx">
</span><span class="cx"> unsigned index = findRange(range);
</span><del>- 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;
</del><ins>+ if (index != UINT_MAX)
+ return subsumesNonEmpty(m_ranges[index], range);
</ins><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -109,17 +102,7 @@
</span><span class="cx"> if (range.begin() == range.end())
</span><span class="cx"> return false;
</span><span class="cx">
</span><del>- 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;
</del><ins>+ return findRange(range) != UINT_MAX;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void clear()
</span><span class="lines">@@ -191,14 +174,13 @@
</span><span class="cx"> {
</span><span class="cx"> const_cast<RangeSet*>(this)->compact();
</span><span class="cx">
</span><del>- 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();
</del><ins>+ // 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;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Vector<Range, 8> m_ranges;
</span></span></pre></div>
<a id="trunkSourceWTFwtfStdLibExtrash"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/StdLibExtras.h (195419 => 195420)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
</del><ins>+ * Copyright (C) 2008 Apple Inc. All Rights Reserved.
</ins><span class="cx"> * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
</span><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="lines">@@ -212,7 +212,7 @@
</span><span class="cx"> ASSERT(mode != KeyMustBePresentInArray || size);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- if (mode != KeyMustBePresentInArray && !size)
</del><ins>+ if (mode == KeyMightNotBePresentInArray && !size)
</ins><span class="cx"> return 0;
</span><span class="cx">
</span><span class="cx"> ArrayElementType* result = &array[offset];
</span><span class="lines">@@ -230,38 +230,38 @@
</span><span class="cx">
</span><span class="cx"> // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Return zero if the element is not found.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Return the element that is either to the left, or the right, of where the element would have been found.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Variants of the above that use const.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
</span><span class="cx"> }
</span></span></pre>
</div>
</div>
</body>
</html>