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. | |
kwiberg-webrtc
2015/10/29 14:40:35
By virtue of having grown as long as the comment,
peah-webrtc
2015/10/29 15:24:52
:-)
Done.
| |
27 template <typename T> | |
28 bool NoopSwapQueueVerifierFunction(const T&) { | |
the sun
2015/10/29 12:48:18
nit: NoopSwapQueueItemVerifierFunction
peah-webrtc
2015/10/29 13:35:56
Done.
| |
29 return true; | |
30 } | |
31 | |
32 } // namespace internal | |
33 | |
34 // Functor to use when supplying a verifier function for the queue item | |
35 // verifcation. | |
the sun
2015/10/29 12:48:18
drop "item verification" at end of sentence
peah-webrtc
2015/10/29 13:35:56
Done.
| |
36 template <typename T, | |
37 bool (*QueueItemVerifierFunction)(const T&) = | |
38 internal::NoopSwapQueueVerifierFunction> | |
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. | |
kwiberg-webrtc
2015/10/29 14:40:35
"the specified number of" can be removed.
peah-webrtc
2015/10/29 15:24:52
Done.
| |
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 | |
the sun
2015/10/29 12:48:18
"Same as above, and accepts a functor..."
peah-webrtc
2015/10/29 13:35:56
Done.
| |
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 | |
the sun
2015/10/29 12:48:18
"Same as above, and accepts a functor..."
peah-webrtc
2015/10/29 13:35:56
Done.
| |
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() { | |
kwiberg-webrtc
2015/10/29 14:40:35
VerifyQueueContents
Although it might be better t
peah-webrtc
2015/10/29 15:24:52
Done.
| |
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_; | |
kwiberg-webrtc
2015/10/29 14:40:35
The verifier is allowed to have mutable state, so
peah-webrtc
2015/10/29 15:24:52
Done.
| |
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() | |
the sun
2015/10/29 12:48:18
Should that be <= queue.size().
You could remove
peah-webrtc
2015/10/29 13:35:56
Done.
kwiberg-webrtc
2015/10/29 14:40:35
Yes. (Remember the discussion about whether num_el
peah-webrtc
2015/10/29 15:24:52
I have rewritten it, please check to see whether i
| |
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 |