1/* 2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11#ifndef WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_ 12#define WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_ 13 14#include <algorithm> 15#include <utility> 16#include <vector> 17 18#include "webrtc/base/checks.h" 19#include "webrtc/base/criticalsection.h" 20 21namespace webrtc { 22 23namespace internal { 24 25// (Internal; please don't use outside this file.) 26template <typename T> 27bool NoopSwapQueueItemVerifierFunction(const T&) { 28 return true; 29} 30 31} // namespace internal 32 33// Functor to use when supplying a verifier function for the queue. 34template <typename T, 35 bool (*QueueItemVerifierFunction)(const T&) = 36 internal::NoopSwapQueueItemVerifierFunction> 37class SwapQueueItemVerifier { 38 public: 39 bool operator()(const T& t) const { return QueueItemVerifierFunction(t); } 40}; 41 42// This class is a fixed-size queue. A producer calls Insert() to insert 43// an element of type T at the back of the queue, and a consumer calls 44// Remove() to remove an element from the front of the queue. It's safe 45// for the producer(s) and the consumer(s) to access the queue 46// concurrently, from different threads. 47// 48// To avoid the construction, copying, and destruction of Ts that a naive 49// queue implementation would require, for each "full" T passed from 50// producer to consumer, SwapQueue<T> passes an "empty" T in the other 51// direction (an "empty" T is one that contains nothing of value for the 52// consumer). This bidirectional movement is implemented with swap(). 53// 54// // Create queue: 55// Bottle proto(568); // Prepare an empty Bottle. Heap allocates space for 56// // 568 ml. 57// SwapQueue<Bottle> q(N, proto); // Init queue with N copies of proto. 58// // Each copy allocates on the heap. 59// // Producer pseudo-code: 60// Bottle b(568); // Prepare an empty Bottle. Heap allocates space for 568 ml. 61// loop { 62// b.Fill(amount); // Where amount <= 568 ml. 63// q.Insert(&b); // Swap our full Bottle for an empty one from q. 64// } 65// 66// // Consumer pseudo-code: 67// Bottle b(568); // Prepare an empty Bottle. Heap allocates space for 568 ml. 68// loop { 69// q.Remove(&b); // Swap our empty Bottle for the next-in-line full Bottle. 70// Drink(&b); 71// } 72// 73// For a well-behaved Bottle class, there are no allocations in the 74// producer, since it just fills an empty Bottle that's already large 75// enough; no deallocations in the consumer, since it returns each empty 76// Bottle to the queue after having drunk it; and no copies along the 77// way, since the queue uses swap() everywhere to move full Bottles in 78// one direction and empty ones in the other. 79template <typename T, typename QueueItemVerifier = SwapQueueItemVerifier<T>> 80class SwapQueue { 81 public: 82 // Creates a queue of size size and fills it with default constructed Ts. 83 explicit SwapQueue(size_t size) : queue_(size) { 84 RTC_DCHECK(VerifyQueueSlots()); 85 } 86 87 // Same as above and accepts an item verification functor. 88 SwapQueue(size_t size, const QueueItemVerifier& queue_item_verifier) 89 : queue_item_verifier_(queue_item_verifier), queue_(size) { 90 RTC_DCHECK(VerifyQueueSlots()); 91 } 92 93 // Creates a queue of size size and fills it with copies of prototype. 94 SwapQueue(size_t size, const T& prototype) : queue_(size, prototype) { 95 RTC_DCHECK(VerifyQueueSlots()); 96 } 97 98 // Same as above and accepts an item verification functor. 99 SwapQueue(size_t size, 100 const T& prototype, 101 const QueueItemVerifier& queue_item_verifier) 102 : queue_item_verifier_(queue_item_verifier), queue_(size, prototype) { 103 RTC_DCHECK(VerifyQueueSlots()); 104 } 105 106 // Resets the queue to have zero content wile maintaining the queue size. 107 void Clear() { 108 rtc::CritScope cs(&crit_queue_); 109 next_write_index_ = 0; 110 next_read_index_ = 0; 111 num_elements_ = 0; 112 } 113 114 // Inserts a "full" T at the back of the queue by swapping *input with an 115 // "empty" T from the queue. 116 // Returns true if the item was inserted or false if not (the queue was full). 117 // When specified, the T given in *input must pass the ItemVerifier() test. 118 // The contents of *input after the call are then also guaranteed to pass the 119 // ItemVerifier() test. 120 bool Insert(T* input) WARN_UNUSED_RESULT { 121 RTC_DCHECK(input); 122 123 rtc::CritScope cs(&crit_queue_); 124 125 RTC_DCHECK(queue_item_verifier_(*input)); 126 127 if (num_elements_ == queue_.size()) { 128 return false; 129 } 130 131 using std::swap; 132 swap(*input, queue_[next_write_index_]); 133 134 ++next_write_index_; 135 if (next_write_index_ == queue_.size()) { 136 next_write_index_ = 0; 137 } 138 139 ++num_elements_; 140 141 RTC_DCHECK_LT(next_write_index_, queue_.size()); 142 RTC_DCHECK_LE(num_elements_, queue_.size()); 143 144 return true; 145 } 146 147 // Removes the frontmost "full" T from the queue by swapping it with 148 // the "empty" T in *output. 149 // Returns true if an item could be removed or false if not (the queue was 150 // empty). When specified, The T given in *output must pass the ItemVerifier() 151 // test and the contents of *output after the call are then also guaranteed to 152 // pass the ItemVerifier() test. 153 bool Remove(T* output) WARN_UNUSED_RESULT { 154 RTC_DCHECK(output); 155 156 rtc::CritScope cs(&crit_queue_); 157 158 RTC_DCHECK(queue_item_verifier_(*output)); 159 160 if (num_elements_ == 0) { 161 return false; 162 } 163 164 using std::swap; 165 swap(*output, queue_[next_read_index_]); 166 167 ++next_read_index_; 168 if (next_read_index_ == queue_.size()) { 169 next_read_index_ = 0; 170 } 171 172 --num_elements_; 173 174 RTC_DCHECK_LT(next_read_index_, queue_.size()); 175 RTC_DCHECK_LE(num_elements_, queue_.size()); 176 177 return true; 178 } 179 180 private: 181 // Verify that the queue slots complies with the ItemVerifier test. 182 bool VerifyQueueSlots() { 183 rtc::CritScope cs(&crit_queue_); 184 for (const auto& v : queue_) { 185 RTC_DCHECK(queue_item_verifier_(v)); 186 } 187 return true; 188 } 189 190 rtc::CriticalSection crit_queue_; 191 192 // TODO(peah): Change this to use std::function() once we can use C++11 std 193 // lib. 194 QueueItemVerifier queue_item_verifier_ GUARDED_BY(crit_queue_); 195 196 // (next_read_index_ + num_elements_) % queue_.size() = 197 // next_write_index_ 198 size_t next_write_index_ GUARDED_BY(crit_queue_) = 0; 199 size_t next_read_index_ GUARDED_BY(crit_queue_) = 0; 200 size_t num_elements_ GUARDED_BY(crit_queue_) = 0; 201 202 // queue_.size() is constant. 203 std::vector<T> queue_ GUARDED_BY(crit_queue_); 204 205 RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue); 206}; 207 208} // namespace webrtc 209 210#endif // WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_ 211