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