Home | History | Annotate | Download | only in wtf 
      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:
     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 
     75         static double infiniteTime() { return std::numeric_limits<double>::max(); }
     76 
     77     private:
     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>
     87     MessageQueue<DataType>::~MessageQueue()
     88     {
     89         deleteAllValues(m_queue);
     90     }
     91 
     92     template<typename DataType>
     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>
    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>
    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>
    120     inline PassOwnPtr<DataType> MessageQueue<DataType>::waitForMessage()
    121     {
    122         MessageQueueWaitResult exitReason;
    123         PassOwnPtr<DataType> result = waitForMessageFilteredWithTimeout(exitReason, MessageQueue<DataType>::alwaysTruePredicate, infiniteTime());
    124         ASSERT(exitReason == MessageQueueTerminated || exitReason == MessageQueueMessageReceived);
    125         return result;
    126     }
    127 
    128     template<typename DataType>
    129     template<typename Predicate>
    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 0;
    144         }
    145 
    146         if (timedOut) {
    147             result = MessageQueueTimeout;
    148             return 0;
    149         }
    150 
    151         ASSERT(found != m_queue.end());
    152         DataType* message = *found;
    153         m_queue.remove(found);
    154         result = MessageQueueMessageReceived;
    155         return message;
    156     }
    157 
    158     template<typename DataType>
    159     inline PassOwnPtr<DataType> MessageQueue<DataType>::tryGetMessage()
    160     {
    161         MutexLocker lock(m_mutex);
    162         if (m_killed)
    163             return 0;
    164         if (m_queue.isEmpty())
    165             return 0;
    166 
    167         return m_queue.takeFirst();
    168     }
    169 
    170     template<typename DataType>
    171     template<typename 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>
    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>
    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>
    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