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