Changed queue implementation to the proposed vector-based solution.

webrtc/common_audio/swap_queue.h

+/*
+ *  Copyright (c) 2015 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_
+#define WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_
+
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/criticalsection.h"
+
+namespace webrtc {
+
+namespace internal {
+
+// This class is a one-way queue where data is written from one end and read
+// from the other end. The queue can be applied to any swappable objects.

[the sun, 2015/10/26 15:16:20]

objects -> type

[peah-webrtc, 2015/10/26 22:27:02]

Please see below.

+// The queue is safe to access the class concurrently from multiple threads.

[the sun, 2015/10/26 15:16:20]

Remove "the class"

[peah-webrtc, 2015/10/26 22:27:02]

Please see below.

+//
+// Conceptually, the queue maintains an ordered sequence and an unordered bunch

[the sun, 2015/10/26 15:16:21]

Where's the shorter description that me and Karl suggested?

[peah-webrtc, 2015/10/26 22:27:02]

That is a very good question. Seems like something went wrong on the way. Will
add it again and update. Sorry about that!

+// of Ts. At all times, the number of Ts in the sequence and the bunch combined
+// is N, a constant set in the constructor call. The following operations
+// modify the sequence and the bunch:
+//
+//   - The constructor populates the bunch with N Ts (either by
+//     default-constructing them or copy-constructing them from a supplied
+//     prototype T), and leaves the sequence empty.
+//
+//   - Insert() steals the given T and puts it last in the sequence; it gives
+//     back an arbitrary T from the bunch. (Accomplished with a single swap, by
+//     reassigning the physical location of the removed bunch T to the
+//     sequence.)
+//
+//   - Remove() steals the given T and puts it in the bunch; it gives back the
+//     first element in the sequence. (Accomplished with a single swap, by
+//     reassigning the physical location of the removed sequence T to the
+//     bunch.)
+//
+//   - Clear() moves all Ts from the sequence into the bunch. (This is done
+//     without touching any Ts, by reassigning their physical locations.)
+//
+// The intended use is for one client (the producer) to fill a T with useful
+// stuff, and use Insert() to swap it for a T that doesn't contain useful
+// stuff; and for another client (the consumer) to use Remove() to swap a T
+// that doesn't contain useful stuff for a T that does. The point of passing Ts
+// that don't contain anything useful in the reverse direction is to avoid
+// having to make heap allocations at the producer and releasing them at the
+// consumer.
+//
+// Example of queue usage:
+// SwapQueue<int> q(2)); // q contains [0 0];
+// int i = 1;
+// q.Insert(&i); // q contains [1 0], i=0
+//  i = 2;
+// q.Insert(&i); // q contains [1 2], i=0
+// i = -3(;
+// q.Remove(&i); // q contains [-3 2], i=1
+// i = 4;
+// q.Insert(&i); // q contains [4 2], i=-3
+// i = -5;
+// q.Remove(&i); // q contains [4 -5], i=2
+// i = -6;
+// q.Remove(&i); // q contains [-6 -5], i=4
+//
+// It should be noted that if you want the T returned from the bunch at the call
+// to Insert to be of a certain characteristic (e.g., certain size), care must
+// be taken that the queue is initialized with such elements, and that all Ts
+// used as input to Remove also have that characteristic. In order to verify
+// this invariance a callback function can be supplied that verifies this in
+// debug mode (via RTC_DCHECK) for the queue elements. Examples of this can be
+// found in the unit tests.
+
+// (Internal; please don't use outside this file.)
+// Default item invariance verifier callback function.
+template <typename T>
+bool SwapQueueItemVerifierFunction(const T&) {
+  return true;
+}
+
+}  // namespace internal
+
+// Functor to use when supplying a verifier function for the queue item
+// verifcation.
+template <typename T,
+          bool (*QueueItemVerifierFunction)(const T&) =
+              internal::SwapQueueItemVerifierFunction>
+class SwapQueueItemVerifier {
+ public:
+  bool operator()(const T& t) const { return QueueItemVerifierFunction(t); }
+};
+
+// Queue template implementing a queue of elements of type T and with an

[the sun, 2015/10/26 15:16:21]

Too verbose.
"Queue on type T."

[peah-webrtc, 2015/10/26 22:27:02]

Done.

+// optional invariance verifier callback functor that verifies
+// that the queue elements are compliant to a certain requirement.
+template <typename T, typename QueueItemVerifier = SwapQueueItemVerifier<T> >

[the sun, 2015/10/26 15:16:21]

QueueItemVerifier shouldn't be needed as a template argument now that you can
give it to the c-tor.

[peah-webrtc, 2015/10/26 22:27:02]

How do you mean? I still need to have the type of QueueItemVerifier to be able
to store it in a type-safe manner inside the Queue, right? Not sure on how to do
that without the type as a template argument.

[the sun, 2015/10/27 13:51:33]

You're right. The template argument is needed.

[peah-webrtc, 2015/10/29 06:15:14]

Acknowledged.

+class SwapQueue {
+ public:
+  // Creates a queue of size size and fills it with the specified number of
+  // default constructed Ts.
+  explicit SwapQueue(size_t size) : queue_(size) {
+    RTC_DCHECK(VerifyQueueContent());
+  }
+
+  // Creates a queue of size size and fills it with the specified number of
+  // default constructed Ts and accepts a functor to use for initializing the
+  // item verification functor.
+  explicit SwapQueue(size_t size, const QueueItemVerifier& queue_item_verifier)

[the sun, 2015/10/26 15:16:20]

remove "explicit"

[peah-webrtc, 2015/10/26 22:27:02]

Done.

+      : queue_(size), queue_item_verifier_(queue_item_verifier) {
+    RTC_DCHECK(VerifyQueueContent());
+  }
+
+  // Creates a queue of size size and fills it with copies of prototype.
+  SwapQueue(size_t size, const T& prototype) : queue_(size, prototype) {
+    RTC_DCHECK(VerifyQueueContent());
+  }
+
+  // Creates a queue of size size and fills it with copies of prototype and
+  // accepts a functor to use for initializing the item verification functor.
+  SwapQueue(size_t size,
+            QueueItemVerifier const& queue_item_verifier,
+            const T& prototype)
+      : queue_(size, prototype), queue_item_verifier_(queue_item_verifier) {
+    RTC_DCHECK(VerifyQueueContent());
+  }
+
+  // Resets the queue to have zero content.
+  void Clear() {
+    rtc::CritScope cs(&crit_queue_);
+    next_write_index_ = 0;
+    next_read_index_ = 0;
+    num_elements_ = 0;
+  }
+
+  // Inserts a T into the queue by swapping *input with an element already in
+  // the queue (an object from the unordered bunch).
+  // Returns true if the item was inserted or false if not (the queue was full).
+  // When specified, the T given in *input must pass the ItemVerifier() test.
+  // The contents of *input after the call are then also guaranteed to pass the
+  // ItemVerifier() test.
+  bool Insert(T* input) {
+    RTC_DCHECK(input);
+    RTC_DCHECK(queue_item_verifier_(*input));
+
+    rtc::CritScope cs(&crit_queue_);
+
+    if (num_elements_ == queue_.size()) {
+      return false;
+    }
+
+    using std::swap;
+    swap(*input, queue_[next_write_index_]);
+
+    next_write_index_++;
+    if (next_write_index_ == queue_.size()) {
+      next_write_index_ = 0;
+    }
+
+    num_elements_++;
+    return true;
+  }
+
+  // Removes a T from the queue by swapping *output with an element in the
+  // queue.
+  // The T in *output before the call is swapped into the queue (into the
+  // unordered bunch in the queue).
+  // Returns true if an item could be removed or false if not (the queue was
+  // empty). When specified, The T given in *output must pass the ItemVerifier()
+  // test and the contents of *output after the call are then also guaranteed to
+  // pass the ItemVerifier() test.
+  bool Remove(T* output) {
+    RTC_DCHECK(output);
+    RTC_DCHECK(queue_item_verifier_(*output));
+
+    rtc::CritScope cs(&crit_queue_);
+
+    if (num_elements_ == 0) {
+      return false;
+    }
+
+    using std::swap;
+    swap(*output, queue_[next_read_index_]);
+
+    next_read_index_++;
+    if (next_read_index_ == queue_.size()) {
+      next_read_index_ = 0;
+    }
+
+    num_elements_--;
+    return true;
+  }
+
+ private:
+  // Verify that the queue content complies with the ItemVerifier test.
+  bool VerifyQueueContent() {
+    rtc::CritScope cs(&crit_queue_);
+    for (const auto& v : queue_) {
+      RTC_DCHECK(queue_item_verifier_(v));
+    }
+

[the sun, 2015/10/26 15:16:20]

remove blank

[peah-webrtc, 2015/10/26 22:27:02]

Done.

+    return true;
+  }
+
+  // queue_.size() is constant.
+  std::vector<T> queue_ GUARDED_BY(crit_queue_);
+
+  QueueItemVerifier queue_item_verifier_;
+
+  // (next_read_index_ + num_elements_) % queue_.size() =
+  //  next_write_index_
+  // 0 <= next_write_index_ <= queue.size()

[the sun, 2015/10/26 15:16:21]

next_write_index_ < queue.size()

[peah-webrtc, 2015/10/26 22:27:02]

Done.

+  size_t next_write_index_ GUARDED_BY(crit_queue_) = 0;
+  // 0 <= next_read_index_ <= queue.size()

[the sun, 2015/10/26 15:16:21]

next_read_index_ < queue.size()

[peah-webrtc, 2015/10/26 22:27:02]

Done.

+  size_t next_read_index_ GUARDED_BY(crit_queue_) = 0;
+
+  // 0 <= num_elements_ <= queue.size()
+  size_t num_elements_ GUARDED_BY(crit_queue_) = 0;
+
+  rtc::CriticalSection crit_queue_;

[the sun, 2015/10/26 15:16:21]

nit: I would have used the order:

queue_item_verifier_

crit_queue_;
indices
queue_

crit_queue_ becomes a header for the attributes it protects

[peah-webrtc, 2015/10/26 22:27:02]

Makes sense! Will change to that.

[peah-webrtc, 2015/10/26 22:27:02]

Done.

+
+  RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue);
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_COMMON_AUDIO_SWAP_QUEUE_H_