Libosmium  2.14.2
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-2018 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  static constexpr const std::size_t initial_buffer_size = 1024 * 1024;
119  static constexpr const std::size_t removed_item_offset = std::numeric_limits<std::size_t>::max();
120 
122  std::vector<std::size_t> m_index;
123  std::size_t m_count_items = 0;
124  std::size_t m_count_removed = 0;
125 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
126  int64_t m_gc_time = 0;
127 #endif
128 
130 
131  std::vector<std::size_t>& m_index;
132  std::size_t m_pos = 0;
133 
134  public:
135 
136  explicit cleanup_helper(std::vector<std::size_t>& index) :
137  m_index(index) {
138  }
139 
140  void moving_in_buffer(std::size_t old_offset, std::size_t new_offset) {
141  while (m_index[m_pos] != old_offset) {
142  ++m_pos;
143  assert(m_pos < m_index.size());
144  }
145  m_index[m_pos] = new_offset;
146  ++m_pos;
147  }
148 
149  }; // cleanup_helper
150 
151  std::size_t& get_item_offset_ref(handle_type handle) noexcept {
152  assert(handle.valid() && "handle must be valid");
153  assert(handle.value <= m_index.size());
154  auto& offset = m_index[handle.value - 1];
155  assert(offset != removed_item_offset);
156  assert(offset < m_buffer.committed());
157  return offset;
158  }
159 
160  std::size_t get_item_offset(handle_type handle) const noexcept {
161  assert(handle.valid() && "handle must be valid");
162  assert(handle.value <= m_index.size());
163  const auto& offset = m_index[handle.value - 1];
164  assert(offset != removed_item_offset);
165  assert(offset < m_buffer.committed());
166  return offset;
167  }
168 
169  // This function decides whether it makes sense to garbage collect the
170  // database. The values here are the result of some experimentation
171  // with real data. We need to balance the memory use with the time
172  // spent on garbage collecting. We don't need to garbage collect if
173  // there is enough space in the buffer anyway (*4). On the other hand,
174  // if there aren't enough removed objects we would just call the
175  // garbage collection again and again, then it is better to let the
176  // buffer grow (*3). The checks (*1) and (*2) make sure there is
177  // minimum and maximum for the number of removed objects.
178  bool should_gc() const noexcept {
179  if (m_count_removed < 10 * 1000) { // *1
180  return false;
181  }
182  if (m_count_removed > 5 * 1000 * 1000) { // *2
183  return true;
184  }
185  if (m_count_removed * 5 < m_count_items) { // *3
186  return false;
187  }
188  return m_buffer.capacity() - m_buffer.committed() < 10 * 1024; // *4
189  }
190 
191  public:
192 
194  m_buffer(initial_buffer_size, osmium::memory::Buffer::auto_grow::yes) {
195  }
196 
203  std::size_t used_memory() const noexcept {
204  return sizeof(ItemStash) +
205  m_buffer.capacity() +
206  m_index.capacity() * sizeof(std::size_t);
207  }
208 
215  std::size_t size() const noexcept {
216  return m_count_items;
217  }
218 
225  std::size_t count_removed() const noexcept {
226  return m_count_removed;
227  }
228 
233  void clear() {
234  m_buffer.clear();
235  m_index.clear();
236  m_count_items = 0;
237  m_count_removed = 0;
238  }
239 
247  if (should_gc()) {
248  garbage_collect();
249  }
250  ++m_count_items;
251  const auto offset = m_buffer.committed();
252  m_buffer.add_item(item);
253  m_buffer.commit();
254  m_index.push_back(offset);
255  return handle_type{m_index.size()};
256  }
257 
270  return m_buffer.get<osmium::memory::Item>(get_item_offset(handle));
271  }
272 
288  template <typename T>
289  T& get(handle_type handle) const {
290  return static_cast<T&>(get_item(handle));
291  }
292 
302 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
303  std::cerr << "GC items=" << m_count_items << " removed=" << m_count_removed << " buffer.committed=" << m_buffer.committed() << " buffer.capacity=" << m_buffer.capacity() << "\n";
304  using clock = std::chrono::high_resolution_clock;
305  std::chrono::time_point<clock> start = clock::now();
306 #endif
307 
308  m_count_removed = 0;
309  cleanup_helper helper{m_index};
310  m_buffer.purge_removed(&helper);
311 
312 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
313  std::chrono::time_point<clock> stop = clock::now();
314  const int64_t time = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();
315  m_gc_time += time;
316  std::cerr << " time=" << time
317  << "us total=" << m_gc_time << "us\n";
318 #endif
319  }
320 
333  void remove_item(handle_type handle) {
334  auto& offset = get_item_offset_ref(handle);
335  auto& item = m_buffer.get<osmium::memory::Item>(offset);
336  assert(!item.removed() && "can not call remove_item() on already removed item");
337  item.set_removed(true);
338  offset = removed_item_offset;
339  --m_count_items;
340  ++m_count_removed;
341  }
342 
343  }; // class ItemStash
344 
345 } // namespace osmium
346 
347 #endif // OSMIUM_STORAGE_ITEM_STASH_HPP
std::size_t capacity() const noexcept
Definition: buffer.hpp:253
std::size_t commit()
Definition: buffer.hpp:348
std::size_t m_count_items
Definition: item_stash.hpp:123
std::size_t value
Definition: item_stash.hpp:75
handle_type add_item(const osmium::memory::Item &item)
Definition: item_stash.hpp:246
handle_type() noexcept
The default constructor creates an invalid handle.
Definition: item_stash.hpp:90
cleanup_helper(std::vector< std::size_t > &index)
Definition: item_stash.hpp:136
std::size_t count_removed() const noexcept
Definition: item_stash.hpp:225
Definition: item_stash.hpp:71
static constexpr const std::size_t initial_buffer_size
Definition: item_stash.hpp:118
osmium::memory::Item & get_item(handle_type handle) const
Definition: item_stash.hpp:269
std::size_t used_memory() const noexcept
Definition: item_stash.hpp:203
std::size_t m_count_removed
Definition: item_stash.hpp:124
std::size_t clear()
Definition: buffer.hpp:379
std::size_t committed() const noexcept
Definition: buffer.hpp:261
static constexpr const std::size_t removed_item_offset
Definition: item_stash.hpp:119
osmium::memory::Buffer m_buffer
Definition: item_stash.hpp:121
Definition: item_stash.hpp:57
handle_type(std::size_t new_value) noexcept
Definition: item_stash.hpp:82
Definition: item.hpp:103
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
T & add_item(const T &item)
Definition: buffer.hpp:476
std::vector< std::size_t > m_index
Definition: item_stash.hpp:122
void purge_removed(TCallbackClass *callback)
Definition: buffer.hpp:724
T & get(const std::size_t offset) const
Definition: buffer.hpp:398
bool should_gc() const noexcept
Definition: item_stash.hpp:178
ItemStash()
Definition: item_stash.hpp:193
void garbage_collect()
Definition: item_stash.hpp:301
void moving_in_buffer(std::size_t old_offset, std::size_t new_offset)
Definition: item_stash.hpp:140
void set_removed(bool removed) noexcept
Definition: item.hpp:177
std::vector< std::size_t > & m_index
Definition: item_stash.hpp:131
std::size_t size() const noexcept
Definition: item_stash.hpp:215
friend class ItemStash
Definition: item_stash.hpp:73
Definition: buffer.hpp:97
void remove_item(handle_type handle)
Definition: item_stash.hpp:333
bool valid() const noexcept
Is this a valid handle?
Definition: item_stash.hpp:95
std::size_t & get_item_offset_ref(handle_type handle) noexcept
Definition: item_stash.hpp:151
void clear()
Definition: item_stash.hpp:233
std::size_t get_item_offset(handle_type handle) const noexcept
Definition: item_stash.hpp:160
Definition: item_stash.hpp:129