OLD | NEW |
(Empty) | |
| 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 |
| 21 namespace webrtc { |
| 22 |
| 23 namespace internal { |
| 24 |
| 25 // (Internal; please don't use outside this file.) |
| 26 template <typename T> |
| 27 bool NoopSwapQueueItemVerifierFunction(const T&) { |
| 28 return true; |
| 29 } |
| 30 |
| 31 } // namespace internal |
| 32 |
| 33 // Functor to use when supplying a verifier function for the queue. |
| 34 template <typename T, |
| 35 bool (*QueueItemVerifierFunction)(const T&) = |
| 36 internal::NoopSwapQueueItemVerifierFunction> |
| 37 class 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. |
| 79 template <typename T, typename QueueItemVerifier = SwapQueueItemVerifier<T>> |
| 80 class 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_ |
OLD | NEW |