Libosmium
2.15.1
Fast and flexible C++ library for working with OpenStreetMap data
|
Go to the documentation of this file. 1 #ifndef OSMIUM_INDEX_ID_SET_HPP
2 #define OSMIUM_INDEX_ID_SET_HPP
45 #include <type_traits>
74 virtual
void set(T
id) = 0;
79 virtual
bool get(T
id) const noexcept = 0;
105 default_chunk_bits = 22u
110 template <
typename T, std::
size_t chunk_bits = detail::default_chunk_bits>
116 template <
typename T, std::
size_t chunk_bits>
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);
133 const auto slot = m_set->
m_data[cid][id_set::offset(m_value)];
159 if (m_value != m_last) {
173 return m_set == rhs.m_set && m_value == rhs.m_value;
177 return !(*
this == rhs);
181 assert(m_value < m_last);
194 template <
typename T, std::
size_t chunk_bits>
201 chunk_size = 1u << chunk_bits
204 std::vector<std::unique_ptr<unsigned char[]>>
m_data;
208 return id >> (chunk_bits + 3u);
211 static std::size_t
offset(T
id) noexcept {
212 return (
id >> 3u) & ((1u << chunk_bits) - 1u);
216 return 1u << (
id & 0x7u);
220 return static_cast<T
>(m_data.size()) * chunk_size * 8;
224 const auto cid = chunk_id(
id);
225 if (cid >= m_data.size()) {
226 m_data.resize(cid + 1);
229 auto& chunk = m_data[cid];
231 chunk.reset(
new unsigned char[chunk_size]);
232 ::memset(chunk.get(), 0, chunk_size);
235 return chunk[offset(
id)];
251 auto& element = get_element(
id);
253 if ((element & bitmask(
id)) == 0) {
254 element |= bitmask(
id);
268 (void)check_and_set(
id);
277 auto& element = get_element(
id);
279 if ((element & bitmask(
id)) != 0) {
280 element &= ~bitmask(
id);
290 bool get(T
id)
const noexcept
final {
291 if (chunk_id(
id) >= m_data.size()) {
294 const auto* r = m_data[chunk_id(
id)].get();
298 return (r[offset(
id)] & bitmask(
id)) != 0;
324 return m_data.size() * chunk_size;
328 return {
this, 0, last()};
332 return {
this, last(), last()};
341 template <
typename T>
352 m_data.push_back(
id);
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();
376 return std::binary_search(m_data.cbegin(), m_data.cend(),
id);
383 return m_data.empty();
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());
410 std::size_t
size() const noexcept {
411 return m_data.size();
415 return m_data.capacity() *
sizeof(T);
422 return m_data.cbegin();
426 return m_data.cend();
430 return m_data.cbegin();
434 return m_data.cend();
440 template <
template <
typename>
class IdSetType>
463 #endif // OSMIUM_INDEX_ID_SET_HPP
void next() noexcept
Definition: id_set.hpp:126
bool operator==(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:172
void sort_unique()
Definition: id_set.hpp:397
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:414
bool empty() const noexcept final
Definition: id_set.hpp:382
const_iterator cbegin() const noexcept
Definition: id_set.hpp:429
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:449
virtual bool get(T id) const noexcept=0
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:375
bool check_and_set(T id)
Definition: id_set.hpp:250
IdSetDenseIterator operator++(int) noexcept
Definition: id_set.hpp:166
IdSetDenseIterator(const id_set *set, T value, T last) noexcept
Definition: id_set.hpp:151
void clear() final
Definition: id_set.hpp:389
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:207
T size() const noexcept
Definition: id_set.hpp:311
const id_set * m_set
Definition: id_set.hpp:122
T m_last
Definition: id_set.hpp:124
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:146
IdSetDenseIterator & operator++() noexcept
Definition: id_set.hpp:158
Definition: id_set.hpp:441
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:204
bool get(T id) const noexcept final
Definition: id_set.hpp:290
IdSet(IdSet &&) noexcept=default
IdSet(const IdSet &)=default
T operator*() const noexcept
Definition: id_set.hpp:180
std::size_t size() const noexcept
Definition: id_set.hpp:410
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:323
const_iterator end() const
Definition: id_set.hpp:331
IdSet & operator=(const IdSet &)=default
bool get(T id) const noexcept final
Definition: id_set.hpp:360
Definition: id_set.hpp:195
Definition: id_set.hpp:117
const_iterator begin() const
Definition: id_set.hpp:327
static unsigned int bitmask(T id) noexcept
Definition: id_set.hpp:215
unsigned char & get_element(T id)
Definition: id_set.hpp:223
T last() const noexcept
Definition: id_set.hpp:219
void clear() final
Definition: id_set.hpp:318
virtual std::size_t used_memory() const noexcept=0
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:443
value_type & reference
Definition: id_set.hpp:149
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:419
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:453
bool operator!=(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:176
const_iterator cend() const noexcept
Definition: id_set.hpp:433
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:211
T value_type
Definition: id_set.hpp:147
Definition: location.hpp:550
void set(T id) final
Definition: id_set.hpp:351
const_iterator end() const noexcept
Definition: id_set.hpp:425
virtual bool empty() const =0
void set(T id) final
Definition: id_set.hpp:267
bool empty() const noexcept final
Definition: id_set.hpp:304
std::vector< T > m_data
Definition: id_set.hpp:344
void unset(T id)
Definition: id_set.hpp:276
value_type * pointer
Definition: id_set.hpp:148
Definition: id_set.hpp:57
const_iterator begin() const noexcept
Definition: id_set.hpp:421
type
Definition: entity_bits.hpp:63
item_type
Definition: item_type.hpp:43
unsigned int item_type_to_nwr_index(item_type type) noexcept
Definition: item_type.hpp:82
T m_value
Definition: id_set.hpp:123
Definition: id_set.hpp:342