20#ifndef FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
21#define FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
32#pragma push_macro("max")
34#define FASTDDS_RESTORE_MAX
38#pragma push_macro("min")
40#define FASTDDS_RESTORE_MIN
45#ifndef DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
74template<
class T,
class Diff = DiffFunction<T>, u
int32_t NBITS = 256>
77 #define NITEMS ((NBITS + 31u) / 32u)
117 uint32_t max_bits) noexcept
160 uint32_t max_bits)
noexcept
188 shift_map_left(n_bits);
194 shift_map_right(n_bits);
231 uint32_t n_longs = (
num_bits_ + 31u) / 32u;
232 for (uint32_t i = 0; i < n_longs; i++)
243 _BitScanReverse(&bit, bits);
244 uint32_t offset = 31u ^ bit;
246 uint32_t offset =
static_cast<uint32_t
>(__builtin_clz(bits));
250 return item + offset;
268 const T& item)
const noexcept
275 uint32_t diff = d_func(item,
base_);
278 uint32_t pos = diff >> 5;
280 return (
bitmap_[pos] & (1u << (31u - diff))) != 0;
296 const T& item)
noexcept
303 uint32_t diff = d_func(item,
base_);
305 uint32_t pos = diff >> 5;
307 bitmap_[pos] |= (1u << (31u - diff));
327 constexpr uint32_t full_mask = (std::numeric_limits<uint32_t>::max)();
341 uint32_t offset = d_func(
min,
base_);
342 uint32_t n_bits = d_func(
max,
min);
346 uint32_t pos = offset >> 5;
348 uint32_t mask = full_mask;
350 uint32_t bits_in_mask = 32u - offset;
353 while (n_bits >= bits_in_mask)
357 n_bits -= bits_in_mask;
365 bitmap_[pos] |= mask & (full_mask << (bits_in_mask - n_bits));
376 const T& item)
noexcept
380 if ((item >=
base_) && (max_value >= item))
384 uint32_t diff = d_func(item,
base_);
385 uint32_t pos = diff >> 5;
387 bitmap_[pos] &= ~(1u << (31u - diff));
389 if (item == max_value)
391 calc_maximum_bit_set(pos + 1, 0);
407 uint32_t& num_longs_used)
const noexcept
410 num_longs_used = (
num_bits_ + 31u) / 32u;
423 const uint32_t* bitmap)
noexcept
426 uint32_t num_items = ((
num_bits_ + 31u) / 32u);
427 uint32_t num_bytes = num_items *
static_cast<uint32_t
>(
sizeof(uint32_t));
429 memcpy(
bitmap_.data(), bitmap, num_bytes);
431 short shift = num_bits & 31u;
432 if (0 < num_bits && shift != 0)
434 bitmap_[num_items - 1] &= ~((std::numeric_limits<uint32_t>::max)() >> shift);
436 calc_maximum_bit_set(num_items, 0);
444 template<
class UnaryFunc>
451 uint32_t n_longs = (
num_bits_ + 31u) / 32u;
452 for (uint32_t i = 0; i < n_longs; i++)
464 _BitScanReverse(&bit, bits);
465 uint32_t offset = 31u ^ bit;
467 uint32_t offset =
static_cast<uint32_t
>(__builtin_clz(bits));
468 uint32_t bit = 31u ^ offset;
475 bits &= ~(1u << bit);
507 uint32_t n_items = n_bits >> 5;
513 std::fill_n(
bitmap_.rbegin(), n_items, 0);
523 uint32_t overflow_bits = 32u - n_bits;
524 size_t last_index = NITEMS - 1u;
525 for (
size_t i = 0, n = n_items; n < last_index; i++, n++)
532 std::fill_n(
bitmap_.rbegin(), n_items, 0);
537 void shift_map_right(
550 uint32_t new_num_bits =
num_bits_ + n_bits;
551 bool find_new_max = new_num_bits > NBITS;
554 uint32_t n_items = n_bits >> 5;
560 std::fill_n(
bitmap_.begin(), n_items, 0);
571 uint32_t overflow_bits = 32u - n_bits;
572 size_t last_index = NITEMS - 1u;
573 for (
size_t i = last_index, n = last_index - n_items; n > 0; i--, n--)
580 std::fill_n(
bitmap_.begin(), n_items, 0);
586 calc_maximum_bit_set(NITEMS, n_items);
591 void calc_maximum_bit_set(
592 uint32_t starting_index,
596 for (uint32_t i = starting_index; i > min_index;)
602 bits = (bits & ~(bits - 1));
605 _BitScanReverse(&bit, bits);
606 uint32_t offset = (31u ^ bit) + 1;
608 uint32_t offset =
static_cast<uint32_t
>(__builtin_clz(bits)) + 1u;
625#if defined(FASTDDS_RESTORE_MIN)
626#pragma pop_macro("min")
627#undef FASTDDS_RESTORE_MIN
630#if defined(FASTDDS_RESTORE_MAX)
631#pragma pop_macro("max")
632#undef FASTDDS_RESTORE_MAX
Template class to hold a range of items using a custom bitmap.
Definition fixed_size_bitmap.hpp:76
bitmap_type bitmap_
Holds the bitmap values.
Definition fixed_size_bitmap.hpp:487
T base() const noexcept
Get base of the range.
Definition fixed_size_bitmap.hpp:131
uint32_t num_bits_
Holds the highest bit set in the bitmap.
Definition fixed_size_bitmap.hpp:488
bool empty() const noexcept
Returns whether the range is empty (i.e.
Definition fixed_size_bitmap.hpp:207
bool add(const T &item) noexcept
Adds an element to the range.
Definition fixed_size_bitmap.hpp:295
void bitmap_get(uint32_t &num_bits, bitmap_type &bitmap, uint32_t &num_longs_used) const noexcept
Gets the current value of the bitmap.
Definition fixed_size_bitmap.hpp:404
T min() const noexcept
Returns the lowest value set in the range.
Definition fixed_size_bitmap.hpp:227
std::array< uint32_t, NITEMS > bitmap_type
Definition fixed_size_bitmap.hpp:82
void bitmap_set(uint32_t num_bits, const uint32_t *bitmap) noexcept
Sets the current value of the bitmap.
Definition fixed_size_bitmap.hpp:421
T base_
Holds base value of the range.
Definition fixed_size_bitmap.hpp:485
void add_range(const T &from, const T &to)
Adds a range of elements to the range.
Definition fixed_size_bitmap.hpp:323
void base_update(T base) noexcept
Set a new base for the range, keeping old values where possible.
Definition fixed_size_bitmap.hpp:174
T range_max_
Holds maximum allowed value of the range.
Definition fixed_size_bitmap.hpp:486
BitmapRange(T base) noexcept
Base-specific constructor.
Definition fixed_size_bitmap.hpp:102
void base(T base, uint32_t max_bits) noexcept
Set a new base and maximum bits for the range.
Definition fixed_size_bitmap.hpp:158
void for_each(UnaryFunc f) const
Apply a function on every item on the range.
Definition fixed_size_bitmap.hpp:445
bool is_set(const T &item) const noexcept
Checks if an element is present in the bitmap.
Definition fixed_size_bitmap.hpp:267
BitmapRange(T base, uint32_t max_bits) noexcept
Range specific constructor.
Definition fixed_size_bitmap.hpp:115
BitmapRange() noexcept
Default constructor.
Definition fixed_size_bitmap.hpp:88
void base(T base) noexcept
Set a new base for the range.
Definition fixed_size_bitmap.hpp:142
T max() const noexcept
Returns the highest value set in the range.
Definition fixed_size_bitmap.hpp:217
void remove(const T &item) noexcept
Removes an element from the range.
Definition fixed_size_bitmap.hpp:375
eProsima namespace.
Definition LibrarySettingsAttributes.h:23
Definition fixed_size_bitmap.hpp:53
constexpr auto operator()(T a, T b) const -> decltype(a - b)
Definition fixed_size_bitmap.hpp:54