Loading...
Searching...
No Matches
item_stash.hpp
Go to the documentation of this file.
#ifndef OSMIUM_STORAGE_ITEM_STASH_HPP
#define OSMIUM_STORAGE_ITEM_STASH_HPP
/*
This file is part of Osmium (https://osmcode.org/libosmium).
Copyright 2013-2025 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/memory/buffer.hpp>
#include <osmium/memory/item.hpp>
#include <cassert>
#include <cstdlib>
#include <limits>
#include <ostream>
#include <vector>
#ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
# include <iostream>
# include <chrono>
#endif
namespace osmium {
class ItemStash {
public:
class handle_type {
friend class ItemStash;
std::size_t value; // NOLINT(modernize-use-default-member-init)
// Some compilers don't like the default member
// init: "error: defaulted default constructor
// of 'handle_type' cannot be used by non-static
// data member initializer which appears before
// end of class definition"
explicit handle_type(std::size_t new_value) noexcept :
value(new_value) {
assert(new_value > 0);
}
public:
handle_type() noexcept :
value(0) {
}
bool valid() const noexcept {
return value != 0;
}
template <typename TChar, typename TTraits>
friend inline std::basic_ostream<TChar, TTraits>& operator<<(std::basic_ostream<TChar, TTraits>& out, const ItemStash::handle_type& handle) { // NOLINT(readability-redundant-inline-specifier)
if (handle.valid()) {
out << handle.value;
} else {
out << '-';
}
return out;
}
}; // class handle_type
private:
enum {
initial_buffer_size = 1024UL * 1024UL
};
enum {
removed_item_offset = std::numeric_limits<std::size_t>::max()
};
osmium::memory::Buffer m_buffer;
std::vector<std::size_t> m_index;
std::size_t m_count_items = 0;
std::size_t m_count_removed = 0;
#ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
int64_t m_gc_time = 0;
#endif
class cleanup_helper {
std::vector<std::size_t>& m_index;
std::size_t m_pos = 0;
public:
explicit cleanup_helper(std::vector<std::size_t>& index) :
m_index(index) {
}
void moving_in_buffer(std::size_t old_offset, std::size_t new_offset) {
while (m_index[m_pos] != old_offset) {
++m_pos;
assert(m_pos < m_index.size());
}
m_index[m_pos] = new_offset;
++m_pos;
}
}; // cleanup_helper
std::size_t& get_item_offset_ref(handle_type handle) noexcept {
assert(handle.valid() && "handle must be valid");
assert(handle.value <= m_index.size());
auto& offset = m_index[handle.value - 1];
assert(offset != removed_item_offset);
assert(offset < m_buffer.committed());
return offset;
}
std::size_t get_item_offset(handle_type handle) const noexcept {
assert(handle.valid() && "handle must be valid");
assert(handle.value <= m_index.size());
const auto& offset = m_index[handle.value - 1];
assert(offset != removed_item_offset);
assert(offset < m_buffer.committed());
return offset;
}
// This function decides whether it makes sense to garbage collect the
// database. The values here are the result of some experimentation
// with real data. We need to balance the memory use with the time
// spent on garbage collecting. We don't need to garbage collect if
// there is enough space in the buffer anyway (*4). On the other hand,
// if there aren't enough removed objects we would just call the
// garbage collection again and again, then it is better to let the
// buffer grow (*3). The checks (*1) and (*2) make sure there is
// minimum and maximum for the number of removed objects.
bool should_gc() const noexcept {
if (m_count_removed < 10UL * 1000UL) { // *1
return false;
}
if (m_count_removed > 5UL * 1000UL * 1000UL) { // *2
return true;
}
if (m_count_removed * 5UL < m_count_items) { // *3
return false;
}
return m_buffer.capacity() - m_buffer.committed() < 10UL * 1024UL; // *4
}
public:
ItemStash() :
m_buffer(initial_buffer_size, osmium::memory::Buffer::auto_grow::yes) {
}
std::size_t used_memory() const noexcept {
return sizeof(ItemStash) +
m_buffer.capacity() +
(m_index.capacity() * sizeof(std::size_t));
}
std::size_t size() const noexcept {
return m_count_items;
}
std::size_t count_removed() const noexcept {
return m_count_removed;
}
void clear() {
m_buffer.clear();
m_index.clear();
m_count_items = 0;
m_count_removed = 0;
}
handle_type add_item(const osmium::memory::Item& item) {
if (should_gc()) {
garbage_collect();
}
++m_count_items;
const auto offset = m_buffer.committed();
m_buffer.add_item(item);
m_buffer.commit();
m_index.push_back(offset);
return handle_type{m_index.size()};
}
osmium::memory::Item& get_item(handle_type handle) const {
return m_buffer.get<osmium::memory::Item>(get_item_offset(handle));
}
template <typename T>
T& get(handle_type handle) const {
return static_cast<T&>(get_item(handle));
}
void garbage_collect() {
#ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
std::cerr << "GC items=" << m_count_items << " removed=" << m_count_removed << " buffer.committed=" << m_buffer.committed() << " buffer.capacity=" << m_buffer.capacity() << "\n";
using clock = std::chrono::high_resolution_clock;
std::chrono::time_point<clock> start = clock::now();
#endif
m_count_removed = 0;
cleanup_helper helper{m_index};
m_buffer.purge_removed(&helper);
#ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
std::chrono::time_point<clock> stop = clock::now();
const int64_t time = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();
m_gc_time += time;
std::cerr << " time=" << time
<< "us total=" << m_gc_time << "us\n";
#endif
}
void remove_item(handle_type handle) {
auto& offset = get_item_offset_ref(handle);
auto& item = m_buffer.get<osmium::memory::Item>(offset);
assert(!item.removed() && "can not call remove_item() on already removed item");
item.set_removed(true);
offset = removed_item_offset;
--m_count_items;
++m_count_removed;
}
}; // class ItemStash
} // namespace osmium
#endif // OSMIUM_STORAGE_ITEM_STASH_HPP
buffer.hpp
osmium::ItemStash::cleanup_helper
Definition item_stash.hpp:134
osmium::ItemStash::cleanup_helper::m_index
std::vector< std::size_t > & m_index
Definition item_stash.hpp:136
osmium::ItemStash::cleanup_helper::cleanup_helper
cleanup_helper(std::vector< std::size_t > &index)
Definition item_stash.hpp:141
osmium::ItemStash::cleanup_helper::moving_in_buffer
void moving_in_buffer(std::size_t old_offset, std::size_t new_offset)
Definition item_stash.hpp:145
osmium::ItemStash::cleanup_helper::m_pos
std::size_t m_pos
Definition item_stash.hpp:137
osmium::ItemStash::handle_type
Definition item_stash.hpp:71
osmium::ItemStash::handle_type::valid
bool valid() const noexcept
Is this a valid handle?
Definition item_stash.hpp:95
osmium::ItemStash::handle_type::handle_type
handle_type(std::size_t new_value) noexcept
Definition item_stash.hpp:82
osmium::ItemStash::handle_type::operator<<
friend std::basic_ostream< TChar, TTraits > & operator<<(std::basic_ostream< TChar, TTraits > &out, const ItemStash::handle_type &handle)
Definition item_stash.hpp:105
osmium::ItemStash::handle_type::handle_type
handle_type() noexcept
The default constructor creates an invalid handle.
Definition item_stash.hpp:90
osmium::ItemStash::handle_type::value
std::size_t value
Definition item_stash.hpp:75
osmium::ItemStash
Definition item_stash.hpp:57
osmium::ItemStash::get
T & get(handle_type handle) const
Definition item_stash.hpp:294
osmium::ItemStash::remove_item
void remove_item(handle_type handle)
Definition item_stash.hpp:338
osmium::ItemStash::initial_buffer_size
@ initial_buffer_size
Definition item_stash.hpp:119
osmium::ItemStash::get_item_offset
std::size_t get_item_offset(handle_type handle) const noexcept
Definition item_stash.hpp:165
osmium::ItemStash::get_item_offset_ref
std::size_t & get_item_offset_ref(handle_type handle) noexcept
Definition item_stash.hpp:156
osmium::ItemStash::get_item
osmium::memory::Item & get_item(handle_type handle) const
Definition item_stash.hpp:274
osmium::ItemStash::m_index
std::vector< std::size_t > m_index
Definition item_stash.hpp:127
osmium::ItemStash::add_item
handle_type add_item(const osmium::memory::Item &item)
Definition item_stash.hpp:251
osmium::ItemStash::clear
void clear()
Definition item_stash.hpp:238
osmium::ItemStash::m_count_items
std::size_t m_count_items
Definition item_stash.hpp:128
osmium::ItemStash::size
std::size_t size() const noexcept
Definition item_stash.hpp:220
osmium::ItemStash::count_removed
std::size_t count_removed() const noexcept
Definition item_stash.hpp:230
osmium::ItemStash::garbage_collect
void garbage_collect()
Definition item_stash.hpp:306
osmium::ItemStash::removed_item_offset
@ removed_item_offset
Definition item_stash.hpp:123
osmium::ItemStash::used_memory
std::size_t used_memory() const noexcept
Definition item_stash.hpp:208
osmium::ItemStash::ItemStash
ItemStash()
Definition item_stash.hpp:198
osmium::ItemStash::m_buffer
osmium::memory::Buffer m_buffer
Definition item_stash.hpp:126
osmium::ItemStash::should_gc
bool should_gc() const noexcept
Definition item_stash.hpp:183
osmium::ItemStash::m_count_removed
std::size_t m_count_removed
Definition item_stash.hpp:129
osmium::memory::Item
Definition item.hpp:105
item.hpp
osmium
Namespace for everything in the Osmium library.
Definition assembler.hpp:53