Libosmium  2.15.1
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 <cassert>
41 #include <cstddef>
42 #include <cstring>
43 #include <iterator>
44 #include <memory>
45 #include <type_traits>
46 #include <vector>
47 
48 namespace osmium {
49 
50  namespace index {
51 
56  template <typename T>
57  class IdSet {
58 
59  public:
60 
61  IdSet() = default;
62 
63  IdSet(const IdSet&) = default;
64  IdSet& operator=(const IdSet&) = default;
65 
66  IdSet(IdSet&&) noexcept = default;
67  IdSet& operator=(IdSet&&) noexcept = default;
68 
69  virtual ~IdSet() = default;
70 
74  virtual void set(T id) = 0;
75 
79  virtual bool get(T id) const noexcept = 0;
80 
84  virtual bool empty() const = 0;
85 
89  virtual void clear() = 0;
90 
94  virtual std::size_t used_memory() const noexcept = 0;
95 
96  }; // class IdSet
97 
98  namespace detail {
99 
100  // This value is a compromise. For node Ids it could be bigger
101  // which would mean less (but larger) memory allocations. For
102  // relations Ids it could be smaller, because they would all fit
103  // into a smaller allocation.
104  enum : std::size_t {
105  default_chunk_bits = 22u
106  };
107 
108  } // namespace detail
109 
110  template <typename T, std::size_t chunk_bits = detail::default_chunk_bits>
111  class IdSetDense;
112 
116  template <typename T, std::size_t chunk_bits>
118 
119 
121 
122  const id_set* m_set;
125 
126  void next() noexcept {
127  while (m_value != m_last && !m_set->get(m_value)) {
128  const T cid = id_set::chunk_id(m_value);
129  assert(cid < m_set->m_data.size());
130  if (!m_set->m_data[cid]) {
131  m_value = (cid + 1) << (chunk_bits + 3);
132  } else {
133  const auto slot = m_set->m_data[cid][id_set::offset(m_value)];
134  if (slot == 0) {
135  m_value += 8;
136  m_value &= ~0x7ull;
137  } else {
138  ++m_value;
139  }
140  }
141  }
142  }
143 
144  public:
145 
146  using iterator_category = std::forward_iterator_tag;
147  using value_type = T;
148  using pointer = value_type*;
150 
151  IdSetDenseIterator(const id_set* set, T value, T last) noexcept :
152  m_set(set),
153  m_value(value),
154  m_last(last) {
155  next();
156  }
157 
159  if (m_value != m_last) {
160  ++m_value;
161  next();
162  }
163  return *this;
164  }
165 
167  IdSetDenseIterator tmp{*this};
168  operator++();
169  return tmp;
170  }
171 
172  bool operator==(const IdSetDenseIterator& rhs) const noexcept {
173  return m_set == rhs.m_set && m_value == rhs.m_value;
174  }
175 
176  bool operator!=(const IdSetDenseIterator& rhs) const noexcept {
177  return !(*this == rhs);
178  }
179 
180  T operator*() const noexcept {
181  assert(m_value < m_last);
182  return m_value;
183  }
184 
185  }; // class IdSetDenseIterator
186 
194  template <typename T, std::size_t chunk_bits>
195  class IdSetDense : public IdSet<T> {
196 
197 
198  friend class IdSetDenseIterator<T, chunk_bits>;
199 
200  enum : std::size_t {
201  chunk_size = 1u << chunk_bits
202  };
203 
204  std::vector<std::unique_ptr<unsigned char[]>> m_data;
205  T m_size = 0;
206 
207  static std::size_t chunk_id(T id) noexcept {
208  return id >> (chunk_bits + 3u);
209  }
210 
211  static std::size_t offset(T id) noexcept {
212  return (id >> 3u) & ((1u << chunk_bits) - 1u);
213  }
214 
215  static unsigned int bitmask(T id) noexcept {
216  return 1u << (id & 0x7u);
217  }
218 
219  T last() const noexcept {
220  return static_cast<T>(m_data.size()) * chunk_size * 8;
221  }
222 
223  unsigned char& get_element(T id) {
224  const auto cid = chunk_id(id);
225  if (cid >= m_data.size()) {
226  m_data.resize(cid + 1);
227  }
228 
229  auto& chunk = m_data[cid];
230  if (!chunk) {
231  chunk.reset(new unsigned char[chunk_size]);
232  ::memset(chunk.get(), 0, chunk_size);
233  }
234 
235  return chunk[offset(id)];
236  }
237 
238  public:
239 
241 
242  IdSetDense() = default;
243 
250  bool check_and_set(T id) {
251  auto& element = get_element(id);
252 
253  if ((element & bitmask(id)) == 0) {
254  element |= bitmask(id);
255  ++m_size;
256  return true;
257  }
258 
259  return false;
260  }
261 
267  void set(T id) final {
268  (void)check_and_set(id);
269  }
270 
276  void unset(T id) {
277  auto& element = get_element(id);
278 
279  if ((element & bitmask(id)) != 0) {
280  element &= ~bitmask(id);
281  --m_size;
282  }
283  }
284 
290  bool get(T id) const noexcept final {
291  if (chunk_id(id) >= m_data.size()) {
292  return false;
293  }
294  const auto* r = m_data[chunk_id(id)].get();
295  if (!r) {
296  return false;
297  }
298  return (r[offset(id)] & bitmask(id)) != 0;
299  }
300 
304  bool empty() const noexcept final {
305  return m_size == 0;
306  }
307 
311  T size() const noexcept {
312  return m_size;
313  }
314 
318  void clear() final {
319  m_data.clear();
320  m_size = 0;
321  }
322 
323  std::size_t used_memory() const noexcept final {
324  return m_data.size() * chunk_size;
325  }
326 
328  return {this, 0, last()};
329  }
330 
331  const_iterator end() const {
332  return {this, last(), last()};
333  }
334 
335  }; // class IdSetDense
336 
341  template <typename T>
342  class IdSetSmall : public IdSet<T> {
343 
344  std::vector<T> m_data;
345 
346  public:
347 
351  void set(T id) final {
352  m_data.push_back(id);
353  }
354 
360  bool get(T id) const noexcept final {
361  const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
362  return it != m_data.cend();
363  }
364 
375  bool get_binary_search(T id) const noexcept {
376  return std::binary_search(m_data.cbegin(), m_data.cend(), id);
377  }
378 
382  bool empty() const noexcept final {
383  return m_data.empty();
384  }
385 
389  void clear() final {
390  m_data.clear();
391  }
392 
397  void sort_unique() {
398  std::sort(m_data.begin(), m_data.end());
399  const auto last = std::unique(m_data.begin(), m_data.end());
400  m_data.erase(last, m_data.end());
401 
402  }
403 
410  std::size_t size() const noexcept {
411  return m_data.size();
412  }
413 
414  std::size_t used_memory() const noexcept final {
415  return m_data.capacity() * sizeof(T);
416  }
417 
419  using const_iterator = typename std::vector<T>::const_iterator;
420 
421  const_iterator begin() const noexcept {
422  return m_data.cbegin();
423  }
424 
425  const_iterator end() const noexcept {
426  return m_data.cend();
427  }
428 
429  const_iterator cbegin() const noexcept {
430  return m_data.cbegin();
431  }
432 
433  const_iterator cend() const noexcept {
434  return m_data.cend();
435  }
436 
437  }; // class IdSetSmall
438 
440  template <template <typename> class IdSetType>
441  class NWRIdSet {
442 
443  using id_set_type = IdSetType<osmium::unsigned_object_id_type>;
444 
446 
447  public:
448 
451  }
452 
453  const id_set_type& operator()(osmium::item_type type) const noexcept {
455  }
456 
457  }; // class NWRIdSet
458 
459  } // namespace index
460 
461 } // namespace osmium
462 
463 #endif // OSMIUM_INDEX_ID_SET_HPP
T size() const noexcept
Definition: id_set.hpp:311
const_iterator end() const
Definition: id_set.hpp:331
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:443
IdSetDenseIterator & operator++() noexcept
Definition: id_set.hpp:158
Definition: id_set.hpp:441
Definition: id_set.hpp:57
void next() noexcept
Definition: id_set.hpp:126
virtual void clear()=0
T last() const noexcept
Definition: id_set.hpp:219
item_type
Definition: item_type.hpp:43
IdSetDenseIterator(const id_set *set, T value, T last) noexcept
Definition: id_set.hpp:151
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:207
const id_set * m_set
Definition: id_set.hpp:122
void clear() final
Definition: id_set.hpp:389
std::vector< T > m_data
Definition: id_set.hpp:344
T value_type
Definition: id_set.hpp:147
Definition: id_set.hpp:111
bool get(T id) const noexcept final
Definition: id_set.hpp:360
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:290
IdSetDenseIterator operator++(int) noexcept
Definition: id_set.hpp:166
const_iterator cend() const noexcept
Definition: id_set.hpp:433
value_type & reference
Definition: id_set.hpp:149
T m_size
Definition: id_set.hpp:205
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:414
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:375
T m_last
Definition: id_set.hpp:124
void set(T id) final
Definition: id_set.hpp:267
const_iterator end() const noexcept
Definition: id_set.hpp:425
const_iterator begin() const
Definition: id_set.hpp:327
Definition: id_set.hpp:201
Definition: id_set.hpp:117
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
Definition: attr.hpp:333
const_iterator begin() const noexcept
Definition: id_set.hpp:421
bool check_and_set(T id)
Definition: id_set.hpp:250
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:449
bool operator!=(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:176
id_set_type m_sets[3]
Definition: id_set.hpp:445
value_type * pointer
Definition: id_set.hpp:148
void unset(T id)
Definition: id_set.hpp:276
T m_value
Definition: id_set.hpp:123
IdSet & operator=(const IdSet &)=default
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:453
void set(T id) final
Definition: id_set.hpp:351
T operator*() const noexcept
Definition: id_set.hpp:180
void clear() final
Definition: id_set.hpp:318
virtual std::size_t used_memory() const noexcept=0
Definition: id_set.hpp:342
std::size_t size() const noexcept
Definition: id_set.hpp:410
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:204
virtual void set(T id)=0
virtual ~IdSet()=default
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:211
const_iterator cbegin() const noexcept
Definition: id_set.hpp:429
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:419
unsigned char & get_element(T id)
Definition: id_set.hpp:223
virtual bool get(T id) const noexcept=0
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:146
bool empty() const noexcept final
Definition: id_set.hpp:382
static unsigned int bitmask(T id) noexcept
Definition: id_set.hpp:215
bool operator==(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:172
virtual bool empty() const =0
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:323
void sort_unique()
Definition: id_set.hpp:397
bool empty() const noexcept final
Definition: id_set.hpp:304