OLD | NEW |
1 /* | 1 /* |
2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. | 2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license | 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 | 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 | 6 * tree. An additional intellectual property rights grant can be found |
7 * in the file PATENTS. All contributing project authors may | 7 * in the file PATENTS. All contributing project authors may |
8 * be found in the AUTHORS file in the root of the source tree. | 8 * be found in the AUTHORS file in the root of the source tree. |
9 */ | 9 */ |
10 | 10 |
11 #ifndef WEBRTC_BASE_SWAP_QUEUE_H_ | 11 #ifndef WEBRTC_BASE_SWAP_QUEUE_H_ |
12 #define WEBRTC_BASE_SWAP_QUEUE_H_ | 12 #define WEBRTC_BASE_SWAP_QUEUE_H_ |
13 | 13 |
14 #include <algorithm> | |
15 #include <utility> | |
16 #include <vector> | |
17 | 14 |
18 #include "webrtc/base/checks.h" | 15 // This header is deprecated and is just left here temporarily during |
19 #include "webrtc/base/constructormagic.h" | 16 // refactoring. See https://bugs.webrtc.org/7634 for more details. |
20 #include "webrtc/base/criticalsection.h" | 17 #include "webrtc/rtc_base/swap_queue.h" |
21 | |
22 namespace webrtc { | |
23 | |
24 namespace internal { | |
25 | |
26 // (Internal; please don't use outside this file.) | |
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 default constructed Ts. | |
84 explicit SwapQueue(size_t size) : queue_(size) { | |
85 RTC_DCHECK(VerifyQueueSlots()); | |
86 } | |
87 | |
88 // Same as above and accepts an item verification functor. | |
89 SwapQueue(size_t size, const QueueItemVerifier& queue_item_verifier) | |
90 : queue_item_verifier_(queue_item_verifier), queue_(size) { | |
91 RTC_DCHECK(VerifyQueueSlots()); | |
92 } | |
93 | |
94 // Creates a queue of size size and fills it with copies of prototype. | |
95 SwapQueue(size_t size, const T& prototype) : queue_(size, prototype) { | |
96 RTC_DCHECK(VerifyQueueSlots()); | |
97 } | |
98 | |
99 // Same as above and accepts an item verification functor. | |
100 SwapQueue(size_t size, | |
101 const T& prototype, | |
102 const QueueItemVerifier& queue_item_verifier) | |
103 : queue_item_verifier_(queue_item_verifier), queue_(size, prototype) { | |
104 RTC_DCHECK(VerifyQueueSlots()); | |
105 } | |
106 | |
107 // Resets the queue to have zero content wile maintaining the queue size. | |
108 void Clear() { | |
109 rtc::CritScope cs(&crit_queue_); | |
110 next_write_index_ = 0; | |
111 next_read_index_ = 0; | |
112 num_elements_ = 0; | |
113 } | |
114 | |
115 // Inserts a "full" T at the back of the queue by swapping *input with an | |
116 // "empty" T from the queue. | |
117 // Returns true if the item was inserted or false if not (the queue was full). | |
118 // When specified, the T given in *input must pass the ItemVerifier() test. | |
119 // The contents of *input after the call are then also guaranteed to pass the | |
120 // ItemVerifier() test. | |
121 bool Insert(T* input) RTC_WARN_UNUSED_RESULT { | |
122 RTC_DCHECK(input); | |
123 | |
124 rtc::CritScope cs(&crit_queue_); | |
125 | |
126 RTC_DCHECK(queue_item_verifier_(*input)); | |
127 | |
128 if (num_elements_ == queue_.size()) { | |
129 return false; | |
130 } | |
131 | |
132 using std::swap; | |
133 swap(*input, queue_[next_write_index_]); | |
134 | |
135 ++next_write_index_; | |
136 if (next_write_index_ == queue_.size()) { | |
137 next_write_index_ = 0; | |
138 } | |
139 | |
140 ++num_elements_; | |
141 | |
142 RTC_DCHECK_LT(next_write_index_, queue_.size()); | |
143 RTC_DCHECK_LE(num_elements_, queue_.size()); | |
144 | |
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) RTC_WARN_UNUSED_RESULT { | |
155 RTC_DCHECK(output); | |
156 | |
157 rtc::CritScope cs(&crit_queue_); | |
158 | |
159 RTC_DCHECK(queue_item_verifier_(*output)); | |
160 | |
161 if (num_elements_ == 0) { | |
162 return false; | |
163 } | |
164 | |
165 using std::swap; | |
166 swap(*output, queue_[next_read_index_]); | |
167 | |
168 ++next_read_index_; | |
169 if (next_read_index_ == queue_.size()) { | |
170 next_read_index_ = 0; | |
171 } | |
172 | |
173 --num_elements_; | |
174 | |
175 RTC_DCHECK_LT(next_read_index_, queue_.size()); | |
176 RTC_DCHECK_LE(num_elements_, queue_.size()); | |
177 | |
178 return true; | |
179 } | |
180 | |
181 private: | |
182 // Verify that the queue slots complies with the ItemVerifier test. | |
183 bool VerifyQueueSlots() { | |
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 rtc::CriticalSection crit_queue_; | |
192 | |
193 // TODO(peah): Change this to use std::function() once we can use C++11 std | |
194 // lib. | |
195 QueueItemVerifier queue_item_verifier_ GUARDED_BY(crit_queue_); | |
196 | |
197 // (next_read_index_ + num_elements_) % queue_.size() = | |
198 // next_write_index_ | |
199 size_t next_write_index_ GUARDED_BY(crit_queue_) = 0; | |
200 size_t next_read_index_ GUARDED_BY(crit_queue_) = 0; | |
201 size_t num_elements_ GUARDED_BY(crit_queue_) = 0; | |
202 | |
203 // queue_.size() is constant. | |
204 std::vector<T> queue_ GUARDED_BY(crit_queue_); | |
205 | |
206 RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue); | |
207 }; | |
208 | |
209 } // namespace webrtc | |
210 | 18 |
211 #endif // WEBRTC_BASE_SWAP_QUEUE_H_ | 19 #endif // WEBRTC_BASE_SWAP_QUEUE_H_ |
OLD | NEW |