Libosmium  2.13.0
Fast and flexible C++ library for working with OpenStreetMap data
flex_mem.hpp
Go to the documentation of this file.
1 #ifndef OSMIUM_INDEX_MAP_FLEX_MEM_HPP
2 #define OSMIUM_INDEX_MAP_FLEX_MEM_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 <algorithm>
37 #include <cstddef>
38 #include <cstdint>
39 #include <utility>
40 #include <vector>
41 
42 #include <osmium/index/map.hpp>
43 #include <osmium/index/index.hpp>
44 
45 #define OSMIUM_HAS_INDEX_MAP_FLEX_MEM
46 
47 namespace osmium {
48 
49  namespace index {
50 
51  namespace map {
52 
60  template <typename TId, typename TValue>
61  class FlexMem : public osmium::index::map::Map<TId, TValue> {
62 
63  // This value is based on benchmarks with a planet file and
64  // some smaller files.
66  bits = 16
67  };
68 
69  enum constant_block_size : uint64_t {
70  block_size = 1ll << bits
71  };
72 
73  // Minimum number of entries in the sparse index before we
74  // are considering switching to a dense index.
75  enum constant_min_dense_entries : int64_t {
76  min_dense_entries = 0xffffff
77  };
78 
79  // When more than a third of all Ids are in the index, we
80  // switch to the dense index. This is a compromise between
81  // the best memory efficiency (which we would get at a factor
82  // of 2) and the performance (dense index is much faster then
83  // the sparse index).
86  };
87 
88  // An entry in the sparse index
89  struct entry {
90  uint64_t id;
91  TValue value;
92 
93  entry(uint64_t i, TValue v) :
94  id(i),
95  value(v) {
96  }
97 
98  bool operator<(const entry other) const noexcept {
99  return id < other.id;
100  }
101  };
102 
103  std::vector<entry> m_sparse_entries;
104 
105  std::vector<std::vector<TValue>> m_dense_blocks;
106 
107  // The maximum Id that was seen yet. Only set in sparse mode.
108  uint64_t m_max_id = 0;
109 
110  // Set to false in sparse mode and to true in dense mode.
111  bool m_dense;
112 
113  static uint64_t block(const uint64_t id) noexcept {
114  return id >> bits;
115  }
116 
117  static uint64_t offset(const uint64_t id) noexcept {
118  return id & (block_size - 1);
119  }
120 
121  // Assure that the block with the given number exists. Create
122  // it if needed.
123  void assure_block(const uint64_t num) {
124  if (num >= m_dense_blocks.size()) {
125  m_dense_blocks.resize(num + 1);
126  }
127  if (m_dense_blocks[num].empty()) {
128  m_dense_blocks[num].assign(block_size, osmium::index::empty_value<TValue>());
129  }
130  }
131 
132  void set_sparse(const uint64_t id, const TValue value) {
133  m_sparse_entries.emplace_back(id, value);
134  if (id > m_max_id) {
135  m_max_id = id;
136 
137  if (m_sparse_entries.size() >= min_dense_entries) {
138  if (m_max_id < m_sparse_entries.size() * density_factor) {
139  switch_to_dense();
140  }
141  }
142  }
143  }
144 
145  TValue get_sparse(const uint64_t id) const noexcept {
146  const auto it = std::lower_bound(m_sparse_entries.begin(),
147  m_sparse_entries.end(),
148  entry{id, osmium::index::empty_value<TValue>()});
149  if (it == m_sparse_entries.end() || it->id != id) {
150  return osmium::index::empty_value<TValue>();
151  }
152  return it->value;
153  }
154 
155  void set_dense(const uint64_t id, const TValue value) {
156  assure_block(block(id));
157  m_dense_blocks[block(id)][offset(id)] = value;
158  }
159 
160  TValue get_dense(const uint64_t id) const noexcept {
161  if (m_dense_blocks.size() <= block(id) || m_dense_blocks[block(id)].empty()) {
162  return osmium::index::empty_value<TValue>();
163  }
164  return m_dense_blocks[block(id)][offset(id)];
165  }
166 
167  public:
168 
178  explicit FlexMem(bool use_dense = false) :
179  m_dense(use_dense) {
180  }
181 
182  ~FlexMem() noexcept final = default;
183 
184  bool is_dense() const noexcept {
185  return m_dense;
186  }
187 
188  std::size_t size() const noexcept final {
189  if (m_dense) {
190  return m_dense_blocks.size() * block_size;
191  }
192  return m_sparse_entries.size();
193  }
194 
195  std::size_t used_memory() const noexcept final {
196  return sizeof(FlexMem) +
197  m_sparse_entries.size() * sizeof(entry) +
198  m_dense_blocks.size() * (block_size * sizeof(TValue) + sizeof(std::vector<TValue>));
199  }
200 
201  void set(const TId id, const TValue value) final {
202  if (m_dense) {
203  set_dense(id, value);
204  } else {
205  set_sparse(id, value);
206  }
207  }
208 
209  TValue get_noexcept(const TId id) const noexcept final {
210  if (m_dense) {
211  return get_dense(id);
212  }
213  return get_sparse(id);
214  }
215 
216  TValue get(const TId id) const final {
217  const auto value = get_noexcept(id);
218  if (value == osmium::index::empty_value<TValue>()) {
219  throw osmium::not_found{id};
220  }
221  return value;
222  }
223 
224  void clear() final {
225  m_sparse_entries.clear();
226  m_sparse_entries.shrink_to_fit();
227  m_dense_blocks.clear();
228  m_dense_blocks.shrink_to_fit();
229  m_max_id = 0;
230  m_dense = false;
231  }
232 
233  void sort() final {
234  std::sort(m_sparse_entries.begin(), m_sparse_entries.end());
235  }
236 
246  if (m_dense) {
247  return;
248  }
249  for (const auto entry : m_sparse_entries) {
251  }
252  m_sparse_entries.clear();
253  m_sparse_entries.shrink_to_fit();
254  m_max_id = 0;
255  m_dense = true;
256  }
257 
258  std::pair<std::size_t, std::size_t> stats() const noexcept {
259  std::size_t used_blocks = 0;
260  std::size_t empty_blocks = 0;
261 
262  for (const auto& block : m_dense_blocks) {
263  if (block.empty()) {
264  ++empty_blocks;
265  } else {
266  ++used_blocks;
267  }
268  }
269 
270  return std::make_pair(used_blocks, empty_blocks);
271  }
272 
273  }; // class FlexMem
274 
275  } // namespace map
276 
277  } // namespace index
278 
279 } // namespace osmium
280 
281 #ifdef OSMIUM_WANT_NODE_LOCATION_MAPS
283 #endif
284 
285 #endif // OSMIUM_INDEX_MAP_FLEX_MEM_HPP
bool operator<(const entry other) const noexcept
Definition: flex_mem.hpp:98
std::size_t size() const noexcept final
Definition: flex_mem.hpp:188
TValue get_noexcept(const TId id) const noexcept final
Definition: flex_mem.hpp:209
#define REGISTER_MAP(id, value, klass, name)
Definition: map.hpp:283
void set_dense(const uint64_t id, const TValue value)
Definition: flex_mem.hpp:155
TValue get_dense(const uint64_t id) const noexcept
Definition: flex_mem.hpp:160
uint64_t unsigned_object_id_type
Type for OSM object (node, way, or relation) IDs where we only allow positive IDs.
Definition: types.hpp:46
bool is_dense() const noexcept
Definition: flex_mem.hpp:184
constant_min_dense_entries
Definition: flex_mem.hpp:75
uint64_t m_max_id
Definition: flex_mem.hpp:108
Definition: flex_mem.hpp:89
entry(uint64_t i, TValue v)
Definition: flex_mem.hpp:93
TValue get_sparse(const uint64_t id) const noexcept
Definition: flex_mem.hpp:145
constant_density_factor
Definition: flex_mem.hpp:84
std::vector< entry > m_sparse_entries
Definition: flex_mem.hpp:103
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
constant_block_size
Definition: flex_mem.hpp:69
std::pair< std::size_t, std::size_t > stats() const noexcept
Definition: flex_mem.hpp:258
void set_sparse(const uint64_t id, const TValue value)
Definition: flex_mem.hpp:132
void assure_block(const uint64_t num)
Definition: flex_mem.hpp:123
void sort() final
Definition: flex_mem.hpp:233
Definition: flex_mem.hpp:70
TValue value
Definition: flex_mem.hpp:91
static uint64_t offset(const uint64_t id) noexcept
Definition: flex_mem.hpp:117
Definition: location.hpp:273
~FlexMem() noexcept final=default
std::vector< std::vector< TValue > > m_dense_blocks
Definition: flex_mem.hpp:105
Definition: flex_mem.hpp:66
constant_bits
Definition: flex_mem.hpp:65
Definition: index.hpp:48
static uint64_t block(const uint64_t id) noexcept
Definition: flex_mem.hpp:113
std::size_t used_memory() const noexcept final
Definition: flex_mem.hpp:195
Definition: flex_mem.hpp:61
uint64_t id
Definition: flex_mem.hpp:90
bool m_dense
Definition: flex_mem.hpp:111
void clear() final
Definition: flex_mem.hpp:224
void switch_to_dense()
Definition: flex_mem.hpp:245
FlexMem(bool use_dense=false)
Definition: flex_mem.hpp:178
Definition: map.hpp:96