flex_mem.hpp

Go to the documentation of this file.

#ifndef OSMIUM_INDEX_MAP_FLEX_MEM_HPP
#define OSMIUM_INDEX_MAP_FLEX_MEM_HPP
 
/*
 
This file is part of Osmium (https://osmcode.org/libosmium).
 
Copyright 2013-2023 Jochen Topf <jochen@topf.org> and others (see README).
 
Boost Software License - Version 1.0 - August 17th, 2003
 
Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:
 
The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
*/
 
#include <osmium/index/index.hpp>
#include <osmium/index/map.hpp>
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>
 
#define OSMIUM_HAS_INDEX_MAP_FLEX_MEM
 
namespace osmium {
 
    namespace index {
 
        namespace map {
 
            template <typename TId, typename TValue>
            class FlexMem : public osmium::index::map::Map<TId, TValue> {
 
                // This value is based on benchmarks with a planet file and
                // some smaller files.
                enum {
                    bits = 16
                };
 
                enum : uint64_t {
                    block_size = 1ULL << bits
                };
 
                // Minimum number of entries in the sparse index before we
                // are considering switching to a dense index.
                enum : int64_t {
                    min_dense_entries = 0xffffff
                };
 
                // When more than a third of all Ids are in the index, we
                // switch to the dense index. This is a compromise between
                // the best memory efficiency (which we would get at a factor
                // of 2) and the performance (dense index is much faster then
                // the sparse index).
                enum {
                    density_factor = 3
                };
 
                // An entry in the sparse index
                struct entry {
                    uint64_t id;
                    TValue value;
 
                    entry(uint64_t i, TValue v) :
                        id(i),
                        value(std::move(v)) {
                    }
 
                    bool operator<(const entry other) const noexcept {
                        return id < other.id;
                    }
                };
 
                std::vector<entry> m_sparse_entries;
 
                std::vector<std::vector<TValue>> m_dense_blocks;
 
                // The maximum Id that was seen yet. Only set in sparse mode.
                uint64_t m_max_id = 0;
 
                // Set to false in sparse mode and to true in dense mode.
                bool m_dense;
 
                static uint64_t block(const uint64_t id) noexcept {
                    return id >> bits;
                }
 
                static uint64_t offset(const uint64_t id) noexcept {
                    return id & (block_size - 1);
                }
 
                // Assure that the block with the given number exists. Create
                // it if needed.
                void assure_block(const uint64_t num) {
                    if (num >= m_dense_blocks.size()) {
                        m_dense_blocks.resize(num + 1);
                    }
                    if (m_dense_blocks[num].empty()) {
                        m_dense_blocks[num].assign(block_size, osmium::index::empty_value<TValue>());
                    }
                }
 
                void set_sparse(const uint64_t id, const TValue value) {
                    m_sparse_entries.emplace_back(id, value);
                    if (id > m_max_id) {
                        m_max_id = id;
 
                        if (m_sparse_entries.size() >= min_dense_entries) {
                            if (m_max_id < m_sparse_entries.size() * density_factor) {
                                switch_to_dense();
                            }
                        }
                    }
                }
 
                TValue get_sparse(const uint64_t id) const noexcept {
                    const auto it = std::lower_bound(m_sparse_entries.begin(),
                                                     m_sparse_entries.end(),
                                                     entry{id, osmium::index::empty_value<TValue>()});
                    if (it == m_sparse_entries.end() || it->id != id) {
                        return osmium::index::empty_value<TValue>();
                    }
                    return it->value;
                }
 
                void set_dense(const uint64_t id, const TValue value) {
                    assure_block(block(id));
                    m_dense_blocks[block(id)][offset(id)] = value;
                }
 
                TValue get_dense(const uint64_t id) const noexcept {
                    if (m_dense_blocks.size() <= block(id) || m_dense_blocks[block(id)].empty()) {
                        return osmium::index::empty_value<TValue>();
                    }
                    return m_dense_blocks[block(id)][offset(id)];
                }
 
            public:
 
                explicit FlexMem(bool use_dense = false) :
                    m_dense(use_dense) {
                }
 
                bool is_dense() const noexcept {
                    return m_dense;
                }
 
                std::size_t size() const noexcept final {
                    if (m_dense) {
                        return m_dense_blocks.size() * block_size;
                    }
                    return m_sparse_entries.size();
                }
 
                std::size_t used_memory() const noexcept final {
                    return sizeof(FlexMem) +
                           m_sparse_entries.size() * sizeof(entry) +
                           m_dense_blocks.size() * (block_size * sizeof(TValue) + sizeof(std::vector<TValue>));
                }
 
                void set(const TId id, const TValue value) final {
                    if (m_dense) {
                        set_dense(id, value);
                    } else {
                        set_sparse(id, value);
                    }
                }
 
                TValue get_noexcept(const TId id) const noexcept final {
                    if (m_dense) {
                        return get_dense(id);
                    }
                    return get_sparse(id);
                }
 
                TValue get(const TId id) const final {
                    const auto value = get_noexcept(id);
                    if (value == osmium::index::empty_value<TValue>()) {
                        throw osmium::not_found{id};
                    }
                    return value;
                }
 
                void clear() final {
                    m_sparse_entries.clear();
                    m_sparse_entries.shrink_to_fit();
                    m_dense_blocks.clear();
                    m_dense_blocks.shrink_to_fit();
                    m_max_id = 0;
                    m_dense = false;
                }
 
                void sort() final {
                    std::sort(m_sparse_entries.begin(), m_sparse_entries.end());
                }
 
                void switch_to_dense() {
                    if (m_dense) {
                        return;
                    }
                    for (const auto& entry : m_sparse_entries) {
                        set_dense(entry.id, entry.value);
                    }
                    m_sparse_entries.clear();
                    m_sparse_entries.shrink_to_fit();
                    m_max_id = 0;
                    m_dense = true;
                }
 
                std::pair<std::size_t, std::size_t> stats() const noexcept {
                    std::size_t used_blocks = 0;
                    std::size_t empty_blocks = 0;
 
                    for (const auto& dense_block : m_dense_blocks) {
                        if (dense_block.empty()) {
                            ++empty_blocks;
                        } else {
                            ++used_blocks;
                        }
                    }
 
                    return std::make_pair(used_blocks, empty_blocks);
                }
 
            }; // class FlexMem
 
        } // namespace map
 
    } // namespace index
 
} // namespace osmium
 
#ifdef OSMIUM_WANT_NODE_LOCATION_MAPS
    REGISTER_MAP(osmium::unsigned_object_id_type, osmium::Location, osmium::index::map::FlexMem, flex_mem)
#endif
 
#endif // OSMIUM_INDEX_MAP_FLEX_MEM_HPP