Libosmium  2.15.2
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 (https://osmcode.org/libosmium).
7 
8 Copyright 2013-2019 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/index/index.hpp>
37 #include <osmium/index/map.hpp>
38 
39 #include <algorithm>
40 #include <cstddef>
41 #include <cstdint>
42 #include <utility>
43 #include <vector>
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.
65  enum {
66  bits = 16
67  };
68 
69  enum : uint64_t {
70  block_size = 1ULL << bits
71  };
72 
73  // Minimum number of entries in the sparse index before we
74  // are considering switching to a dense index.
75  enum : 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).
84  enum {
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(std::move(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  bool is_dense() const noexcept {
183  return m_dense;
184  }
185 
186  std::size_t size() const noexcept final {
187  if (m_dense) {
188  return m_dense_blocks.size() * block_size;
189  }
190  return m_sparse_entries.size();
191  }
192 
193  std::size_t used_memory() const noexcept final {
194  return sizeof(FlexMem) +
195  m_sparse_entries.size() * sizeof(entry) +
196  m_dense_blocks.size() * (block_size * sizeof(TValue) + sizeof(std::vector<TValue>));
197  }
198 
199  void set(const TId id, const TValue value) final {
200  if (m_dense) {
201  set_dense(id, value);
202  } else {
203  set_sparse(id, value);
204  }
205  }
206 
207  TValue get_noexcept(const TId id) const noexcept final {
208  if (m_dense) {
209  return get_dense(id);
210  }
211  return get_sparse(id);
212  }
213 
214  TValue get(const TId id) const final {
215  const auto value = get_noexcept(id);
216  if (value == osmium::index::empty_value<TValue>()) {
217  throw osmium::not_found{id};
218  }
219  return value;
220  }
221 
222  void clear() final {
223  m_sparse_entries.clear();
224  m_sparse_entries.shrink_to_fit();
225  m_dense_blocks.clear();
226  m_dense_blocks.shrink_to_fit();
227  m_max_id = 0;
228  m_dense = false;
229  }
230 
231  void sort() final {
232  std::sort(m_sparse_entries.begin(), m_sparse_entries.end());
233  }
234 
244  if (m_dense) {
245  return;
246  }
247  for (const auto entry : m_sparse_entries) {
249  }
250  m_sparse_entries.clear();
251  m_sparse_entries.shrink_to_fit();
252  m_max_id = 0;
253  m_dense = true;
254  }
255 
256  std::pair<std::size_t, std::size_t> stats() const noexcept {
257  std::size_t used_blocks = 0;
258  std::size_t empty_blocks = 0;
259 
260  for (const auto& block : m_dense_blocks) {
261  if (block.empty()) {
262  ++empty_blocks;
263  } else {
264  ++used_blocks;
265  }
266  }
267 
268  return std::make_pair(used_blocks, empty_blocks);
269  }
270 
271  }; // class FlexMem
272 
273  } // namespace map
274 
275  } // namespace index
276 
277 } // namespace osmium
278 
279 #ifdef OSMIUM_WANT_NODE_LOCATION_MAPS
281 #endif
282 
283 #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:186
TValue get_noexcept(const TId id) const noexcept final
Definition: flex_mem.hpp:207
#define REGISTER_MAP(id, value, klass, name)
Definition: map.hpp:285
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
Definition: location.hpp:550
bool is_dense() const noexcept
Definition: flex_mem.hpp:182
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
std::vector< entry > m_sparse_entries
Definition: flex_mem.hpp:103
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
Definition: flex_mem.hpp:70
std::pair< std::size_t, std::size_t > stats() const noexcept
Definition: flex_mem.hpp:256
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:231
Definition: flex_mem.hpp:66
TValue value
Definition: flex_mem.hpp:91
static uint64_t offset(const uint64_t id) noexcept
Definition: flex_mem.hpp:117
Definition: location.hpp:271
std::vector< std::vector< TValue > > m_dense_blocks
Definition: flex_mem.hpp:105
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:193
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:222
void switch_to_dense()
Definition: flex_mem.hpp:243
FlexMem(bool use_dense=false)
Definition: flex_mem.hpp:178
Definition: map.hpp:96