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_MODULES_SWAP_QUEUE_H_
+#define WEBRTC_MODULES_SWAP_QUEUE_H_

[kwiberg-webrtc, 2015/10/14 14:10:16]

Don't worry, you'll get it right one of these days!

[peah-webrtc, 2015/10/15 07:35:00]

Done.

[peah-webrtc, 2015/10/15 07:35:00]

:-)

+
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/criticalsection.h"
+
+namespace webrtc {
+
+// This class is a one-way queue where data is written from one end and read
+// from the other end.
+// It is safe to access the class concurrently from multiple threads.
+// The queueable objects must all be swappable as the Insert and Remove methods

[kwiberg-webrtc, 2015/10/14 14:10:16]

"queuable" -> "enqueued", maybe?

[peah-webrtc, 2015/10/15 07:34:59]

Used a slightly different wording.

+// work by swapping the "empty" and "full" items with the existing content in
+// the queue. When doing an Insert, the "empty" content in the next write
+// position in the queue is swapped for the "full" item in the input to Insert,
+// and that queue position then becomes "full", while the input item to Insert
+// becomes "empty". In contrast, when doing a Remove, the "empty" content in the
+// input to Remove is swapped for the "full" element in the next read position
+// in the queue. After the call the input to Remove is "full" and the element
+// in the queue is "empty".

[kwiberg-webrtc, 2015/10/14 14:10:16]

Perhaps still a bit too imprecise. How about something like this:

// Conceptually, the queue maintains an ordered sequence and an unordered bunch
// 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.)
//
//   - Clean() 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.

Note that I didn't reveal the implementation detail that the "bunch"
is also an ordered sequence; this in turn allowed me to talk about
just "the sequence" and "the bunch" instead of, say, "the 'full'
sequence" and "the 'empty' sequence".

[peah-webrtc, 2015/10/15 07:34:59]

This looks super. I used it as it is, and added some additional documentation
before and after it. Please behold.

+// This is illustrated in the example below:
+//
+// Example of queue usage:
+// SwapQueue<int> q(2)); // q contains [0(empty) 0(empty)];
+// int i = 1;
+// q.Insert(&i); // q contains [1(full) 0(empty)], i=0
+//  i = 2;
+// q.Insert(&i); // q contains [1(full) 2(full)], i=0
+// i = -3(;
+// q.Remove(&i); // q contains [-3(empty) 2(full)], i=1
+// i = 4;
+// q.Insert(&i); // q contains [4(full) 2(full)], i=-3
+// i = -5;
+// q.Remove(&i); // q contains [4(full) -5(empty)], i=2
+// i = -6;
+// q.Remove(&i); // q contains [-6(empty) -5(empty)], i=4
+//
+// It should be noted that if you want the "empty" Ts that are returned from the
+// Insert to be of a certain characteristic (e.g., certain size), care must be
+// taken that the queue is initialized with such elements, and all Ts that are
+// used as input to Remove 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.
+
+// Default item invariance verifier callback function.

[the sun, 2015/10/14 13:05:21]

Please use the term "invariant" as that is more common in programming than
invariance (which is more common in the world of signals...)
https://www.google.se/search?q=invariant+definition&oq=invariant

also, prepend "SwapQueue" since this is in the vast webrtc:: namespace.

[kwiberg-webrtc, 2015/10/14 14:10:16]

You could conceivably also put it in its own namespace, e.g. "internal". That's
the suggestion I got for webrtc/base/buffer.h.

[peah-webrtc, 2015/10/15 07:35:00]

I'm still not fully happy with invariant. I change it to verifier, does that
sound ok?

[peah-webrtc, 2015/10/15 07:35:00]

Done.

[kwiberg-webrtc, 2015/10/15 08:55:40]

That works too. But the usual meaning of "invariant" in the context of data
structures is simply "predicate that always holds", so checking an invariant is
exactly what the supplied function does.

[peah-webrtc, 2015/10/26 08:56:57]

Not sure about the conclusion, should we go for invariant or verifier?
The new functor implementation makes things a bit different as the verifier does
no longer need to be invariant over time.

+template <typename T>
+bool DefaultItemInvarianceVerifier(const T&) {
+  return true;
+}
+
+// Queue template implementing a queue of elements of type T and with an
+// optional invariance verifier callback function that verifies
+// that the queue elements are compliant to a certain requirement.
+template <typename T,
+          bool (*ItemInvarianceVerifier)(const T&) =

[the sun, 2015/10/14 13:05:21]

I think CheckItemInvariant was a better name...

[peah-webrtc, 2015/10/15 07:34:59]

Hmm, I'm not either superhappy about the current name. I'll discuss it more in
the comment below.

+              DefaultItemInvarianceVerifier>

[kwiberg-webrtc, 2015/10/14 14:10:16]

Not too happy with this name. Maybe simply "ItemChecker"?

[peah-webrtc, 2015/10/15 07:35:00]

Me neither. I changed it now to ItemVerifier. In my mind, the function should
verify the properties of the items. ItemChecker is close to that but I think it
is a bit more vague. CheckItemInvariant I think is a bit narrow since there is
actually not any strict requirement that the items should be invariant.

Any opinions or further suggestions?

[kwiberg-webrtc, 2015/10/15 08:55:40]

That we allow the user to require an invariant (which is just a predicate) to
hold is no restriction. The user is free to specify as lax a predicate as she
likes. That said, "verifier" works too.

[peah-webrtc, 2015/10/26 08:56:57]

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) { CheckQueueInvariance(); }
+
+  // Creates a queue of size and fills it with copies of prototype.

