chunked-vector.hh

Go to the documentation of this file.

#pragma once
 
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <limits>
 
namespace nix {

template<typename T, size_t ChunkSize>
class ChunkedVector {
private:
    uint32_t size_ = 0;
    std::vector<std::vector<T>> chunks;

    [[gnu::noinline]]
    auto & addChunk()
    {
        if (size_ >= std::numeric_limits<uint32_t>::max() - ChunkSize)
            abort();
        chunks.emplace_back();
        chunks.back().reserve(ChunkSize);
        return chunks.back();
    }
 
public:
    ChunkedVector(uint32_t reserve)
    {
        chunks.reserve(reserve);
        addChunk();
    }
 
    uint32_t size() const { return size_; }
 
    std::pair<T &, uint32_t> add(T value)
    {
        const auto idx = size_++;
        auto & chunk = [&] () -> auto & {
            if (auto & back = chunks.back(); back.size() < ChunkSize)
                return back;
            return addChunk();
        }();
        auto & result = chunk.emplace_back(std::move(value));
        return {result, idx};
    }
 
    const T & operator[](uint32_t idx) const
    {
        return chunks[idx / ChunkSize][idx % ChunkSize];
    }
 
    template<typename Fn>
    void forEach(Fn fn) const
    {
        for (const auto & c : chunks)
            for (const auto & e : c)
                fn(e);
    }
};
}