New implementation of generic cyclic buffer.

webrtc/base/numerics/cyclic_buffer.h

+/*
+ *  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.
+ */
+
+#ifndef WEBRTC_BASE_NUMERICS_CYCLIC_BUFFER_H_
+#define WEBRTC_BASE_NUMERICS_CYCLIC_BUFFER_H_
+
+#include <utility>  // for move
+
+#include "webrtc/base/checks.h"
+
+namespace webrtc {
+
+enum GrowthPolicy { ASSERT = 0, DISCARD_OLDEST, GROW_BUFFER };
+
+template <typename T, GrowthPolicy policy>
+class CyclicBuffer {
+ public:
+  explicit CyclicBuffer(size_t size);
+  ~CyclicBuffer();
+
+  // TODO(terelius): Check what happens if size_ == capacity_ == 1
+  // TODO(terelius): Overload for rvalue references. Refactor to avoid code
+  // duplication.
+  void push_back(const T& elem) {
+    T* new_position = extend_back();
+    *new_position = elem;
+  }
+
+  void push_back(T&& elem) {
+    T* new_position = extend_back();
+    *new_position = std::move(elem);
+  }
+
+  void push_front(const T& elem) {
+    T* new_position = extend_front();
+    *new_position = elem;
+  }
+
+  void push_front(T&& elem) {
+    T* new_position = extend_front();
+    *new_position = std::move(elem);
+  }
+
+  void pop_front() {
+    RTC_DCHECK_GT(size_, 0);
+    if (size_ == 1) {
+      head_ = tail_ = nullptr;
+      size_ = 0;
+      return;
+    }
+
+    head_++;
+    if (head_ == buffer_end_)
+      head_ = buffer_begin_;
+    size_--;
+  }
+
+  void pop_back() {
+    RTC_DCHECK_GT(size_, 0);
+    if (size_ == 1) {
+      head_ = tail_ = nullptr;
+      size_ = 0;
+      return;
+    }
+
+    if (tail_ == buffer_begin_)
+      tail_ = buffer_end_;
+    tail_--;
+    size_--;
+  }
+
+  T& front() {
+    RTC_DCHECK_GT(size_, 0);
+    return *head_;
+  }
+
+  const T& front() const {
+    RTC_DCHECK_GT(size_, 0);
+    return *head_;
+  }
+
+  T& back() {
+    RTC_DCHECK_GT(size_, 0);
+    return *tail_;
+  }
+
+  const T& back() const {
+    RTC_DCHECK_GT(size_, 0);
+    return *tail_;
+  }
+
+  size_t size() const { return size_; }
+
+  size_t capacity() const { return capacity_; }
+
+  // TODO(terelius): Implement resize() instead? Make it private?
+  void Grow(size_t new_capacity) {
+    RTC_DCHECK_GT(new_capacity, capacity_);
+    T* new_buffer = new T[new_capacity];
+    T* read_it = head_;
+    T* write_it = new_buffer;
+    if (size_ > 0) {
+      // Copy the contents to the new buffer
+      do {
+        *write_it = *read_it;
+        write_it++;
+        read_it++;
+        if (read_it == buffer_end_)
+          read_it = buffer_begin_;
+      } while (read_it != tail_);
+    }
+
+    delete[] buffer_begin_;
+    buffer_begin_ = new_buffer;
+    buffer_end_ = buffer_begin_ + new_capacity;
+    capacity_ = new_capacity;
+    head_ = buffer_begin_;
+    tail_ = buffer_begin_ + size_ - 1;
+  }
+
+ private:
+  T* extend_back();
+  T* extend_front();
+
+  T* buffer_begin_;
+  T* buffer_end_;
+  T* head_;
+  T* tail_;
+  size_t capacity_;
+  size_t size_;
+};
+
+template <typename T, GrowthPolicy policy>
+CyclicBuffer<T, policy>::CyclicBuffer(size_t capacity)
+    : buffer_begin_(nullptr),
+      buffer_end_(nullptr),
+      head_(nullptr),
+      tail_(nullptr),
+      capacity_(capacity),
+      size_(0) {
+  RTC_CHECK(capacity > 0);
+  buffer_begin_ = new T[capacity];
+  buffer_end_ = buffer_begin_ + capacity;
+}
+
+template <typename T, GrowthPolicy policy>
+CyclicBuffer<T, policy>::~CyclicBuffer() {
+  delete[] buffer_begin_;
+}
+
+// TODO(terelius): Handle capacity 0?
+// TODO(terelius): Verify correctness for capacity 1.
+template <typename T, GrowthPolicy policy>
+T* CyclicBuffer<T, policy>::extend_back() {
+  if (size_ == 0) {
+    head_ = tail_ = buffer_begin_;
+    size_++;
+    return tail_;
+  }
+
+  // Ensure there is enough space to insert the element.
+  if (policy == ASSERT) {
+    RTC_DCHECK_LT(size_, capacity_);
+  } else if (policy == DISCARD_OLDEST && size_ == capacity_) {
+    pop_front();  // Redundant if we discard oldest element below.
+  } else if (policy == GROW_BUFFER && size_ == capacity_) {
+    Grow(2 * capacity_ + 1);
+  }
+  // Find next place to insert.
+  tail_++;
+  if (tail_ == buffer_end_)
+    tail_ = buffer_begin_;
+
+  // Discard oldest element if buffer is full.
+  if (tail_ == head_) {
+    head_++;
+    if (head_ == buffer_end_)
+      head_ = buffer_begin_;
+    size_--;
+  }
+
+  // Insert element.
+  size_++;
+  return tail_;
+}
+
+// TODO(terelius): Handle capacity 0?
+// TODO(terelius): Verify correctness for capacity 1.
+template <typename T, GrowthPolicy policy>
+T* CyclicBuffer<T, policy>::extend_front() {
+  if (size_ == 0) {
+    head_ = tail_ = buffer_begin_;
+    size_++;
+    return tail_;
+  }
+
+  // Ensure there is enough space to insert the element.
+  if (policy == ASSERT) {
+    RTC_DCHECK_LT(size_, capacity_);
+  } else if (policy == DISCARD_OLDEST && size_ == capacity_) {
+    pop_back();  // Redundant if we discard oldest element below.
+  } else if (policy == GROW_BUFFER && size_ == capacity_) {
+    Grow(2 * capacity_ + 1);
+  }
+  // Find next place to insert.
+  if (head_ == buffer_begin_)
+    head_ = buffer_end_;
+  head_--;
+
+  // Discard oldest element if buffer is full.
+  if (head_ == tail_) {
+    if (tail_ == buffer_begin_)
+      tail_ = buffer_end_;
+    tail_--;
+    size_--;
+  }
+
+  // Insert element.
+  size_++;
+  return head_;
+}
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_BASE_NUMERICS_CYCLIC_BUFFER_H_