Program Listing for File buffer.hpp

↰ Return to documentation for file (include/util/buffer.hpp)

// SPDX-FileCopyrightText: 2021 Christian Göhring <mostsig@gmail.com>
// SPDX-License-Identifier: MIT

#ifndef THAT_THIS_UTIL_BUFFER_HEADER_IS_ALREADY_INCLUDED
#define THAT_THIS_UTIL_BUFFER_HEADER_IS_ALREADY_INCLUDED

#include <array>
#include <cstddef>
#include <memory>
#include <vector>

namespace util {

namespace detail {
template <bool IsConst, class T, std::size_t N, class Allocator>
class buffer_iterator;
}  // namespace detail

template <class T, std::size_t N = 16, class Allocator = std::allocator<T>>
class buffer {
public:
    using allocator_type = Allocator;
    using difference_type = std::ptrdiff_t;
    using size_type = std::size_t;
    using value_type = T;

    using iterator = detail::buffer_iterator<false, T, N, Allocator>;
    using const_iterator = detail::buffer_iterator<true, T, N, Allocator>;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;

    buffer() = default;
    ~buffer() = default;
    buffer(const buffer&) = default;
    buffer(buffer&&) noexcept = default;
    auto operator=(const buffer&) -> buffer& = default;
    auto operator=(buffer&&) noexcept -> buffer& = default;

    buffer(const std::initializer_list<T>& list);

    auto at(size_type pos) -> reference;
    auto at(size_type pos) const -> const_reference;
    auto operator[](size_type pos) -> reference;
    auto operator[](size_type pos) const -> const_reference;
    auto front() -> reference;
    auto front() const -> const_reference;
    auto back() -> reference;
    auto back() const -> const_reference;
    auto stack_data() noexcept -> pointer;
    auto stack_data() const noexcept -> const_pointer;
    auto heap_data() noexcept -> pointer;
    auto heap_data() const noexcept -> const_pointer;

    auto begin() noexcept -> iterator;
    auto begin() const noexcept -> const_iterator;
    auto cbegin() const noexcept -> const_iterator;
    auto end() noexcept -> iterator;
    auto end() const noexcept -> const_iterator;
    auto cend() const noexcept -> const_iterator;
    auto rbegin() noexcept -> iterator;
    auto rbegin() const noexcept -> const_iterator;
    auto crbegin() const noexcept -> const_iterator;
    auto rend() noexcept -> iterator;
    auto rend() const noexcept -> const_iterator;
    auto crend() const noexcept -> const_iterator;

    auto empty() const noexcept -> bool;
    auto size() const noexcept -> size_type;
    auto max_size() const noexcept -> size_type;

    void resize(size_type n, const value_type& val);
    auto capacity() const noexcept -> size_type;

private:
    std::size_t stack_pos = 0U;      // position of the next available slot on the stack
    std::array<T, N> stack = {T()};  // fixed-size container of stack elements
    std::vector<T, Allocator> heap;  // dynamically growing container of heap elements
};

namespace detail {

template <bool IsConst, class T, std::size_t N, class Allocator>
class buffer_iterator {
public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using reference = typename std::conditional<IsConst, const value_type&, value_type&>::type;
    using pointer = typename std::conditional<IsConst, const value_type*, value_type*>::type;
    using buffer_type = util::buffer<T, N, Allocator>;
    using buffer_pointer =
        typename std::conditional<IsConst, const buffer_type*, buffer_type*>::type;
    using size_type = typename buffer_type::size_type;

    explicit buffer_iterator(size_type pos, const buffer_pointer& buffer_ptr) noexcept
        : pos(pos), buffer_ptr(buffer_ptr) {}

    auto operator*() const -> reference { return buffer_ptr->operator[](pos); }
    auto operator->() -> pointer { return buffer_ptr->operator[](pos); }

    auto operator++() -> buffer_iterator& {
        pos++;
        return *this;
    }

    auto operator++(int) -> buffer_iterator {
        buffer_iterator tmp = *this;
        ++(*this);
        return tmp;
    }

