Libosmium  2.10.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 (http://osmcode.org/libosmium).
7 
8 Copyright 2013-2016 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 <cstring>
39 #include <memory>
40 #include <type_traits>
41 #include <unordered_set>
42 #include <vector>
43 
44 #include <osmium/osm/item_type.hpp>
45 #include <osmium/osm/types.hpp>
46 
47 namespace osmium {
48 
49  namespace index {
50 
55  template <typename T>
56  class IdSet {
57 
58  public:
59 
60  virtual ~IdSet() {
61  }
62 
66  virtual void set(T id) = 0;
67 
71  virtual bool get(T id) const noexcept = 0;
72 
76  virtual bool empty() const = 0;
77 
81  virtual void clear() = 0;
82 
83  }; // class IdSet
84 
85  template <typename T>
86  class IdSetDense;
87 
91  template <typename T>
93 
96  T m_last;
97 
98  void next() noexcept {
99  while (m_value != m_last && !m_set->get(m_value)) {
100  const auto cid = IdSetDense<T>::chunk_id(m_value);
101  assert(cid < m_set->m_data.size());
102  if (!m_set->m_data[cid]) {
103  m_value = (cid + 1) << (IdSetDense<T>::chunk_bits + 3);
104  } else {
105  const auto slot = m_set->m_data[cid][IdSetDense<T>::offset(m_value)];
106  if (slot == 0) {
107  m_value += 8;
108  m_value &= ~0x7;
109  } else {
110  ++m_value;
111  }
112  }
113  }
114  }
115 
116  public:
117 
118  using iterator_category = std::forward_iterator_tag;
119  using value_type = T;
120  using pointer = value_type*;
122 
123  IdSetDenseIterator(const IdSetDense<T>* set, T value, T last) noexcept :
124  m_set(set),
125  m_value(value),
126  m_last(last) {
127  next();
128  }
129 
131  if (m_value != m_last) {
132  ++m_value;
133  next();
134  }
135  return *this;
136  }
137 
139  IdSetDenseIterator<T> tmp(*this);
140  operator++();
141  return tmp;
142  }
143 
144  bool operator==(const IdSetDenseIterator<T>& rhs) const noexcept {
145  return m_set == rhs.m_set && m_value == rhs.m_value;
146  }
147 
148  bool operator!=(const IdSetDenseIterator<T>& rhs) const noexcept {
149  return ! (*this == rhs);
150  }
151 
152  T operator*() const noexcept {
153  assert(m_value < m_last);
154  return m_value;
155  }
156 
157  }; // class IdSetDenseIterator
158 
166  template <typename T>
167  class IdSetDense : public IdSet<T> {
168 
169 
170  friend class IdSetDenseIterator<T>;
171 
172  // This value is a compromise. For node Ids it could be bigger
173  // which would mean less (but larger) memory allocations. For
174  // relations Ids it could be smaller, because they would all fit
175  // into a smaller allocation.
176  constexpr static const size_t chunk_bits = 22;
177  constexpr static const size_t chunk_size = 1 << chunk_bits;
178 
179  std::vector<std::unique_ptr<unsigned char[]>> m_data;
180  size_t m_size = 0;
181 
182  static size_t chunk_id(T id) noexcept {
183  return id >> (chunk_bits + 3);
184  }
185 
186  static size_t offset(T id) noexcept {
187  return (id >> 3) & ((1 << chunk_bits) - 1);
188  }
189 
190  static unsigned char bitmask(T id) noexcept {
191  return 1 << (id & 0x7);
192  }
193 
194  T last() const noexcept {
195  return m_data.size() * chunk_size * 8;
196  }
197 
198  unsigned char& get_element(T id) {
199  const auto cid = chunk_id(id);
200  if (cid >= m_data.size()) {
201  m_data.resize(cid + 1);
202  }
203 
204  auto& chunk = m_data[cid];
205  if (!chunk) {
206  chunk.reset(new unsigned char[chunk_size]);
207  ::memset(chunk.get(), 0, chunk_size);
208  }
209 
210  return chunk[offset(id)];
211  }
212 
213  public:
214 
216 
217  IdSetDense() = default;
218 
225  bool check_and_set(T id) {
226  auto& element = get_element(id);
227 
228  if ((element & bitmask(id)) == 0) {
229  element |= bitmask(id);
230  ++m_size;
231  return true;
232  }
233 
234  return false;
235  }
236 
242  void set(T id) override final {
243  (void)check_and_set(id);
244  }
245 
251  void unset(T id) {
252  auto& element = get_element(id);
253 
254  if ((element & bitmask(id)) != 0) {
255  element &= ~bitmask(id);
256  --m_size;
257  }
258  }
259 
265  bool get(T id) const noexcept override final {
266  if (chunk_id(id) >= m_data.size()) {
267  return false;
268  }
269  auto* r = m_data[chunk_id(id)].get();
270  if (!r) {
271  return false;
272  }
273  return (r[offset(id)] & bitmask(id)) != 0;
274  }
275 
279  bool empty() const noexcept override final {
280  return m_size == 0;
281  }
282 
286  size_t size() const noexcept {
287  return m_size;
288  }
289 
293  void clear() override final {
294  m_data.clear();
295  m_size = 0;
296  }
297 
299  return IdSetDenseIterator<T>{this, 0, last()};
300  }
301 
303  return IdSetDenseIterator<T>{this, last(), last()};
304  }
305 
306  }; // class IdSetDense
307 
312  template <typename T>
313  class IdSetSmall : public IdSet<T> {
314 
315  std::vector<T> m_data;
316 
317  public:
318 
322  void set(T id) override final {
323  m_data.push_back(id);
324  }
325 
331  bool get(T id) const noexcept override final {
332  const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
333  return it != m_data.cend();
334  }
335 
346  bool get_binary_search(T id) const noexcept {
347  return std::binary_search(m_data.cbegin(), m_data.cend(), id);
348  }
349 
353  bool empty() const noexcept override final {
354  return m_data.empty();
355  }
356 
360  void clear() override final {
361  m_data.clear();
362  }
363 
368  void sort_unique() {
369  std::sort(m_data.begin(), m_data.end());
370  const auto last = std::unique(m_data.begin(), m_data.end());
371  m_data.erase(last, m_data.end());
372 
373  }
374 
381  size_t size() const noexcept {
382  return m_data.size();
383  }
384 
386  using const_iterator = typename std::vector<T>::const_iterator;
387 
388  const_iterator begin() const noexcept {
389  return m_data.cbegin();
390  }
391 
392  const_iterator end() const noexcept {
393  return m_data.cend();
394  }
395 
396  const_iterator cbegin() const noexcept {
397  return m_data.cbegin();
398  }
399 
400  const_iterator cend() const noexcept {
401  return m_data.cend();
402  }
403 
404  }; // class IdSetSmall
405 
406  template <template<typename> class IdSetType>
407  class NWRIdSet {
408 
409  using id_set_type = IdSetType<osmium::unsigned_object_id_type>;
410 
411  id_set_type m_sets[3];
412 
413  public:
414 
416  return m_sets[osmium::item_type_to_nwr_index(type)];
417  }
418 
419  const id_set_type& operator()(osmium::item_type type) const noexcept {
420  return m_sets[osmium::item_type_to_nwr_index(type)];
421  }
422 
423  }; // class NWRIdSet
424 
425  } // namespace index
426 
427 } // namespace osmium
428 
429 #endif // OSMIUM_INDEX_ID_SET_HPP
void unset(T id)
Definition: id_set.hpp:251
void clear() override final
Definition: id_set.hpp:360
T m_last
Definition: id_set.hpp:96
static size_t offset(T id) noexcept
Definition: id_set.hpp:186
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:409
Definition: id_set.hpp:407
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:118
Definition: id_set.hpp:56
virtual ~IdSet()
Definition: id_set.hpp:60
virtual void clear()=0
item_type
Definition: item_type.hpp:43
T last() const noexcept
Definition: id_set.hpp:194
value_type * pointer
Definition: id_set.hpp:120
std::vector< T > m_data
Definition: id_set.hpp:315
Definition: id_set.hpp:86
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:400
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:346
const_iterator end() const noexcept
Definition: id_set.hpp:392
IdSetDenseIterator< T > begin() const
Definition: id_set.hpp:298
bool operator==(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:144
size_t size() const noexcept
Definition: id_set.hpp:286
Definition: id_set.hpp:92
Namespace for everything in the Osmium library.
Definition: assembler.hpp:73
bool empty() const noexcept override final
Definition: id_set.hpp:279
const_iterator begin() const noexcept
Definition: id_set.hpp:388
static unsigned char bitmask(T id) noexcept
Definition: id_set.hpp:190
const IdSetDense< T > * m_set
Definition: id_set.hpp:94
bool get(T id) const noexcept override final
Definition: id_set.hpp:265
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:415
IdSetDenseIterator(const IdSetDense< T > *set, T value, T last) noexcept
Definition: id_set.hpp:123
T operator*() const noexcept
Definition: id_set.hpp:152
T m_value
Definition: id_set.hpp:95
bool check_and_set(T id)
Definition: id_set.hpp:225
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:419
size_t size() const noexcept
Definition: id_set.hpp:381
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:179
IdSetDenseIterator< T > operator++(int) noexcept
Definition: id_set.hpp:138
IdSetDenseIterator< T > & operator++() noexcept
Definition: id_set.hpp:130
T value_type
Definition: id_set.hpp:119
value_type & reference
Definition: id_set.hpp:121
IdSetDenseIterator< T > end() const
Definition: id_set.hpp:302
Definition: id_set.hpp:313
bool operator!=(const IdSetDenseIterator< T > &rhs) const noexcept
Definition: id_set.hpp:148
const_iterator cbegin() const noexcept
Definition: id_set.hpp:396
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:386
void next() noexcept
Definition: id_set.hpp:98
static size_t chunk_id(T id) noexcept
Definition: id_set.hpp:182
virtual bool empty() const =0
bool empty() const noexcept override final
Definition: id_set.hpp:353
void clear() override final
Definition: id_set.hpp:293
void sort_unique()
Definition: id_set.hpp:368
unsigned char & get_element(T id)
Definition: id_set.hpp:198