Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (215134 => 215135)
--- trunk/Source/_javascript_Core/ChangeLog 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-04-08 01:15:09 UTC (rev 215135)
@@ -1,3 +1,22 @@
+2017-04-07 Keith Miller <[email protected]>
+
+ 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.
+
2017-04-07 Yuichiro Kikura <[email protected]>
WebGPU: implement ComputeCommandEncoder and related components
Modified: trunk/Source/_javascript_Core/wasm/WasmWorklist.cpp (215134 => 215135)
--- trunk/Source/_javascript_Core/wasm/WasmWorklist.cpp 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/_javascript_Core/wasm/WasmWorklist.cpp 2017-04-08 01:15:09 UTC (rev 215135)
@@ -67,16 +67,15 @@
auto& queue = worklist.m_queue;
synchronize.notifyAll();
- while (!queue.empty()) {
-
- Priority priority = queue.top().priority;
+ while (!queue.isEmpty()) {
+ Priority priority = queue.peek().priority;
if (priority == Worklist::Priority::Shutdown)
return PollResult::Stop;
- element = queue.top();
+ element = queue.peek();
// Only one thread should validate/prepare.
- if (!queue.top().plan->hasBeenPrepared()) {
- queue.pop();
+ if (!queue.peek().plan->hasBeenPrepared()) {
+ queue.dequeue();
return PollResult::Work;
}
@@ -84,7 +83,7 @@
return PollResult::Work;
// There must be a another thread linking this plan so we can deque and see if there is other work.
- queue.pop();
+ queue.dequeue();
element = QueueElement();
}
return PollResult::Wait;
@@ -92,7 +91,9 @@
WorkResult work() override
{
- auto complete = [&] () {
+ 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
element = QueueElement();
return WorkResult::Continue;
};
@@ -102,29 +103,19 @@
if (!plan->hasBeenPrepared()) {
plan->parseAndValidateModule();
if (!plan->hasWork())
- return complete();
+ return complete(holdLock(*worklist.m_lock));
plan->prepare();
LockHolder locker(*worklist.m_lock);
element.setToNextPriority();
- worklist.m_queue.push(element);
+ worklist.m_queue.enqueue(WTFMove(element));
worklist.m_planEnqueued->notifyAll(locker);
+ return complete(locker);
}
- // 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
plan->compileFunctions(Plan::Partial);
-
- 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();
+ return complete(holdLock(*worklist.m_lock));
}
public:
@@ -148,47 +139,17 @@
RELEASE_ASSERT_NOT_REACHED();
}
-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);
-}
-
void Worklist::enqueue(Ref<Plan> plan)
{
LockHolder locker(*m_lock);
if (!ASSERT_DISABLED) {
- iterate(locker, [&] (QueueElement& element) {
+ for (const auto& element : m_queue)
ASSERT_UNUSED(element, element.plan.get() != &plan.get());
- return IterateResult::Continue;
- });
}
dataLogLnIf(verbose, "Enqueuing plan");
- m_queue.push({ Priority::Preparation, nextTicket(), WTFMove(plan) });
+ m_queue.enqueue({ Priority::Preparation, nextTicket(), WTFMove(plan) });
m_planEnqueued->notifyOne(locker);
}
@@ -196,12 +157,12 @@
{
{
LockHolder locker(*m_lock);
- iterate(locker, [&] (QueueElement& element) {
+ m_queue.decreaseKey([&] (QueueElement& element) {
if (element.plan == &plan) {
element.priority = Priority::Synchronous;
- return IterateResult::UpdateAndBreak;
+ return true;
}
- return IterateResult::Continue;
+ return false;
});
for (auto& thread : m_threads) {
@@ -216,18 +177,22 @@
void Worklist::stopAllPlansForVM(VM& vm)
{
LockHolder locker(*m_lock);
- iterate(locker, [&] (QueueElement& element) {
+ Vector<QueueElement> elements;
+ while (!m_queue.isEmpty()) {
+ QueueElement element = m_queue.dequeue();
bool didCancel = element.plan->tryRemoveVMAndCancelIfLast(vm);
- if (didCancel)
- return IterateResult::DropAndContinue;
- return IterateResult::Continue;
- });
+ if (!didCancel)
+ elements.append(WTFMove(element));
+ }
+ for (auto& element : elements)
+ m_queue.enqueue(WTFMove(element));
+
for (auto& thread : m_threads) {
if (thread->element.plan) {
bool didCancel = thread->element.plan->tryRemoveVMAndCancelIfLast(vm);
if (didCancel) {
- // 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.
+ // 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.
thread->synchronize.wait(*m_lock);
}
}
@@ -249,7 +214,7 @@
{
{
LockHolder locker(*m_lock);
- m_queue.push({ Priority::Shutdown, nextTicket(), nullptr });
+ m_queue.enqueue({ Priority::Shutdown, nextTicket(), nullptr });
m_planEnqueued->notifyAll(locker);
}
for (unsigned i = 0; i < m_threads.size(); ++i)
Modified: trunk/Source/_javascript_Core/wasm/WasmWorklist.h (215134 => 215135)
--- trunk/Source/_javascript_Core/wasm/WasmWorklist.h 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Source/_javascript_Core/wasm/WasmWorklist.h 2017-04-08 01:15:09 UTC (rev 215135)
@@ -32,6 +32,7 @@
#include <queue>
#include <wtf/AutomaticThread.h>
+#include <wtf/PriorityQueue.h>
#include <wtf/Vector.h>
namespace JSC {
@@ -79,17 +80,13 @@
void setToNextPriority();
};
- 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;
- }
- };
+ static bool isHigherPriority(const QueueElement& left, const QueueElement& right)
+ {
+ if (left.priority == right.priority)
+ return left.ticket > right.ticket;
+ return left.priority > right.priority;
+ }
- template<typename Functor>
- void iterate(const AbstractLocker&, const Functor&);
Box<Lock> m_lock;
RefPtr<AutomaticThreadCondition> m_planEnqueued;
@@ -96,9 +93,7 @@
// Technically, this could overflow but that's unlikely. Even if it did, we will just compile things of the same
// Priority it the wrong order, which isn't wrong, just suboptimal.
Ticket m_lastGrantedTicket { 0 };
- // 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;
+ PriorityQueue<QueueElement, isHigherPriority, 10> m_queue;
Vector<std::unique_ptr<Thread>> m_threads;
};
Modified: trunk/Source/WTF/ChangeLog (215134 => 215135)
--- 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)
@@ -1,3 +1,48 @@
+2017-04-07 Keith Miller <[email protected]>
+
+ 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):
+
2017-04-07 Alex Christensen <[email protected]>
Use audit_token_t instead of pid_t for checking sandbox of other processes
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (215134 => 215135)
--- 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)
@@ -149,6 +149,7 @@
515F79561CFD3A6900CCED93 /* CrossThreadQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 515F79551CFD3A6900CCED93 /* CrossThreadQueue.h */; };
52183012C99E476A84EEBEA8 /* SymbolImpl.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F72BBDB107FA424886178B9E /* SymbolImpl.cpp */; };
539EB0631D55284200C82EF7 /* LEBDecoder.h in Headers */ = {isa = PBXBuildFile; fileRef = 539EB0621D55284200C82EF7 /* LEBDecoder.h */; };
+ 53EC253E1E95AD30000831B9 /* PriorityQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 53EC253C1E95AD30000831B9 /* PriorityQueue.h */; settings = {ATTRIBUTES = (Private, ); }; };
553071CA1C40427200384898 /* TinyLRUCache.h in Headers */ = {isa = PBXBuildFile; fileRef = 553071C91C40427200384898 /* TinyLRUCache.h */; };
5597F82F1D94B9970066BC21 /* SynchronizedFixedQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 5597F82C1D94B9970066BC21 /* SynchronizedFixedQueue.h */; };
5C7C88D41D0A3A0A009D2F6D /* UniqueRef.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C7C88D31D0A3A0A009D2F6D /* UniqueRef.h */; };
@@ -178,6 +179,7 @@
974CFC8E16A4F327006D5404 /* WeakPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = 974CFC8D16A4F327006D5404 /* WeakPtr.h */; };
9BC70F05176C379D00101DEC /* AtomicStringTable.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */; };
9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */ = {isa = PBXBuildFile; fileRef = 9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */; };
+ A3B725EC987446AD93F1A440 /* RandomDevice.cpp in Sources */ = {isa = PBXBuildFile; fileRef = C8F597CA2A57417FBAB92FD6 /* RandomDevice.cpp */; };
A5098B001C169E0700087797 /* SandboxSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = A5098AFF1C169E0700087797 /* SandboxSPI.h */; };
A5098B021C16A4F900087797 /* SecuritySPI.h in Headers */ = {isa = PBXBuildFile; fileRef = A5098B011C16A4F900087797 /* SecuritySPI.h */; };
A561F3101DF2642100FF675D /* DeprecatedOptional.h in Headers */ = {isa = PBXBuildFile; fileRef = A561F30F1DF2642100FF675D /* DeprecatedOptional.h */; };
@@ -383,13 +385,12 @@
E4A0AD3A1A96245500536DF6 /* WorkQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = E4A0AD381A96245500536DF6 /* WorkQueue.h */; };
E4A0AD3D1A96253C00536DF6 /* WorkQueueCocoa.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E4A0AD3C1A96253C00536DF6 /* WorkQueueCocoa.cpp */; };
EB95E1F0161A72410089A2F5 /* ByteOrder.h in Headers */ = {isa = PBXBuildFile; fileRef = EB95E1EF161A72410089A2F5 /* ByteOrder.h */; };
+ FC6EC2BF20F849969C6A5BE1 /* RandomDevice.h in Headers */ = {isa = PBXBuildFile; fileRef = 24F1B248619F412296D1C19C /* RandomDevice.h */; };
FE8225311B2A1E5B00BA68FD /* NakedPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = FE8225301B2A1E5B00BA68FD /* NakedPtr.h */; };
FE86A8751E59440200111BBF /* ForbidHeapAllocation.h in Headers */ = {isa = PBXBuildFile; fileRef = FE86A8741E59440200111BBF /* ForbidHeapAllocation.h */; };
FE8925B01D00DAEC0046907E /* Indenter.h in Headers */ = {isa = PBXBuildFile; fileRef = FE8925AF1D00DAEC0046907E /* Indenter.h */; };
FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEDACD3B1630F83F00C69634 /* StackStats.cpp */; };
FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */ = {isa = PBXBuildFile; fileRef = FEDACD3C1630F83F00C69634 /* StackStats.h */; };
- FC6EC2BF20F849969C6A5BE1 /* RandomDevice.h in Headers */ = {isa = PBXBuildFile; fileRef = 24F1B248619F412296D1C19C /* RandomDevice.h */; };
- A3B725EC987446AD93F1A440 /* RandomDevice.cpp in Sources */ = {isa = PBXBuildFile; fileRef = C8F597CA2A57417FBAB92FD6 /* RandomDevice.cpp */; };
/* End PBXBuildFile section */
/* Begin PBXContainerItemProxy section */
@@ -526,6 +527,7 @@
1CCDB1511E566BC5006C73C0 /* CFStringSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CFStringSPI.h; path = cf/CFStringSPI.h; sourceTree = "<group>"; };
1FA47C88152502DA00568D1B /* WebCoreThread.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WebCoreThread.cpp; sourceTree = "<group>"; };
1FA47C89152502DA00568D1B /* WebCoreThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WebCoreThread.h; sourceTree = "<group>"; };
+ 24F1B248619F412296D1C19C /* RandomDevice.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RandomDevice.h; sourceTree = "<group>"; };
26147B0815DDCCDC00DDB907 /* IntegerToStringConversion.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IntegerToStringConversion.h; sourceTree = "<group>"; };
26299B6D17A9E5B800ADEBE5 /* Ref.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Ref.h; sourceTree = "<group>"; };
2684D4351C000D400081D663 /* IndexSparseSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexSparseSet.h; sourceTree = "<group>"; };
@@ -542,6 +544,7 @@
515F794D1CFC9F4A00CCED93 /* CrossThreadTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CrossThreadTask.h; sourceTree = "<group>"; };
515F79551CFD3A6900CCED93 /* CrossThreadQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CrossThreadQueue.h; sourceTree = "<group>"; };
539EB0621D55284200C82EF7 /* LEBDecoder.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LEBDecoder.h; sourceTree = "<group>"; };
+ 53EC253C1E95AD30000831B9 /* PriorityQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PriorityQueue.h; sourceTree = "<group>"; };
553071C91C40427200384898 /* TinyLRUCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyLRUCache.h; sourceTree = "<group>"; };
5597F82C1D94B9970066BC21 /* SynchronizedFixedQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SynchronizedFixedQueue.h; sourceTree = "<group>"; };
5B43383A5D0B463C9433D933 /* IndexMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexMap.h; sourceTree = "<group>"; };
@@ -760,6 +763,7 @@
ADF2CE651E39F106006889DB /* MemoryFootprint.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MemoryFootprint.cpp; sourceTree = "<group>"; };
B38FD7BC168953E80065C969 /* FeatureDefines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FeatureDefines.h; sourceTree = "<group>"; };
C4F8A93619C65EB400B2B15D /* Stopwatch.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Stopwatch.h; sourceTree = "<group>"; };
+ C8F597CA2A57417FBAB92FD6 /* RandomDevice.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RandomDevice.cpp; sourceTree = "<group>"; };
CD5497AA15857D0300B5BC30 /* MediaTime.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MediaTime.cpp; sourceTree = "<group>"; };
CD5497AB15857D0300B5BC30 /* MediaTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MediaTime.h; sourceTree = "<group>"; };
CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NSMapTableSPI.h; sourceTree = "<group>"; };
@@ -790,8 +794,6 @@
FE8925AF1D00DAEC0046907E /* Indenter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Indenter.h; sourceTree = "<group>"; };
FEDACD3B1630F83F00C69634 /* StackStats.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StackStats.cpp; sourceTree = "<group>"; };
FEDACD3C1630F83F00C69634 /* StackStats.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StackStats.h; sourceTree = "<group>"; };
- 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>"; };
/* End PBXFileReference section */
/* Begin PBXFrameworksBuildPhase section */
@@ -1103,6 +1105,7 @@
0FF860941BCCBD740045127F /* PointerComparison.h */,
0F9D335D165DBA73005AD387 /* PrintStream.cpp */,
0F9D335E165DBA73005AD387 /* PrintStream.h */,
+ 53EC253C1E95AD30000831B9 /* PriorityQueue.h */,
0FC4488216FE9FE100844BE9 /* ProcessID.h */,
143F611D1565F0F900DB514A /* RAMSize.cpp */,
143F611E1565F0F900DB514A /* RAMSize.h */,
@@ -1412,6 +1415,7 @@
8134013915B092FD001FF0B8 /* Base64.h in Headers */,
A8A473A9151A825B004123FF /* bignum-dtoa.h in Headers */,
A8A473AB151A825B004123FF /* bignum.h in Headers */,
+ 53EC253E1E95AD30000831B9 /* PriorityQueue.h in Headers */,
A8A47452151A825B004123FF /* BinarySemaphore.h in Headers */,
A8A4738A151A825B004123FF /* Bitmap.h in Headers */,
A8A4738C151A825B004123FF /* BitVector.h in Headers */,
Modified: trunk/Source/WTF/wtf/MathExtras.h (215134 => 215135)
--- 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)
@@ -277,6 +277,11 @@
return !!((value >> 1) >> (power - 1));
}
+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; }
+
#ifndef UINT64_C
#if COMPILER(MSVC)
#define UINT64_C(c) c ## ui64
Added: trunk/Source/WTF/wtf/PriorityQueue.h (0 => 215135)
--- trunk/Source/WTF/wtf/PriorityQueue.h (rev 0)
+++ trunk/Source/WTF/wtf/PriorityQueue.h 2017-04-08 01:15:09 UTC (rev 215135)
@@ -0,0 +1,141 @@
+/*
+ * 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;
Modified: trunk/Tools/ChangeLog (215134 => 215135)
--- trunk/Tools/ChangeLog 2017-04-08 01:11:10 UTC (rev 215134)
+++ trunk/Tools/ChangeLog 2017-04-08 01:15:09 UTC (rev 215135)
@@ -1,3 +1,18 @@
+2017-04-07 Keith Miller <[email protected]>
+
+ 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):
+
2017-04-07 Ryosuke Niwa <[email protected]>
Replace ES6SampleBench by ARES-6 in run-benchmark
Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (215134 => 215135)
--- 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)
@@ -170,6 +170,7 @@
531C1D8E1DF8EF72006E979F /* LEBDecoder.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 531C1D8D1DF8EF72006E979F /* LEBDecoder.cpp */; };
536770341CC8022800D425B1 /* WebScriptObjectDescription.mm in Sources */ = {isa = PBXBuildFile; fileRef = 536770331CC8022800D425B1 /* WebScriptObjectDescription.mm */; };
536770361CC81B6100D425B1 /* WebScriptObjectDescription.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 536770351CC812F900D425B1 /* WebScriptObjectDescription.html */; };
+ 53EC25411E96FD87000831B9 /* PriorityQueue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 53EC253F1E96BC80000831B9 /* PriorityQueue.cpp */; };
5597F8361D9596C80066BC21 /* SynchronizedFixedQueue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5597F8341D9596C80066BC21 /* SynchronizedFixedQueue.cpp */; };
5714ECB91CA8B5B000051AC8 /* DownloadRequestOriginalURL.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 5714ECB81CA8B58800051AC8 /* DownloadRequestOriginalURL.html */; };
5714ECBB1CA8BFE400051AC8 /* DownloadRequestOriginalURLFrame.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 5714ECBA1CA8BFD100051AC8 /* DownloadRequestOriginalURLFrame.html */; };
@@ -1087,6 +1088,7 @@
531C1D8D1DF8EF72006E979F /* LEBDecoder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LEBDecoder.cpp; sourceTree = "<group>"; };
536770331CC8022800D425B1 /* WebScriptObjectDescription.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = WebScriptObjectDescription.mm; sourceTree = "<group>"; };
536770351CC812F900D425B1 /* WebScriptObjectDescription.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = WebScriptObjectDescription.html; sourceTree = "<group>"; };
+ 53EC253F1E96BC80000831B9 /* PriorityQueue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PriorityQueue.cpp; sourceTree = "<group>"; };
5597F8341D9596C80066BC21 /* SynchronizedFixedQueue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SynchronizedFixedQueue.cpp; sourceTree = "<group>"; };
5714ECB81CA8B58800051AC8 /* DownloadRequestOriginalURL.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = DownloadRequestOriginalURL.html; sourceTree = "<group>"; };
5714ECBA1CA8BFD100051AC8 /* DownloadRequestOriginalURLFrame.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = DownloadRequestOriginalURLFrame.html; sourceTree = "<group>"; };
@@ -2097,6 +2099,7 @@
1AFDE6541953B2C000C48FFA /* Optional.cpp */,
CE50D8C81C8665CE0072EA5A /* OptionSet.cpp */,
0FE447971B76F1E3009498EB /* ParkingLot.cpp */,
+ 53EC253F1E96BC80000831B9 /* PriorityQueue.cpp */,
0FC6C4CB141027E0005B7F0C /* RedBlackTree.cpp */,
93A427AA180DA26400CD24D7 /* Ref.cpp */,
86BD19971A2DB05B006DCF0A /* RefCounter.cpp */,
@@ -2643,6 +2646,7 @@
1A77BAA31D9AFFFC005FC568 /* OptionSet.cpp in Sources */,
7C83DF021D0A590C00FEBCF3 /* OSObjectPtr.cpp in Sources */,
7C83DF591D0A590C00FEBCF3 /* ParkingLot.cpp in Sources */,
+ 53EC25411E96FD87000831B9 /* PriorityQueue.cpp in Sources */,
7C83DF131D0A590C00FEBCF3 /* RedBlackTree.cpp in Sources */,
7C83DF141D0A590C00FEBCF3 /* Ref.cpp in Sources */,
7C83DF151D0A590C00FEBCF3 /* RefCounter.cpp in Sources */,
Added: trunk/Tools/TestWebKitAPI/Tests/WTF/PriorityQueue.cpp (0 => 215135)
--- 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)
@@ -0,0 +1,256 @@
+/*
+ * 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());
+ }
+}
