sparse_array.h

/*******************************************************************************
 * Copyright 2017 MINRES Technologies GmbH
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *******************************************************************************/
 
#ifndef _SPARSE_ARRAY_H_
#define _SPARSE_ARRAY_H_
 
#include "ities.h"
#include <array>
#include <cassert>

namespace util {

template <typename T> class sparse_array_b {
public:
    const uint64_t mem_size;
 
    const uint64_t page_addr_mask;
 
    const uint64_t page_size;
 
    const unsigned page_count;
 
    const uint64_t page_addr_width;
 
    using page_type = std::vector<T>;
    sparse_array_b(uint64_t SIZE, unsigned PAGE_ADDR_BITS = 24)
    : mem_size{SIZE}
    , page_addr_mask{(1ULL << PAGE_ADDR_BITS) - 1}
    , page_size{(1ULL << PAGE_ADDR_BITS)}
    , page_count{(SIZE + page_size - 1) / page_size}
    , page_addr_width{PAGE_ADDR_BITS}
    , arr{SIZE / (1 << PAGE_ADDR_BITS) + 1} {
        assert(SIZE > 0 && "sparse_array size must be greater than 0");
        arr.fill(nullptr);
    }

    ~sparse_array_b() {
        for(auto i : arr)
            delete i;
    }

    T& operator[](uint32_t addr) {
        assert(addr < mem_size);
        T nr = addr >> page_addr_width;
        if(arr[nr] == nullptr)
            arr[nr] = new page_type();
        return arr[nr]->at(addr & page_addr_mask);
    }

    page_type& operator()(uint32_t page_nr) {
        assert(page_nr < page_count);
        if(arr[page_nr] == nullptr)
            arr.at(page_nr) = new page_type(page_size);
        return *(arr[page_nr]);
    }

    bool is_allocated(uint32_t addr) {
        assert(addr < mem_size);
        T nr = addr >> page_addr_width;
        return arr.at(nr) != nullptr;
    }

    uint64_t size() { return mem_size; }
 
protected:
    std::vector<page_type*> arr;
};

template <typename T, uint64_t SIZE, unsigned PAGE_ADDR_BITS = 24> class sparse_array {
public:
    static_assert(SIZE > 0, "sparse_array size must be greater than 0");
 
    static constexpr uint64_t page_addr_mask = (1 << PAGE_ADDR_BITS) - 1;
 
    static constexpr uint64_t page_size = (1 << PAGE_ADDR_BITS);
 
    static constexpr unsigned page_count = (SIZE + page_size - 1) / page_size;
 
    static constexpr uint64_t page_addr_width = PAGE_ADDR_BITS;
 
    using page_type = std::array<T, 1 << PAGE_ADDR_BITS>;
    sparse_array() { arr.fill(nullptr); }
    ~sparse_array() {
        for(auto i : arr)
            delete i;
    }

    T& operator[](uint32_t addr) {
        assert(addr < SIZE);
        T nr = addr >> PAGE_ADDR_BITS;
        if(arr[nr] == nullptr)
            arr[nr] = new page_type();
        return arr[nr]->at(addr & page_addr_mask);
    }

    page_type& operator()(uint32_t page_nr) {
        assert(page_nr < page_count);
        if(arr[page_nr] == nullptr)
            arr.at(page_nr) = new page_type();
        return *(arr[page_nr]);
    }

    bool is_allocated(uint32_t addr) {
        assert(addr < SIZE);
        T nr = addr >> PAGE_ADDR_BITS;
        return arr.at(nr) != nullptr;
    }

    uint64_t size() { return SIZE; }
 
protected:
    std::array<page_type*, SIZE / (1 << PAGE_ADDR_BITS) + 1> arr;
};
} // namespace util
#endif /* _SPARSE_ARRAY_H_ */