Libosmium  2.14.1
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-2018 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  static const size_t removed_value = std::numeric_limits<std::size_t>::max();
71 
78 
82  std::size_t member_num;
83 
87  std::size_t relation_pos;
88 
96 
97  explicit element(std::size_t rel_pos, osmium::object_id_type memb_id, std::size_t memb_num) noexcept :
98  member_id(memb_id),
99  member_num(memb_num),
100  relation_pos(rel_pos) {
101  }
102 
108  explicit element(osmium::object_id_type m_id) noexcept :
109  member_id(m_id),
110  member_num(0),
111  relation_pos(0) {
112  }
113 
114  bool is_removed() const noexcept {
115  return member_num == removed_value;
116  }
117 
118  void remove() noexcept {
119  member_num = removed_value;
120  }
121 
122  bool operator<(const element& other) const noexcept {
123  return std::tie(member_id, member_num, relation_pos) <
124  std::tie(other.member_id, other.member_num, other.relation_pos);
125  }
126 
127  }; // struct element
128 
129  // comparison function only comparing member_id.
131  bool operator()(const element& a, const element& b) const noexcept {
132  return a.member_id < b.member_id;
133  }
134  };
135 
136  std::vector<element> m_elements{};
137 
138  protected:
139 
142 
143 #ifndef NDEBUG
144  // This is used only in debug builds to make sure the
145  // prepare_for_lookup() function is called at the right place.
146  bool m_init_phase = true;
147 #endif
148 
149  using iterator = std::vector<element>::iterator;
150  using const_iterator = std::vector<element>::const_iterator;
151 
153  return make_range(std::equal_range(m_elements.begin(), m_elements.end(), element{id}, compare_member_id{}));
154  }
155 
157  return make_range(std::equal_range(m_elements.cbegin(), m_elements.cend(), element{id}, compare_member_id{}));
158  }
159 
161  return std::count_if(range.begin(), range.end(), [](const element& elem) {
162  return !elem.is_removed();
163  });
164  }
165 
167  const auto handle = m_stash.add_item(object);
168  for (auto& elem : range) {
169  elem.object_handle = handle;
170  }
171  }
172 
174  m_stash(stash),
175  m_relations_db(relations_db) {
176  }
177 
178  public:
179 
185  std::size_t used_memory() const noexcept {
186  return sizeof(element) * m_elements.capacity() +
187  sizeof(MembersDatabaseCommon);
188  }
189 
197  std::size_t size() const noexcept {
198  return m_elements.size();
199  }
200 
204  struct counts {
206  std::size_t tracked = 0;
208  std::size_t available = 0;
210  std::size_t removed = 0;
211  };
212 
219  counts count() const noexcept {
220  counts c;
221 
222  for (const auto& elem : m_elements) {
223  if (elem.is_removed()) {
224  ++c.removed;
225  } else if (elem.object_handle.valid()) {
226  ++c.available;
227  } else {
228  ++c.tracked;
229  }
230  }
231 
232  return c;
233  }
234 
245  assert(m_init_phase && "Can not call MembersDatabase::track() after MembersDatabase::prepare_for_lookup().");
246  assert(rel_handle.relation_database() == &m_relations_db);
247  m_elements.emplace_back(rel_handle.pos(), member_id, member_num);
248  rel_handle.increment_members();
249  }
250 
258  assert(m_init_phase && "Can not call MembersDatabase::prepare_for_lookup() twice.");
259  std::sort(m_elements.begin(), m_elements.end());
260 #ifndef NDEBUG
261  m_init_phase = false;
262 #endif
263  }
264 
270  const auto range = find(member_id);
271 
272  if (range.empty()) {
273  return;
274  }
275 
276  // If this is the last time this object was needed, remove it
277  // from the stash.
278  if (count_not_removed(range) == 1) {
279  m_stash.remove_item(range.begin()->object_handle);
280  }
281 
282  for (auto& elem : range) {
283  if (!elem.is_removed() && relation_id == m_relations_db[elem.relation_pos]->id()) {
284  elem.remove();
285  break;
286  }
287  }
288  }
289 
299  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get_object().");
300  const auto range = find(id);
301  if (range.empty()) {
302  return nullptr;
303  }
304  const auto handle = range.begin()->object_handle;
305  if (handle.valid()) {
306  return &m_stash.get<osmium::OSMObject>(handle);
307  }
308  return nullptr;
309  }
310 
311  }; // class MembersDatabaseCommon
312 
325  template <typename TObject>
327 
328 
329  public:
330 
342  MembersDatabaseCommon(stash, relation_db) {
343  }
344 
355  template <typename TFunc>
356  bool add(const TObject& object, TFunc&& func) {
357  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling add().");
358  auto range = find(object.id());
359 
360  if (range.empty()) {
361  // No relation needs this object.
362  return false;
363  }
364 
365  // At least one relation needs this object. Store it and
366  // "tell" all relations.
367  add_object(object, range);
368 
369  for (auto& elem : range) {
370  assert(!elem.is_removed());
371  assert(elem.member_id == object.id());
372 
373  auto rel_handle = m_relations_db[elem.relation_pos];
374  assert(elem.member_num < rel_handle->members().size());
375  rel_handle.decrement_members();
376 
377  if (rel_handle.has_all_members()) {
378  func(rel_handle);
379  }
380  }
381 
382  return true;
383  }
384 
393  const TObject* get(osmium::object_id_type id) const {
394  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get().");
395  return static_cast<const TObject*>(get_object(id));
396  }
397 
398  }; // class MembersDatabase
399 
400  } // namespace relations
401 
402 } // namespace osmium
403 
404 #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:160
std::size_t used_memory() const noexcept
Definition: members_database.hpp:185
Definition: iterator.hpp:42
osmium::ItemStash::handle_type object_handle
Definition: members_database.hpp:95
std::size_t available
The number of members tracked and found already.
Definition: members_database.hpp:208
osmium::object_id_type member_id
Definition: members_database.hpp:77
static const size_t removed_value
Definition: members_database.hpp:70
bool add(const TObject &object, TFunc &&func)
Definition: members_database.hpp:356
osmium::ItemStash & m_stash
Definition: members_database.hpp:140
handle_type add_item(const osmium::memory::Item &item)
Definition: item_stash.hpp:246
std::size_t removed
The number of members that were tracked, found and then removed because of a completed relation...
Definition: members_database.hpp:210
Definition: item_stash.hpp:71
std::vector< element >::iterator iterator
Definition: members_database.hpp:149
element(std::size_t rel_pos, osmium::object_id_type memb_id, std::size_t memb_num) noexcept
Definition: members_database.hpp:97
Definition: members_database.hpp:64
Definition: members_database.hpp:326
void track(RelationHandle &rel_handle, osmium::object_id_type member_id, std::size_t member_num)
Definition: members_database.hpp:244
iterator_range< It > make_range(P &&p) noexcept
Definition: iterator.hpp:68
bool is_removed() const noexcept
Definition: members_database.hpp:114
std::size_t pos() const noexcept
Definition: relations_database.hpp:238
std::vector< element > m_elements
Definition: members_database.hpp:136
Definition: item_stash.hpp:57
std::size_t tracked
The number of members tracked and not found yet.
Definition: members_database.hpp:206
osmium::relations::RelationsDatabase & m_relations_db
Definition: members_database.hpp:141
std::size_t member_num
Definition: members_database.hpp:82
T & get(handle_type handle) const
Definition: item_stash.hpp:289
const osmium::OSMObject * get_object(osmium::object_id_type id) const
Definition: members_database.hpp:298
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
MembersDatabaseCommon(osmium::ItemStash &stash, osmium::relations::RelationsDatabase &relations_db)
Definition: members_database.hpp:173
void add_object(const osmium::OSMObject &object, iterator_range< iterator > &range)
Definition: members_database.hpp:166
void increment_members() noexcept
Definition: relations_database.hpp:288
MembersDatabase(osmium::ItemStash &stash, osmium::relations::RelationsDatabase &relation_db)
Definition: members_database.hpp:341
bool operator<(const element &other) const noexcept
Definition: members_database.hpp:122
iterator_range< iterator > find(osmium::object_id_type id)
Definition: members_database.hpp:152
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:156
Definition: members_database.hpp:204
Definition: relations_database.hpp:82
bool m_init_phase
Definition: members_database.hpp:146
std::vector< element >::const_iterator const_iterator
Definition: members_database.hpp:150
std::size_t relation_pos
Definition: members_database.hpp:87
void remove_item(handle_type handle)
Definition: item_stash.hpp:333
element(osmium::object_id_type m_id) noexcept
Definition: members_database.hpp:108
RelationsDatabase * relation_database() const noexcept
Definition: relations_database.hpp:225
bool operator()(const element &a, const element &b) const noexcept
Definition: members_database.hpp:131
Definition: members_database.hpp:62
counts count() const noexcept
Definition: members_database.hpp:219
void prepare_for_lookup()
Definition: members_database.hpp:257
std::size_t size() const noexcept
Definition: members_database.hpp:197
Definition: object.hpp:64