[kwiberg-webrtc, 2015/10/14 14:10:16]

"size" -> "size size".

[peah-webrtc, 2015/10/15 07:34:59]

Done.

+  SwapQueue(size_t size, const T& prototype) : queue_(size, prototype) {
+    CheckQueueInvariance();
+  }
+
+  // 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 Y into the queue. The "full" input is swapped with the "empty"

[the sun, 2015/10/14 13:05:21]

Y -> T

"Insert a T into the queue by swapping *input with an element already in the
queue.
Returns true if the item was inserted or false if not (the queue was full).
The T given in *input must pass a CheckItemInvariant() test.
The contents of *input after the call are guaranteed to also pass a
CheckItemInvariant() test."

[kwiberg-webrtc, 2015/10/14 14:10:16]

"Y" -> "T"

[peah-webrtc, 2015/10/15 07:35:00]

Done.

[peah-webrtc, 2015/10/15 07:35:00]

Looks super. I did some minor editing, in particular about that the test is
optional. Please behold!

+  // content of type T present in the queue.
+  // Returns false if the queue was already  full (in which case no insert
+  //  is performed), and true if not.
+  bool Insert(T* input) {
+    RTC_DCHECK(input);
+    RTC_DCHECK(ItemInvarianceVerifier(*input));
+
+    rtc::CritScope cs(&crit_queue_);
+
+    if (num_elements_ == queue_.size()) {

[the sun, 2015/10/14 13:05:21]

Thank you! :)

[kwiberg-webrtc, 2015/10/14 14:10:16]

Aww! Don't give in just because he's more intimidating than I am!

[peah-webrtc, 2015/10/15 07:35:00]

:D

[peah-webrtc, 2015/10/15 07:35:00]

This is tricky, and I'm a bit split in this. 
I've been bashed through many years with that braces were needed and required
for security reasons and I definitely agree that they are safer and avoids
python-style indentation errors.
However,...., I personally prefer compact code, and therefore definitely I
prefer not to use braces.

+      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 chunk of data from the queue. The "full" queue element is swapped

[the sun, 2015/10/14 13:05:21]

"Remove a T from the queue by swapping *output with an element in the queue.
Returns true if an item could be removed or false if not (the queue was empty).
The T given in *output must pass a CheckItemInvariant() test."

[kwiberg-webrtc, 2015/10/14 14:10:16]

"chunk of data" -> "T"

[peah-webrtc, 2015/10/15 07:34:59]

Done.

[peah-webrtc, 2015/10/15 07:35:00]

Nice! I changed to that, but revised it a bit. Please behold!

+  // with the existing "empty" content of output.
+  // Returns false if the queue was already empty (om which case no element is
+  // removed), and true if not.
+  bool Remove(T* output) {
+    RTC_DCHECK(output);
+    RTC_DCHECK(ItemInvarianceVerifier(*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:
+  // Checks queue invariance.
+  void CheckQueueInvariance() {

[kwiberg-webrtc, 2015/10/14 14:10:16]

invariance -> invariants. Otherwise, it sounds as if the whole queue is
invariant, i.e. constant.

Also, queue -> element, since that's what it checks.

End result: CheckElementInvariants.

[peah-webrtc, 2015/10/15 07:35:00]

I think that what we do is to verify the compliance of the elements to
ItemVerifier, which actually not necessarily should mean that the elements are
invariants. I changed it to reflect that.

Please behold and comment!

+    rtc::CritScope cs(&crit_queue_);
+    for (const auto& v : queue_) {
+      RTC_DCHECK(ItemInvarianceVerifier(v));
+    }
+  }
+
+  // queue_.size() is constant.
+  std::vector<T> queue_ GUARDED_BY(crit_queue_);
+
+  // (next_read_index_ + num_elements_) % queue_.size() =
+  //  next_write_index_
+  // 0 <= next_write_index_ <= queue.size()
+  size_t next_write_index_ GUARDED_BY(crit_queue_) = 0;
+  // 0 <= next_read_index_ <= queue.size()
+  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_;
+
+  RTC_DISALLOW_COPY_AND_ASSIGN(SwapQueue);
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_