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/Threading.h>
38 
39 namespace 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:
MessageQueue()54         MessageQueue() : m_killed(false) { }
55         ~MessageQueue();
56 
57         void append(PassOwnPtr<DataType>);
58         bool appendAndCheckEmpty(PassOwnPtr<DataType>);
59         void prepend(PassOwnPtr<DataType>);
60 
61         PassOwnPtr<DataType> waitForMessage();
62         PassOwnPtr<DataType> tryGetMessage();
63         template<typename Predicate>
64         PassOwnPtr<DataType> waitForMessageFilteredWithTimeout(MessageQueueWaitResult&, Predicate&, double absoluteTime);
65 
66         template<typename Predicate>
67         void removeIf(Predicate&);
68 
69         void kill();
70         bool killed() const;
71 
72         // The result of isEmpty() is only valid if no other thread is manipulating the queue at the same time.
73         bool isEmpty();
74 
infiniteTime()75         static double infiniteTime() { return std::numeric_limits<double>::max(); }
76 
77     private:
alwaysTruePredicate(DataType *)78         static bool alwaysTruePredicate(DataType*) { return true; }
79 
80         mutable Mutex m_mutex;
81         ThreadCondition m_condition;
82         Deque<DataType*> m_queue;
83         bool m_killed;
84     };
85 
86     template<typename DataType>
~MessageQueue()87     MessageQueue<DataType>::~MessageQueue()
88     {
89         deleteAllValues(m_queue);
90     }
91 
92     template<typename DataType>
append(PassOwnPtr<DataType> message)93     inline void MessageQueue<DataType>::append(PassOwnPtr<DataType> message)
94     {
95         MutexLocker lock(m_mutex);
96         m_queue.append(message.leakPtr());
97         m_condition.signal();
98     }
99 
100     // Returns true if the queue was empty before the item was added.
101     template<typename DataType>
appendAndCheckEmpty(PassOwnPtr<DataType> message)102     inline bool MessageQueue<DataType>::appendAndCheckEmpty(PassOwnPtr<DataType> message)
103     {
104         MutexLocker lock(m_mutex);
105         bool wasEmpty = m_queue.isEmpty();
106         m_queue.append(message.leakPtr());
107         m_condition.signal();
108         return wasEmpty;
109     }
110 
111     template<typename DataType>
prepend(PassOwnPtr<DataType> message)112     inline void MessageQueue<DataType>::prepend(PassOwnPtr<DataType> message)
113     {
114         MutexLocker lock(m_mutex);
115         m_queue.prepend(message.leakPtr());
116         m_condition.signal();
117     }
118 
119     template<typename DataType>
waitForMessage()120     inline PassOwnPtr<DataType> MessageQueue<DataType>::waitForMessage()
121     {
122         MessageQueueWaitResult exitReason;
123         OwnPtr<DataType> result = waitForMessageFilteredWithTimeout(exitReason, MessageQueue<DataType>::alwaysTruePredicate, infiniteTime());
124         ASSERT(exitReason == MessageQueueTerminated || exitReason == MessageQueueMessageReceived);
125         return result.release();
126     }
127 
128     template<typename DataType>
129     template<typename Predicate>
waitForMessageFilteredWithTimeout(MessageQueueWaitResult & result,Predicate & predicate,double absoluteTime)130     inline PassOwnPtr<DataType> MessageQueue<DataType>::waitForMessageFilteredWithTimeout(MessageQueueWaitResult& result, Predicate& predicate, double absoluteTime)
131     {
132         MutexLocker lock(m_mutex);
133         bool timedOut = false;
134 
135         DequeConstIterator<DataType*> found = m_queue.end();
136         while (!m_killed && !timedOut && (found = m_queue.findIf(predicate)) == m_queue.end())
137             timedOut = !m_condition.timedWait(m_mutex, absoluteTime);
138 
139         ASSERT(!timedOut || absoluteTime != infiniteTime());
140 
141         if (m_killed) {
142             result = MessageQueueTerminated;
143             return nullptr;
144         }
145 
146         if (timedOut) {
147             result = MessageQueueTimeout;
148             return nullptr;
149         }
150 
151         ASSERT(found != m_queue.end());
152         OwnPtr<DataType> message = adoptPtr(*found);
153         m_queue.remove(found);
154         result = MessageQueueMessageReceived;
155         return message.release();
156     }
157 
158     template<typename DataType>
tryGetMessage()159     inline PassOwnPtr<DataType> MessageQueue<DataType>::tryGetMessage()
160     {
161         MutexLocker lock(m_mutex);
162         if (m_killed)
163             return nullptr;
164         if (m_queue.isEmpty())
165             return nullptr;
166 
167         return adoptPtr(m_queue.takeFirst());
168     }
169 
170     template<typename DataType>
171     template<typename Predicate>
removeIf(Predicate & predicate)172     inline void MessageQueue<DataType>::removeIf(Predicate& predicate)
173     {
174         MutexLocker lock(m_mutex);
175         // See bug 31657 for why this loop looks so weird
176         while (true) {
177             DequeConstIterator<DataType*> found = m_queue.findIf(predicate);
178             if (found == m_queue.end())
179                 break;
180 
181             DataType* message = *found;
182             m_queue.remove(found);
183             delete message;
184        }
185     }
186 
187     template<typename DataType>
isEmpty()188     inline bool MessageQueue<DataType>::isEmpty()
189     {
190         MutexLocker lock(m_mutex);
191         if (m_killed)
192             return true;
193         return m_queue.isEmpty();
194     }
195 
196     template<typename DataType>
kill()197     inline void MessageQueue<DataType>::kill()
198     {
199         MutexLocker lock(m_mutex);
200         m_killed = true;
201         m_condition.broadcast();
202     }
203 
204     template<typename DataType>
killed()205     inline bool MessageQueue<DataType>::killed() const
206     {
207         MutexLocker lock(m_mutex);
208         return m_killed;
209     }
210 } // namespace WTF
211 
212 using WTF::MessageQueue;
213 // MessageQueueWaitResult enum and all its values.
214 using WTF::MessageQueueWaitResult;
215 using WTF::MessageQueueTerminated;
216 using WTF::MessageQueueTimeout;
217 using WTF::MessageQueueMessageReceived;
218 
219 #endif // MessageQueue_h
220