1 files changed, 378 insertions, 0 deletions
diff --git a/src/seastar/include/seastar/core/circular_buffer_fixed_capacity.hh b/src/seastar/include/seastar/core/circular_buffer_fixed_capacity.hh
new file mode 100644
index 000000000..7e7c093e2
--- /dev/null
+++ b/src/seastar/include/seastar/core/circular_buffer_fixed_capacity.hh
@@ -0,0 +1,378 @@
+/*
+ * This file is open source software, licensed to you under the terms
+ * of the Apache License, Version 2.0 (the "License").  See the NOTICE file
+ * distributed with this work for additional information regarding copyright
+ * ownership.  You may not use this file except in compliance with the License.
+ *
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+/*
+ * Copyright (C) 2017 ScyllaDB
+ */
+
+#pragma once
+
+// A fixed capacity double-ended queue container that can be efficiently
+// extended (and shrunk) from both ends.  Implementation is a single
+// storage vector.
+//
+// Similar to libstdc++'s std::deque, except that it uses a single level
+// store, and so is more efficient for simple stored items.
+
+#include <type_traits>
+#include <cstddef>
+#include <iterator>
+#include <utility>
+
+
+/// \file
+
+namespace seastar {
+
+/// A fixed-capacity container (like boost::static_vector) that can insert
+/// and remove at both ends (like std::deque). Does not allocate.
+///
+/// Does not perform overflow checking when size exceeds capacity.
+///
+/// \tparam T type of objects stored in the container; must be noexcept move enabled
+/// \tparam Capacity maximum number of objects that can be stored in the container; must be a power of 2
+template <typename T, size_t Capacity>
+class circular_buffer_fixed_capacity {
+    size_t _begin = 0;
+    size_t _end = 0;
+    union maybe_storage {
+        T data;
+        maybe_storage() noexcept {}
+        ~maybe_storage() {}
+    };
+    maybe_storage _storage[Capacity];
+private:
+    static size_t mask(size_t idx) { return idx % Capacity; }
+    T* obj(size_t idx) { return &_storage[mask(idx)].data; }
+    const T* obj(size_t idx) const { return &_storage[mask(idx)].data; }
+public:
+    static_assert((Capacity & (Capacity - 1)) == 0, "capacity must be a power of two");
+    static_assert(std::is_nothrow_move_constructible<T>::value && std::is_nothrow_move_assignable<T>::value,
+            "circular_buffer_fixed_capacity only supports nothrow-move value types");
+    using value_type = T;
+    using size_type = size_t;
+    using reference = T&;
+    using pointer = T*;
+    using const_reference = const T&;
+    using const_pointer = const T*;
+    using difference_type = ssize_t;
+public:
+    template <typename ValueType>
+    class cbiterator {
+        using holder = std::conditional_t<std::is_const<ValueType>::value, const maybe_storage, maybe_storage>;
+        holder* _start;
+        size_t _idx;
+    private:
+        cbiterator(holder* start, size_t idx) noexcept : _start(start), _idx(idx) {}
+    public:
+        using iterator_category = std::random_access_iterator_tag;
+        using value_type = ValueType;
+        using difference_type = ssize_t;
+        using pointer = ValueType*;
+        using reference = ValueType&;
+    public:
+        cbiterator();
+        ValueType& operator*() const { return _start[mask(_idx)].data; }
+        ValueType* operator->() const { return &operator*(); }
+        // prefix
+        cbiterator& operator++() {
+            ++_idx;
+            return *this;
+        }
+        // postfix
+        cbiterator operator++(int) {
+            auto v = *this;
+            ++_idx;
+            return v;
+        }
+        // prefix
+        cbiterator& operator--() {
+            --_idx;
+            return *this;
+        }
+        // postfix
+        cbiterator operator--(int) {
+            auto v = *this;
+            --_idx;
+            return v;
+        }
+        cbiterator operator+(difference_type n) const {
+            return cbiterator{_start, _idx + n};
+        }
+        friend cbiterator operator+(difference_type n, cbiterator i) {
+            return i + n;
+        }
+        cbiterator operator-(difference_type n) const {
+            return cbiterator{_start, _idx - n};
+        }
+        cbiterator& operator+=(difference_type n) {
+            _idx += n;
+            return *this;
+        }
+        cbiterator& operator-=(difference_type n) {
+            _idx -= n;
+            return *this;
+        }
+        bool operator==(const cbiterator& rhs) const {
+            return _idx == rhs._idx;
+        }
+        bool operator!=(const cbiterator& rhs) const {
+            return _idx != rhs._idx;
+        }
+        bool operator<(const cbiterator& rhs) const {
+            return ssize_t(_idx - rhs._idx) < 0;
+        }
+        bool operator>(const cbiterator& rhs) const {
+            return ssize_t(_idx - rhs._idx) > 0;
+        }
+        bool operator<=(const cbiterator& rhs) const {
+            return ssize_t(_idx - rhs._idx) <= 0;
+        }
+        bool operator>=(const cbiterator& rhs) const {
+            return ssize_t(_idx - rhs._idx) >= 0;
+        }
+        difference_type operator-(const cbiterator& rhs) const {
+            return _idx - rhs._idx;
+        }
+        friend class circular_buffer_fixed_capacity;
+    };
+public:
+    using iterator = cbiterator<T>;
+    using const_iterator = cbiterator<const T>;
+public:
+    circular_buffer_fixed_capacity() = default;
+    circular_buffer_fixed_capacity(circular_buffer_fixed_capacity&& x) noexcept;
+    ~circular_buffer_fixed_capacity();
+    circular_buffer_fixed_capacity& operator=(circular_buffer_fixed_capacity&& x) noexcept;
+    void push_front(const T& data);
+    void push_front(T&& data);
+    template <typename... A>
+    T& emplace_front(A&&... args);
+    void push_back(const T& data);
+    void push_back(T&& data);
+    template <typename... A>
+    T& emplace_back(A&&... args);
+    T& front();
+    T& back();
+    void pop_front();
+    void pop_back();
+    bool empty() const;
+    size_t size() const;
+    size_t capacity() const;
+    T& operator[](size_t idx);
+    void clear();
+    iterator begin() {
+        return iterator(_storage, _begin);
+    }
+    const_iterator begin() const {
+        return const_iterator(_storage, _begin);
+    }
+    iterator end() {
+        return iterator(_storage, _end);
+    }
+    const_iterator end() const {
+        return const_iterator(_storage, _end);
+    }
+    const_iterator cbegin() const {
+        return const_iterator(_storage, _begin);
+    }
+    const_iterator cend() const {
+        return const_iterator(_storage, _end);
+    }
+    iterator erase(iterator first, iterator last);
+};
+
+template <typename T, size_t Capacity>
+inline
+bool
+circular_buffer_fixed_capacity<T, Capacity>::empty() const {
+    return _begin == _end;
+}
+
+template <typename T, size_t Capacity>
+inline
+size_t
+circular_buffer_fixed_capacity<T, Capacity>::size() const {
+    return _end - _begin;
+}
+
+template <typename T, size_t Capacity>
+inline
+size_t
+circular_buffer_fixed_capacity<T, Capacity>::capacity() const {
+    return Capacity;
+}
+
+template <typename T, size_t Capacity>
+inline
+circular_buffer_fixed_capacity<T, Capacity>::circular_buffer_fixed_capacity(circular_buffer_fixed_capacity&& x) noexcept
+        : _begin(x._begin), _end(x._end) {
+    // This is std::uninitialized_move, but that is c++17 only
+    auto dest = begin();
+    for (auto& obj : x) {
+        new (&*dest++) T(std::move(obj));
+    }
+}
+
+template <typename T, size_t Capacity>
+inline
+circular_buffer_fixed_capacity<T, Capacity>&
+circular_buffer_fixed_capacity<T, Capacity>::operator=(circular_buffer_fixed_capacity&& x) noexcept {
+    if (this != &x) {
+        this->~circular_buffer_fixed_capacity();
+        new (this) circular_buffer_fixed_capacity(std::move(x));
+    }
+    return *this;
+}
+
+template <typename T, size_t Capacity>
+inline
+circular_buffer_fixed_capacity<T, Capacity>::~circular_buffer_fixed_capacity() {
+    clear();
+}
+
+template <typename T, size_t Capacity>
+inline
+void
+circular_buffer_fixed_capacity<T, Capacity>::push_front(const T& data) {
+    new (obj(_begin - 1)) T(data);
+    --_begin;
+}
+
+template <typename T, size_t Capacity>
+inline
+void
+circular_buffer_fixed_capacity<T, Capacity>::push_front(T&& data) {
+    new (obj(_begin - 1)) T(std::move(data));
+    --_begin;
+}
+
+template <typename T, size_t Capacity>
+template <typename... Args>
+inline
+T&
+circular_buffer_fixed_capacity<T, Capacity>::emplace_front(Args&&... args) {
+    auto p = new (obj(_begin - 1)) T(std::forward<Args>(args)...);
+    --_begin;
+    return *p;
+}
+
+template <typename T, size_t Capacity>
+inline
+void
+circular_buffer_fixed_capacity<T, Capacity>::push_back(const T& data) {
+    new (obj(_end)) T(data);
+    ++_end;
+}
+
+template <typename T, size_t Capacity>
+inline
+void
+circular_buffer_fixed_capacity<T, Capacity>::push_back(T&& data) {
+    new (obj(_end)) T(std::move(data));
+    ++_end;
+}
+
+template <typename T, size_t Capacity>
+template <typename... Args>
+inline
+T&
+circular_buffer_fixed_capacity<T, Capacity>::emplace_back(Args&&... args) {
+    auto p = new (obj(_end)) T(std::forward<Args>(args)...);
+    ++_end;
+    return *p;
+}
+
+template <typename T, size_t Capacity>
+inline
+T&
+circular_buffer_fixed_capacity<T, Capacity>::front() {
+    return *obj(_begin);
+}
+
+template <typename T, size_t Capacity>
+inline
+T&
+circular_buffer_fixed_capacity<T, Capacity>::back() {
+    return *obj(_end - 1);
+}
+
+template <typename T, size_t Capacity>
+inline
+void
+circular_buffer_fixed_capacity<T, Capacity>::pop_front() {
+    obj(_begin)->~T();
+    ++_begin;
+}
+
+template <typename T, size_t Capacity>
+inline
+void
+circular_buffer_fixed_capacity<T, Capacity>::pop_back() {
+    obj(_end - 1)->~T();
+    --_end;
+}
+
+template <typename T, size_t Capacity>
+inline
+T&
+circular_buffer_fixed_capacity<T, Capacity>::operator[](size_t idx) {
+    return *obj(_begin + idx);
+}
+
+template <typename T, size_t Capacity>
+inline
+typename circular_buffer_fixed_capacity<T, Capacity>::iterator
+circular_buffer_fixed_capacity<T, Capacity>::erase(iterator first, iterator last) {
+    static_assert(std::is_nothrow_move_assignable<T>::value, "erase() assumes move assignment does not throw");
+    if (first == last) {
+        return last;
+    }
+    // Move to the left or right depending on which would result in least amount of moves.
+    // This also guarantees that iterators will be stable when removing from either front or back.
+    if (std::distance(begin(), first) < std::distance(last, end())) {
+        auto new_start = std::move_backward(begin(), first, last);
+        auto i = begin();
+        while (i < new_start) {
+            *i++.~T();
+        }
+        _begin = new_start.idx;
+        return last;
+    } else {
+        auto new_end = std::move(last, end(), first);
+        auto i = new_end;
+        auto e = end();
+        while (i < e) {
+            *i++.~T();
+        }
+        _end = new_end.idx;
+        return first;
+    }
+}
+
+template <typename T, size_t Capacity>
+inline
+void
+circular_buffer_fixed_capacity<T, Capacity>::clear() {
+    for (auto& obj : *this) {
+        obj.~T();
+    }
+    _begin = _end = 0;
+}
+
+}
+