SegmentedVector.h

Go to the documentation of this file.

#ifndef CONTAINER_SEGMENTED_VECTOR_H_
#define CONTAINER_SEGMENTED_VECTOR_H_
/*
 * 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 SimPT_Sim {
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
        // ==================================================================

        SegmentedVector() : m_size(0) {}

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

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

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

        self_type& operator= (self_type&& other)
        {
                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
        // ==================================================================

        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 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(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
                        Chunk* 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
} // namespace

#endif // end_of_include_guard