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/ThreadingPrimitives.h"
38
39namespace WTF {
40
41    enum MessageQueueWaitResult {
42        MessageQueueTerminated,       // Queue was destroyed while waiting for message.
43        MessageQueueTimeout,          // Timeout was specified and it expired.
44        MessageQueueMessageReceived   // A message was successfully received and returned.
45    };
46
47    // The queue takes ownership of messages and transfer it to the new owner
48    // when messages are fetched from the queue.
49    // Essentially, MessageQueue acts as a queue of OwnPtr<DataType>.
50    template<typename DataType>
51    class MessageQueue {
52        WTF_MAKE_NONCOPYABLE(MessageQueue);
53    public:
54        MessageQueue() : m_killed(false) { }
55        ~MessageQueue();
56
57        // Returns true if the queue is still alive, false if the queue has been killed.
58        bool append(PassOwnPtr<DataType>);
59        void appendAndKill(PassOwnPtr<DataType>);
60        bool appendAndCheckEmpty(PassOwnPtr<DataType>);
61        void prepend(PassOwnPtr<DataType>);
62
63        PassOwnPtr<DataType> waitForMessage();
64        PassOwnPtr<DataType> tryGetMessage();
65        PassOwnPtr<DataType> tryGetMessageIgnoringKilled();
66        template<typename Predicate>
67        PassOwnPtr<DataType> waitForMessageFilteredWithTimeout(MessageQueueWaitResult&, Predicate&, double absoluteTime);
68
69        template<typename Predicate>
70        void removeIf(Predicate&);
71
72        void kill();
73        bool killed() const;
74
75        // The result of isEmpty() is only valid if no other thread is manipulating the queue at the same time.
76        bool isEmpty();
77
78        static double infiniteTime() { return std::numeric_limits<double>::max(); }
79
80    private:
81        static bool alwaysTruePredicate(DataType*) { return true; }
82
83        mutable Mutex m_mutex;
84        ThreadCondition m_condition;
85        Deque<DataType*> m_queue;
86        bool m_killed;
87    };
88
89    template<typename DataType>
90    MessageQueue<DataType>::~MessageQueue()
91    {
92        deleteAllValues(m_queue);
93    }
94
95    template<typename DataType>
96    inline bool MessageQueue<DataType>::append(PassOwnPtr<DataType> message)
97    {
98        MutexLocker lock(m_mutex);
99        m_queue.append(message.leakPtr());
100        m_condition.signal();
101        return !m_killed;
102    }
103
104    template<typename DataType>
105    inline void MessageQueue<DataType>::appendAndKill(PassOwnPtr<DataType> message)
106    {
107        MutexLocker lock(m_mutex);
108        m_queue.append(message.leakPtr());
109        m_killed = true;
110        m_condition.broadcast();
111    }
112
113    // Returns true if the queue was empty before the item was added.
114    template<typename DataType>
115    inline bool MessageQueue<DataType>::appendAndCheckEmpty(PassOwnPtr<DataType> message)
116    {
117        MutexLocker lock(m_mutex);
118        bool wasEmpty = m_queue.isEmpty();
119        m_queue.append(message.leakPtr());
120        m_condition.signal();
121        return wasEmpty;
122    }
123
124    template<typename DataType>
125    inline void MessageQueue<DataType>::prepend(PassOwnPtr<DataType> message)
126    {
127        MutexLocker lock(m_mutex);
128        m_queue.prepend(message.leakPtr());
129        m_condition.signal();
130    }
131
132    template<typename DataType>
133    inline PassOwnPtr<DataType> MessageQueue<DataType>::waitForMessage()
134    {
135        MessageQueueWaitResult exitReason;
136        OwnPtr<DataType> result = waitForMessageFilteredWithTimeout(exitReason, MessageQueue<DataType>::alwaysTruePredicate, infiniteTime());
137        ASSERT(exitReason == MessageQueueTerminated || exitReason == MessageQueueMessageReceived);
138        return result.release();
139    }
140
141    template<typename DataType>
142    template<typename Predicate>
143    inline PassOwnPtr<DataType> MessageQueue<DataType>::waitForMessageFilteredWithTimeout(MessageQueueWaitResult& result, Predicate& predicate, double absoluteTime)
144    {
145        MutexLocker lock(m_mutex);
146        bool timedOut = false;
147
148        DequeConstIterator<DataType*> found = m_queue.end();
149        while (!m_killed && !timedOut && (found = m_queue.findIf(predicate)) == m_queue.end())
150            timedOut = !m_condition.timedWait(m_mutex, absoluteTime);
151
152        ASSERT(!timedOut || absoluteTime != infiniteTime());
153
154        if (m_killed) {
155            result = MessageQueueTerminated;
156            return nullptr;
157        }
158
159        if (timedOut) {
160            result = MessageQueueTimeout;
161            return nullptr;
162        }
163
164        ASSERT(found != m_queue.end());
165        OwnPtr<DataType> message = adoptPtr(*found);
166        m_queue.remove(found);
167        result = MessageQueueMessageReceived;
168        return message.release();
169    }
170
171    template<typename DataType>
172    inline PassOwnPtr<DataType> MessageQueue<DataType>::tryGetMessage()
173    {
174        MutexLocker lock(m_mutex);
175        if (m_killed)
176            return nullptr;
177        if (m_queue.isEmpty())
178            return nullptr;
179
180        return adoptPtr(m_queue.takeFirst());
181    }
182
183    template<typename DataType>
184    inline PassOwnPtr<DataType> MessageQueue<DataType>::tryGetMessageIgnoringKilled()
185    {
186        MutexLocker lock(m_mutex);
187        if (m_queue.isEmpty())
188            return nullptr;
189
190        return adoptPtr(m_queue.takeFirst());
191    }
192
193    template<typename DataType>
194    template<typename Predicate>
195    inline void MessageQueue<DataType>::removeIf(Predicate& predicate)
196    {
197        MutexLocker lock(m_mutex);
198        DequeConstIterator<DataType*> found = m_queue.end();
199        while ((found = m_queue.findIf(predicate)) != m_queue.end()) {
200            DataType* message = *found;
201            m_queue.remove(found);
202            delete message;
203        }
204    }
205
206    template<typename DataType>
207    inline bool MessageQueue<DataType>::isEmpty()
208    {
209        MutexLocker lock(m_mutex);
210        if (m_killed)
211            return true;
212        return m_queue.isEmpty();
213    }
214
215    template<typename DataType>
216    inline void MessageQueue<DataType>::kill()
217    {
218        MutexLocker lock(m_mutex);
219        m_killed = true;
220        m_condition.broadcast();
221    }
222
223    template<typename DataType>
224    inline bool MessageQueue<DataType>::killed() const
225    {
226        MutexLocker lock(m_mutex);
227        return m_killed;
228    }
229} // namespace WTF
230
231using WTF::MessageQueue;
232// MessageQueueWaitResult enum and all its values.
233using WTF::MessageQueueWaitResult;
234using WTF::MessageQueueTerminated;
235using WTF::MessageQueueTimeout;
236using WTF::MessageQueueMessageReceived;
237
238#endif // MessageQueue_h
239