<!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>[215135] trunk</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/215135">215135</a></dd>
<dt>Author</dt> <dd>keith_miller@apple.com</dd>
<dt>Date</dt> <dd>2017-04-07 18:15:09 -0700 (Fri, 07 Apr 2017)</dd>
</dl>
<h3>Log Message</h3>
<pre>Add a PriorityQueue class
https://bugs.webkit.org/show_bug.cgi?id=170579
Reviewed by Saam Barati.
Source/JavaScriptCore:
Update Wasm::Worklist to use WTF::PriorityQueue.
* wasm/WasmWorklist.cpp:
(JSC::Wasm::Worklist::enqueue):
(JSC::Wasm::Worklist::completePlanSynchronously):
(JSC::Wasm::Worklist::stopAllPlansForVM):
(JSC::Wasm::Worklist::~Worklist):
(JSC::Wasm::Worklist::iterate): Deleted.
* wasm/WasmWorklist.h:
(JSC::Wasm::Worklist::isHigherPriority):
(JSC::Wasm::Worklist::Comparator::operator()): Deleted.
Source/WTF:
This patch adds a new PriorityQueue class that is backed by
WTF::Vector. It also has a number of other niceties such as being
able to iterate the queue and increase or decrease keys.
One note is that increaseKey and decreaseKey are O(n) rather than
O(log(n)). Traditionally, the lookup of the key is done with a
hash map but that's not feasible here. This is because unless the
queue's element type is a pointer there is no good way maintain a
persistent reference to every entry in the queue while we sift.
The only way to update the location of an entry is to do a hash
table lookup with the entry's hash but this is probably more
expensive than just doing a linear search.
Also, add comparison operator functions, which can be passed to PriorityQueue.
* WTF.xcodeproj/project.pbxproj:
* wtf/MathExtras.h:
(isLessThan):
(isLessThanEqual):
(isGreaterThan):
(isGreaterThanEqual):
* wtf/PriorityQueue.h: Added.
(WTF::PriorityQueue::size):
(WTF::PriorityQueue::isEmpty):
(WTF::PriorityQueue::enqueue):
(WTF::PriorityQueue::peek):
(WTF::PriorityQueue::dequeue):
(WTF::PriorityQueue::decreaseKey):
(WTF::PriorityQueue::increaseKey):
(WTF::PriorityQueue::begin):
(WTF::PriorityQueue::end):
(WTF::PriorityQueue::isValidHeap):
(WTF::PriorityQueue::parentOf):
(WTF::PriorityQueue::leftChildOf):
(WTF::PriorityQueue::rightChildOf):
(WTF::PriorityQueue::siftUp):
(WTF::PriorityQueue::siftDown):
Tools:
* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WTF/PriorityQueue.cpp: Added.
(operator _z ):
(enqueue):
(dequeue):
(TEST):
(compareMove):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCorewasmWasmWorklistcpp">trunk/Source/JavaScriptCore/wasm/WasmWorklist.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorewasmWasmWorklisth">trunk/Source/JavaScriptCore/wasm/WasmWorklist.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfMathExtrash">trunk/Source/WTF/wtf/MathExtras.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj">trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfPriorityQueueh">trunk/Source/WTF/wtf/PriorityQueue.h</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWTFPriorityQueuecpp">trunk/Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/JavaScriptCore/ChangeLog 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -1,3 +1,22 @@
</span><ins>+2017-04-07 Keith Miller <keith_miller@apple.com>
+
+ Add a PriorityQueue class
+ https://bugs.webkit.org/show_bug.cgi?id=170579
+
+ Reviewed by Saam Barati.
+
+ Update Wasm::Worklist to use WTF::PriorityQueue.
+
+ * wasm/WasmWorklist.cpp:
+ (JSC::Wasm::Worklist::enqueue):
+ (JSC::Wasm::Worklist::completePlanSynchronously):
+ (JSC::Wasm::Worklist::stopAllPlansForVM):
+ (JSC::Wasm::Worklist::~Worklist):
+ (JSC::Wasm::Worklist::iterate): Deleted.
+ * wasm/WasmWorklist.h:
+ (JSC::Wasm::Worklist::isHigherPriority):
+ (JSC::Wasm::Worklist::Comparator::operator()): Deleted.
+
</ins><span class="cx"> 2017-04-07 Yuichiro Kikura <y.kikura@gmail.com>
</span><span class="cx">
</span><span class="cx"> WebGPU: implement ComputeCommandEncoder and related components
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorewasmWasmWorklistcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/wasm/WasmWorklist.cpp (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/wasm/WasmWorklist.cpp 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/JavaScriptCore/wasm/WasmWorklist.cpp 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -67,16 +67,15 @@
</span><span class="cx"> auto& queue = worklist.m_queue;
</span><span class="cx"> synchronize.notifyAll();
</span><span class="cx">
</span><del>- while (!queue.empty()) {
-
- Priority priority = queue.top().priority;
</del><ins>+ while (!queue.isEmpty()) {
+ Priority priority = queue.peek().priority;
</ins><span class="cx"> if (priority == Worklist::Priority::Shutdown)
</span><span class="cx"> return PollResult::Stop;
</span><span class="cx">
</span><del>- element = queue.top();
</del><ins>+ element = queue.peek();
</ins><span class="cx"> // Only one thread should validate/prepare.
</span><del>- if (!queue.top().plan->hasBeenPrepared()) {
- queue.pop();
</del><ins>+ if (!queue.peek().plan->hasBeenPrepared()) {
+ queue.dequeue();
</ins><span class="cx"> return PollResult::Work;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -84,7 +83,7 @@
</span><span class="cx"> return PollResult::Work;
</span><span class="cx">
</span><span class="cx"> // There must be a another thread linking this plan so we can deque and see if there is other work.
</span><del>- queue.pop();
</del><ins>+ queue.dequeue();
</ins><span class="cx"> element = QueueElement();
</span><span class="cx"> }
</span><span class="cx"> return PollResult::Wait;
</span><span class="lines">@@ -92,7 +91,9 @@
</span><span class="cx">
</span><span class="cx"> WorkResult work() override
</span><span class="cx"> {
</span><del>- auto complete = [&] () {
</del><ins>+ auto complete = [&] (const AbstractLocker&) {
+ // We need to hold the lock to release our plan otherwise the main thread, while canceling plans
+ // might use after free the plan we are looking at
</ins><span class="cx"> element = QueueElement();
</span><span class="cx"> return WorkResult::Continue;
</span><span class="cx"> };
</span><span class="lines">@@ -102,29 +103,19 @@
</span><span class="cx"> if (!plan->hasBeenPrepared()) {
</span><span class="cx"> plan->parseAndValidateModule();
</span><span class="cx"> if (!plan->hasWork())
</span><del>- return complete();
</del><ins>+ return complete(holdLock(*worklist.m_lock));
</ins><span class="cx">
</span><span class="cx"> plan->prepare();
</span><span class="cx">
</span><span class="cx"> LockHolder locker(*worklist.m_lock);
</span><span class="cx"> element.setToNextPriority();
</span><del>- worklist.m_queue.push(element);
</del><ins>+ worklist.m_queue.enqueue(WTFMove(element));
</ins><span class="cx"> worklist.m_planEnqueued->notifyAll(locker);
</span><ins>+ return complete(locker);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // FIXME: this should check in occasionally to see if there are new, higher priority e.g. synchronous, plans that need to be run.
- // https://bugs.webkit.org/show_bug.cgi?id=170204
</del><span class="cx"> plan->compileFunctions(Plan::Partial);
</span><del>-
- if (!plan->hasWork()) {
- LockHolder locker(*worklist.m_lock);
- auto queue = worklist.m_queue;
- // Another thread may have removed our plan from the queue already.
- if (!queue.empty() && queue.top().plan == element.plan)
- queue.pop();
- }
-
- return complete();
</del><ins>+ return complete(holdLock(*worklist.m_lock));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> public:
</span><span class="lines">@@ -148,47 +139,17 @@
</span><span class="cx"> RELEASE_ASSERT_NOT_REACHED();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-enum class IterateResult { UpdateAndBreak, DropAndContinue, Continue };
-
-template<typename Functor>
-void Worklist::iterate(const AbstractLocker&, const Functor& func)
-{
- // std::priority_queue does not have an iterator or decrease_key... :( While this is gross, this function
- // shouldn't be called very often and the queue should be small.
- // FIXME: we should have our own PriorityQueue that doesn't suck.
- // https://bugs.webkit.org/show_bug.cgi?id=170145
- std::vector<QueueElement> elements;
- while (!m_queue.empty()) {
- QueueElement element = m_queue.top();
- m_queue.pop();
- IterateResult result = func(element);
- if (result == IterateResult::UpdateAndBreak) {
- elements.push_back(element);
- break;
- }
-
- if (result == IterateResult::Continue)
- elements.push_back(element);
- continue;
- }
-
- for (auto element : elements)
- m_queue.push(element);
-}
-
</del><span class="cx"> void Worklist::enqueue(Ref<Plan> plan)
</span><span class="cx"> {
</span><span class="cx"> LockHolder locker(*m_lock);
</span><span class="cx">
</span><span class="cx"> if (!ASSERT_DISABLED) {
</span><del>- iterate(locker, [&] (QueueElement& element) {
</del><ins>+ for (const auto& element : m_queue)
</ins><span class="cx"> ASSERT_UNUSED(element, element.plan.get() != &plan.get());
</span><del>- return IterateResult::Continue;
- });
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> dataLogLnIf(verbose, "Enqueuing plan");
</span><del>- m_queue.push({ Priority::Preparation, nextTicket(), WTFMove(plan) });
</del><ins>+ m_queue.enqueue({ Priority::Preparation, nextTicket(), WTFMove(plan) });
</ins><span class="cx"> m_planEnqueued->notifyOne(locker);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -196,12 +157,12 @@
</span><span class="cx"> {
</span><span class="cx"> {
</span><span class="cx"> LockHolder locker(*m_lock);
</span><del>- iterate(locker, [&] (QueueElement& element) {
</del><ins>+ m_queue.decreaseKey([&] (QueueElement& element) {
</ins><span class="cx"> if (element.plan == &plan) {
</span><span class="cx"> element.priority = Priority::Synchronous;
</span><del>- return IterateResult::UpdateAndBreak;
</del><ins>+ return true;
</ins><span class="cx"> }
</span><del>- return IterateResult::Continue;
</del><ins>+ return false;
</ins><span class="cx"> });
</span><span class="cx">
</span><span class="cx"> for (auto& thread : m_threads) {
</span><span class="lines">@@ -216,18 +177,22 @@
</span><span class="cx"> void Worklist::stopAllPlansForVM(VM& vm)
</span><span class="cx"> {
</span><span class="cx"> LockHolder locker(*m_lock);
</span><del>- iterate(locker, [&] (QueueElement& element) {
</del><ins>+ Vector<QueueElement> elements;
+ while (!m_queue.isEmpty()) {
+ QueueElement element = m_queue.dequeue();
</ins><span class="cx"> bool didCancel = element.plan->tryRemoveVMAndCancelIfLast(vm);
</span><del>- if (didCancel)
- return IterateResult::DropAndContinue;
- return IterateResult::Continue;
- });
</del><ins>+ if (!didCancel)
+ elements.append(WTFMove(element));
+ }
</ins><span class="cx">
</span><ins>+ for (auto& element : elements)
+ m_queue.enqueue(WTFMove(element));
+
</ins><span class="cx"> for (auto& thread : m_threads) {
</span><span class="cx"> if (thread->element.plan) {
</span><span class="cx"> bool didCancel = thread->element.plan->tryRemoveVMAndCancelIfLast(vm);
</span><span class="cx"> if (didCancel) {
</span><del>- // We don't have to worry about the deadlocking since the thread can't block without clearing the plan and must hold the lock to do so.
</del><ins>+ // We don't have to worry about the deadlocking since the thread can't block without checking for a new plan and must hold the lock to do so.
</ins><span class="cx"> thread->synchronize.wait(*m_lock);
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -249,7 +214,7 @@
</span><span class="cx"> {
</span><span class="cx"> {
</span><span class="cx"> LockHolder locker(*m_lock);
</span><del>- m_queue.push({ Priority::Shutdown, nextTicket(), nullptr });
</del><ins>+ m_queue.enqueue({ Priority::Shutdown, nextTicket(), nullptr });
</ins><span class="cx"> m_planEnqueued->notifyAll(locker);
</span><span class="cx"> }
</span><span class="cx"> for (unsigned i = 0; i < m_threads.size(); ++i)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorewasmWasmWorklisth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/wasm/WasmWorklist.h (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/wasm/WasmWorklist.h 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/JavaScriptCore/wasm/WasmWorklist.h 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -32,6 +32,7 @@
</span><span class="cx"> #include <queue>
</span><span class="cx">
</span><span class="cx"> #include <wtf/AutomaticThread.h>
</span><ins>+#include <wtf/PriorityQueue.h>
</ins><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="lines">@@ -79,17 +80,13 @@
</span><span class="cx"> void setToNextPriority();
</span><span class="cx"> };
</span><span class="cx">
</span><del>- struct Comparator {
- bool operator()(const QueueElement& left, const QueueElement& right) const
- {
- if (left.priority == right.priority)
- return left.ticket > right.ticket;
- return left.priority > right.priority;
- }
- };
</del><ins>+ static bool isHigherPriority(const QueueElement& left, const QueueElement& right)
+ {
+ if (left.priority == right.priority)
+ return left.ticket > right.ticket;
+ return left.priority > right.priority;
+ }
</ins><span class="cx">
</span><del>- template<typename Functor>
- void iterate(const AbstractLocker&, const Functor&);
</del><span class="cx">
</span><span class="cx"> Box<Lock> m_lock;
</span><span class="cx"> RefPtr<AutomaticThreadCondition> m_planEnqueued;
</span><span class="lines">@@ -96,9 +93,7 @@
</span><span class="cx"> // Technically, this could overflow but that's unlikely. Even if it did, we will just compile things of the same
</span><span class="cx"> // Priority it the wrong order, which isn't wrong, just suboptimal.
</span><span class="cx"> Ticket m_lastGrantedTicket { 0 };
</span><del>- // FIXME: This should use WTF::Vector but WTF::Vector does not support random access iterator.
- std::priority_queue<QueueElement, std::vector<QueueElement>, Comparator> m_queue;
- HashMap<JSPromiseDeferred*, Plan*> m_activePlans;
</del><ins>+ PriorityQueue<QueueElement, isHigherPriority, 10> m_queue;
</ins><span class="cx"> Vector<std::unique_ptr<Thread>> m_threads;
</span><span class="cx"> };
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/WTF/ChangeLog 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -1,3 +1,48 @@
</span><ins>+2017-04-07 Keith Miller <keith_miller@apple.com>
+
+ Add a PriorityQueue class
+ https://bugs.webkit.org/show_bug.cgi?id=170579
+
+ Reviewed by Saam Barati.
+
+ This patch adds a new PriorityQueue class that is backed by
+ WTF::Vector. It also has a number of other niceties such as being
+ able to iterate the queue and increase or decrease keys.
+
+ One note is that increaseKey and decreaseKey are O(n) rather than
+ O(log(n)). Traditionally, the lookup of the key is done with a
+ hash map but that's not feasible here. This is because unless the
+ queue's element type is a pointer there is no good way maintain a
+ persistent reference to every entry in the queue while we sift.
+ The only way to update the location of an entry is to do a hash
+ table lookup with the entry's hash but this is probably more
+ expensive than just doing a linear search.
+
+ Also, add comparison operator functions, which can be passed to PriorityQueue.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/MathExtras.h:
+ (isLessThan):
+ (isLessThanEqual):
+ (isGreaterThan):
+ (isGreaterThanEqual):
+ * wtf/PriorityQueue.h: Added.
+ (WTF::PriorityQueue::size):
+ (WTF::PriorityQueue::isEmpty):
+ (WTF::PriorityQueue::enqueue):
+ (WTF::PriorityQueue::peek):
+ (WTF::PriorityQueue::dequeue):
+ (WTF::PriorityQueue::decreaseKey):
+ (WTF::PriorityQueue::increaseKey):
+ (WTF::PriorityQueue::begin):
+ (WTF::PriorityQueue::end):
+ (WTF::PriorityQueue::isValidHeap):
+ (WTF::PriorityQueue::parentOf):
+ (WTF::PriorityQueue::leftChildOf):
+ (WTF::PriorityQueue::rightChildOf):
+ (WTF::PriorityQueue::siftUp):
+ (WTF::PriorityQueue::siftDown):
+
</ins><span class="cx"> 2017-04-07 Alex Christensen <achristensen@webkit.org>
</span><span class="cx">
</span><span class="cx"> Use audit_token_t instead of pid_t for checking sandbox of other processes
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -149,6 +149,7 @@
</span><span class="cx"> 515F79561CFD3A6900CCED93 /* CrossThreadQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 515F79551CFD3A6900CCED93 /* CrossThreadQueue.h */; };
</span><span class="cx"> 52183012C99E476A84EEBEA8 /* SymbolImpl.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F72BBDB107FA424886178B9E /* SymbolImpl.cpp */; };
</span><span class="cx"> 539EB0631D55284200C82EF7 /* LEBDecoder.h in Headers */ = {isa = PBXBuildFile; fileRef = 539EB0621D55284200C82EF7 /* LEBDecoder.h */; };
</span><ins>+ 53EC253E1E95AD30000831B9 /* PriorityQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 53EC253C1E95AD30000831B9 /* PriorityQueue.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 553071CA1C40427200384898 /* TinyLRUCache.h in Headers */ = {isa = PBXBuildFile; fileRef = 553071C91C40427200384898 /* TinyLRUCache.h */; };
</span><span class="cx"> 5597F82F1D94B9970066BC21 /* SynchronizedFixedQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 5597F82C1D94B9970066BC21 /* SynchronizedFixedQueue.h */; };
</span><span class="cx"> 5C7C88D41D0A3A0A009D2F6D /* UniqueRef.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C7C88D31D0A3A0A009D2F6D /* UniqueRef.h */; };
</span><span class="lines">@@ -178,6 +179,7 @@
</span><span class="cx"> 974CFC8E16A4F327006D5404 /* WeakPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = 974CFC8D16A4F327006D5404 /* WeakPtr.h */; };
</span><span class="cx"> 9BC70F05176C379D00101DEC /* AtomicStringTable.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */; };
</span><span class="cx"> 9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */ = {isa = PBXBuildFile; fileRef = 9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */; };
</span><ins>+ A3B725EC987446AD93F1A440 /* RandomDevice.cpp in Sources */ = {isa = PBXBuildFile; fileRef = C8F597CA2A57417FBAB92FD6 /* RandomDevice.cpp */; };
</ins><span class="cx"> A5098B001C169E0700087797 /* SandboxSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = A5098AFF1C169E0700087797 /* SandboxSPI.h */; };
</span><span class="cx"> A5098B021C16A4F900087797 /* SecuritySPI.h in Headers */ = {isa = PBXBuildFile; fileRef = A5098B011C16A4F900087797 /* SecuritySPI.h */; };
</span><span class="cx"> A561F3101DF2642100FF675D /* DeprecatedOptional.h in Headers */ = {isa = PBXBuildFile; fileRef = A561F30F1DF2642100FF675D /* DeprecatedOptional.h */; };
</span><span class="lines">@@ -383,13 +385,12 @@
</span><span class="cx"> E4A0AD3A1A96245500536DF6 /* WorkQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = E4A0AD381A96245500536DF6 /* WorkQueue.h */; };
</span><span class="cx"> E4A0AD3D1A96253C00536DF6 /* WorkQueueCocoa.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E4A0AD3C1A96253C00536DF6 /* WorkQueueCocoa.cpp */; };
</span><span class="cx"> EB95E1F0161A72410089A2F5 /* ByteOrder.h in Headers */ = {isa = PBXBuildFile; fileRef = EB95E1EF161A72410089A2F5 /* ByteOrder.h */; };
</span><ins>+ FC6EC2BF20F849969C6A5BE1 /* RandomDevice.h in Headers */ = {isa = PBXBuildFile; fileRef = 24F1B248619F412296D1C19C /* RandomDevice.h */; };
</ins><span class="cx"> FE8225311B2A1E5B00BA68FD /* NakedPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = FE8225301B2A1E5B00BA68FD /* NakedPtr.h */; };
</span><span class="cx"> FE86A8751E59440200111BBF /* ForbidHeapAllocation.h in Headers */ = {isa = PBXBuildFile; fileRef = FE86A8741E59440200111BBF /* ForbidHeapAllocation.h */; };
</span><span class="cx"> FE8925B01D00DAEC0046907E /* Indenter.h in Headers */ = {isa = PBXBuildFile; fileRef = FE8925AF1D00DAEC0046907E /* Indenter.h */; };
</span><span class="cx"> FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEDACD3B1630F83F00C69634 /* StackStats.cpp */; };
</span><span class="cx"> FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */ = {isa = PBXBuildFile; fileRef = FEDACD3C1630F83F00C69634 /* StackStats.h */; };
</span><del>- FC6EC2BF20F849969C6A5BE1 /* RandomDevice.h in Headers */ = {isa = PBXBuildFile; fileRef = 24F1B248619F412296D1C19C /* RandomDevice.h */; };
- A3B725EC987446AD93F1A440 /* RandomDevice.cpp in Sources */ = {isa = PBXBuildFile; fileRef = C8F597CA2A57417FBAB92FD6 /* RandomDevice.cpp */; };
</del><span class="cx"> /* End PBXBuildFile section */
</span><span class="cx">
</span><span class="cx"> /* Begin PBXContainerItemProxy section */
</span><span class="lines">@@ -526,6 +527,7 @@
</span><span class="cx"> 1CCDB1511E566BC5006C73C0 /* CFStringSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CFStringSPI.h; path = cf/CFStringSPI.h; sourceTree = "<group>"; };
</span><span class="cx"> 1FA47C88152502DA00568D1B /* WebCoreThread.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WebCoreThread.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 1FA47C89152502DA00568D1B /* WebCoreThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WebCoreThread.h; sourceTree = "<group>"; };
</span><ins>+ 24F1B248619F412296D1C19C /* RandomDevice.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RandomDevice.h; sourceTree = "<group>"; };
</ins><span class="cx"> 26147B0815DDCCDC00DDB907 /* IntegerToStringConversion.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IntegerToStringConversion.h; sourceTree = "<group>"; };
</span><span class="cx"> 26299B6D17A9E5B800ADEBE5 /* Ref.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Ref.h; sourceTree = "<group>"; };
</span><span class="cx"> 2684D4351C000D400081D663 /* IndexSparseSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexSparseSet.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -542,6 +544,7 @@
</span><span class="cx"> 515F794D1CFC9F4A00CCED93 /* CrossThreadTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CrossThreadTask.h; sourceTree = "<group>"; };
</span><span class="cx"> 515F79551CFD3A6900CCED93 /* CrossThreadQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CrossThreadQueue.h; sourceTree = "<group>"; };
</span><span class="cx"> 539EB0621D55284200C82EF7 /* LEBDecoder.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LEBDecoder.h; sourceTree = "<group>"; };
</span><ins>+ 53EC253C1E95AD30000831B9 /* PriorityQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PriorityQueue.h; sourceTree = "<group>"; };
</ins><span class="cx"> 553071C91C40427200384898 /* TinyLRUCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyLRUCache.h; sourceTree = "<group>"; };
</span><span class="cx"> 5597F82C1D94B9970066BC21 /* SynchronizedFixedQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SynchronizedFixedQueue.h; sourceTree = "<group>"; };
</span><span class="cx"> 5B43383A5D0B463C9433D933 /* IndexMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexMap.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -760,6 +763,7 @@
</span><span class="cx"> ADF2CE651E39F106006889DB /* MemoryFootprint.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MemoryFootprint.cpp; sourceTree = "<group>"; };
</span><span class="cx"> B38FD7BC168953E80065C969 /* FeatureDefines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FeatureDefines.h; sourceTree = "<group>"; };
</span><span class="cx"> C4F8A93619C65EB400B2B15D /* Stopwatch.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Stopwatch.h; sourceTree = "<group>"; };
</span><ins>+ C8F597CA2A57417FBAB92FD6 /* RandomDevice.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RandomDevice.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> CD5497AA15857D0300B5BC30 /* MediaTime.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MediaTime.cpp; sourceTree = "<group>"; };
</span><span class="cx"> CD5497AB15857D0300B5BC30 /* MediaTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MediaTime.h; sourceTree = "<group>"; };
</span><span class="cx"> CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NSMapTableSPI.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -790,8 +794,6 @@
</span><span class="cx"> FE8925AF1D00DAEC0046907E /* Indenter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Indenter.h; sourceTree = "<group>"; };
</span><span class="cx"> FEDACD3B1630F83F00C69634 /* StackStats.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StackStats.cpp; sourceTree = "<group>"; };
</span><span class="cx"> FEDACD3C1630F83F00C69634 /* StackStats.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StackStats.h; sourceTree = "<group>"; };
</span><del>- 24F1B248619F412296D1C19C /* RandomDevice.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = RandomDevice.h; path = RandomDevice.h; sourceTree = "<group>"; };
- C8F597CA2A57417FBAB92FD6 /* RandomDevice.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = RandomDevice.cpp; path = RandomDevice.cpp; sourceTree = "<group>"; };
</del><span class="cx"> /* End PBXFileReference section */
</span><span class="cx">
</span><span class="cx"> /* Begin PBXFrameworksBuildPhase section */
</span><span class="lines">@@ -1103,6 +1105,7 @@
</span><span class="cx"> 0FF860941BCCBD740045127F /* PointerComparison.h */,
</span><span class="cx"> 0F9D335D165DBA73005AD387 /* PrintStream.cpp */,
</span><span class="cx"> 0F9D335E165DBA73005AD387 /* PrintStream.h */,
</span><ins>+ 53EC253C1E95AD30000831B9 /* PriorityQueue.h */,
</ins><span class="cx"> 0FC4488216FE9FE100844BE9 /* ProcessID.h */,
</span><span class="cx"> 143F611D1565F0F900DB514A /* RAMSize.cpp */,
</span><span class="cx"> 143F611E1565F0F900DB514A /* RAMSize.h */,
</span><span class="lines">@@ -1412,6 +1415,7 @@
</span><span class="cx"> 8134013915B092FD001FF0B8 /* Base64.h in Headers */,
</span><span class="cx"> A8A473A9151A825B004123FF /* bignum-dtoa.h in Headers */,
</span><span class="cx"> A8A473AB151A825B004123FF /* bignum.h in Headers */,
</span><ins>+ 53EC253E1E95AD30000831B9 /* PriorityQueue.h in Headers */,
</ins><span class="cx"> A8A47452151A825B004123FF /* BinarySemaphore.h in Headers */,
</span><span class="cx"> A8A4738A151A825B004123FF /* Bitmap.h in Headers */,
</span><span class="cx"> A8A4738C151A825B004123FF /* BitVector.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfMathExtrash"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/MathExtras.h (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/MathExtras.h 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/WTF/wtf/MathExtras.h 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -277,6 +277,11 @@
</span><span class="cx"> return !!((value >> 1) >> (power - 1));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template<typename T> constexpr inline bool isLessThan(const T& a, const T& b) { return a < b; }
+template<typename T> constexpr inline bool isLessThanEqual(const T& a, const T& b) { return a <= b; }
+template<typename T> constexpr inline bool isGreaterThan(const T& a, const T& b) { return a > b; }
+template<typename T> constexpr inline bool isGreaterThanEqual(const T& a, const T& b) { return a >= b; }
+
</ins><span class="cx"> #ifndef UINT64_C
</span><span class="cx"> #if COMPILER(MSVC)
</span><span class="cx"> #define UINT64_C(c) c ## ui64
</span></span></pre></div>
<a id="trunkSourceWTFwtfPriorityQueueh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/PriorityQueue.h (0 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/PriorityQueue.h (rev 0)
+++ trunk/Source/WTF/wtf/PriorityQueue.h 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -0,0 +1,141 @@
</span><ins>+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <wtf/MathExtras.h>
+#include <wtf/Vector.h>
+
+namespace WTF {
+
+// This class implements a basic priority queue. The class is backed as a binary heap, like std::priority_queue.
+// PriorityQueue has a couple of advantages over std::priority_queue:
+//
+// 1) The backing vector is fastMalloced.
+// 2) You can iterate the elements.
+// 3) It has in-place decrease/increaseKey methods, although they are still O(n) rather than O(log(n)).
+
+template<typename T, bool (*isHigherPriority)(const T&, const T&) = isLessThan<T>, size_t inlineCapacity = 0>
+class PriorityQueue {
+ using BufferType = Vector<T, inlineCapacity>;
+ using const_iterator = typename BufferType::const_iterator;
+public:
+ size_t size() const { return m_buffer.size(); }
+ bool isEmpty() const { return m_buffer.isEmpty(); }
+
+ void enqueue(T element)
+ {
+ size_t location = m_buffer.size();
+ m_buffer.append(std::forward<T>(element));
+ siftUp(location);
+ }
+
+ const T& peek() const { return m_buffer[0]; }
+ T dequeue()
+ {
+ std::swap(m_buffer[0], m_buffer.last());
+ T result = m_buffer.takeLast();
+ siftDown(0);
+ return result;
+ }
+
+ template<typename Functor>
+ void decreaseKey(const Functor& desiredElement)
+ {
+ for (size_t i = 0; i < m_buffer.size(); ++i) {
+ if (desiredElement(m_buffer[i])) {
+ siftDown(i);
+ return;
+ }
+ }
+ ASSERT(isValidHeap());
+ }
+
+ template<typename Functor>
+ void increaseKey(const Functor& desiredElement)
+ {
+ for (size_t i = 0; i < m_buffer.size(); ++i) {
+ if (desiredElement(m_buffer[i])) {
+ siftUp(i);
+ return;
+ }
+ }
+ ASSERT(isValidHeap());
+ }
+
+ const_iterator begin() const { return m_buffer.begin(); };
+ const_iterator end() const { return m_buffer.end(); };
+
+ bool isValidHeap() const
+ {
+ for (size_t i = 0; i < m_buffer.size(); ++i) {
+ if (leftChildOf(i) < m_buffer.size() && !isHigherPriority(m_buffer[i], m_buffer[leftChildOf(i)]))
+ return false;
+ if (rightChildOf(i) < m_buffer.size() && !isHigherPriority(m_buffer[i], m_buffer[rightChildOf(i)]))
+ return false;
+ }
+ return true;
+ }
+
+protected:
+ static constexpr size_t parentOf(size_t location) { ASSERT(location); return (location - 1) / 2; }
+ static constexpr size_t leftChildOf(size_t location) { return location * 2 + 1; }
+ static constexpr size_t rightChildOf(size_t location) { return leftChildOf(location) + 1; }
+
+ void siftUp(size_t location)
+ {
+ while (location) {
+ auto parent = parentOf(location);
+ if (isHigherPriority(m_buffer[parent], m_buffer[location]))
+ return;
+
+ std::swap(m_buffer[parent], m_buffer[location]);
+ location = parent;
+ }
+ }
+
+ void siftDown(size_t location)
+ {
+ while (leftChildOf(location) < m_buffer.size()) {
+ size_t higherPriorityChild;
+ if (LIKELY(rightChildOf(location) < m_buffer.size()))
+ higherPriorityChild = isHigherPriority(m_buffer[leftChildOf(location)], m_buffer[rightChildOf(location)]) ? leftChildOf(location) : rightChildOf(location);
+ else
+ higherPriorityChild = leftChildOf(location);
+
+ if (isHigherPriority(m_buffer[location], m_buffer[higherPriorityChild]))
+ return;
+
+ std::swap(m_buffer[location], m_buffer[higherPriorityChild]);
+ location = higherPriorityChild;
+ }
+ }
+
+ Vector<T, inlineCapacity> m_buffer;
+};
+
+} // namespace WTF
+
+using WTF::PriorityQueue;
</ins></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Tools/ChangeLog 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2017-04-07 Keith Miller <keith_miller@apple.com>
+
+ Add a PriorityQueue class
+ https://bugs.webkit.org/show_bug.cgi?id=170579
+
+ Reviewed by Saam Barati.
+
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+ * TestWebKitAPI/Tests/WTF/PriorityQueue.cpp: Added.
+ (operator _z ):
+ (enqueue):
+ (dequeue):
+ (TEST):
+ (compareMove):
+
</ins><span class="cx"> 2017-04-07 Ryosuke Niwa <rniwa@webkit.org>
</span><span class="cx">
</span><span class="cx"> Replace ES6SampleBench by ARES-6 in run-benchmark
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (215134 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -170,6 +170,7 @@
</span><span class="cx"> 531C1D8E1DF8EF72006E979F /* LEBDecoder.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 531C1D8D1DF8EF72006E979F /* LEBDecoder.cpp */; };
</span><span class="cx"> 536770341CC8022800D425B1 /* WebScriptObjectDescription.mm in Sources */ = {isa = PBXBuildFile; fileRef = 536770331CC8022800D425B1 /* WebScriptObjectDescription.mm */; };
</span><span class="cx"> 536770361CC81B6100D425B1 /* WebScriptObjectDescription.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 536770351CC812F900D425B1 /* WebScriptObjectDescription.html */; };
</span><ins>+ 53EC25411E96FD87000831B9 /* PriorityQueue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 53EC253F1E96BC80000831B9 /* PriorityQueue.cpp */; };
</ins><span class="cx"> 5597F8361D9596C80066BC21 /* SynchronizedFixedQueue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5597F8341D9596C80066BC21 /* SynchronizedFixedQueue.cpp */; };
</span><span class="cx"> 5714ECB91CA8B5B000051AC8 /* DownloadRequestOriginalURL.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 5714ECB81CA8B58800051AC8 /* DownloadRequestOriginalURL.html */; };
</span><span class="cx"> 5714ECBB1CA8BFE400051AC8 /* DownloadRequestOriginalURLFrame.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 5714ECBA1CA8BFD100051AC8 /* DownloadRequestOriginalURLFrame.html */; };
</span><span class="lines">@@ -1087,6 +1088,7 @@
</span><span class="cx"> 531C1D8D1DF8EF72006E979F /* LEBDecoder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LEBDecoder.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 536770331CC8022800D425B1 /* WebScriptObjectDescription.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = WebScriptObjectDescription.mm; sourceTree = "<group>"; };
</span><span class="cx"> 536770351CC812F900D425B1 /* WebScriptObjectDescription.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = WebScriptObjectDescription.html; sourceTree = "<group>"; };
</span><ins>+ 53EC253F1E96BC80000831B9 /* PriorityQueue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PriorityQueue.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> 5597F8341D9596C80066BC21 /* SynchronizedFixedQueue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SynchronizedFixedQueue.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 5714ECB81CA8B58800051AC8 /* DownloadRequestOriginalURL.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = DownloadRequestOriginalURL.html; sourceTree = "<group>"; };
</span><span class="cx"> 5714ECBA1CA8BFD100051AC8 /* DownloadRequestOriginalURLFrame.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = DownloadRequestOriginalURLFrame.html; sourceTree = "<group>"; };
</span><span class="lines">@@ -2097,6 +2099,7 @@
</span><span class="cx"> 1AFDE6541953B2C000C48FFA /* Optional.cpp */,
</span><span class="cx"> CE50D8C81C8665CE0072EA5A /* OptionSet.cpp */,
</span><span class="cx"> 0FE447971B76F1E3009498EB /* ParkingLot.cpp */,
</span><ins>+ 53EC253F1E96BC80000831B9 /* PriorityQueue.cpp */,
</ins><span class="cx"> 0FC6C4CB141027E0005B7F0C /* RedBlackTree.cpp */,
</span><span class="cx"> 93A427AA180DA26400CD24D7 /* Ref.cpp */,
</span><span class="cx"> 86BD19971A2DB05B006DCF0A /* RefCounter.cpp */,
</span><span class="lines">@@ -2643,6 +2646,7 @@
</span><span class="cx"> 1A77BAA31D9AFFFC005FC568 /* OptionSet.cpp in Sources */,
</span><span class="cx"> 7C83DF021D0A590C00FEBCF3 /* OSObjectPtr.cpp in Sources */,
</span><span class="cx"> 7C83DF591D0A590C00FEBCF3 /* ParkingLot.cpp in Sources */,
</span><ins>+ 53EC25411E96FD87000831B9 /* PriorityQueue.cpp in Sources */,
</ins><span class="cx"> 7C83DF131D0A590C00FEBCF3 /* RedBlackTree.cpp in Sources */,
</span><span class="cx"> 7C83DF141D0A590C00FEBCF3 /* Ref.cpp in Sources */,
</span><span class="cx"> 7C83DF151D0A590C00FEBCF3 /* RefCounter.cpp in Sources */,
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFPriorityQueuecpp"></a>
<div class="addfile"><h4>Added: trunk/Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp (0 => 215135)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp 2017-04-08 01:15:09 UTC (rev 215135)
</span><span class="lines">@@ -0,0 +1,256 @@
</span><ins>+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include "MoveOnly.h"
+
+#include <type_traits>
+#include <wtf/HashSet.h>
+#include <wtf/PriorityQueue.h>
+
+constexpr std::size_t operator "" _z ( unsigned long long n ) { return n; }
+
+template<typename T, bool (*isHigherPriority)(const T&, const T&)>
+static void enqueue(PriorityQueue<T, isHigherPriority>& queue, T element)
+{
+ size_t sizeBefore = queue.size();
+ queue.enqueue(WTFMove(element));
+ EXPECT_EQ(sizeBefore + 1, queue.size());
+ EXPECT_FALSE(queue.isEmpty());
+}
+
+template<typename T, bool (*isHigherPriority)(const T&, const T&)>
+static T dequeue(PriorityQueue<T, isHigherPriority>& queue)
+{
+ EXPECT_FALSE(queue.isEmpty());
+ size_t sizeBefore = queue.size();
+ T result = queue.dequeue();
+ EXPECT_EQ(sizeBefore - 1, queue.size());
+ return result;
+}
+
+
+TEST(WTF_PriorityQueue, Basic)
+{
+ const unsigned numElements = 10;
+ PriorityQueue<unsigned> queue;
+
+ EXPECT_EQ(0_z, queue.size());
+ EXPECT_TRUE(queue.isEmpty());
+
+ for (unsigned i = 0; i < numElements; ++i)
+ enqueue(queue, i);
+
+ for (unsigned i = 0; i < numElements; ++i) {
+ EXPECT_EQ(i, queue.peek());
+ EXPECT_EQ(i, dequeue(queue));
+ EXPECT_EQ(numElements - i - 1, queue.size());
+ }
+
+ EXPECT_TRUE(queue.isEmpty());
+}
+
+TEST(WTF_PriorityQueue, CustomPriorityFunction)
+{
+ const unsigned numElements = 10;
+ PriorityQueue<unsigned, isGreaterThan<unsigned>> queue;
+
+ EXPECT_EQ(0_z, queue.size());
+ EXPECT_TRUE(queue.isEmpty());
+
+ for (unsigned i = 0; i < numElements; ++i) {
+ enqueue(queue, i);
+ EXPECT_EQ(i + 1, queue.size());
+ EXPECT_FALSE(queue.isEmpty());
+ }
+
+ for (unsigned i = 0; i < numElements; ++i) {
+ EXPECT_EQ(numElements - i - 1, queue.peek());
+ EXPECT_EQ(numElements - i - 1, dequeue(queue));
+ EXPECT_EQ(numElements - i - 1, queue.size());
+ }
+
+ EXPECT_TRUE(queue.isEmpty());
+}
+
+template<bool (*isHigherPriority)(const unsigned&, const unsigned&)>
+static bool compareMove(const MoveOnly& m1, const MoveOnly& m2)
+{
+ return isHigherPriority(m1.value(), m2.value());
+}
+
+
+TEST(WTF_PriorityQueue, MoveOnly)
+{
+ PriorityQueue<MoveOnly, compareMove<isLessThan<unsigned>>> queue;
+
+ Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
+ Vector<unsigned> sorted = values;
+ std::sort(sorted.begin(), sorted.end());
+
+ for (auto value : values)
+ queue.enqueue(MoveOnly(value));
+
+ for (auto sortedValue : sorted) {
+ auto value = queue.dequeue();
+ EXPECT_EQ(sortedValue, value.value());
+ }
+}
+
+TEST(WTF_PriorityQueue, DecreaseKey)
+{
+ PriorityQueue<MoveOnly, compareMove<isLessThan<unsigned>>> queue;
+
+ Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
+ Vector<unsigned> sorted = values;
+ sorted[3] = 12;
+ std::sort(sorted.begin(), sorted.end());
+
+ for (auto value : values)
+ queue.enqueue(MoveOnly(value));
+
+ queue.decreaseKey([] (MoveOnly& m) {
+ if (m.value() == 8) {
+ m = MoveOnly(12);
+ return true;
+ }
+ return false;
+ });
+
+ for (auto sortedValue : sorted) {
+ auto value = queue.dequeue();
+ EXPECT_EQ(sortedValue, value.value());
+ }
+}
+
+TEST(WTF_PriorityQueue, IncreaseKey)
+{
+ PriorityQueue<MoveOnly, compareMove<isGreaterThan<unsigned>>> queue;
+
+ Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
+ Vector<unsigned> sorted = values;
+ sorted[3] = 12;
+ std::sort(sorted.begin(), sorted.end(), std::greater<unsigned>());
+
+ for (auto value : values)
+ queue.enqueue(MoveOnly(value));
+
+ queue.increaseKey([] (MoveOnly& m) {
+ if (m.value() == 8) {
+ m = MoveOnly(12);
+ return true;
+ }
+ return false;
+ });
+
+ for (auto sortedValue : sorted) {
+ auto value = queue.dequeue();
+ EXPECT_EQ(sortedValue, value.value());
+ }
+}
+
+TEST(WTF_PriorityQueue, Iteration)
+{
+ PriorityQueue<MoveOnly, compareMove<isGreaterThan<unsigned>>> queue;
+
+ Vector<unsigned> values = { 23, 54, 4, 8, 1, 2, 4, 0 };
+ Vector<unsigned> sorted = values;
+ std::sort(sorted.begin(), sorted.end(), std::greater<unsigned>());
+
+ for (auto value : values)
+ queue.enqueue(MoveOnly(value));
+
+ values.clear();
+ for (auto& element : queue)
+ values.append(element.value());
+
+ std::sort(values.begin(), values.end(), std::greater<unsigned>());
+ EXPECT_EQ(values.size(), sorted.size());
+ if (values.size() == sorted.size()) {
+ for (size_t i = 0; i < values.size(); ++i)
+ EXPECT_EQ(sorted[i], values[i]);
+ }
+}
+
+TEST(WTF_PriorityQueue, RandomActions)
+{
+ const uint64_t prime1 = 15487237;
+ const uint64_t prime2 = 179428283;
+ uint64_t randomNumber = 19405709;
+
+ auto nextRandom = [&] () -> uint64_t {
+ randomNumber = randomNumber * prime1 + prime2;
+ return randomNumber;
+ };
+
+ PriorityQueue<uint64_t> queue;
+ Vector<uint64_t> values;
+
+ enum Cases {
+ Enqueue,
+ Dequeue,
+ NumberOfCases
+ };
+
+ // Seed the queue.
+ for (unsigned i = 0; i < 100; ++i) {
+ auto number = nextRandom();
+ queue.enqueue(number);
+ values.append(number);
+ EXPECT_TRUE(queue.isValidHeap());
+ }
+
+ for (unsigned i = 0; i < 10000; ++i) {
+ auto number = nextRandom();
+ switch (number % NumberOfCases) {
+ case Enqueue: {
+ queue.enqueue(number);
+ values.append(number);
+ EXPECT_TRUE(queue.isValidHeap());
+ EXPECT_EQ(values.size(), queue.size());
+ continue;
+ }
+
+ case Dequeue: {
+ EXPECT_EQ(values.size(), queue.size());
+ if (values.size() != queue.size())
+ break;
+
+ if (!values.size())
+ continue;
+
+ // Sort with greater so the last element should be the one we dequeue.
+ std::sort(values.begin(), values.end(), std::greater<uint64_t>());
+ EXPECT_EQ(values.takeLast(), queue.dequeue());
+
+ continue;
+ }
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+ EXPECT_TRUE(queue.isValidHeap());
+ }
+}
</ins></span></pre>
</div>
</div>
</body>
</html>