20 #ifndef FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
21 #define FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
32 #ifndef DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
61 template<
class T,
class Diff = DiffFunction<T>, u
int32_t NBITS = 256>
64 #define NITEMS ((NBITS + 31u) / 32u)
144 shift_map_left(n_bits);
150 shift_map_right(n_bits);
187 uint32_t n_longs = (
num_bits_ + 31u) / 32u;
188 for (uint32_t i = 0; i < n_longs; i++)
199 _BitScanReverse(&bit, bits);
200 uint32_t offset = 31u ^ bit;
202 uint32_t offset =
static_cast<uint32_t
>(__builtin_clz(bits));
206 return item + offset;
224 const T& item)
const noexcept
231 uint32_t diff = d_func(item,
base_);
234 uint32_t pos = diff >> 5;
236 return (
bitmap_[pos] & (1u << (31u - diff))) != 0;
252 const T& item) noexcept
259 uint32_t diff = d_func(item,
base_);
261 uint32_t pos = diff >> 5;
263 bitmap_[pos] |= (1u << (31u - diff));
283 constexpr uint32_t full_mask = std::numeric_limits<uint32_t>::max();
297 uint32_t offset = d_func(
min,
base_);
298 uint32_t n_bits = d_func(
max,
min);
302 uint32_t pos = offset >> 5;
304 uint32_t mask = full_mask;
306 uint32_t bits_in_mask = 32u - offset;
309 while (n_bits >= bits_in_mask)
313 n_bits -= bits_in_mask;
321 bitmap_[pos] |= mask & (full_mask << (bits_in_mask - n_bits));
332 const T& item) noexcept
336 if ((item >=
base_) && (max_value >= item))
340 uint32_t diff = d_func(item,
base_);
341 uint32_t pos = diff >> 5;
343 bitmap_[pos] &= ~(1u << (31u - diff));
345 if (item == max_value)
347 calc_maximum_bit_set(pos + 1, 0);
363 uint32_t& num_longs_used)
const noexcept
366 num_longs_used = (
num_bits_ + 31u) / 32u;
379 const uint32_t* bitmap) noexcept
382 uint32_t num_items = ((
num_bits_ + 31u) / 32u);
383 uint32_t num_bytes = num_items *
static_cast<uint32_t
>(
sizeof(uint32_t));
385 memcpy(
bitmap_.data(), bitmap, num_bytes);
388 bitmap_[num_items - 1] &= ~(std::numeric_limits<uint32_t>::max() >> (num_bits & 31u));
390 calc_maximum_bit_set(num_items, 0);
398 template<
class UnaryFunc>
405 uint32_t n_longs = (
num_bits_ + 31u) / 32u;
406 for (uint32_t i = 0; i < n_longs; i++)
418 _BitScanReverse(&bit, bits);
419 uint32_t offset = 31u ^ bit;
421 uint32_t offset =
static_cast<uint32_t
>(__builtin_clz(bits));
422 uint32_t bit = 31u ^ offset;
429 bits &= ~(1u << bit);
461 uint32_t n_items = n_bits >> 5;
467 std::fill_n(
bitmap_.rbegin(), n_items, 0);
477 uint32_t overflow_bits = 32u - n_bits;
478 size_t last_index = NITEMS - 1u;
479 for (
size_t i = 0, n = n_items; n < last_index; i++, n++)
486 std::fill_n(
bitmap_.rbegin(), n_items, 0);
491 void shift_map_right(
504 uint32_t new_num_bits =
num_bits_ + n_bits;
505 bool find_new_max = new_num_bits > NBITS;
508 uint32_t n_items = n_bits >> 5;
514 std::fill_n(
bitmap_.begin(), n_items, 0);
525 uint32_t overflow_bits = 32u - n_bits;
526 size_t last_index = NITEMS - 1u;
527 for (
size_t i = last_index, n = last_index - n_items; n > 0; i--, n--)
534 std::fill_n(
bitmap_.begin(), n_items, 0);
540 calc_maximum_bit_set(NITEMS, n_items);
545 void calc_maximum_bit_set(
546 uint32_t starting_index,
550 for (uint32_t i = starting_index; i > min_index;)
556 bits = (bits & ~(bits - 1));
559 _BitScanReverse(&bit, bits);
560 uint32_t offset = (31u ^ bit) + 1;
562 uint32_t offset =
static_cast<uint32_t
>(__builtin_clz(bits)) + 1u;
Template class to hold a range of items using a custom bitmap.
Definition: fixed_size_bitmap.hpp:63
bitmap_type bitmap_
Holds the bitmap values.
Definition: fixed_size_bitmap.hpp:441
T base() const noexcept
Get base of the range.
Definition: fixed_size_bitmap.hpp:104
uint32_t num_bits_
Holds the highest bit set in the bitmap.
Definition: fixed_size_bitmap.hpp:442
bool empty() const noexcept
Returns whether the range is empty (i.e.
Definition: fixed_size_bitmap.hpp:163
bool add(const T &item) noexcept
Adds an element to the range.
Definition: fixed_size_bitmap.hpp:251
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:360
T min() const noexcept
Returns the lowest value set in the range.
Definition: fixed_size_bitmap.hpp:183
std::array< uint32_t, NITEMS > bitmap_type
Definition: fixed_size_bitmap.hpp:69
void bitmap_set(uint32_t num_bits, const uint32_t *bitmap) noexcept
Sets the current value of the bitmap.
Definition: fixed_size_bitmap.hpp:377
T base_
Holds base value of the range.
Definition: fixed_size_bitmap.hpp:439
void add_range(const T &from, const T &to)
Adds a range of elements to the range.
Definition: fixed_size_bitmap.hpp:279
void base_update(T base) noexcept
Set a new base for the range, keeping old values where possible.
Definition: fixed_size_bitmap.hpp:130
T range_max_
Holds maximum allowed value of the range.
Definition: fixed_size_bitmap.hpp:440
BitmapRange(T base) noexcept
Base-specific constructor.
Definition: fixed_size_bitmap.hpp:89
void for_each(UnaryFunc f) const
Apply a function on every item on the range.
Definition: fixed_size_bitmap.hpp:399
bool is_set(const T &item) const noexcept
Checks if an element is present in the bitmap.
Definition: fixed_size_bitmap.hpp:223
BitmapRange() noexcept
Default constructor.
Definition: fixed_size_bitmap.hpp:75
void base(T base) noexcept
Set a new base for the range.
Definition: fixed_size_bitmap.hpp:115
T max() const noexcept
Returns the highest value set in the range.
Definition: fixed_size_bitmap.hpp:173
void remove(const T &item) noexcept
Removes an element from the range.
Definition: fixed_size_bitmap.hpp:331
eProsima namespace.
Definition: LibrarySettingsAttributes.h:23
Definition: fixed_size_bitmap.hpp:40
constexpr auto operator()(T a, T b) const -> decltype(a - b)
Definition: fixed_size_bitmap.hpp:41