Libosmium  2.15.5
Fast and flexible C++ library for working with OpenStreetMap data
members_database.hpp
Go to the documentation of this file.
1 #ifndef OSMIUM_RELATIONS_MEMBERS_DATABASE_HPP
2 #define OSMIUM_RELATIONS_MEMBERS_DATABASE_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/osm/object.hpp>
37 #include <osmium/osm/relation.hpp>
38 #include <osmium/osm/types.hpp>
41 #include <osmium/util/iterator.hpp>
42 
43 #include <algorithm>
44 #include <cassert>
45 #include <cstddef>
46 #include <limits>
47 #include <tuple>
48 #include <type_traits>
49 #include <vector>
50 
51 namespace osmium {
52 
53  namespace relations {
54 
63 
64  struct element {
65 
70  enum {
71  removed_value = std::numeric_limits<std::size_t>::max()
72  };
73 
80 
84  std::size_t member_num;
85 
89  std::size_t relation_pos;
90 
98 
99  explicit element(std::size_t rel_pos, osmium::object_id_type memb_id, std::size_t memb_num) noexcept :
100  member_id(memb_id),
101  member_num(memb_num),
102  relation_pos(rel_pos) {
103  }
104 
110  explicit element(osmium::object_id_type m_id) noexcept :
111  member_id(m_id),
112  member_num(0),
113  relation_pos(0) {
114  }
115 
116  bool is_removed() const noexcept {
117  return member_num == removed_value;
118  }
119 
120  void remove() noexcept {
121  member_num = removed_value;
122  }
123 
124  bool operator<(const element& other) const noexcept {
125  return std::tie(member_id, member_num, relation_pos) <
126  std::tie(other.member_id, other.member_num, other.relation_pos);
127  }
128 
129  }; // struct element
130 
131  // comparison function only comparing member_id.
133  bool operator()(const element& a, const element& b) const noexcept {
134  return a.member_id < b.member_id;
135  }
136  };
137 
138  std::vector<element> m_elements{};
139 
140  protected:
141 
144 
145 #ifndef NDEBUG
146  // This is used only in debug builds to make sure the
147  // prepare_for_lookup() function is called at the right place.
148  bool m_init_phase = true;
149 #endif
150 
151  using iterator = std::vector<element>::iterator;
152  using const_iterator = std::vector<element>::const_iterator;
153 
155  return make_range(std::equal_range(m_elements.begin(), m_elements.end(), element{id}, compare_member_id{}));
156  }
157 
159  return make_range(std::equal_range(m_elements.cbegin(), m_elements.cend(), element{id}, compare_member_id{}));
160  }
161 
163  return std::count_if(range.begin(), range.end(), [](const element& elem) {
164  return !elem.is_removed();
165  });
166  }
167 
169  const auto handle = m_stash.add_item(object);
170  for (auto& elem : range) {
171  elem.object_handle = handle;
172  }
173  }
174 
176  m_stash(stash),
177  m_relations_db(relations_db) {
178  }
179 
180  public:
181 
187  std::size_t used_memory() const noexcept {
188  return sizeof(element) * m_elements.capacity() +
189  sizeof(MembersDatabaseCommon);
190  }
191 
199  std::size_t size() const noexcept {
200  return m_elements.size();
201  }
202 
206  struct counts {
208  std::size_t tracked = 0;
210  std::size_t available = 0;
212  std::size_t removed = 0;
213  };
214 
221  counts count() const noexcept {
222  counts c;
223 
224  for (const auto& elem : m_elements) {
225  if (elem.is_removed()) {
226  ++c.removed;
227  } else if (elem.object_handle.valid()) {
228  ++c.available;
229  } else {
230  ++c.tracked;
231  }
232  }
233 
234  return c;
235  }
236 
247  assert(m_init_phase && "Can not call MembersDatabase::track() after MembersDatabase::prepare_for_lookup().");
248  assert(rel_handle.relation_database() == &m_relations_db);
249  m_elements.emplace_back(rel_handle.pos(), member_id, member_num);
250  rel_handle.increment_members();
251  }
252 
260  assert(m_init_phase && "Can not call MembersDatabase::prepare_for_lookup() twice.");
261  std::sort(m_elements.begin(), m_elements.end());
262 #ifndef NDEBUG
263  m_init_phase = false;
264 #endif
265  }
266 
272  const auto range = find(member_id);
273 
274  if (range.empty()) {
275  return;
276  }
277 
278  // If this is the last time this object was needed, remove it
279  // from the stash.
280  if (count_not_removed(range) == 1) {
281  m_stash.remove_item(range.begin()->object_handle);
282  }
283 
284  for (auto& elem : range) {
285  if (!elem.is_removed() && relation_id == m_relations_db[elem.relation_pos]->id()) {
286  elem.remove();
287  break;
288  }
289  }
290  }
291 
301  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get_object().");
302  const auto range = find(id);
303  if (range.empty()) {
304  return nullptr;
305  }
306  const auto handle = range.begin()->object_handle;
307  if (handle.valid()) {
308  return &m_stash.get<osmium::OSMObject>(handle);
309  }
310  return nullptr;
311  }
312 
313  }; // class MembersDatabaseCommon
314 
327  template <typename TObject>
329 
330 
331  public:
332 
344  MembersDatabaseCommon(stash, relation_db) {
345  }
346 
357  template <typename TFunc>
358  bool add(const TObject& object, TFunc&& func) {
359  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling add().");
360  auto range = find(object.id());
361 
362  if (range.empty()) {
363  // No relation needs this object.
364  return false;
365  }
366 
367  // At least one relation needs this object. Store it and
368  // "tell" all relations.
369  add_object(object, range);
370 
371  for (auto& elem : range) {
372  assert(!elem.is_removed());
373  assert(elem.member_id == object.id());
374 
375  auto rel_handle = m_relations_db[elem.relation_pos];
376  assert(elem.member_num < rel_handle->members().size());
377  rel_handle.decrement_members();
378 
379  if (rel_handle.has_all_members()) {
380  func(rel_handle);
381  }
382  }
383 
384  return true;
385  }
386 
395  const TObject* get(osmium::object_id_type id) const {
396  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get().");
397  return static_cast<const TObject*>(get_object(id));
398  }
399 
400  }; // class MembersDatabase
401 
402  } // namespace relations
403 
404 } // namespace osmium
405 
406 #endif // OSMIUM_RELATIONS_MEMBERS_DATABASE_HPP
static iterator_range< iterator >::iterator::difference_type count_not_removed(const iterator_range< iterator > &range) noexcept
Definition: members_database.hpp:162
std::size_t used_memory() const noexcept
Definition: members_database.hpp:187
Definition: iterator.hpp:42
osmium::ItemStash::handle_type object_handle
Definition: members_database.hpp:97
std::size_t available
The number of members tracked and found already.
Definition: members_database.hpp:210
osmium::object_id_type member_id
Definition: members_database.hpp:79
bool add(const TObject &object, TFunc &&func)
Definition: members_database.hpp:358
osmium::ItemStash & m_stash
Definition: members_database.hpp:142
handle_type add_item(const osmium::memory::Item &item)
Definition: item_stash.hpp:251
std::size_t removed
The number of members that were tracked, found and then removed because of a completed relation...
Definition: members_database.hpp:212
Definition: item_stash.hpp:71
std::vector< element >::iterator iterator
Definition: members_database.hpp:151
element(std::size_t rel_pos, osmium::object_id_type memb_id, std::size_t memb_num) noexcept
Definition: members_database.hpp:99
Definition: members_database.hpp:64
Definition: members_database.hpp:328
void track(RelationHandle &rel_handle, osmium::object_id_type member_id, std::size_t member_num)
Definition: members_database.hpp:246
iterator_range< It > make_range(P &&p) noexcept
Definition: iterator.hpp:68
bool is_removed() const noexcept
Definition: members_database.hpp:116
std::size_t pos() const noexcept
Definition: relations_database.hpp:238
std::vector< element > m_elements
Definition: members_database.hpp:138
Definition: item_stash.hpp:57
std::size_t tracked
The number of members tracked and not found yet.
Definition: members_database.hpp:208
osmium::relations::RelationsDatabase & m_relations_db
Definition: members_database.hpp:143
std::size_t member_num
Definition: members_database.hpp:84
T & get(handle_type handle) const
Definition: item_stash.hpp:294
const osmium::OSMObject * get_object(osmium::object_id_type id) const
Definition: members_database.hpp:300
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
MembersDatabaseCommon(osmium::ItemStash &stash, osmium::relations::RelationsDatabase &relations_db)
Definition: members_database.hpp:175
void add_object(const osmium::OSMObject &object, iterator_range< iterator > &range)
Definition: members_database.hpp:168
void increment_members() noexcept
Definition: relations_database.hpp:288
MembersDatabase(osmium::ItemStash &stash, osmium::relations::RelationsDatabase &relation_db)
Definition: members_database.hpp:343
bool operator<(const element &other) const noexcept
Definition: members_database.hpp:124
iterator_range< iterator > find(osmium::object_id_type id)
Definition: members_database.hpp:154
int64_t object_id_type
Type for OSM object (node, way, or relation) IDs.
Definition: types.hpp:45
Definition: relations_database.hpp:208
iterator_range< const_iterator > find(osmium::object_id_type id) const
Definition: members_database.hpp:158
Definition: members_database.hpp:206
Definition: relations_database.hpp:82
bool m_init_phase
Definition: members_database.hpp:148
std::vector< element >::const_iterator const_iterator
Definition: members_database.hpp:152
std::size_t relation_pos
Definition: members_database.hpp:89
void remove_item(handle_type handle)
Definition: item_stash.hpp:338
element(osmium::object_id_type m_id) noexcept
Definition: members_database.hpp:110
RelationsDatabase * relation_database() const noexcept
Definition: relations_database.hpp:225
bool operator()(const element &a, const element &b) const noexcept
Definition: members_database.hpp:133
Definition: members_database.hpp:62
counts count() const noexcept
Definition: members_database.hpp:221
void prepare_for_lookup()
Definition: members_database.hpp:259
std::size_t size() const noexcept
Definition: members_database.hpp:199
Definition: object.hpp:64