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