SegmentedVector.h

Go to the documentation of this file.

#pragma once
/*
 * Copyright 2011-2016 Universiteit Antwerpen
 *
 * Licensed under the EUPL, Version 1.1 or  as soon they will be approved by
 * the European Commission - subsequent versions of the EUPL (the "Licence");
 * You may not use this work except in compliance with the Licence.
 * You may obtain a copy of the Licence at: http://ec.europa.eu/idabc/eupl5
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the Licence is distributed on an "AS IS" basis,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the Licence for the specific language governing
 * permissions and limitations under the Licence.
 */
#include "SVIterator.h"

#include <array>
#include <cassert>
#include <iterator>
#include <limits>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

namespace UA_CoMP {
namespace Container {

template <typename T, size_t N = 512>
class SegmentedVector
{
public:
        // ==================================================================
        // Member types
        // ==================================================================
        using value_type = T;
        using size_type = std::size_t;
        using self_type = SegmentedVector<T, N>;
        using iterator = SVIterator<T, N, T*, T&, false>;
        using const_iterator = SVIterator<T, N>;

        // ==================================================================
        // Construction / Copy / Move / Destruction
        // ==================================================================

        explicit SegmentedVector() : m_blocks(), m_size(0) {}

        SegmentedVector(const self_type& other) : m_blocks(), m_size(0)
        {
                reserve(other.capacity());
                for (const auto& elem : other) {
                        push_back(elem);
                }
                assert(m_size == other.m_size);
                assert(m_blocks.size() == other.m_blocks.size());
                assert(this->capacity() == other.capacity());
        }

        SegmentedVector(self_type&& other) noexcept : m_blocks(std::move(other.m_blocks)), m_size(other.m_size)
        {
                other.m_size = 0;
        }

        SegmentedVector& operator=(const self_type& other)
        {
                if (this != &other) {
                        clear();
                        reserve(other.capacity());
                        for (const auto& elem : other) {
                                push_back(elem);
                        }
                        assert(m_size == other.m_size);
                        assert(m_blocks.size() == other.m_blocks.size());
                        assert(this->capacity() == other.capacity());
                }
                return *this;
        }

        SegmentedVector& operator=(self_type&& other) noexcept
        {
                if (this != &other) {
                        clear();
                        m_blocks = std::move(other.m_blocks);
                        std::swap(m_size, other.m_size);
                }
                return *this;
        }

        ~SegmentedVector() { clear(); }

        // ==================================================================
        // Element access
        // ==================================================================

        T& at(std::size_t pos)
        {
                if (pos >= m_size) {
                        throw std::out_of_range("CompactStorage: index out of range.");
                }
                const size_t b = pos / N;
                const size_t i = pos % N;
                return *static_cast<T*>(static_cast<void*>(&(m_blocks[b][i])));
        }

        const T& at(std::size_t pos) const
        {
                if (pos >= m_size) {
                        throw std::out_of_range("CompactStorage: index out of range.");
                }
                const size_t b = pos / N;
                const size_t i = pos % N;
                return *static_cast<const T*>(static_cast<const void*>(&(m_blocks[b][i])));
        }

        T& back() { return *static_cast<T*>(static_cast<void*>(&m_blocks[(m_size - 1) / N][(m_size - 1) % N])); }

        const T& back() const
        {
                return *static_cast<const T*>(static_cast<const void*>(&m_blocks[(m_size - 1) / N][(m_size - 1) % N]));
        }

        T& operator[](size_t pos) { return *static_cast<T*>(static_cast<void*>(&(m_blocks[pos / N][pos % N]))); }

        const T& operator[](size_t pos) const
        {
                return *static_cast<const T*>(static_cast<const void*>(&(m_blocks[pos / N][pos % N])));
        }

        // ==================================================================
        // Iterators
        // ==================================================================

        iterator begin() { return (m_size == 0) ? end() : iterator(0, this); }

        const_iterator begin() const { return (m_size == 0) ? end() : const_iterator(0, this); }

        const_iterator cbegin() const { return (m_size == 0) ? end() : const_iterator(0, this); }

        iterator end() { return iterator(iterator::m_end, this); }

        const_iterator end() const { return const_iterator(const_iterator::m_end, this); }

        const_iterator cend() const { return const_iterator(const_iterator::m_end, this); }

        // ==================================================================
        // Capacity
        // ==================================================================

        std::size_t capacity() const { return N * m_blocks.size(); }

        bool empty() const { return m_size == 0; }

        std::size_t get_block_count() const { return m_blocks.size(); }

        std::size_t get_elements_per_block() const { return N; }

        std::size_t size() const { return m_size; }

        // ==================================================================
        // Modifiers
        // ==================================================================

        void reserve(size_type new_capacity)
        {
                while (new_capacity > capacity()) {
                        m_blocks.push_back(new Chunk[N]);
                }
        }

        void shrink_to_fit()
        {
                size_type req_blocks = 1 + (size() - 1) / N;
                while (req_blocks < m_blocks.size()) {
                        delete[] m_blocks.back();
                        m_blocks.pop_back();
                }
        }
        void clear()
        {
                for (auto& i : *this) {
                        i.~T();
                }
                for (auto p : m_blocks) {
                        delete[] p;
                }
                m_blocks.clear();
                m_size = 0;
        }

        template <class... Args>
        T* emplace_back(Args&&... args)
        {
                T* memory = this->get_chunk();
                return new (memory) T(std::forward<Args>(args)...); // construct new object
        }

        void pop_back()
        {
                // No pop on empty container.
                if (m_size <= 0) {
                        throw std::logic_error("CompactStorage::pop_back called on empty object.");
                }

                // Element destruction.
                at(m_size - 1).~T();
                --m_size;

                // If tail block vacated, release it.
                const size_t last_block_index = m_blocks.size() - 1;
                if (m_size <= last_block_index * N) {
                        delete[] m_blocks[last_block_index];
                        m_blocks.pop_back();
                }
        }

        T* push_back(const T& obj)
        {
                T* memory = get_chunk();
                return new (memory) T(obj); // copy-construct new object
        }

        T* push_back(T&& obj)
        {
                T* memory = get_chunk();
                return new (memory) T(std::move(obj)); // move-construct new object
        }

private:
        using Chunk = typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type;

private:
        friend class SVIterator<T, N>;
        friend class SVIterator<T, N, T*, T&, false>;

private:
        T* get_chunk()
        {
                const size_t b = m_size / N; // Index of block in vector m_blocks
                const size_t i = m_size % N; // Offset of chunk within its block

                if (b == m_blocks.size()) { // Out of buffers, last buffer is full
                        auto chunk = new Chunk[N];
                        m_blocks.push_back(chunk);
                }
                ++m_size;
                return static_cast<T*>(static_cast<void*>(&((m_blocks[b])[i])));
        }

private:
        std::vector<Chunk*> m_blocks; 
        size_t m_size;                
};

} // namespace Container
} // namespace UA_CoMP