Libosmium  2.13.1
Fast and flexible C++ library for working with OpenStreetMap data
item_stash.hpp
Go to the documentation of this file.
1 #ifndef OSMIUM_ITEM_STASH_HPP
2 #define OSMIUM_ITEM_STASH_HPP
3 
4 /*
5 
6 This file is part of Osmium (http://osmcode.org/libosmium).
7 
8 Copyright 2013-2017 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 <cassert>
37 #include <cstdlib>
38 #include <limits>
39 #include <ostream>
40 #include <vector>
41 
42 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
43 # include <iostream>
44 # include <chrono>
45 #endif
46 
47 #include <osmium/memory/buffer.hpp>
48 #include <osmium/memory/item.hpp>
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;
76 
77  explicit handle_type(std::size_t new_value) noexcept :
78  value(new_value) {
79  assert(new_value > 0);
80  }
81 
82  public:
83 
85  handle_type() noexcept :
86  value(0) {
87  }
88 
90  bool valid() const noexcept {
91  return value != 0;
92  }
93 
99  template <typename TChar, typename TTraits>
100  friend inline std::basic_ostream<TChar, TTraits>& operator<<(std::basic_ostream<TChar, TTraits>& out, const ItemStash::handle_type& handle) {
101  if (handle.valid()) {
102  out << handle.value;
103  } else {
104  out << '-';
105  }
106  return out;
107  }
108 
109  }; // class handle_type
110 
111  private:
112 
113  static constexpr const std::size_t initial_buffer_size = 1024 * 1024;
114  static constexpr const std::size_t removed_item_offset = std::numeric_limits<std::size_t>::max();
115 
117  std::vector<std::size_t> m_index;
118  std::size_t m_count_items = 0;
119  std::size_t m_count_removed = 0;
120 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
121  int64_t m_gc_time = 0;
122 #endif
123 
125 
126  std::vector<std::size_t>& m_index;
127  std::size_t m_pos = 0;
128 
129  public:
130 
131  explicit cleanup_helper(std::vector<std::size_t>& index) :
132  m_index(index) {
133  }
134 
135  void moving_in_buffer(std::size_t old_offset, std::size_t new_offset) {
136  while (m_index[m_pos] != old_offset) {
137  ++m_pos;
138  assert(m_pos < m_index.size());
139  }
140  m_index[m_pos] = new_offset;
141  ++m_pos;
142  }
143 
144  }; // cleanup_helper
145 
146  std::size_t& get_item_offset_ref(handle_type handle) noexcept {
147  assert(handle.valid() && "handle must be valid");
148  assert(handle.value <= m_index.size());
149  auto& offset = m_index[handle.value - 1];
150  assert(offset != removed_item_offset);
151  assert(offset < m_buffer.committed());
152  return offset;
153  }
154 
155  std::size_t get_item_offset(handle_type handle) const noexcept {
156  assert(handle.valid() && "handle must be valid");
157  assert(handle.value <= m_index.size());
158  const auto& offset = m_index[handle.value - 1];
159  assert(offset != removed_item_offset);
160  assert(offset < m_buffer.committed());
161  return offset;
162  }
163 
164  // This function decides whether it makes sense to garbage collect the
165  // database. The values here are the result of some experimentation
166  // with real data. We need to balance the memory use with the time
167  // spent on garbage collecting. We don't need to garbage collect if
168  // there is enough space in the buffer anyway (*4). On the other hand,
169  // if there aren't enough removed objects we would just call the
170  // garbage collection again and again, then it is better to let the
171  // buffer grow (*3). The checks (*1) and (*2) make sure there is
172  // minimum and maximum for the number of removed objects.
173  bool should_gc() const noexcept {
174  if (m_count_removed < 10 * 1000) { // *1
175  return false;
176  }
177  if (m_count_removed > 5 * 1000 * 1000) { // *2
178  return true;
179  }
180  if (m_count_removed * 5 < m_count_items) { // *3
181  return false;
182  }
183  return m_buffer.capacity() - m_buffer.committed() < 10 * 1024; // *4
184  }
185 
186  public:
187 
189  m_buffer(initial_buffer_size, osmium::memory::Buffer::auto_grow::yes) {
190  }
191 
198  std::size_t used_memory() const noexcept {
199  return sizeof(ItemStash) +
200  m_buffer.capacity() +
201  m_index.capacity() * sizeof(std::size_t);
202  }
203 
210  std::size_t size() const noexcept {
211  return m_count_items;
212  }
213 
220  std::size_t count_removed() const noexcept {
221  return m_count_removed;
222  }
223 
228  void clear() {
229  m_buffer.clear();
230  m_index.clear();
231  m_count_items = 0;
232  m_count_removed = 0;
233  }
234 
242  if (should_gc()) {
243  garbage_collect();
244  }
245  ++m_count_items;
246  const auto offset = m_buffer.committed();
247  m_buffer.add_item(item);
248  m_buffer.commit();
249  m_index.push_back(offset);
250  return handle_type{m_index.size()};
251  }
252 
265  return m_buffer.get<osmium::memory::Item>(get_item_offset(handle));
266  }
267 
283  template <typename T>
284  T& get(handle_type handle) const {
285  return static_cast<T&>(get_item(handle));
286  }
287 
297 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
298  std::cerr << "GC items=" << m_count_items << " removed=" << m_count_removed << " buffer.committed=" << m_buffer.committed() << " buffer.capacity=" << m_buffer.capacity() << "\n";
299  using clock = std::chrono::high_resolution_clock;
300  std::chrono::time_point<clock> start = clock::now();
301 #endif
302 
303  m_count_removed = 0;
304  cleanup_helper helper{m_index};
305  m_buffer.purge_removed(&helper);
306 
307 #ifdef OSMIUM_ITEM_STORAGE_GC_DEBUG
308  std::chrono::time_point<clock> stop = clock::now();
309  const int64_t time = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();
310  m_gc_time += time;
311  std::cerr << " time=" << time
312  << "us total=" << m_gc_time << "us\n";
313 #endif
314  }
315 
328  void remove_item(handle_type handle) {
329  auto& offset = get_item_offset_ref(handle);
330  auto& item = m_buffer.get<osmium::memory::Item>(offset);
331  assert(!item.removed() && "can not call remove_item() on already removed item");
332  item.set_removed(true);
333  offset = removed_item_offset;
334  --m_count_items;
335  ++m_count_removed;
336  }
337 
338  }; // class ItemStash
339 
340 } // namespace osmium
341 
342 #endif // OSMIUM_ITEM_STASH_HPP
std::size_t capacity() const noexcept
Definition: buffer.hpp:260
std::size_t commit()
Definition: buffer.hpp:355
std::size_t m_count_items
Definition: item_stash.hpp:118
std::size_t value
Definition: item_stash.hpp:75
handle_type add_item(const osmium::memory::Item &item)
Definition: item_stash.hpp:241
handle_type() noexcept
The defalt constructor creates an invalid handle.
Definition: item_stash.hpp:85
cleanup_helper(std::vector< std::size_t > &index)
Definition: item_stash.hpp:131
std::size_t count_removed() const noexcept
Definition: item_stash.hpp:220
Definition: item_stash.hpp:71
static constexpr const std::size_t initial_buffer_size
Definition: item_stash.hpp:113
osmium::memory::Item & get_item(handle_type handle) const
Definition: item_stash.hpp:264
std::size_t used_memory() const noexcept
Definition: item_stash.hpp:198
std::size_t m_count_removed
Definition: item_stash.hpp:119
std::size_t clear()
Definition: buffer.hpp:386
std::size_t committed() const noexcept
Definition: buffer.hpp:268
static constexpr const std::size_t removed_item_offset
Definition: item_stash.hpp:114
osmium::memory::Buffer m_buffer
Definition: item_stash.hpp:116
Definition: item_stash.hpp:57
handle_type(std::size_t new_value) noexcept
Definition: item_stash.hpp:77
Definition: item.hpp:105
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
T & add_item(const T &item)
Definition: buffer.hpp:483
std::vector< std::size_t > m_index
Definition: item_stash.hpp:117
void purge_removed(TCallbackClass *callback)
Definition: buffer.hpp:731
T & get(const std::size_t offset) const
Definition: buffer.hpp:405
bool should_gc() const noexcept
Definition: item_stash.hpp:173
ItemStash()
Definition: item_stash.hpp:188
void garbage_collect()
Definition: item_stash.hpp:296
void moving_in_buffer(std::size_t old_offset, std::size_t new_offset)
Definition: item_stash.hpp:135
void set_removed(bool removed) noexcept
Definition: item.hpp:177
std::vector< std::size_t > & m_index
Definition: item_stash.hpp:126
std::size_t size() const noexcept
Definition: item_stash.hpp:210
friend class ItemStash
Definition: item_stash.hpp:73
Definition: buffer.hpp:98
void remove_item(handle_type handle)
Definition: item_stash.hpp:328
bool valid() const noexcept
Is this a valid handle?
Definition: item_stash.hpp:90
std::size_t & get_item_offset_ref(handle_type handle) noexcept
Definition: item_stash.hpp:146
void clear()
Definition: item_stash.hpp:228
std::size_t get_item_offset(handle_type handle) const noexcept
Definition: item_stash.hpp:155
Definition: item_stash.hpp:124