| // Ceres Solver - A fast non-linear least squares minimizer |
| // Copyright 2018 Google Inc. All rights reserved. |
| // http://ceres-solver.org/ |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are met: |
| // |
| // * Redistributions of source code must retain the above copyright notice, |
| // this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above copyright notice, |
| // this list of conditions and the following disclaimer in the documentation |
| // and/or other materials provided with the distribution. |
| // * Neither the name of Google Inc. nor the names of its contributors may be |
| // used to endorse or promote products derived from this software without |
| // specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
| // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| // POSSIBILITY OF SUCH DAMAGE. |
| // |
| // Author: vitus@google.com (Michael Vitus) |
| |
| #ifndef CERES_INTERNAL_CONCURRENT_QUEUE_H_ |
| #define CERES_INTERNAL_CONCURRENT_QUEUE_H_ |
| |
| #include <condition_variable> |
| #include <mutex> |
| #include <queue> |
| #include <thread> |
| |
| #include "glog/logging.h" |
| |
| namespace ceres { |
| namespace internal { |
| |
| // A thread-safe multi-producer, multi-consumer queue for queueing items that |
| // are typically handled asynchronously by multiple threads. The ConcurrentQueue |
| // has two states which only affect the Wait call: |
| // |
| // (1) Waiters have been enabled (enabled by default or calling |
| // EnableWaiters). The call to Wait will block until an item is available. |
| // Push and pop will operate as expected. |
| // |
| // (2) StopWaiters has been called. All threads blocked in a Wait() call will |
| // be woken up and pop any available items from the queue. All future Wait |
| // requests will either return an element from the queue or return |
| // immediately if no element is present. Push and pop will operate as |
| // expected. |
| // |
| // A common use case is using the concurrent queue as an interface for |
| // scheduling tasks for a set of thread workers: |
| // |
| // ConcurrentQueue<Task> task_queue; |
| // |
| // [Worker threads]: |
| // Task task; |
| // while(task_queue.Wait(&task)) { |
| // ... |
| // } |
| // |
| // [Producers]: |
| // task_queue.Push(...); |
| // .. |
| // task_queue.Push(...); |
| // ... |
| // // Signal worker threads to stop blocking on Wait and terminate. |
| // task_queue.StopWaiters(); |
| // |
| template <typename T> |
| class ConcurrentQueue { |
| public: |
| // Defaults the queue to blocking on Wait calls. |
| ConcurrentQueue() : wait_(true) {} |
| |
| // Atomically push an element onto the queue. If a thread was waiting for an |
| // element, wake it up. |
| void Push(const T& value) { |
| std::unique_lock<std::mutex> lock(mutex_); |
| queue_.push(value); |
| work_pending_condition_.notify_one(); |
| } |
| |
| // Atomically pop an element from the queue. If an element is present, return |
| // true. If the queue was empty, return false. |
| bool Pop(T* value) { |
| CHECK(value != nullptr); |
| |
| std::unique_lock<std::mutex> lock(mutex_); |
| return PopUnlocked(value); |
| } |
| |
| // Atomically pop an element from the queue. Blocks until one is available or |
| // StopWaiters is called. Returns true if an element was successfully popped |
| // from the queue, otherwise returns false. |
| bool Wait(T* value) { |
| CHECK(value != nullptr); |
| |
| std::unique_lock<std::mutex> lock(mutex_); |
| work_pending_condition_.wait(lock, |
| [&]() { return !(wait_ && queue_.empty()); }); |
| |
| return PopUnlocked(value); |
| } |
| |
| // Unblock all threads waiting to pop a value from the queue, and they will |
| // exit Wait() without getting a value. All future Wait requests will return |
| // immediately if no element is present until EnableWaiters is called. |
| void StopWaiters() { |
| std::unique_lock<std::mutex> lock(mutex_); |
| wait_ = false; |
| work_pending_condition_.notify_all(); |
| } |
| |
| // Enable threads to block on Wait calls. |
| void EnableWaiters() { |
| std::unique_lock<std::mutex> lock(mutex_); |
| wait_ = true; |
| } |
| |
| private: |
| // Pops an element from the queue. If an element is present, return |
| // true. If the queue was empty, return false. Not thread-safe. Must acquire |
| // the lock before calling. |
| bool PopUnlocked(T* value) { |
| if (queue_.empty()) { |
| return false; |
| } |
| |
| *value = queue_.front(); |
| queue_.pop(); |
| |
| return true; |
| } |
| |
| // The mutex controls read and write access to the queue_ and stop_ |
| // variables. It is also used to block the calling thread until an element is |
| // available to pop from the queue. |
| std::mutex mutex_; |
| std::condition_variable work_pending_condition_; |
| |
| std::queue<T> queue_; |
| // If true, signals that callers of Wait will block waiting to pop an |
| // element off the queue. |
| bool wait_; |
| }; |
| |
| |
| } // namespace internal |
| } // namespace ceres |
| |
| #endif // CERES_INTERNAL_CONCURRENT_QUEUE_H_ |