Line data Source code
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_BASE_SWAP_QUEUE_H_
12 : #define WEBRTC_BASE_SWAP_QUEUE_H_
13 :
14 : #include <algorithm>
15 : #include <utility>
16 : #include <vector>
17 :
18 : #include "webrtc/base/checks.h"
19 : #include "webrtc/base/constructormagic.h"
20 : #include "webrtc/base/criticalsection.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 0 : 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 0 : SwapQueue(size_t size,
101 : const T& prototype,
102 : const QueueItemVerifier& queue_item_verifier)
103 0 : : queue_item_verifier_(queue_item_verifier), queue_(size, prototype) {
104 0 : RTC_DCHECK(VerifyQueueSlots());
105 0 : }
106 :
107 : // Resets the queue to have zero content wile maintaining the queue size.
108 0 : void Clear() {
109 0 : rtc::CritScope cs(&crit_queue_);
110 0 : next_write_index_ = 0;
111 0 : next_read_index_ = 0;
112 0 : num_elements_ = 0;
113 0 : }
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 0 : bool Insert(T* input) WARN_UNUSED_RESULT {
122 0 : RTC_DCHECK(input);
123 :
124 0 : rtc::CritScope cs(&crit_queue_);
125 :
126 0 : RTC_DCHECK(queue_item_verifier_(*input));
127 :
128 0 : if (num_elements_ == queue_.size()) {
129 0 : return false;
130 : }
131 :
132 : using std::swap;
133 0 : swap(*input, queue_[next_write_index_]);
134 :
135 0 : ++next_write_index_;
136 0 : if (next_write_index_ == queue_.size()) {
137 0 : next_write_index_ = 0;
138 : }
139 :
140 0 : ++num_elements_;
141 :
142 0 : RTC_DCHECK_LT(next_write_index_, queue_.size());
143 0 : RTC_DCHECK_LE(num_elements_, queue_.size());
144 :
145 0 : 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 0 : bool Remove(T* output) WARN_UNUSED_RESULT {
155 0 : RTC_DCHECK(output);
156 :
157 0 : rtc::CritScope cs(&crit_queue_);
158 :
159 0 : RTC_DCHECK(queue_item_verifier_(*output));
160 :
161 0 : if (num_elements_ == 0) {
162 0 : return false;
163 : }
164 :
165 : using std::swap;
166 0 : swap(*output, queue_[next_read_index_]);
167 :
168 0 : ++next_read_index_;
169 0 : if (next_read_index_ == queue_.size()) {
170 0 : next_read_index_ = 0;
171 : }
172 :
173 0 : --num_elements_;
174 :
175 0 : RTC_DCHECK_LT(next_read_index_, queue_.size());
176 0 : RTC_DCHECK_LE(num_elements_, queue_.size());
177 :
178 0 : return true;
179 : }
180 :
181 : private:
182 : // Verify that the queue slots complies with the ItemVerifier test.
183 0 : bool VerifyQueueSlots() {
184 0 : rtc::CritScope cs(&crit_queue_);
185 0 : for (const auto& v : queue_) {
186 0 : RTC_DCHECK(queue_item_verifier_(v));
187 : }
188 0 : 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 :
211 : #endif // WEBRTC_BASE_SWAP_QUEUE_H_
|
