Libosmium  2.14.2
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-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/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  template <typename T>
99  class IdSetDense;
100 
104  template <typename T>
106 
107 
111 
112  void next() noexcept {
113  while (m_value != m_last && !m_set->get(m_value)) {
114  const T cid = IdSetDense<T>::chunk_id(m_value);
115  assert(cid < m_set->m_data.size());
116  if (!m_set->m_data[cid]) {
117  m_value = (cid + 1) << (IdSetDense<T>::chunk_bits + 3);
118  } else {
119  const auto slot = m_set->m_data[cid][IdSetDense<T>::offset(m_value)];
120  if (slot == 0) {
121  m_value += 8;
122  m_value &= ~0x7ull;
123  } else {
124  ++m_value;
125  }
126  }
127  }
128  }
129 
130  public:
131 
132  using iterator_category = std::forward_iterator_tag;
133  using value_type = T;
134  using pointer = value_type*;
136 
137  IdSetDenseIterator(const IdSetDense<T>* set, T value, T last) noexcept :
138  m_set(set),
139  m_value(value),
140  m_last(last) {
141  next();
142  }
143 
145  if (m_value != m_last) {
146  ++m_value;
147  next();
148  }
149  return *this;
150  }
151 
153  IdSetDenseIterator<T> tmp{*this};
154  operator++();
155  return tmp;
156  }
157 
158  bool operator==(const IdSetDenseIterator<T>& rhs) const noexcept {
159  return m_set == rhs.m_set && m_value == rhs.m_value;
160  }
161 
162  bool operator!=(const IdSetDenseIterator<T>& rhs) const noexcept {
163  return !(*this == rhs);
164  }
165 
166  T operator*() const noexcept {
167  assert(m_value < m_last);
168  return m_value;
169  }
170 
171  }; // class IdSetDenseIterator
172 
180  template <typename T>
181  class IdSetDense : public IdSet<T> {
182 
183 
184  friend class IdSetDenseIterator<T>;
185 
186  // This value is a compromise. For node Ids it could be bigger
187  // which would mean less (but larger) memory allocations. For
188  // relations Ids it could be smaller, because they would all fit
189  // into a smaller allocation.
190  constexpr static const std::size_t chunk_bits = 22u;
191  constexpr static const std::size_t chunk_size = 1u << chunk_bits;
192 
193  std::vector<std::unique_ptr<unsigned char[]>> m_data;
194  T m_size = 0;
195 
196  static std::size_t chunk_id(T id) noexcept {
197  return id >> (chunk_bits + 3u);
198  }
199 
200  static std::size_t offset(T id) noexcept {
201  return (id >> 3u) & ((1u << chunk_bits) - 1u);
202  }
203 
204  static unsigned char bitmask(T id) noexcept {
205  return 1u << (id & 0x7u);
206  }
207 
208  T last() const noexcept {
209  return static_cast<T>(m_data.size()) * chunk_size * 8;
210  }
211 
212  unsigned char& get_element(T id) {
213  const auto cid = chunk_id(id);
214  if (cid >= m_data.size()) {
215  m_data.resize(cid + 1);
216  }
217 
218  auto& chunk = m_data[cid];
219  if (!chunk) {
220  chunk.reset(new unsigned char[chunk_size]);
221  ::memset(chunk.get(), 0, chunk_size);
222  }
223 
224  return chunk[offset(id)];
225  }
226 
227  public:
228 
230 
231  IdSetDense() = default;
232 
239  bool check_and_set(T id) {
240  auto& element = get_element(id);
241 
242  if ((element & bitmask(id)) == 0) {
243  element |= bitmask(id);
244  ++m_size;
245  return true;
246  }
247 
248  return false;
249  }
250 
256  void set(T id) final {
257  (void)check_and_set(id);
258  }
259 
265  void unset(T id) {
266  auto& element = get_element(id);
267 
268  if ((element & bitmask(id)) != 0) {
269  element &= ~bitmask(id);
270  --m_size;
271  }
272  }
273 
279  bool get(T id) const noexcept final {
280  if (chunk_id(id) >= m_data.size()) {
281  return false;
282  }
283  auto* r = m_data[chunk_id(id)].get();
284  if (!r) {
285  return false;
286  }
287  return (r[offset(id)] & bitmask(id)) != 0;
288  }
289 
293  bool empty() const noexcept final {
294  return m_size == 0;
295  }
296 
300  T size() const noexcept {
301  return m_size;
302  }
303 
307  void clear() final {
308  m_data.clear();
309  m_size = 0;
310  }
311 
312  std::size_t used_memory() const noexcept final {
313  return m_data.size() * chunk_size;
314  }
315 
317  return {this, 0, last()};
318  }
319 
321  return {this, last(), last()};
322  }
323 
324  }; // class IdSetDense
325 
330  template <typename T>
331  class IdSetSmall : public IdSet<T> {
332 
333  std::vector<T> m_data;
334 
335  public:
336 
340  void set(T id) final {
341  m_data.push_back(id);
342  }
343 
349  bool get(T id) const noexcept final {
350  const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
351  return it != m_data.cend();
352  }
353 
364  bool get_binary_search(T id) const noexcept {
365  return std::binary_search(m_data.cbegin(), m_data.cend(), id);
366  }
367 
371  bool empty() const noexcept final {
372  return m_data.empty();
373  }
374 
378  void clear() final {
379  m_data.clear();
380  }
381 
386  void sort_unique() {
387  std::sort(m_data.begin(), m_data.end());
388  const auto last = std::unique(m_data.begin(), m_data.end());
389  m_data.erase(last, m_data.end());
390 
391  }
392 
399  std::size_t size() const noexcept {
400  return m_data.size();
401  }
402 
403  std::size_t used_memory() const noexcept final {
404  return m_data.capacity() * sizeof(T);
405  }
406 
408  using const_iterator = typename std::vector<T>::const_iterator;
409 
410  const_iterator begin() const noexcept {
411  return m_data.cbegin();
412  }
413 
414  const_iterator end() const noexcept {
415  return m_data.cend();
416  }
417 
418  const_iterator cbegin() const noexcept {
419  return m_data.cbegin();
420  }
421 
422  const_iterator cend() const noexcept {
423  return m_data.cend();
424  }
425 
426  }; // class IdSetSmall
427 
429  template <template <typename> class IdSetType>
430  class NWRIdSet {
431 
432  using id_set_type = IdSetType<osmium::unsigned_object_id_type>;
433 
435 
436  public:
437 
440  }
441 
442  const id_set_type& operator()(osmium::item_type type) const noexcept {
444  }
445 
446  }; // class NWRIdSet
447 
448  } // namespace index
449 
450 } // namespace osmium
451 
452 #endif // OSMIUM_INDEX_ID_SET_HPP
void unset(T id)
Definition: id_set.hpp:265
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:312
T m_last
Definition: id_set.hpp:110
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:432
Definition: id_set.hpp:430
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:132
Definition: id_set.hpp:57
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:200
virtual void clear()=0
item_type
Definition: item_type.hpp:43
T last() const noexcept
Definition: id_set.hpp:208
value_type * pointer
Definition: id_set.hpp:134
void clear() final
Definition: id_set.hpp:378
std::vector< T > m_data
Definition: id_set.hpp:333
bool get(T id) const noexcept final
Definition: id_set.hpp:279
Definition: id_set.hpp:99
bool get(T id) const noexcept final
Definition: id_set.hpp:349
unsigned int item_type_to_nwr_index(item_type type) noexcept
Definition: item_type.hpp:82
const_iterator cend() const noexcept
Definition: id_set.hpp:422
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:403
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:364
const_iterator end() const noexcept
Definition: id_set.hpp:414
T m_size
Definition: id_set.hpp:194
IdSetDenseIterator< T > begin() const
Definition: id_set.hpp:316
bool operator==(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:158
Definition: id_set.hpp:105
static constexpr const std::size_t chunk_bits
Definition: id_set.hpp:190
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
const_iterator begin() const noexcept
Definition: id_set.hpp:410
static unsigned char bitmask(T id) noexcept
Definition: id_set.hpp:204
const IdSetDense< T > * m_set
Definition: id_set.hpp:108
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:438
id_set_type m_sets[3]
Definition: id_set.hpp:434
IdSetDenseIterator(const IdSetDense< T > *set, T value, T last) noexcept
Definition: id_set.hpp:137
T operator*() const noexcept
Definition: id_set.hpp:166
T m_value
Definition: id_set.hpp:109
IdSet & operator=(const IdSet &)=default
bool check_and_set(T id)
Definition: id_set.hpp:239
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:442
bool empty() const noexcept final
Definition: id_set.hpp:293
void set(T id) final
Definition: id_set.hpp:340
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:193
void set(T id) final
Definition: id_set.hpp:256
IdSetDenseIterator< T > operator++(int) noexcept
Definition: id_set.hpp:152
IdSetDenseIterator< T > & operator++() noexcept
Definition: id_set.hpp:144
T value_type
Definition: id_set.hpp:133
value_type & reference
Definition: id_set.hpp:135
IdSetDenseIterator< T > end() const
Definition: id_set.hpp:320
virtual std::size_t used_memory() const noexcept=0
Definition: id_set.hpp:331
std::size_t size() const noexcept
Definition: id_set.hpp:399
bool operator!=(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:162
virtual void set(T id)=0
virtual ~IdSet()=default
const_iterator cbegin() const noexcept
Definition: id_set.hpp:418
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:408
void next() noexcept
Definition: id_set.hpp:112
virtual bool get(T id) const noexcept=0
bool empty() const noexcept final
Definition: id_set.hpp:371
void clear() final
Definition: id_set.hpp:307
T size() const noexcept
Definition: id_set.hpp:300
virtual bool empty() const =0
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:196
void sort_unique()
Definition: id_set.hpp:386
static constexpr const std::size_t chunk_size
Definition: id_set.hpp:191
unsigned char & get_element(T id)
Definition: id_set.hpp:212