Libosmium  2.20.0
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-2023 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 {
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 
162  static typename std::iterator_traits<iterator>::difference_type count_not_removed(const iterator_range<iterator>& range) noexcept {
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 
246  void track(RelationHandle& rel_handle, osmium::object_id_type member_id, std::size_t member_num) {
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 
273  void remove(osmium::object_id_type member_id, osmium::object_id_type relation_id) {
274  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling remove().");
275  const auto range = find(member_id);
276 
277  if (range.empty()) {
278  return;
279  }
280 
281  // If this is the last time this object was needed, remove it
282  // from the stash.
283  if (count_not_removed(range) == 1) {
284  m_stash.remove_item(range.begin()->object_handle);
285  }
286 
287  for (auto& elem : range) {
288  if (!elem.is_removed() && relation_id == m_relations_db[elem.relation_pos]->id()) {
289  elem.remove();
290  break;
291  }
292  }
293  }
294 
306  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get_object().");
307  const auto range = find(id);
308  if (range.empty()) {
309  return nullptr;
310  }
311  const auto handle = range.begin()->object_handle;
312  if (handle.valid()) {
313  return &m_stash.get<osmium::OSMObject>(handle);
314  }
315  return nullptr;
316  }
317 
318  }; // class MembersDatabaseCommon
319 
332  template <typename TObject>
334 
335 
336  public:
337 
349  MembersDatabaseCommon(stash, relation_db) {
350  }
351 
363  template <typename TFunc>
364  bool add(const TObject& object, TFunc&& func) {
365  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling add().");
366  auto range = find(object.id());
367 
368  if (range.empty()) {
369  // No relation needs this object.
370  return false;
371  }
372 
373  // At least one relation needs this object. Store it and
374  // "tell" all relations.
375  add_object(object, range);
376 
377  for (auto& elem : range) {
378  assert(!elem.is_removed());
379  assert(elem.member_id == object.id());
380 
381  auto rel_handle = m_relations_db[elem.relation_pos];
382  assert(elem.member_num < rel_handle->members().size());
383  rel_handle.decrement_members();
384 
385  if (rel_handle.has_all_members()) {
386  func(rel_handle);
387  }
388  }
389 
390  return true;
391  }
392 
403  const TObject* get(osmium::object_id_type id) const {
404  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get().");
405  return static_cast<const TObject*>(get_object(id));
406  }
407 
408  }; // class MembersDatabase
409 
410  } // namespace relations
411 
412 } // namespace osmium
413 
414 #endif // OSMIUM_RELATIONS_MEMBERS_DATABASE_HPP
Definition: item_stash.hpp:71
Definition: item_stash.hpp:57
void remove_item(handle_type handle)
Definition: item_stash.hpp:338
T & get(handle_type handle) const
Definition: item_stash.hpp:294
handle_type add_item(const osmium::memory::Item &item)
Definition: item_stash.hpp:251
Definition: object.hpp:64
Definition: members_database.hpp:62
iterator_range< const_iterator > find(osmium::object_id_type id) const
Definition: members_database.hpp:158
void prepare_for_lookup()
Definition: members_database.hpp:259
std::vector< element > m_elements
Definition: members_database.hpp:138
std::size_t size() const noexcept
Definition: members_database.hpp:199
void track(RelationHandle &rel_handle, osmium::object_id_type member_id, std::size_t member_num)
Definition: members_database.hpp:246
std::vector< element >::const_iterator const_iterator
Definition: members_database.hpp:152
bool m_init_phase
Definition: members_database.hpp:148
osmium::relations::RelationsDatabase & m_relations_db
Definition: members_database.hpp:143
void remove(osmium::object_id_type member_id, osmium::object_id_type relation_id)
Definition: members_database.hpp:273
static std::iterator_traits< iterator >::difference_type count_not_removed(const iterator_range< iterator > &range) noexcept
Definition: members_database.hpp:162
osmium::ItemStash & m_stash
Definition: members_database.hpp:142
iterator_range< iterator > find(osmium::object_id_type id)
Definition: members_database.hpp:154
std::vector< element >::iterator iterator
Definition: members_database.hpp:151
const osmium::OSMObject * get_object(osmium::object_id_type id) const
Definition: members_database.hpp:305
MembersDatabaseCommon(osmium::ItemStash &stash, osmium::relations::RelationsDatabase &relations_db)
Definition: members_database.hpp:175
counts count() const noexcept
Definition: members_database.hpp:221
std::size_t used_memory() const noexcept
Definition: members_database.hpp:187
void add_object(const osmium::OSMObject &object, iterator_range< iterator > &range)
Definition: members_database.hpp:168
Definition: members_database.hpp:333
MembersDatabase(osmium::ItemStash &stash, osmium::relations::RelationsDatabase &relation_db)
Definition: members_database.hpp:348
bool add(const TObject &object, TFunc &&func)
Definition: members_database.hpp:364
const TObject * get(osmium::object_id_type id) const
Definition: members_database.hpp:403
Definition: relations_database.hpp:208
std::size_t pos() const noexcept
Definition: relations_database.hpp:238
RelationsDatabase * relation_database() const noexcept
Definition: relations_database.hpp:225
void increment_members() noexcept
Definition: relations_database.hpp:288
Definition: relations_database.hpp:82
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
iterator_range< It > make_range(P &&p) noexcept
Definition: iterator.hpp:68
int64_t object_id_type
Type for OSM object (node, way, or relation) IDs.
Definition: types.hpp:45
Definition: iterator.hpp:42
bool operator()(const element &a, const element &b) const noexcept
Definition: members_database.hpp:133
Definition: members_database.hpp:206
std::size_t available
The number of members tracked and found already.
Definition: members_database.hpp:210
std::size_t tracked
The number of members tracked and not found yet.
Definition: members_database.hpp:208
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: members_database.hpp:64
bool is_removed() const noexcept
Definition: members_database.hpp:116
void remove() noexcept
Definition: members_database.hpp:120
element(std::size_t rel_pos, osmium::object_id_type memb_id, std::size_t memb_num) noexcept
Definition: members_database.hpp:99
@ removed_value
Definition: members_database.hpp:71
element(osmium::object_id_type m_id) noexcept
Definition: members_database.hpp:110
std::size_t relation_pos
Definition: members_database.hpp:89
osmium::object_id_type member_id
Definition: members_database.hpp:79
bool operator<(const element &other) const noexcept
Definition: members_database.hpp:124
std::size_t member_num
Definition: members_database.hpp:84
osmium::ItemStash::handle_type object_handle
Definition: members_database.hpp:97