Libosmium  2.16.0
Fast and flexible C++ library for working with OpenStreetMap data
id_set.hpp
Go to the documentation of this file.
1 #ifndef OSMIUM_INDEX_ID_SET_HPP
2 #define OSMIUM_INDEX_ID_SET_HPP
3 
4 /*
5 
6 This file is part of Osmium (https://osmcode.org/libosmium).
7 
8 Copyright 2013-2021 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/item_type.hpp>
37 #include <osmium/osm/types.hpp>
38 
39 #include <algorithm>
40 #include <array>
41 #include <cassert>
42 #include <cstddef>
43 #include <cstring>
44 #include <iterator>
45 #include <memory>
46 #include <type_traits>
47 #include <vector>
48 
49 namespace osmium {
50 
51  namespace index {
52 
57  template <typename T>
58  class IdSet {
59 
60  public:
61 
62  IdSet() = default;
63 
64  IdSet(const IdSet&) = default;
65  IdSet& operator=(const IdSet&) = default;
66 
67  IdSet(IdSet&&) noexcept = default;
68  IdSet& operator=(IdSet&&) noexcept = default;
69 
70  virtual ~IdSet() = default;
71 
75  virtual void set(T id) = 0;
76 
80  virtual bool get(T id) const noexcept = 0;
81 
85  virtual bool empty() const = 0;
86 
90  virtual void clear() = 0;
91 
95  virtual std::size_t used_memory() const noexcept = 0;
96 
97  }; // class IdSet
98 
99  namespace detail {
100 
101  // This value is a compromise. For node Ids it could be bigger
102  // which would mean less (but larger) memory allocations. For
103  // relations Ids it could be smaller, because they would all fit
104  // into a smaller allocation.
105  enum : std::size_t {
106  default_chunk_bits = 22U
107  };
108 
109  } // namespace detail
110 
111  template <typename T, std::size_t chunk_bits = detail::default_chunk_bits>
112  class IdSetDense;
113 
117  template <typename T, std::size_t chunk_bits>
119 
120 
122 
123  const id_set* m_set;
126 
127  void next() noexcept {
128  while (m_value != m_last && !m_set->get(m_value)) {
129  const T cid = id_set::chunk_id(m_value);
130  assert(cid < m_set->m_data.size());
131  if (!m_set->m_data[cid]) {
132  m_value = (cid + 1) << (chunk_bits + 3);
133  } else {
134  const auto slot = m_set->m_data[cid][id_set::offset(m_value)];
135  if (slot == 0) {
136  m_value += 8;
137  m_value &= ~0x7ULL;
138  } else {
139  ++m_value;
140  }
141  }
142  }
143  }
144 
145  public:
146 
147  using iterator_category = std::forward_iterator_tag;
148  using value_type = T;
149  using pointer = value_type*;
151 
152  IdSetDenseIterator(const id_set* set, T value, T last) noexcept :
153  m_set(set),
154  m_value(value),
155  m_last(last) {
156  next();
157  }
158 
160  if (m_value != m_last) {
161  ++m_value;
162  next();
163  }
164  return *this;
165  }
166 
168  IdSetDenseIterator tmp{*this};
169  operator++();
170  return tmp;
171  }
172 
173  bool operator==(const IdSetDenseIterator& rhs) const noexcept {
174  return m_set == rhs.m_set && m_value == rhs.m_value;
175  }
176 
177  bool operator!=(const IdSetDenseIterator& rhs) const noexcept {
178  return !(*this == rhs);
179  }
180 
181  T operator*() const noexcept {
182  assert(m_value < m_last);
183  return m_value;
184  }
185 
186  }; // class IdSetDenseIterator
187 
195  template <typename T, std::size_t chunk_bits>
196  class IdSetDense : public IdSet<T> {
197 
198 
199  friend class IdSetDenseIterator<T, chunk_bits>;
200 
201  enum : std::size_t {
202  chunk_size = 1U << chunk_bits
203  };
204 
205  std::vector<std::unique_ptr<unsigned char[]>> m_data;
206  T m_size = 0;
207 
208  static std::size_t chunk_id(T id) noexcept {
209  return id >> (chunk_bits + 3U);
210  }
211 
212  static std::size_t offset(T id) noexcept {
213  return (id >> 3U) & ((1U << chunk_bits) - 1U);
214  }
215 
216  static unsigned int bitmask(T id) noexcept {
217  return 1U << (id & 0x7U);
218  }
219 
220  T last() const noexcept {
221  return static_cast<T>(m_data.size()) * chunk_size * 8;
222  }
223 
224  unsigned char& get_element(T id) {
225  const auto cid = chunk_id(id);
226  if (cid >= m_data.size()) {
227  m_data.resize(cid + 1);
228  }
229 
230  auto& chunk = m_data[cid];
231  if (!chunk) {
232  chunk.reset(new unsigned char[chunk_size]);
233  ::memset(chunk.get(), 0, chunk_size);
234  }
235 
236  return chunk[offset(id)];
237  }
238 
239  public:
240 
242 
243  friend void swap(IdSetDense& first, IdSetDense& second) noexcept {
244  using std::swap;
245  swap(first.m_data, second.m_data);
246  swap(first.m_size, second.m_size);
247  }
248 
249  IdSetDense() = default;
250 
251  IdSetDense(const IdSetDense& other) :
252  IdSet<T>(other),
253  m_size(other.m_size) {
254  m_data.reserve(other.m_data.size());
255  for (const auto& ptr: other.m_data) {
256  if (ptr) {
257  m_data.emplace_back(new unsigned char[chunk_size]);
258  ::memcpy(m_data.back().get(), ptr.get(), chunk_size);
259  } else {
260  m_data.emplace_back();
261  }
262  }
263  }
264 
266  swap(*this, other);
267  return *this;
268  }
269 
270  IdSetDense(IdSetDense&&) noexcept = default;
271 
272  // This should really be noexcept, but GCC 4.8 doesn't like it.
273  // NOLINTNEXTLINE(hicpp-noexcept-move, performance-noexcept-move-constructor)
274  IdSetDense& operator=(IdSetDense&&) = default;
275 
276  ~IdSetDense() noexcept override = default;
277 
284  bool check_and_set(T id) {
285  auto& element = get_element(id);
286 
287  if ((element & bitmask(id)) == 0) {
288  element |= bitmask(id);
289  ++m_size;
290  return true;
291  }
292 
293  return false;
294  }
295 
301  void set(T id) final {
302  (void)check_and_set(id);
303  }
304 
310  void unset(T id) {
311  auto& element = get_element(id);
312 
313  if ((element & bitmask(id)) != 0) {
314  element &= ~bitmask(id);
315  --m_size;
316  }
317  }
318 
324  bool get(T id) const noexcept final {
325  if (chunk_id(id) >= m_data.size()) {
326  return false;
327  }
328  const auto* r = m_data[chunk_id(id)].get();
329  if (!r) {
330  return false;
331  }
332  return (r[offset(id)] & bitmask(id)) != 0;
333  }
334 
338  bool empty() const noexcept final {
339  return m_size == 0;
340  }
341 
345  T size() const noexcept {
346  return m_size;
347  }
348 
352  void clear() final {
353  m_data.clear();
354  m_size = 0;
355  }
356 
357  std::size_t used_memory() const noexcept final {
358  return m_data.size() * chunk_size;
359  }
360 
362  return {this, 0, last()};
363  }
364 
365  const_iterator end() const {
366  return {this, last(), last()};
367  }
368 
369  }; // class IdSetDense
370 
375  template <typename T>
376  class IdSetSmall : public IdSet<T> {
377 
378  std::vector<T> m_data;
379 
380  public:
381 
385  void set(T id) final {
386  if (m_data.empty() || m_data.back() != id) {
387  m_data.push_back(id);
388  }
389  }
390 
396  bool get(T id) const noexcept final {
397  const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
398  return it != m_data.cend();
399  }
400 
411  bool get_binary_search(T id) const noexcept {
412  return std::binary_search(m_data.cbegin(), m_data.cend(), id);
413  }
414 
418  bool empty() const noexcept final {
419  return m_data.empty();
420  }
421 
425  void clear() final {
426  m_data.clear();
427  }
428 
434  void sort_unique() {
435  std::sort(m_data.begin(), m_data.end());
436  const auto last = std::unique(m_data.begin(), m_data.end());
437  m_data.erase(last, m_data.end());
438 
439  }
440 
447  std::size_t size() const noexcept {
448  return m_data.size();
449  }
450 
451  std::size_t used_memory() const noexcept final {
452  return m_data.capacity() * sizeof(T);
453  }
454 
461  void merge_sorted(const IdSetSmall<T>& other) {
462  std::vector<T> new_data;
463  new_data.reserve(m_data.size() + other.m_data.size());
464  std::set_union(m_data.cbegin(), m_data.cend(),
465  other.m_data.cbegin(), other.m_data.cend(),
466  std::back_inserter(new_data));
467  using std::swap;
468  swap(new_data, m_data);
469  }
470 
472  using const_iterator = typename std::vector<T>::const_iterator;
473 
474  const_iterator begin() const noexcept {
475  return m_data.cbegin();
476  }
477 
478  const_iterator end() const noexcept {
479  return m_data.cend();
480  }
481 
482  const_iterator cbegin() const noexcept {
483  return m_data.cbegin();
484  }
485 
486  const_iterator cend() const noexcept {
487  return m_data.cend();
488  }
489 
490  }; // class IdSetSmall
491 
493  template <template <typename> class IdSetType>
494  class NWRIdSet {
495 
496  using id_set_type = IdSetType<osmium::unsigned_object_id_type>;
497 
498  std::array<id_set_type, 3> m_sets;
499 
500  public:
501 
503  return m_sets[osmium::item_type_to_nwr_index(type)];
504  }
505 
506  const id_set_type& operator()(osmium::item_type type) const noexcept {
507  return m_sets[osmium::item_type_to_nwr_index(type)];
508  }
509 
510  }; // class NWRIdSet
511 
512  } // namespace index
513 
514 } // namespace osmium
515 
516 #endif // OSMIUM_INDEX_ID_SET_HPP
osmium::index::IdSetDenseIterator::next
void next() noexcept
Definition: id_set.hpp:127
osmium::index::IdSetDenseIterator::operator==
bool operator==(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:173
osmium::index::IdSetSmall::sort_unique
void sort_unique()
Definition: id_set.hpp:434
osmium::index::IdSetSmall::used_memory
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:451
osmium::index::IdSetSmall::empty
bool empty() const noexcept final
Definition: id_set.hpp:418
osmium::index::IdSetSmall::cbegin
const_iterator cbegin() const noexcept
Definition: id_set.hpp:482
osmium::index::NWRIdSet::operator()
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:502
types.hpp
osmium::index::IdSet::get
virtual bool get(T id) const noexcept=0
osmium::index::IdSetSmall::get_binary_search
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:411
osmium::index::IdSetDenseIterator::operator++
IdSetDenseIterator operator++(int) noexcept
Definition: id_set.hpp:167
osmium::index::IdSetDenseIterator::IdSetDenseIterator
IdSetDenseIterator(const id_set *set, T value, T last) noexcept
Definition: id_set.hpp:152
osmium::index::IdSetSmall::clear
void clear() final
Definition: id_set.hpp:425
detail
Definition: attr.hpp:342
osmium::index::IdSetDense::chunk_id
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:208
osmium::index::IdSetDense::size
T size() const noexcept
Definition: id_set.hpp:345
osmium::index::IdSetSmall::merge_sorted
void merge_sorted(const IdSetSmall< T > &other)
Definition: id_set.hpp:461
osmium::index::IdSetDense::IdSetDense
IdSetDense(IdSetDense &&) noexcept=default
osmium::index::IdSetDenseIterator::m_set
const id_set * m_set
Definition: id_set.hpp:123
osmium::index::IdSetDenseIterator::m_last
T m_last
Definition: id_set.hpp:125
osmium::index::IdSetDenseIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:147
osmium::index::IdSetDenseIterator::operator++
IdSetDenseIterator & operator++() noexcept
Definition: id_set.hpp:159
osmium::index::NWRIdSet
Definition: id_set.hpp:494
osmium::index::IdSetDense::m_data
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:205
osmium::index::IdSetDense::get
bool get(T id) const noexcept final
Definition: id_set.hpp:324
osmium::index::IdSetDense::operator=
IdSetDense & operator=(IdSetDense other)
Definition: id_set.hpp:265
osmium::index::IdSetDense::IdSetDense
IdSetDense(const IdSetDense &other)
Definition: id_set.hpp:251
osmium::index::IdSet::IdSet
IdSet(IdSet &&) noexcept=default
osmium::index::IdSet::IdSet
IdSet(const IdSet &)=default
osmium::index::IdSetDenseIterator::operator*
T operator*() const noexcept
Definition: id_set.hpp:181
osmium::index::IdSetSmall::size
std::size_t size() const noexcept
Definition: id_set.hpp:447
osmium
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
osmium::index::IdSetDense::used_memory
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:357
osmium::index::IdSetDense::end
const_iterator end() const
Definition: id_set.hpp:365
osmium::index::IdSet::operator=
IdSet & operator=(const IdSet &)=default
osmium::index::IdSetSmall::get
bool get(T id) const noexcept final
Definition: id_set.hpp:396
osmium::index::NWRIdSet::m_sets
std::array< id_set_type, 3 > m_sets
Definition: id_set.hpp:498
osmium::index::IdSetDense
Definition: id_set.hpp:196
osmium::index::IdSetDenseIterator
Definition: id_set.hpp:118
osmium::index::IdSetDense::begin
const_iterator begin() const
Definition: id_set.hpp:361
osmium::index::IdSetDense::bitmask
static unsigned int bitmask(T id) noexcept
Definition: id_set.hpp:216
osmium::index::IdSetDense::get_element
unsigned char & get_element(T id)
Definition: id_set.hpp:224
osmium::index::IdSetDense::IdSetDense
IdSetDense()=default
osmium::index::IdSetDense::last
T last() const noexcept
Definition: id_set.hpp:220
osmium::index::IdSetDense::clear
void clear() final
Definition: id_set.hpp:352
osmium::index::IdSet::used_memory
virtual std::size_t used_memory() const noexcept=0
osmium::index::NWRIdSet::id_set_type
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:496
osmium::index::IdSetDenseIterator::reference
value_type & reference
Definition: id_set.hpp:150
osmium::index::IdSetDense::swap
friend void swap(IdSetDense &first, IdSetDense &second) noexcept
Definition: id_set.hpp:243
osmium::index::IdSetSmall::const_iterator
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:472
osmium::index::NWRIdSet::operator()
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:506
osmium::index::IdSetDenseIterator::operator!=
bool operator!=(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:177
osmium::index::IdSetSmall::cend
const_iterator cend() const noexcept
Definition: id_set.hpp:486
osmium::index::IdSetDense::offset
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:212
osmium::index::IdSetDenseIterator::value_type
T value_type
Definition: id_set.hpp:148
std
Definition: location.hpp:551
osmium::index::IdSetSmall::set
void set(T id) final
Definition: id_set.hpp:385
osmium::memory::swap
void swap(Buffer &lhs, Buffer &rhs)
Definition: buffer.hpp:885
osmium::index::IdSetSmall::end
const_iterator end() const noexcept
Definition: id_set.hpp:478
osmium::index::IdSet::empty
virtual bool empty() const =0
osmium::index::IdSetDense::set
void set(T id) final
Definition: id_set.hpp:301
osmium::index::IdSetDense::empty
bool empty() const noexcept final
Definition: id_set.hpp:338
osmium::index::IdSetSmall::m_data
std::vector< T > m_data
Definition: id_set.hpp:378
osmium::index::IdSetDense::unset
void unset(T id)
Definition: id_set.hpp:310
osmium::index::IdSet::set
virtual void set(T id)=0
osmium::index::IdSetDenseIterator::pointer
value_type * pointer
Definition: id_set.hpp:149
osmium::index::IdSet::clear
virtual void clear()=0
item_type.hpp
osmium::index::IdSet
Definition: id_set.hpp:58
osmium::index::IdSetSmall::begin
const_iterator begin() const noexcept
Definition: id_set.hpp:474
osmium::index::IdSet::IdSet
IdSet()=default
osmium::osm_entity_bits::type
type
Definition: entity_bits.hpp:63
osmium::item_type
item_type
Definition: item_type.hpp:43
osmium::item_type_to_nwr_index
unsigned int item_type_to_nwr_index(item_type type) noexcept
Definition: item_type.hpp:82
osmium::index::IdSetDenseIterator::m_value
T m_value
Definition: id_set.hpp:124
osmium::index::IdSetSmall
Definition: id_set.hpp:376