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