Vector.hpp

Go to the documentation of this file.

/*
 * Sux: Succinct data structures
 *
 * Copyright (C) 2019-2020 Stefano Marchini
 *
 *  This library is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 3 of the License, or (at your option)
 *  any later version.
 *
 * This library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation; either version 3, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE.  See the GNU General Public License for more details.
 *
 * Under Section 7 of GPL version 3, you are granted additional permissions
 * described in the GCC Runtime Library Exception, version 3.1, as published by
 * the Free Software Foundation.
 *
 * You should have received a copy of the GNU General Public License and a copy of
 * the GCC Runtime Library Exception along with this program; see the files
 * COPYING3 and COPYING.RUNTIME respectively.  If not, see
 * <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include "../support/common.hpp"
#include "Expandable.hpp"
#include <assert.h>
#include <iostream>
#include <string>
#include <sys/mman.h>
 
namespace sux::util {
 
enum AllocType {
    MALLOC,
    SMALLPAGE,
    TRANSHUGEPAGE,
    FORCEHUGEPAGE
};
 
template <typename T, AllocType AT = MALLOC> class Vector : public Expandable {
 
#ifndef MAP_HUGETLB
#pragma message("Huge pages not supported")
#define MAP_HUGETLB 0
#define MADV_HUGEPAGE 0
#endif
 
  public:
    static constexpr int PROT = PROT_READ | PROT_WRITE;
    static constexpr int FLAGS = MAP_PRIVATE | MAP_ANONYMOUS | (AT == FORCEHUGEPAGE ? MAP_HUGETLB : 0);
 
  private:
    size_t _size = 0, _capacity = 0;
    T *data = nullptr;
 
  public:
    Vector<T, AT>() = default;
 
    explicit Vector<T, AT>(size_t length) { size(length); }
 
    explicit Vector<T, AT>(const T *data, size_t length) : Vector(length) { memcpy(this->data, data, length); }
 
    ~Vector<T, AT>() {
        if (data) {
            if (AT == MALLOC) {
                free(data);
            } else {
                int result = munmap(data, _capacity);
                assert(result == 0 && "mmunmap failed");
            }
        }
    }
 
    // Delete copy operators
    Vector(const Vector &) = delete;
    Vector &operator=(const Vector &) = delete;
 
    // Define move operators
    Vector(Vector<T, AT> &&oth) : _size(std::exchange(oth._size, 0)), _capacity(std::exchange(oth._capacity, 0)), data(std::exchange(oth.data, nullptr)) {}
 
    Vector<T, AT> &operator=(Vector<T, AT> &&oth) {
        swap(*this, oth);
        return *this;
    }
 
    void trim(size_t capacity) {
        if (capacity >= _size && capacity < _capacity) remap(capacity);
    }
 
    void trimToFit() { trim(_size); }
 
    void reserve(size_t capacity) {
        if (capacity > _capacity) remap(capacity);
    }
 
    void grow(size_t capacity) {
        if (capacity > _capacity) remap(max(capacity, _capacity + (_capacity / 2)));
    }
 
    void resize(size_t size) {
        grow(size);
        _size = size;
    }
 
    void size(size_t size) {
        reserve(size);
        _size = size;
        trimToFit();
    }
 
    void pushBack(T elem) {
        resize(_size + 1);
        data[_size - 1] = elem;
    }
 
    T popBack() { return data[--_size]; }
 
    friend void swap(Vector<T, AT> &first, Vector<T, AT> &second) noexcept {
        std::swap(first._size, second._size);
        std::swap(first._capacity, second._capacity);
        std::swap(first.data, second.data);
    }
 
    inline T *operator&() const { return data; }
 
    inline const T &operator[](size_t i) const { return data[i]; };
 
    inline T &operator[](size_t i) { return data[i]; };
 
    inline size_t size() const { return _size; }
 
    inline size_t capacity() const { return _capacity; }
 
    size_t bitCount() const { return sizeof(*this) * 8 + _capacity * sizeof(T) * 8; }
 
  private:
    static size_t page_aligned(size_t size) {
        if (AT == FORCEHUGEPAGE)
            return ((2 * 1024 * 1024 - 1) | (size * sizeof(T) - 1)) + 1;
        else
            return ((4 * 1024 - 1) | (size * sizeof(T) - 1)) + 1;
    }
 
    void remap(size_t size) {
        if (size == 0) return;
 
        void *mem;
        size_t space; // Space to allocate, in bytes
 
        if (AT == MALLOC) {
            space = size * sizeof(T);
            mem = _capacity == 0 ? malloc(space) : realloc(data, space);
            assert(mem != NULL && "malloc failed");
        } else {
            space = page_aligned(size);
            if (_capacity == 0)
                mem = mmap(nullptr, space, PROT, FLAGS, -1, 0);
            else {
#ifndef MREMAP_MAYMOVE
                mem = mmap(nullptr, space, PROT, FLAGS, -1, 0);
                memcpy(mem, data, page_aligned(_capacity));
#else
                mem = mremap(data, page_aligned(_capacity), space, MREMAP_MAYMOVE, -1, 0);
#endif
            }
            assert(mem != MAP_FAILED && "mmap failed");
 
            if (AT == TRANSHUGEPAGE) {
                int adv = madvise(mem, space, MADV_HUGEPAGE);
                assert(adv == 0 && "madvise failed");
            }
        }
 
        if (_capacity * sizeof(T) < space) memset(static_cast<char *>(mem) + _capacity * sizeof(T), 0, space - _capacity * sizeof(T));
 
        _capacity = space / sizeof(T);
        data = static_cast<T *>(mem);
    }
 
    friend std::ostream &operator<<(std::ostream &os, const Vector<T, AT> &vector) {
        const uint64_t nsize = vector.size();
        os.write((char *)&nsize, sizeof(uint64_t));
        os.write((char *)&vector, vector.size() * sizeof(T));
        return os;
    }
 
    friend std::istream &operator>>(std::istream &is, Vector<T, AT> &vector) {
        uint64_t nsize;
        is.read((char *)&nsize, sizeof(uint64_t));
        vector = Vector<T, AT>(nsize);
        is.read((char *)&vector, vector.size() * sizeof(T));
        return is;
    }
};
 
} // namespace sux::util