Libosmium  2.15.4
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-2019 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_data.reserve(other.m_data.size());
254  for (const auto& ptr: other.m_data) {
255  if (ptr) {
256  m_data.emplace_back(new unsigned char[chunk_size]);
257  ::memcpy(m_data.back().get(), ptr.get(), chunk_size);
258  } else {
259  m_data.emplace_back();
260  }
261  }
262  m_size = other.m_size;
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  IdSetDense& operator=(IdSetDense&&) = default;
274 
275  ~IdSetDense() noexcept override = default;
276 
283  bool check_and_set(T id) {
284  auto& element = get_element(id);
285 
286  if ((element & bitmask(id)) == 0) {
287  element |= bitmask(id);
288  ++m_size;
289  return true;
290  }
291 
292  return false;
293  }
294 
300  void set(T id) final {
301  (void)check_and_set(id);
302  }
303 
309  void unset(T id) {
310  auto& element = get_element(id);
311 
312  if ((element & bitmask(id)) != 0) {
313  element &= ~bitmask(id);
314  --m_size;
315  }
316  }
317 
323  bool get(T id) const noexcept final {
324  if (chunk_id(id) >= m_data.size()) {
325  return false;
326  }
327  const auto* r = m_data[chunk_id(id)].get();
328  if (!r) {
329  return false;
330  }
331  return (r[offset(id)] & bitmask(id)) != 0;
332  }
333 
337  bool empty() const noexcept final {
338  return m_size == 0;
339  }
340 
344  T size() const noexcept {
345  return m_size;
346  }
347 
351  void clear() final {
352  m_data.clear();
353  m_size = 0;
354  }
355 
356  std::size_t used_memory() const noexcept final {
357  return m_data.size() * chunk_size;
358  }
359 
361  return {this, 0, last()};
362  }
363 
364  const_iterator end() const {
365  return {this, last(), last()};
366  }
367 
368  }; // class IdSetDense
369 
374  template <typename T>
375  class IdSetSmall : public IdSet<T> {
376 
377  std::vector<T> m_data;
378 
379  public:
380 
384  void set(T id) final {
385  m_data.push_back(id);
386  }
387 
393  bool get(T id) const noexcept final {
394  const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
395  return it != m_data.cend();
396  }
397 
408  bool get_binary_search(T id) const noexcept {
409  return std::binary_search(m_data.cbegin(), m_data.cend(), id);
410  }
411 
415  bool empty() const noexcept final {
416  return m_data.empty();
417  }
418 
422  void clear() final {
423  m_data.clear();
424  }
425 
430  void sort_unique() {
431  std::sort(m_data.begin(), m_data.end());
432  const auto last = std::unique(m_data.begin(), m_data.end());
433  m_data.erase(last, m_data.end());
434 
435  }
436 
443  std::size_t size() const noexcept {
444  return m_data.size();
445  }
446 
447  std::size_t used_memory() const noexcept final {
448  return m_data.capacity() * sizeof(T);
449  }
450 
452  using const_iterator = typename std::vector<T>::const_iterator;
453 
454  const_iterator begin() const noexcept {
455  return m_data.cbegin();
456  }
457 
458  const_iterator end() const noexcept {
459  return m_data.cend();
460  }
461 
462  const_iterator cbegin() const noexcept {
463  return m_data.cbegin();
464  }
465 
466  const_iterator cend() const noexcept {
467  return m_data.cend();
468  }
469 
470  }; // class IdSetSmall
471 
473  template <template <typename> class IdSetType>
474  class NWRIdSet {
475 
476  using id_set_type = IdSetType<osmium::unsigned_object_id_type>;
477 
478  std::array<id_set_type, 3> m_sets;
479 
480  public:
481 
483  return m_sets[osmium::item_type_to_nwr_index(type)];
484  }
485 
486  const id_set_type& operator()(osmium::item_type type) const noexcept {
487  return m_sets[osmium::item_type_to_nwr_index(type)];
488  }
489 
490  }; // class NWRIdSet
491 
492  } // namespace index
493 
494 } // namespace osmium
495 
496 #endif // OSMIUM_INDEX_ID_SET_HPP
T size() const noexcept
Definition: id_set.hpp:344
const_iterator end() const
Definition: id_set.hpp:364
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:476
IdSetDenseIterator & operator++() noexcept
Definition: id_set.hpp:159
Definition: id_set.hpp:474
Definition: id_set.hpp:58
void next() noexcept
Definition: id_set.hpp:127
virtual void clear()=0
T last() const noexcept
Definition: id_set.hpp:220
item_type
Definition: item_type.hpp:43
IdSetDenseIterator(const id_set *set, T value, T last) noexcept
Definition: id_set.hpp:152
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:208
const id_set * m_set
Definition: id_set.hpp:123
void clear() final
Definition: id_set.hpp:422
std::vector< T > m_data
Definition: id_set.hpp:377
T value_type
Definition: id_set.hpp:148
Definition: id_set.hpp:112
unsigned int item_type_to_nwr_index(item_type type) noexcept
Definition: item_type.hpp:82
bool get(T id) const noexcept final
Definition: id_set.hpp:323
IdSetDenseIterator operator++(int) noexcept
Definition: id_set.hpp:167
const_iterator cend() const noexcept
Definition: id_set.hpp:466
value_type & reference
Definition: id_set.hpp:150
void swap(Buffer &lhs, Buffer &rhs)
Definition: buffer.hpp:885
IdSetDense(const IdSetDense &other)
Definition: id_set.hpp:251
T m_size
Definition: id_set.hpp:206
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:447
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:408
T m_last
Definition: id_set.hpp:125
friend void swap(IdSetDense &first, IdSetDense &second) noexcept
Definition: id_set.hpp:243
const_iterator end() const noexcept
Definition: id_set.hpp:458
const_iterator begin() const
Definition: id_set.hpp:360
Definition: id_set.hpp:118
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
Definition: attr.hpp:333
const_iterator begin() const noexcept
Definition: id_set.hpp:454
bool check_and_set(T id)
Definition: id_set.hpp:283
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:482
bool operator!=(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:177
IdSetDense & operator=(IdSetDense other)
Definition: id_set.hpp:265
value_type * pointer
Definition: id_set.hpp:149
void unset(T id)
Definition: id_set.hpp:309
T m_value
Definition: id_set.hpp:124
IdSet & operator=(const IdSet &)=default
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:486
std::array< id_set_type, 3 > m_sets
Definition: id_set.hpp:478
T operator*() const noexcept
Definition: id_set.hpp:181
void clear() final
Definition: id_set.hpp:351
virtual std::size_t used_memory() const noexcept=0
Definition: id_set.hpp:375
std::size_t size() const noexcept
Definition: id_set.hpp:443
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:205
virtual ~IdSet()=default
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:212
const_iterator cbegin() const noexcept
Definition: id_set.hpp:462
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:452
unsigned char & get_element(T id)
Definition: id_set.hpp:224
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:147
bool empty() const noexcept final
Definition: id_set.hpp:415
static unsigned int bitmask(T id) noexcept
Definition: id_set.hpp:216
bool operator==(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:173
virtual bool empty() const =0
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:356
void sort_unique()
Definition: id_set.hpp:430
bool empty() const noexcept final
Definition: id_set.hpp:337