Libosmium  2.13.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 (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 <cassert>
38 #include <cstddef>
39 #include <limits>
40 #include <tuple>
41 #include <type_traits>
42 #include <vector>
43 
44 #include <osmium/osm/object.hpp>
45 #include <osmium/osm/relation.hpp>
46 #include <osmium/osm/types.hpp>
49 #include <osmium/util/iterator.hpp>
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_elements(),
175  m_stash(stash),
176  m_relations_db(relations_db) {
177  }
178 
179  public:
180 
186  std::size_t used_memory() const noexcept {
187  return sizeof(element) * m_elements.capacity() +
188  sizeof(MembersDatabaseCommon);
189  }
190 
198  std::size_t size() const noexcept {
199  return m_elements.size();
200  }
201 
205  struct counts {
207  std::size_t tracked = 0;
209  std::size_t available = 0;
211  std::size_t removed = 0;
212  };
213 
220  counts count() const noexcept {
221  counts c;
222 
223  for (const auto& elem : m_elements) {
224  if (elem.is_removed()) {
225  ++c.removed;
226  } else if (elem.object_handle.valid()) {
227  ++c.available;
228  } else {
229  ++c.tracked;
230  }
231  }
232 
233  return c;
234  }
235 
246  assert(m_init_phase && "Can not call MembersDatabase::track() after MembersDatabase::prepare_for_lookup().");
247  assert(rel_handle.relation_database() == &m_relations_db);
248  m_elements.emplace_back(rel_handle.pos(), member_id, member_num);
249  rel_handle.increment_members();
250  }
251 
259  assert(m_init_phase && "Can not call MembersDatabase::prepare_for_lookup() twice.");
260  std::sort(m_elements.begin(), m_elements.end());
261 #ifndef NDEBUG
262  m_init_phase = false;
263 #endif
264  }
265 
271  const auto range = find(member_id);
272 
273  if (range.empty()) {
274  return;
275  }
276 
277  // If this is the last time this object was needed, remove it
278  // from the stash.
279  if (count_not_removed(range) == 1) {
280  m_stash.remove_item(range.begin()->object_handle);
281  }
282 
283  for (auto& elem : range) {
284  if (!elem.is_removed() && relation_id == m_relations_db[elem.relation_pos]->id()) {
285  elem.remove();
286  break;
287  }
288  }
289  }
290 
300  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get_object().");
301  const auto range = find(id);
302  if (range.empty()) {
303  return nullptr;
304  }
305  const auto handle = range.begin()->object_handle;
306  if (handle.valid()) {
307  return &m_stash.get<osmium::OSMObject>(handle);
308  }
309  return nullptr;
310  }
311 
312  }; // class MembersDatabaseCommon
313 
326  template <typename TObject>
328 
329 
330  public:
331 
343  MembersDatabaseCommon(stash, relation_db) {
344  }
345 
356  template <typename TFunc>
357  bool add(const TObject& object, TFunc&& func) {
358  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling add().");
359  auto range = find(object.id());
360 
361  if (range.empty()) {
362  // No relation needs this object.
363  return false;
364  }
365 
366  // At least one relation needs this object. Store it and
367  // "tell" all relations.
368  add_object(object, range);
369 
370  for (auto& elem : range) {
371  assert(!elem.is_removed());
372  assert(elem.member_id == object.id());
373 
374  auto rel_handle = m_relations_db[elem.relation_pos];
375  assert(elem.member_num < rel_handle->members().size());
376  rel_handle.decrement_members();
377 
378  if (rel_handle.has_all_members()) {
379  func(rel_handle);
380  }
381  }
382 
383  return true;
384  }
385 
394  const TObject* get(osmium::object_id_type id) const {
395  assert(!m_init_phase && "Call MembersDatabase::prepare_for_lookup() before calling get().");
396  return static_cast<const TObject*>(get_object(id));
397  }
398 
399  }; // class MembersDatabase
400 
401  } // namespace relations
402 
403 } // namespace osmium
404 
405 #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:186
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:209
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:357
osmium::ItemStash & m_stash
Definition: members_database.hpp:140
handle_type add_item(const osmium::memory::Item &item)
Definition: item_stash.hpp:241
std::size_t removed
The number of members that were tracked, found and then removed because of a completed relation...
Definition: members_database.hpp:211
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:327
void track(RelationHandle &rel_handle, osmium::object_id_type member_id, std::size_t member_num)
Definition: members_database.hpp:245
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:207
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:284
const osmium::OSMObject * get_object(osmium::object_id_type id) const
Definition: members_database.hpp:299
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:342
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:205
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:328
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:220
void prepare_for_lookup()
Definition: members_database.hpp:258
std::size_t size() const noexcept
Definition: members_database.hpp:198
Definition: object.hpp:64