1 #ifndef OSMIUM_INDEX_ID_SET_HPP 2 #define OSMIUM_INDEX_ID_SET_HPP 46 #include <type_traits> 70 virtual ~IdSet() =
default;
75 virtual void set(T id) = 0;
80 virtual bool get(T id)
const noexcept = 0;
85 virtual bool empty()
const = 0;
90 virtual void clear() = 0;
95 virtual std::size_t
used_memory()
const noexcept = 0;
106 default_chunk_bits = 22U
111 template <
typename T, std::
size_t chunk_bits = detail::default_chunk_bits>
117 template <
typename T, std::
size_t chunk_bits>
128 while (m_value != m_last && !m_set->
get(m_value)) {
129 const T cid = id_set::chunk_id(m_value);
130 assert(cid < m_set->m_data.size());
131 if (!m_set->
m_data[cid]) {
132 m_value = (cid + 1) << (chunk_bits + 3);
134 const auto slot = m_set->
m_data[cid][id_set::offset(m_value)];
160 if (m_value != m_last) {
174 return m_set == rhs.m_set && m_value == rhs.m_value;
178 return !(*
this == rhs);
182 assert(m_value < m_last);
195 template <
typename T, std::
size_t chunk_bits>
202 chunk_size = 1U << chunk_bits
205 std::vector<std::unique_ptr<unsigned char[]>>
m_data;
209 return id >> (chunk_bits + 3U);
212 static std::size_t
offset(T
id) noexcept {
213 return (
id >> 3U) & ((1U << chunk_bits) - 1U);
217 return 1U << (
id & 0x7U);
221 return static_cast<T
>(m_data.size()) * chunk_size * 8;
225 const auto cid = chunk_id(
id);
226 if (cid >= m_data.size()) {
227 m_data.resize(cid + 1);
230 auto& chunk = m_data[cid];
232 chunk.reset(
new unsigned char[chunk_size]);
233 ::memset(chunk.get(), 0, chunk_size);
236 return chunk[offset(
id)];
245 swap(first.m_data, second.m_data);
246 swap(first.m_size, second.m_size);
253 m_data.reserve(other.
m_data.size());
254 for (
const auto& ptr: other.
m_data) {
256 m_data.emplace_back(
new unsigned char[chunk_size]);
257 ::memcpy(m_data.back().get(), ptr.get(), chunk_size);
259 m_data.emplace_back();
284 auto& element = get_element(
id);
286 if ((element & bitmask(
id)) == 0) {
287 element |= bitmask(
id);
300 void set(T id)
final {
301 (void)check_and_set(
id);
310 auto& element = get_element(
id);
312 if ((element & bitmask(
id)) != 0) {
313 element &= ~bitmask(
id);
323 bool get(T id)
const noexcept
final {
324 if (chunk_id(
id) >= m_data.size()) {
327 const auto* r = m_data[chunk_id(
id)].get();
331 return (r[offset(
id)] & bitmask(
id)) != 0;
357 return m_data.size() * chunk_size;
361 return {
this, 0, last()};
365 return {
this, last(), last()};
374 template <
typename T>
384 void set(T id)
final {
385 m_data.push_back(
id);
393 bool get(T id)
const noexcept
final {
394 const auto it = std::find(m_data.cbegin(), m_data.cend(), id);
395 return it != m_data.cend();
409 return std::binary_search(m_data.cbegin(), m_data.cend(), id);
416 return m_data.empty();
431 std::sort(m_data.begin(), m_data.end());
432 const auto last = std::unique(m_data.begin(), m_data.end());
433 m_data.erase(last, m_data.end());
443 std::size_t
size() const noexcept {
444 return m_data.size();
448 return m_data.capacity() *
sizeof(T);
455 return m_data.cbegin();
459 return m_data.cend();
463 return m_data.cbegin();
467 return m_data.cend();
473 template <
template <
typename>
class IdSetType>
496 #endif // OSMIUM_INDEX_ID_SET_HPP T size() const noexcept
Definition: id_set.hpp:344
const_iterator end() const
Definition: id_set.hpp:364
type
Definition: entity_bits.hpp:63
IdSetType< osmium::unsigned_object_id_type > id_set_type
Definition: id_set.hpp:476
IdSetDenseIterator & operator++() noexcept
Definition: id_set.hpp:159
Definition: id_set.hpp:474
Definition: id_set.hpp:58
void next() noexcept
Definition: id_set.hpp:127
T last() const noexcept
Definition: id_set.hpp:220
item_type
Definition: item_type.hpp:43
IdSetDenseIterator(const id_set *set, T value, T last) noexcept
Definition: id_set.hpp:152
static std::size_t chunk_id(T id) noexcept
Definition: id_set.hpp:208
const id_set * m_set
Definition: id_set.hpp:123
void clear() final
Definition: id_set.hpp:422
std::vector< T > m_data
Definition: id_set.hpp:377
T value_type
Definition: id_set.hpp:148
Definition: id_set.hpp:112
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:323
IdSetDenseIterator operator++(int) noexcept
Definition: id_set.hpp:167
const_iterator cend() const noexcept
Definition: id_set.hpp:466
value_type & reference
Definition: id_set.hpp:150
void swap(Buffer &lhs, Buffer &rhs)
Definition: buffer.hpp:885
IdSetDense(const IdSetDense &other)
Definition: id_set.hpp:251
T m_size
Definition: id_set.hpp:206
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:447
bool get_binary_search(T id) const noexcept
Definition: id_set.hpp:408
T m_last
Definition: id_set.hpp:125
friend void swap(IdSetDense &first, IdSetDense &second) noexcept
Definition: id_set.hpp:243
const_iterator end() const noexcept
Definition: id_set.hpp:458
const_iterator begin() const
Definition: id_set.hpp:360
Definition: id_set.hpp:118
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
const_iterator begin() const noexcept
Definition: id_set.hpp:454
bool check_and_set(T id)
Definition: id_set.hpp:283
id_set_type & operator()(osmium::item_type type) noexcept
Definition: id_set.hpp:482
bool operator!=(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:177
IdSetDense & operator=(IdSetDense other)
Definition: id_set.hpp:265
value_type * pointer
Definition: id_set.hpp:149
void unset(T id)
Definition: id_set.hpp:309
T m_value
Definition: id_set.hpp:124
IdSet & operator=(const IdSet &)=default
const id_set_type & operator()(osmium::item_type type) const noexcept
Definition: id_set.hpp:486
std::array< id_set_type, 3 > m_sets
Definition: id_set.hpp:478
T operator*() const noexcept
Definition: id_set.hpp:181
void clear() final
Definition: id_set.hpp:351
virtual std::size_t used_memory() const noexcept=0
Definition: id_set.hpp:375
std::size_t size() const noexcept
Definition: id_set.hpp:443
std::vector< std::unique_ptr< unsigned char[]> > m_data
Definition: id_set.hpp:205
static std::size_t offset(T id) noexcept
Definition: id_set.hpp:212
const_iterator cbegin() const noexcept
Definition: id_set.hpp:462
typename std::vector< T >::const_iterator const_iterator
Iterator type. There is no non-const iterator.
Definition: id_set.hpp:452
unsigned char & get_element(T id)
Definition: id_set.hpp:224
std::forward_iterator_tag iterator_category
Definition: id_set.hpp:147
bool empty() const noexcept final
Definition: id_set.hpp:415
static unsigned int bitmask(T id) noexcept
Definition: id_set.hpp:216
bool operator==(const IdSetDenseIterator &rhs) const noexcept
Definition: id_set.hpp:173
virtual bool empty() const =0
std::size_t used_memory() const noexcept final
Definition: id_set.hpp:356
void sort_unique()
Definition: id_set.hpp:430
bool empty() const noexcept final
Definition: id_set.hpp:337