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 // Default item invariance verifier callback function. |
| 27 template <typename T> |
| 28 bool NoopSwapQueueVerifierFkn(const T&) { |
| 29 return true; |
| 30 } |
| 31 |
| 32 } // namespace internal |
| 33 |
| 34 // Functor to use when supplying a verifier function for the queue item |
| 35 // verifcation. |
| 36 template <typename T, |
| 37 bool (*QueueItemVerifierFunction)(const T&) = |
| 38 internal::NoopSwapQueueVerifierFkn> |
| 39 class SwapQueueItemVerifier { |
| 40 public: |
| 41 bool operator()(const T& t) const { return QueueItemVerifierFunction(t); } |
| 42 }; |
| 43 |
| 44 // This class is a fixed-size queue. A producer calls Insert() to insert |
| 45 // an element of type T at the back of the queue, and a consumer calls |
| 46 // Remove() to remove an element from the front of the queue. It's safe |
| 47 // for the producer(s) and the consumer(s) to access the queue |
| 48 // concurrently, from different threads. |
| 49 // |
| 50 // To avoid the construction, copying, and destruction of Ts that a naive |
| 51 // queue implementation would require, for each "full" T passed from |
| 52 // producer to consumer, SwapQueue<T> passes an "empty" T in the other |
| 53 // direction (an "empty" T is one that contains nothing of value for the |
| 54 // consumer). This bidirectional movement is implemented with swap(). |
| 55 // |
| 56 // // Create queue: |
| 57 // Bottle proto(568); // Prepare an empty Bottle. Heap allocates space for |
| 58 // // 568 ml. |
| 59 // SwapQueue<Bottle> q(N, proto); // Init queue with N copies of proto. |
| 60 // // Each copy allocates on the heap. |
| 61 // // Producer pseudo-code: |
| 62 // Bottle b(568); // Prepare an empty Bottle. Heap allocates space for 568 ml. |
| 63 // loop { |
| 64 // b.Fill(amount); // Where amount <= 568 ml. |
| 65 // q.Insert(&b); // Swap our full Bottle for an empty one from q. |
| 66 // } |
| 67 // |
| 68 // // Consumer pseudo-code: |
| 69 // Bottle b(568); // Prepare an empty Bottle. Heap allocates space for 568 ml. |
| 70 // loop { |
| 71 // q.Remove(&b); // Swap our empty Bottle for the next-in-line full Bottle. |
| 72 // Drink(&b); |
| 73 // } |
| 74 // |
| 75 // For a well-behaved Bottle class, there are no allocations in the |
| 76 // producer, since it just fills an empty Bottle that's already large |
| 77 // enough; no deallocations in the consumer, since it returns each empty |
| 78 // Bottle to the queue after having drunk it; and no copies along the |
| 79 // way, since the queue uses swap() everywhere to move full Bottles in |
| 80 // one direction and empty ones in the other. |
| 81 template <typename T, typename QueueItemVerifier = SwapQueueItemVerifier<T>> |
| 82 class SwapQueue { |
| 83 public: |
| 84 // Creates a queue of size size and fills it with the specified number of |
| 85 // default constructed Ts. |
| 86 explicit SwapQueue(size_t size) : queue_(size) { |
| 87 RTC_DCHECK(VerifyQueueContent()); |
| 88 } |
| 89 |
| 90 // Creates a queue of size size and fills it with the specified number of |
| 91 // default constructed Ts and accepts a functor to use for initializing the |
| 92 // item verification functor. |
| 93 SwapQueue(size_t size, const QueueItemVerifier& queue_item_verifier) |
| 94 : queue_item_verifier_(queue_item_verifier), queue_(size) { |
| 95 RTC_DCHECK(VerifyQueueContent()); |
| 96 } |
| 97 |
| 98 // Creates a queue of size size and fills it with copies of prototype. |
| 99 SwapQueue(size_t size, const T& prototype) : queue_(size, prototype) { |
| 100 RTC_DCHECK(VerifyQueueContent()); |
| 101 } |
| 102 |
| 103 // Creates a queue of size size and fills it with copies of prototype and |
| 104 // accepts a functor to use for initializing the item verification functor. |
| 105 SwapQueue(size_t size, |
| 106 const QueueItemVerifier& queue_item_verifier, |
| 107 const T& prototype) |
| 108 : queue_item_verifier_(queue_item_verifier), queue_(size, prototype) { |
| 109 RTC_DCHECK(VerifyQueueContent()); |
| 110 } |
| 111 |
| 112 // Resets the queue to have zero content wile maintaining the queue size. |
| 113 void Clear() { |
| 114 rtc::CritScope cs(&crit_queue_); |
| 115 next_write_index_ = 0; |
| 116 next_read_index_ = 0; |
| 117 num_elements_ = 0; |
| 118 } |
| 119 |
| 120 // Inserts a "full" T at the back of the queue by swapping *input with an |
| 121 // "empty" T from the queue. |
| 122 // Returns true if the item was inserted or false if not (the queue was full). |
| 123 // When specified, the T given in *input must pass the ItemVerifier() test. |
| 124 // The contents of *input after the call are then also guaranteed to pass the |
| 125 // ItemVerifier() test. |
| 126 bool Insert(T* input) WARN_UNUSED_RESULT { |
| 127 RTC_DCHECK(input); |
| 128 RTC_DCHECK(queue_item_verifier_(*input)); |
| 129 |
| 130 rtc::CritScope cs(&crit_queue_); |
| 131 |
| 132 if (num_elements_ == queue_.size()) { |
| 133 return false; |
| 134 } |
| 135 |
| 136 using std::swap; |
| 137 swap(*input, queue_[next_write_index_]); |
| 138 |
| 139 ++next_write_index_; |
| 140 if (next_write_index_ == queue_.size()) { |
| 141 next_write_index_ = 0; |
| 142 } |
| 143 |
| 144 ++num_elements_; |
| 145 return true; |
| 146 } |
| 147 |
| 148 // Removes the frontmost "full" T from the queue by swapping it with |
| 149 // the "empty" T in *output. |
| 150 // Returns true if an item could be removed or false if not (the queue was |
| 151 // empty). When specified, The T given in *output must pass the ItemVerifier() |
| 152 // test and the contents of *output after the call are then also guaranteed to |
| 153 // pass the ItemVerifier() test. |
| 154 bool Remove(T* output) WARN_UNUSED_RESULT { |
| 155 RTC_DCHECK(output); |
| 156 RTC_DCHECK(queue_item_verifier_(*output)); |
| 157 |
| 158 rtc::CritScope cs(&crit_queue_); |
| 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 return true; |
| 174 } |
| 175 |
| 176 private: |
| 177 // Verify that the queue contents complies with the ItemVerifier test. |
| 178 bool VerifyQueueContent() { |
| 179 rtc::CritScope cs(&crit_queue_); |
| 180 for (const auto& v : queue_) { |
| 181 RTC_DCHECK(queue_item_verifier_(v)); |
| 182 } |
| 183 return true; |
| 184 } |
| 185 |
| 186 QueueItemVerifier queue_item_verifier_; |
| 187 |
| 188 rtc::CriticalSection crit_queue_; |
| 189 |
| 190 // (next_read_index_ + num_elements_) % queue_.size() = |
| 191 // next_write_index_ |
| 192 // 0 <= next_write_index_ < queue.size() |
| 193 size_t next_write_index_ GUARDED_BY(crit_queue_) = 0; |
| 194 // 0 <= next_read_index_ < queue.size() |
| 195 size_t next_read_index_ GUARDED_BY(crit_queue_) = 0; |
| 196 |
| 197 // 0 <= num_elements_ < queue.size() |
| 198 size_t num_elements_ GUARDED_BY(crit_queue_) = 0; |
| 199 |
| 200 // queue_.size() is constant. |
| 201 std::vector<T> queue_ GUARDED_BY(crit_queue_); |
| 202 |
| 203 RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue); |
| 204 }; |
| 205 |
| 206 } // namespace webrtc |
| 207 |
| 208 #endif // WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_ |
OLD | NEW |