1/*
2 * Copyright (C) 2008 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 Computer, 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#ifndef MessageQueue_h
31#define MessageQueue_h
32
33#include <limits>
34#include "wtf/Assertions.h"
35#include "wtf/Deque.h"
36#include "wtf/Noncopyable.h"
37#include "wtf/PassOwnPtr.h"
38#include "wtf/ThreadingPrimitives.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 OwnPtr<DataType>.
51    template<typename DataType>
52    class MessageQueue {
53        WTF_MAKE_NONCOPYABLE(MessageQueue);
54    public:
55        MessageQueue() : m_killed(false) { }
56        ~MessageQueue();
57
58        // Returns true if the queue is still alive, false if the queue has been killed.
59        bool append(PassOwnPtr<DataType>);
60        void appendAndKill(PassOwnPtr<DataType>);
61        bool appendAndCheckEmpty(PassOwnPtr<DataType>);
62        void prepend(PassOwnPtr<DataType>);
63
64        PassOwnPtr<DataType> waitForMessage();
65        PassOwnPtr<DataType> tryGetMessage();
66        PassOwnPtr<DataType> tryGetMessageIgnoringKilled();
67        template<typename Predicate>
68        PassOwnPtr<DataType> waitForMessageFilteredWithTimeout(MessageQueueWaitResult&, Predicate&, double absoluteTime);
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        static double infiniteTime() { return std::numeric_limits<double>::max(); }
80
81    private:
82        static bool alwaysTruePredicate(DataType*) { return true; }
83
84        mutable Mutex m_mutex;
85        ThreadCondition m_condition;
86        Deque<DataType*> m_queue;
87        bool m_killed;
88    };
89
90    template<typename DataType>
91    MessageQueue<DataType>::~MessageQueue()
92    {
93        deleteAllValues(m_queue);
94    }
95
96    template<typename DataType>
97    inline bool MessageQueue<DataType>::append(PassOwnPtr<DataType> message)
98    {
99        MutexLocker lock(m_mutex);
100        m_queue.append(message.leakPtr());
101        m_condition.signal();
102        return !m_killed;
103    }
104
105    template<typename DataType>
106    inline void MessageQueue<DataType>::appendAndKill(PassOwnPtr<DataType> message)
107    {
108        MutexLocker lock(m_mutex);
109        m_queue.append(message.leakPtr());
110        m_killed = true;
111        m_condition.broadcast();
112    }
113
114    // Returns true if the queue was empty before the item was added.
115    template<typename DataType>
116    inline bool MessageQueue<DataType>::appendAndCheckEmpty(PassOwnPtr<DataType> message)
117    {
118        MutexLocker lock(m_mutex);
119        bool wasEmpty = m_queue.isEmpty();
120        m_queue.append(message.leakPtr());
121        m_condition.signal();
122        return wasEmpty;
123    }
124
125    template<typename DataType>
126    inline void MessageQueue<DataType>::prepend(PassOwnPtr<DataType> message)
127    {
128        MutexLocker lock(m_mutex);
129        m_queue.prepend(message.leakPtr());
130        m_condition.signal();
131    }
132
133    template<typename DataType>
134    inline PassOwnPtr<DataType> MessageQueue<DataType>::waitForMessage()
135    {
136        MessageQueueWaitResult exitReason;
137        OwnPtr<DataType> result = waitForMessageFilteredWithTimeout(exitReason, MessageQueue<DataType>::alwaysTruePredicate, infiniteTime());
138        ASSERT(exitReason == MessageQueueTerminated || exitReason == MessageQueueMessageReceived);
139        return result.release();
140    }
141
142    template<typename DataType>
143    template<typename Predicate>
144    inline PassOwnPtr<DataType> MessageQueue<DataType>::waitForMessageFilteredWithTimeout(MessageQueueWaitResult& result, Predicate& predicate, double absoluteTime)
145    {
146        MutexLocker lock(m_mutex);
147        bool timedOut = false;
148
149        DequeConstIterator<DataType*> found = m_queue.end();
150        while (!m_killed && !timedOut && (found = m_queue.findIf(predicate)) == m_queue.end())
151            timedOut = !m_condition.timedWait(m_mutex, absoluteTime);
152
153        ASSERT(!timedOut || absoluteTime != infiniteTime());
154
155        if (m_killed) {
156            result = MessageQueueTerminated;
157            return nullptr;
158        }
159
160        if (timedOut) {
161            result = MessageQueueTimeout;
162            return nullptr;
163        }
164
165        ASSERT_WITH_SECURITY_IMPLICATION(found != m_queue.end());
166        OwnPtr<DataType> message = adoptPtr(*found);
167        m_queue.remove(found);
168        result = MessageQueueMessageReceived;
169        return message.release();
170    }
171
172    template<typename DataType>
173    inline PassOwnPtr<DataType> MessageQueue<DataType>::tryGetMessage()
174    {
175        MutexLocker lock(m_mutex);
176        if (m_killed)
177            return nullptr;
178        if (m_queue.isEmpty())
179            return nullptr;
180
181        return adoptPtr(m_queue.takeFirst());
182    }
183
184    template<typename DataType>
185    inline PassOwnPtr<DataType> MessageQueue<DataType>::tryGetMessageIgnoringKilled()
186    {
187        MutexLocker lock(m_mutex);
188        if (m_queue.isEmpty())
189            return nullptr;
190
191        return adoptPtr(m_queue.takeFirst());
192    }
193
194    template<typename DataType>
195    template<typename Predicate>
196    inline void MessageQueue<DataType>::removeIf(Predicate& predicate)
197    {
198        MutexLocker lock(m_mutex);
199        DequeConstIterator<DataType*> found = m_queue.end();
200        while ((found = m_queue.findIf(predicate)) != m_queue.end()) {
201            DataType* message = *found;
202            m_queue.remove(found);
203            delete message;
204        }
205    }
206
207    template<typename DataType>
208    inline bool MessageQueue<DataType>::isEmpty()
209    {
210        MutexLocker lock(m_mutex);
211        if (m_killed)
212            return true;
213        return m_queue.isEmpty();
214    }
215
216    template<typename DataType>
217    inline void MessageQueue<DataType>::kill()
218    {
219        MutexLocker lock(m_mutex);
220        m_killed = true;
221        m_condition.broadcast();
222    }
223
224    template<typename DataType>
225    inline bool MessageQueue<DataType>::killed() const
226    {
227        MutexLocker lock(m_mutex);
228        return m_killed;
229    }
230} // namespace WTF
231
232using WTF::MessageQueue;
233// MessageQueueWaitResult enum and all its values.
234using WTF::MessageQueueWaitResult;
235using WTF::MessageQueueTerminated;
236using WTF::MessageQueueTimeout;
237using WTF::MessageQueueMessageReceived;
238
239#endif // MessageQueue_h
240