1/*
2 * Copyright (C) 2008, 2015-2016 Apple Inc. All rights reserved.
3 * Copyright (C) 2009 Google Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of Apple Inc. ("Apple") nor the names of
15 * its contributors may be used to endorse or promote products derived
16 * from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#pragma once
31
32#include <limits>
33#include <wtf/Assertions.h>
34#include <wtf/Condition.h>
35#include <wtf/Deque.h>
36#include <wtf/Lock.h>
37#include <wtf/MonotonicTime.h>
38#include <wtf/Noncopyable.h>
39
40namespace WTF {
41
42 enum MessageQueueWaitResult {
43 MessageQueueTerminated, // Queue was destroyed while waiting for message.
44 MessageQueueTimeout, // Timeout was specified and it expired.
45 MessageQueueMessageReceived // A message was successfully received and returned.
46 };
47
48 // The queue takes ownership of messages and transfer it to the new owner
49 // when messages are fetched from the queue.
50 // Essentially, MessageQueue acts as a queue of std::unique_ptr<DataType>.
51 template<typename DataType>
52 class MessageQueue {
53 WTF_MAKE_NONCOPYABLE(MessageQueue);
54 public:
55 MessageQueue() : m_killed(false) { }
56 ~MessageQueue();
57
58 void append(std::unique_ptr<DataType>);
59 void appendAndKill(std::unique_ptr<DataType>);
60 bool appendAndCheckEmpty(std::unique_ptr<DataType>);
61 void prepend(std::unique_ptr<DataType>);
62
63 std::unique_ptr<DataType> waitForMessage();
64 std::unique_ptr<DataType> tryGetMessage();
65 Deque<std::unique_ptr<DataType>> takeAllMessages();
66 std::unique_ptr<DataType> tryGetMessageIgnoringKilled();
67 template<typename Predicate>
68 std::unique_ptr<DataType> waitForMessageFilteredWithTimeout(MessageQueueWaitResult&, Predicate&&, Seconds relativeTimeout);
69
70 template<typename Predicate>
71 void removeIf(Predicate&&);
72
73 void kill();
74 bool killed() const;
75
76 // The result of isEmpty() is only valid if no other thread is manipulating the queue at the same time.
77 bool isEmpty();
78
79 private:
80 mutable Lock m_mutex;
81 Condition m_condition;
82 Deque<std::unique_ptr<DataType>> m_queue;
83 bool m_killed;
84 };
85
86 template<typename DataType>
87 MessageQueue<DataType>::~MessageQueue()
88 {
89 }
90
91 template<typename DataType>
92 inline void MessageQueue<DataType>::append(std::unique_ptr<DataType> message)
93 {
94 LockHolder lock(m_mutex);
95 m_queue.append(WTFMove(message));
96 m_condition.notifyOne();
97 }
98
99 template<typename DataType>
100 inline void MessageQueue<DataType>::appendAndKill(std::unique_ptr<DataType> message)
101 {
102 LockHolder lock(m_mutex);
103 m_queue.append(WTFMove(message));
104 m_killed = true;
105 m_condition.notifyAll();
106 }
107
108 // Returns true if the queue was empty before the item was added.
109 template<typename DataType>
110 inline bool MessageQueue<DataType>::appendAndCheckEmpty(std::unique_ptr<DataType> message)
111 {
112 LockHolder lock(m_mutex);
113 bool wasEmpty = m_queue.isEmpty();
114 m_queue.append(WTFMove(message));
115 m_condition.notifyOne();
116 return wasEmpty;
117 }
118
119 template<typename DataType>
120 inline void MessageQueue<DataType>::prepend(std::unique_ptr<DataType> message)
121 {
122 LockHolder lock(m_mutex);
123 m_queue.prepend(WTFMove(message));
124 m_condition.notifyOne();
125 }
126
127 template<typename DataType>
128 inline auto MessageQueue<DataType>::waitForMessage() -> std::unique_ptr<DataType>
129 {
130 MessageQueueWaitResult exitReason;
131 std::unique_ptr<DataType> result = waitForMessageFilteredWithTimeout(exitReason, [](const DataType&) { return true; }, Seconds::infinity());
132 ASSERT(exitReason == MessageQueueTerminated || exitReason == MessageQueueMessageReceived);
133 return result;
134 }
135
136 template<typename DataType>
137 template<typename Predicate>
138 inline auto MessageQueue<DataType>::waitForMessageFilteredWithTimeout(MessageQueueWaitResult& result, Predicate&& predicate, Seconds relativeTimeout) -> std::unique_ptr<DataType>
139 {
140 LockHolder lock(m_mutex);
141 bool timedOut = false;
142
143 MonotonicTime absoluteTimeout = MonotonicTime::now() + relativeTimeout;
144 auto found = m_queue.end();
145 while (!m_killed && !timedOut) {
146 found = m_queue.findIf([&predicate](const std::unique_ptr<DataType>& ptr) -> bool {
147 ASSERT(ptr);
148 return predicate(*ptr);
149 });
150 if (found != m_queue.end())
151 break;
152
153 timedOut = !m_condition.waitUntil(m_mutex, absoluteTimeout);
154 }
155
156 ASSERT(!timedOut || absoluteTimeout != MonotonicTime::infinity());
157
158 if (m_killed) {
159 result = MessageQueueTerminated;
160 return nullptr;
161 }
162
163 if (timedOut) {
164 result = MessageQueueTimeout;
165 return nullptr;
166 }
167
168 ASSERT(found != m_queue.end());
169 std::unique_ptr<DataType> message = WTFMove(*found);
170 m_queue.remove(found);
171 result = MessageQueueMessageReceived;
172 return message;
173 }
174
175 template<typename DataType>
176 inline auto MessageQueue<DataType>::tryGetMessage() -> std::unique_ptr<DataType>
177 {
178 LockHolder lock(m_mutex);
179 if (m_killed)
180 return nullptr;
181 if (m_queue.isEmpty())
182 return nullptr;
183
184 return m_queue.takeFirst();
185 }
186
187 template<typename DataType>
188 inline auto MessageQueue<DataType>::takeAllMessages() -> Deque<std::unique_ptr<DataType>>
189 {
190 LockHolder lock(m_mutex);
191 if (m_killed)
192 return { };
193 return WTFMove(m_queue);
194 }
195
196 template<typename DataType>
197 inline auto MessageQueue<DataType>::tryGetMessageIgnoringKilled() -> std::unique_ptr<DataType>
198 {
199 LockHolder lock(m_mutex);
200 if (m_queue.isEmpty())
201 return nullptr;
202
203 return m_queue.takeFirst();
204 }
205
206 template<typename DataType>
207 template<typename Predicate>
208 inline void MessageQueue<DataType>::removeIf(Predicate&& predicate)
209 {
210 LockHolder lock(m_mutex);
211 while (true) {
212 auto found = m_queue.findIf([&predicate](const std::unique_ptr<DataType>& ptr) -> bool {
213 ASSERT(ptr);
214 return predicate(*ptr);
215 });
216
217 if (found == m_queue.end())
218 break;
219
220 m_queue.remove(found);
221 }
222 }
223
224 template<typename DataType>
225 inline bool MessageQueue<DataType>::isEmpty()
226 {
227 LockHolder lock(m_mutex);
228 if (m_killed)
229 return true;
230 return m_queue.isEmpty();
231 }
232
233 template<typename DataType>
234 inline void MessageQueue<DataType>::kill()
235 {
236 LockHolder lock(m_mutex);
237 m_killed = true;
238 m_condition.notifyAll();
239 }
240
241 template<typename DataType>
242 inline bool MessageQueue<DataType>::killed() const
243 {
244 LockHolder lock(m_mutex);
245 return m_killed;
246 }
247} // namespace WTF
248
249using WTF::MessageQueue;
250// MessageQueueWaitResult enum and all its values.
251using WTF::MessageQueueWaitResult;
252using WTF::MessageQueueTerminated;
253using WTF::MessageQueueTimeout;
254using WTF::MessageQueueMessageReceived;
255