Libosmium  2.15.5
Fast and flexible C++ library for working with OpenStreetMap data
item_stash.hpp
Go to the documentation of this file.
1 #ifndef OSMIUM_STORAGE_ITEM_STASH_HPP
2 #define OSMIUM_STORAGE_ITEM_STASH_HPP
3 
4 /*
5 
6 This file is part of Osmium (https://osmcode.org/libosmium).
7 
8 Copyright 2013-2020 Jochen Topf <jochen@topf.org> and others (see README).
9 
10 Boost Software License - Version 1.0 - August 17th, 2003
11 
12 Permission is hereby granted, free of charge, to any person or organization
13 obtaining a copy of the software and accompanying documentation covered by
14 this license (the "Software") to use, reproduce, display, distribute,
15 execute, and transmit the Software, and to prepare derivative works of the
16 Software, and to permit third-parties to whom the Software is furnished to
17 do so, all subject to the following:
18 
19 The copyright notices in the Software and this entire statement, including
20 the above license grant, this restriction and the following disclaimer,
21 must be included in all copies of the Software, in whole or in part, and
22 all derivative works of the Software, unless such copies or derivative
23 works are solely in the form of machine-executable object code generated by
24 a source language processor.
25 
26 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
27 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
28 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
29 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
30 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
31 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
32 DEALINGS IN THE SOFTWARE.
33 
34 */
35 
36 #include <osmium/memory/buffer.hpp>
37 #include <osmium/memory/item.hpp>
38 
39 #include <cassert>
40 #include <cstdlib>
41 #include <limits>
42 #include <ostream>
43 #include <vector>
44 
45 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
46 # include <iostream>
47 # include <chrono>
48 #endif
49 
50 namespace osmium {
51 
57  class ItemStash {
58 
59  public:
60 
71  class handle_type {
72 
73  friend class ItemStash;
74 
75  std::size_t value; // NOLINT(modernize-use-default-member-init)
76  // Some compilers don't like the default member
77  // init: "error: defaulted default constructor
78  // of 'handle_type' cannot be used by non-static
79  // data member initializer which appears before
80  // end of class definition"
81 
82  explicit handle_type(std::size_t new_value) noexcept :
83  value(new_value) {
84  assert(new_value > 0);
85  }
86 
87  public:
88 
90  handle_type() noexcept :
91  value(0) {
92  }
93 
95  bool valid() const noexcept {
96  return value != 0;
97  }
98 
104  template <typename TChar, typename TTraits>
105  friend inline std::basic_ostream<TChar, TTraits>& operator<<(std::basic_ostream<TChar, TTraits>& out, const ItemStash::handle_type& handle) {
106  if (handle.valid()) {
107  out << handle.value;
108  } else {
109  out << '-';
110  }
111  return out;
112  }
113 
114  }; // class handle_type
115 
116  private:
117 
118  enum {
119  initial_buffer_size = 1024UL * 1024UL
120  };
121 
122  enum {
123  removed_item_offset = std::numeric_limits<std::size_t>::max()
124  };
125 
127  std::vector<std::size_t> m_index;
128  std::size_t m_count_items = 0;
129  std::size_t m_count_removed = 0;
130 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
131  int64_t m_gc_time = 0;
132 #endif
133 
135 
136  std::vector<std::size_t>& m_index;
137  std::size_t m_pos = 0;
138 
139  public:
140 
141  explicit cleanup_helper(std::vector<std::size_t>& index) :
142  m_index(index) {
143  }
144 
145  void moving_in_buffer(std::size_t old_offset, std::size_t new_offset) {
146  while (m_index[m_pos] != old_offset) {
147  ++m_pos;
148  assert(m_pos < m_index.size());
149  }
150  m_index[m_pos] = new_offset;
151  ++m_pos;
152  }
153 
154  }; // cleanup_helper
155 
156  std::size_t& get_item_offset_ref(handle_type handle) noexcept {
157  assert(handle.valid() && "handle must be valid");
158  assert(handle.value <= m_index.size());
159  auto& offset = m_index[handle.value - 1];
160  assert(offset != removed_item_offset);
161  assert(offset < m_buffer.committed());
162  return offset;
163  }
164 
165  std::size_t get_item_offset(handle_type handle) const noexcept {
166  assert(handle.valid() && "handle must be valid");
167  assert(handle.value <= m_index.size());
168  const auto& offset = m_index[handle.value - 1];
169  assert(offset != removed_item_offset);
170  assert(offset < m_buffer.committed());
171  return offset;
172  }
173 
174  // This function decides whether it makes sense to garbage collect the
175  // database. The values here are the result of some experimentation
176  // with real data. We need to balance the memory use with the time
177  // spent on garbage collecting. We don't need to garbage collect if
178  // there is enough space in the buffer anyway (*4). On the other hand,
179  // if there aren't enough removed objects we would just call the
180  // garbage collection again and again, then it is better to let the
181  // buffer grow (*3). The checks (*1) and (*2) make sure there is
182  // minimum and maximum for the number of removed objects.
183  bool should_gc() const noexcept {
184  if (m_count_removed < 10 * 1000) { // *1
185  return false;
186  }
187  if (m_count_removed > 5 * 1000 * 1000) { // *2
188  return true;
189  }
190  if (m_count_removed * 5 < m_count_items) { // *3
191  return false;
192  }
193  return m_buffer.capacity() - m_buffer.committed() < 10 * 1024; // *4
194  }
195 
196  public:
197 
199  m_buffer(initial_buffer_size, osmium::memory::Buffer::auto_grow::yes) {
200  }
201 
208  std::size_t used_memory() const noexcept {
209  return sizeof(ItemStash) +
210  m_buffer.capacity() +
211  m_index.capacity() * sizeof(std::size_t);
212  }
213 
220  std::size_t size() const noexcept {
221  return m_count_items;
222  }
223 
230  std::size_t count_removed() const noexcept {
231  return m_count_removed;
232  }
233 
238  void clear() {
239  m_buffer.clear();
240  m_index.clear();
241  m_count_items = 0;
242  m_count_removed = 0;
243  }
244 
252  if (should_gc()) {
253  garbage_collect();
254  }
255  ++m_count_items;
256  const auto offset = m_buffer.committed();
257  m_buffer.add_item(item);
258  m_buffer.commit();
259  m_index.push_back(offset);
260  return handle_type{m_index.size()};
261  }
262 
276  }
277 
293  template <typename T>
294  T& get(handle_type handle) const {
295  return static_cast<T&>(get_item(handle));
296  }
297 
307 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
308  std::cerr << "GC items=" << m_count_items << " removed=" << m_count_removed << " buffer.committed=" << m_buffer.committed() << " buffer.capacity=" << m_buffer.capacity() << "\n";
309  using clock = std::chrono::high_resolution_clock;
310  std::chrono::time_point<clock> start = clock::now();
311 #endif
312 
313  m_count_removed = 0;
314  cleanup_helper helper{m_index};
315  m_buffer.purge_removed(&helper);
316 
317 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
318  std::chrono::time_point<clock> stop = clock::now();
319  const int64_t time = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();
320  m_gc_time += time;
321  std::cerr << " time=" << time
322  << "us total=" << m_gc_time << "us\n";
323 #endif
324  }
325 
338  void remove_item(handle_type handle) {
339  auto& offset = get_item_offset_ref(handle);
340  auto& item = m_buffer.get<osmium::memory::Item>(offset);
341  assert(!item.removed() && "can not call remove_item() on already removed item");
342  item.set_removed(true);
343  offset = removed_item_offset;
344  --m_count_items;
345  ++m_count_removed;
346  }
347 
348  }; // class ItemStash
349 
350 } // namespace osmium
351 
352 #endif // OSMIUM_STORAGE_ITEM_STASH_HPP
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::get
T & get(handle_type handle) const
Definition: item_stash.hpp:294
osmium::ItemStash::m_count_removed
std::size_t m_count_removed
Definition: item_stash.hpp:129
osmium::ItemStash::ItemStash
ItemStash()
Definition: item_stash.hpp:198
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
item.hpp
osmium::ItemStash::handle_type::value
std::size_t value
Definition: item_stash.hpp:75
osmium::ItemStash::get_item_offset
std::size_t get_item_offset(handle_type handle) const noexcept
Definition: item_stash.hpp:165
osmium::ItemStash::removed_item_offset
Definition: item_stash.hpp:123
osmium::ItemStash::m_index
std::vector< std::size_t > m_index
Definition: item_stash.hpp:127
osmium::ItemStash::handle_type::handle_type
handle_type(std::size_t new_value) noexcept
Definition: item_stash.hpp:82
osmium::memory::Buffer::purge_removed
void purge_removed(TCallbackClass *callback)
Definition: buffer.hpp:854
osmium::memory::Buffer::committed
std::size_t committed() const noexcept
Definition: buffer.hpp:356
osmium::memory::Buffer::add_item
T & add_item(const T &item)
Definition: buffer.hpp:601
osmium::ItemStash::used_memory
std::size_t used_memory() const noexcept
Definition: item_stash.hpp:208
osmium::ItemStash::remove_item
void remove_item(handle_type handle)
Definition: item_stash.hpp:338
osmium::ItemStash::get_item
osmium::memory::Item & get_item(handle_type handle) const
Definition: item_stash.hpp:274
osmium::ItemStash::add_item
handle_type add_item(const osmium::memory::Item &item)
Definition: item_stash.hpp:251
osmium::memory::Item::set_removed
void set_removed(const bool removed) noexcept
Definition: item.hpp:179
osmium::ItemStash::should_gc
bool should_gc() const noexcept
Definition: item_stash.hpp:183
osmium::memory::Buffer
Definition: buffer.hpp:97
osmium
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
osmium::memory::Item
Definition: item.hpp:105
osmium::ItemStash::cleanup_helper::m_pos
std::size_t m_pos
Definition: item_stash.hpp:137
osmium::memory::Buffer::clear
std::size_t clear()
Definition: buffer.hpp:499
osmium::ItemStash::m_buffer
osmium::memory::Buffer m_buffer
Definition: item_stash.hpp:126
osmium::ItemStash
Definition: item_stash.hpp:57
osmium::ItemStash::count_removed
std::size_t count_removed() const noexcept
Definition: item_stash.hpp:230
osmium::memory::Buffer::get
T & get(const std::size_t offset) const
Definition: buffer.hpp:518
osmium::ItemStash::handle_type::valid
bool valid() const noexcept
Is this a valid handle?
Definition: item_stash.hpp:95
osmium::ItemStash::handle_type
Definition: item_stash.hpp:71
osmium::memory::Buffer::commit
std::size_t commit()
Definition: buffer.hpp:468
osmium::ItemStash::size
std::size_t size() const noexcept
Definition: item_stash.hpp:220
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::memory::Buffer::capacity
std::size_t capacity() const noexcept
Definition: buffer.hpp:348
osmium::ItemStash::get_item_offset_ref
std::size_t & get_item_offset_ref(handle_type handle) noexcept
Definition: item_stash.hpp:156
osmium::ItemStash::cleanup_helper
Definition: item_stash.hpp:134
osmium::ItemStash::cleanup_helper::cleanup_helper
cleanup_helper(std::vector< std::size_t > &index)
Definition: item_stash.hpp:141
buffer.hpp
osmium::ItemStash::cleanup_helper::m_index
std::vector< std::size_t > & m_index
Definition: item_stash.hpp:136
osmium::ItemStash::initial_buffer_size
Definition: item_stash.hpp:119
osmium::ItemStash::handle_type::handle_type
handle_type() noexcept
The default constructor creates an invalid handle.
Definition: item_stash.hpp:90
osmium::ItemStash::garbage_collect
void garbage_collect()
Definition: item_stash.hpp:306