New implementation of generic cyclic buffer.

webrtc/base/numerics/cyclic_buffer_unittest.cc

+/*
+ *  Copyright (c) 2017 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.
+ */
+
+#include <deque>
+#include <list>
+#include <string>
+
+#include "webrtc/base/numerics/cyclic_buffer.h"
+#include "webrtc/base/timeutils.h"
+#include "webrtc/base/random.h"
+#include "webrtc/test/gtest.h"
+
+namespace {
+
+struct Usage {
+  size_t default_constructor = 0;
+  size_t cast_constructor = 0;
+  size_t copy_constructor = 0;
+  size_t move_constructor = 0;
+  size_t move_cast_constructor = 0;
+  size_t destructors = 0;
+  size_t copy_assignment = 0;
+  size_t cast_assignment = 0;
+  size_t move_assignment = 0;
+  size_t move_cast_assignment = 0;
+  size_t casts = 0;
+};
+
+// void ResetMagicTypeUsage(Usage& usage) {
+//   usage.default_constructor = 0;
+//   usage.cast_constructor = 0;
+//   usage.copy_constructor = 0;
+//   usage.move_constructor = 0;
+//   usage.move_cast_constructor = 0;
+//   usage.destructors = 0;
+//   usage.copy_assignment = 0;
+//   usage.cast_assignment = 0;
+//   usage.move_assignment = 0;
+//   usage.move_cast_assignment = 0;
+//   usage.casts = 0;
+// }
+
+// void PrintMagicTypeUsage(const Usage& usage) {
+//   printf("%zu default constructor calls\n", usage.default_constructor);
+//   printf("%zu cast constructor calls\n", usage.cast_constructor);
+//   printf("%zu copy constructor calls\n", usage.copy_constructor);
+//   printf("%zu move cast constructor calls\n", usage.move_cast_constructor);
+//   printf("%zu move constructor calls\n", usage.move_constructor);
+//   printf("%zu destructor calls\n", usage.destructors);
+//   printf("%zu copy assignments calls\n", usage.copy_assignment);
+//   printf("%zu cast assignments calls\n", usage.cast_assignment);
+//   printf("%zu move assignments calls\n", usage.move_assignment);
+//   printf("%zu move cast assignments calls\n", usage.move_cast_assignment);
+//   printf("%zu casts\n", usage.casts);
+// }
+
+// Wrapper type to detect memory management problems, like using memcpy to copy
+// data without running the constructor, using the data before it has been
+// assigned, or using the data after it has been deleted.
+template <typename T>
+class MagicType {
+ public:
+  MagicType() : magic_(this), constructed_(true), assigned_(false) {
+    usage.default_constructor++;
+  }
+
+  MagicType(const T& value)  // we actually want implicit casts here
+      : value_(value), magic_(this), constructed_(true), assigned_(true) {
+    usage.cast_constructor++;
+  }
+
+  MagicType(T&& value)  // we actually want implicit casts here
+      : value_(std::move(value)),
+        magic_(this),
+        constructed_(true),
+        assigned_(true) {
+    usage.move_cast_constructor++;
+  }
+
+  MagicType(const MagicType<T>& m)
+      : value_(m.value_),
+        magic_(this),
+        constructed_(m.constructed_),
+        assigned_(m.assigned_) {
+    RTC_DCHECK(m.magic_ == &m);
+    RTC_DCHECK(m.constructed_);
+    usage.copy_constructor++;
+  }
+
+  MagicType(MagicType<T>&& m)
+      : value_(std::move(m.value_)),
+        magic_(this),
+        constructed_(m.constructed_),
+        assigned_(m.assigned_) {
+    RTC_DCHECK(m.magic_ == &m);
+    RTC_DCHECK(m.constructed_);
+    usage.move_constructor++;
+  }
+
+  ~MagicType() {
+    RTC_DCHECK(magic_ == this);
+    RTC_DCHECK(constructed_);
+    magic_ = nullptr;
+    constructed_ = false;
+    assigned_ = false;
+    usage.destructors++;
+  }
+
+  MagicType<T>& operator=(const T& value) {
+    RTC_DCHECK(magic_ == this);
+    RTC_DCHECK(constructed_);
+    value_ = value;
+    assigned_ = true;
+    usage.cast_assignment++;
+    return *this;
+  }
+
+  MagicType<T>& operator=(T&& value) {
+    RTC_DCHECK(magic_ == this);
+    RTC_DCHECK(constructed_);
+    value_ = value;
+    assigned_ = true;
+    usage.move_cast_assignment++;
+    return *this;
+  }
+
+  MagicType<T>& operator=(const MagicType<T>& m) {
+    RTC_DCHECK(m.magic_ == &m);
+    RTC_DCHECK(m.constructed_);
+    RTC_DCHECK(magic_ == this);
+    RTC_DCHECK(constructed_);
+    value_ = m.value_;
+    assigned_ = m.assigned_;
+    usage.copy_assignment++;
+    return *this;
+  }
+
+  MagicType<T>& operator=(MagicType<T>&& m) {
+    RTC_DCHECK(m.magic_ == &m);
+    RTC_DCHECK(m.constructed_);
+    RTC_DCHECK(magic_ == this);
+    RTC_DCHECK(constructed_);
+    value_ = m.value_;
+    assigned_ = m.assigned_;
+    usage.move_assignment++;
+    return *this;
+  }
+
+  operator T() const {
+    RTC_DCHECK(magic_ == this);
+    RTC_DCHECK(constructed_);
+    RTC_DCHECK(assigned_);
+    usage.casts++;
+    return value_;
+  }
+
+  static Usage usage;
+
+ private:
+  T value_;
+  MagicType<T>* magic_;
+  bool constructed_;
+  bool assigned_;
+};
+
+template <typename T>
+Usage MagicType<T>::usage;
+}  // namespace
+
+namespace webrtc {
+
+TEST(CyclicBufferTest, EmptyBuffer) {
+  CyclicBuffer<int, GrowthPolicy::ASSERT> buffer(5);
+  EXPECT_EQ(buffer.size(), 0u);
+}
+
+TEST(CyclicBufferTest, PushBack) {
+  CyclicBuffer<int, GrowthPolicy::ASSERT> buffer(5);
+  buffer.push_back(45);
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 45);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.push_back(98);
+  EXPECT_EQ(buffer.size(), 2u);
+  EXPECT_EQ(buffer.back(), 98);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.push_back(35);
+  EXPECT_EQ(buffer.size(), 3u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 45);
+}
+
+TEST(CyclicBufferTest, PopFront) {
+  CyclicBuffer<int, GrowthPolicy::ASSERT> buffer(5);
+  buffer.push_back(45);
+  buffer.push_back(98);
+  buffer.push_back(35);
+  EXPECT_EQ(buffer.size(), 3u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 2u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 98);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 35);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 0u);
+}
+
+TEST(CyclicBufferTest, PushFront) {
+  CyclicBuffer<int, GrowthPolicy::ASSERT> buffer(5);
+  buffer.push_front(45);
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 45);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.push_front(98);
+  EXPECT_EQ(buffer.size(), 2u);
+  EXPECT_EQ(buffer.back(), 45);
+  EXPECT_EQ(buffer.front(), 98);
+  buffer.push_front(35);
+  EXPECT_EQ(buffer.size(), 3u);
+  EXPECT_EQ(buffer.back(), 45);
+  EXPECT_EQ(buffer.front(), 35);
+}
+
+TEST(CyclicBufferTest, PopBack) {
+  CyclicBuffer<int, GrowthPolicy::ASSERT> buffer(5);
+  buffer.push_front(45);
+  buffer.push_front(98);
+  buffer.push_front(35);
+  EXPECT_EQ(buffer.size(), 3u);
+  EXPECT_EQ(buffer.back(), 45);
+  EXPECT_EQ(buffer.front(), 35);
+  buffer.pop_back();
+  EXPECT_EQ(buffer.size(), 2u);
+  EXPECT_EQ(buffer.back(), 98);
+  EXPECT_EQ(buffer.front(), 35);
+  buffer.pop_back();
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 35);
+  buffer.pop_back();
+  EXPECT_EQ(buffer.size(), 0u);
+}
+
+TEST(CyclicBufferTest, BufferWithCapacityOne) {
+  CyclicBuffer<int, GrowthPolicy::ASSERT> buffer(1);
+  // Insert and remove one element from a buffer with capacity 1.
+  buffer.push_back(45);
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 45);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 0u);
+  // Verify that we are still in a valid state by attempting a another
+  // operation.
+  buffer.push_back(21);
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 21);
+  EXPECT_EQ(buffer.front(), 21);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 0u);
+}
+
+TEST(CyclicBufferTest, BufferMagicType) {
+  CyclicBuffer<MagicType<int>, GrowthPolicy::ASSERT> buffer(3);
+  buffer.push_back(45);
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 45);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.push_back(98);
+  EXPECT_EQ(buffer.size(), 2u);
+  EXPECT_EQ(buffer.back(), 98);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.push_back(35);
+  EXPECT_EQ(buffer.size(), 3u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 45);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 2u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 98);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 1u);
+  EXPECT_EQ(buffer.back(), 35);
+  EXPECT_EQ(buffer.front(), 35);
+  buffer.pop_front();
+  EXPECT_EQ(buffer.size(), 0u);
+}
+
+template <typename Buffer>
+int64_t TestIntBufferPerformance(Buffer* buffer,
+                                 size_t elements,
+                                 size_t capacity) {
+  int64_t start = rtc::TimeMicros();
+  for (size_t i = 0; i < elements; i++) {
+    if (buffer->size() == capacity)
+      buffer->pop_front();
+    buffer->push_back(i);
+  }
+  int64_t stop = rtc::TimeMicros();
+  return stop - start;
+}
+
+template <typename Buffer>
+int64_t TestStringBufferPerformance(Buffer* buffer,
+                                    size_t elements,
+                                    size_t capacity) {
+  int64_t start = rtc::TimeMicros();
+  for (size_t i = 0; i < elements; i++) {
+    if (buffer->size() == capacity)
+      buffer->pop_front();
+    buffer->push_back(std::to_string(i));
+  }
+  int64_t stop = rtc::TimeMicros();
+  return stop - start;
+}
+
+TEST(CyclicBufferTest, DISABLED_PerformanceInt) {
+  CyclicBuffer<int, GrowthPolicy::ASSERT> cyclic(1023u);
+  std::deque<int> double_ended;
+  // printf("Time used by std::list = %ld\n", TestListPerformance(1000000u,
+  // 1023u));
+
+  int64_t deque_time = 0;
+  int64_t cyclicbuffer_time = 0;
+  for (int i = 0; i < 100; i++) {
+    deque_time += TestIntBufferPerformance(&double_ended, 1000000u, 1023u);
+    cyclicbuffer_time += TestIntBufferPerformance(&cyclic, 1000000u, 1023u);
+  }
+  printf("Time used by std::deque = %ld\n", deque_time / 100);
+  printf("Time used by CyclicBuffer = %ld\n", cyclicbuffer_time / 100);
+}
+
+TEST(CyclicBufferTest, DISABLED_PerformanceDouble) {
+  CyclicBuffer<double, GrowthPolicy::ASSERT> cyclic(1023u);
+  std::deque<double> double_ended;
+
+  int64_t deque_time = 0;
+  int64_t cyclicbuffer_time = 0;
+  for (int i = 0; i < 100; i++) {
+    deque_time += TestIntBufferPerformance(&double_ended, 1000000u, 1023u);
+    cyclicbuffer_time += TestIntBufferPerformance(&cyclic, 1000000u, 1023u);
+  }
+  printf("Time used by std::deque = %ld\n", deque_time / 100);
+  printf("Time used by CyclicBuffer = %ld\n", cyclicbuffer_time / 100);
+}
+
+TEST(CyclicBufferTest, DISABLED_PerformanceString) {
+  CyclicBuffer<std::string, GrowthPolicy::ASSERT> cyclic(1023u);
+  std::deque<std::string> double_ended;
+
+  int64_t deque_time = 0;
+  int64_t cyclicbuffer_time = 0;
+  for (int i = 0; i < 100; i++) {
+    deque_time += TestStringBufferPerformance(&double_ended, 1000000u, 1023u);
+    cyclicbuffer_time += TestStringBufferPerformance(&cyclic, 1000000u, 1023u);
+  }
+  printf("Time used by std::deque = %ld\n", deque_time / 100);
+  printf("Time used by CyclicBuffer = %ld\n", cyclicbuffer_time / 100);
+}
+
+TEST(CyclicBufferTest, DISABLED_PerformanceMagicTypeString) {
+  CyclicBuffer<MagicType<std::string>, GrowthPolicy::ASSERT> cyclic(1023u);
+  std::deque<MagicType<std::string>> double_ended;
+
+  int64_t deque_time = 0;
+  int64_t cyclicbuffer_time = 0;
+  for (int i = 0; i < 100; i++) {
+    // ResetMagicTypeUsage(MagicType<std::string>::usage);
+    deque_time += TestStringBufferPerformance(&double_ended, 1000000u, 1023u);
+    // printf("std::deque performance\n");
+    // PrintMagicTypeUsage(MagicType<std::string>::usage);
+
+    // ResetMagicTypeUsage(MagicType<std::string>::usage);
+    cyclicbuffer_time += TestStringBufferPerformance(&cyclic, 1000000u, 1023u);
+    // printf("CyclicBuffer performance\n");
+    // PrintMagicTypeUsage(MagicType<std::string>::usage);
+    // printf("\n");
+  }
+  printf("Time used by std::deque = %ld\n", deque_time / 100);
+  printf("Time used by CyclicBuffer = %ld\n", cyclicbuffer_time / 100);
+}
+
+void BehavesAsDeque(size_t operations, size_t capacity, uint64_t seed) {
+  Random random(seed);
+  std::deque<uint32_t> q;
+  CyclicBuffer<uint32_t, GrowthPolicy::ASSERT> cq(capacity);
+
+  for (size_t i = 0; i < operations; i++) {
+    bool insert = random.Rand<bool>();
+    bool front = random.Rand<bool>();
+    if ((insert && q.size() < capacity) || q.empty()) {
+      uint32_t value = random.Rand<uint32_t>();
+      if (front) {
+        q.push_front(value);
+        cq.push_front(value);
+      } else {
+        q.push_back(value);
+        cq.push_back(value);
+      }
+    } else {
+      if (front) {
+        q.pop_front();
+        cq.pop_front();
+      } else {
+        q.pop_back();
+        cq.pop_back();
+      }
+    }
+
+    EXPECT_EQ(q.size(), cq.size());
+    if (!q.empty()) {
+      EXPECT_EQ(q.front(), cq.front());
+      EXPECT_EQ(q.back(), cq.back());
+    }
+  }
+}
+
+TEST(CyclicBufferTest, BehavesAsDeque) {
+  BehavesAsDeque(1000000, 1023, 123454321);
+}
+
+TEST(CyclicBufferTest, BehavesAsDequeSmallBuffer) {
+  BehavesAsDeque(1000000, 4, 123454321);
+}
+
+}  // namespace webrtc