    friend auto operator==(const buffer_iterator& lhs, const buffer_iterator& rhs) -> bool {
        return lhs.pos == rhs.pos && lhs.buffer_ptr == rhs.buffer_ptr;
    };
    friend auto operator!=(const buffer_iterator& lhs, const buffer_iterator& rhs) -> bool {
        return lhs.pos != rhs.pos || lhs.buffer_ptr != rhs.buffer_ptr;
    };

private:
    size_type pos = 0;
    buffer_pointer buffer_ptr;
};

// assert if a buffer_iterator is trivially copy constructible
static_assert(std::is_trivially_copy_constructible<buffer<int>::iterator>::value, "");

// assert if a buffer_const_iterator is trivially copy constructible
static_assert(std::is_trivially_copy_constructible<buffer<int>::const_iterator>::value, "");

}  // namespace detail

template <class T, std::size_t N, class Allocator>
buffer<T, N, Allocator>::buffer(const std::initializer_list<T>& list) {
    if (list.size() <= N) {
        std::copy(list.begin(), list.end(), stack.begin());
        stack_pos = list.size();
    } else {
        std::copy(list.begin(), list.begin() + N, stack.begin());
        heap.reserve(list.size() - N);
        std::copy(list.begin() + N, list.end(), std::back_inserter(heap));
        stack_pos = N;
    }
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::at(size_type pos) -> reference {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) @see Effective C++ by Scott Meyers
    return const_cast<reference>(const_cast<const buffer<T, N, Allocator>*>(this)->at(pos));
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::at(size_type pos) const -> const_reference {
    if (pos >= size()) {
        throw std::out_of_range{"pos is out of range"};
    }

    if (pos < N) {
        return stack.at(pos);
    }
    return heap.at(pos - N);
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::operator[](size_type pos) -> reference {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) @see Effective C++ by Scott Meyers
    return const_cast<reference>(const_cast<const buffer<T, N, Allocator>*>(this)->operator[](pos));
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::operator[](size_type pos) const -> const_reference {
    if (pos < N) {
        return stack[pos];
    }
    return heap[pos - N];
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::front() -> reference {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) @see Effective C++ by Scott Meyers
    return const_cast<reference>(const_cast<const buffer<T, N, Allocator>*>(this)->front());
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::front() const -> const_reference {
    return stack[0];
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::back() -> reference {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) @see Effective C++ by Scott Meyers
    return const_cast<reference>(const_cast<const buffer<T, N, Allocator>*>(this)->back());
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::back() const -> const_reference {
    if (stack_pos == N) {
        return heap.back();
    }

    return stack[stack_pos - 1];
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::stack_data() noexcept -> pointer {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) @see Effective C++ by Scott Meyers
    return const_cast<pointer>(const_cast<const buffer<T, N, Allocator>*>(this)->stack_data());
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::stack_data() const noexcept -> const_pointer {
    return stack.data();
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::heap_data() noexcept -> pointer {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) @see Effective C++ by Scott Meyers
    return const_cast<pointer>(const_cast<const buffer<T, N, Allocator>*>(this)->heap_data());
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::heap_data() const noexcept -> const_pointer {
    return heap.data();
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::begin() noexcept -> iterator {
    return iterator(0, this);
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::begin() const noexcept -> const_iterator {
    return const_iterator(0, this);
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::cbegin() const noexcept -> const_iterator {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) calls similar const-method
    return const_cast<const buffer*>(this)->begin();
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::end() noexcept -> iterator {
    return iterator(size(), this);
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::end() const noexcept -> const_iterator {
    return const_iterator(size(), this);
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::cend() const noexcept -> const_iterator {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) calls similar const-method
    return const_cast<const buffer*>(this)->end();
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::empty() const noexcept -> bool {
    return stack_pos == 0;
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::size() const noexcept -> size_type {
    if (stack_pos < N) {
        return stack_pos;
    }
    return N + heap.size();
}

template <class T, std::size_t N, class Allocator>
auto buffer<T, N, Allocator>::max_size() const noexcept -> size_type {
    return stack.max_size() + heap.max_size();
}

}  // namespace util

#endif  // THAT_THIS_UTIL_BUFFER_HEADER_IS_ALREADY_INCLUDED