Program Listing for File fixed_size_bitmap.hpp
↰ Return to documentation for file (/tmp/ws/src/fastrtps/include/fastrtps/utils/fixed_size_bitmap.hpp
)
// Copyright 2018 Proyectos y Sistemas de Mantenimiento SL (eProsima).
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
#define FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
#include <array>
#include <cstdint>
#include <string.h>
#include <limits>
#if _MSC_VER
#include <intrin.h>
#if defined(max)
#pragma push_macro("max")
#undef max
#define FASTDDS_RESTORE_MAX
#endif // defined(max)
#if defined(min)
#pragma push_macro("min")
#undef min
#define FASTDDS_RESTORE_MIN
#endif // defined(min)
#endif // if _MSC_VER
#ifndef DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
namespace eprosima {
namespace fastrtps {
using std::uint32_t;
template <class T>
struct DiffFunction
{
constexpr auto operator () (
T a,
T b) const
-> decltype(a - b)
{
return a - b;
}
};
template<class T, class Diff = DiffFunction<T>, uint32_t NBITS = 256>
class BitmapRange
{
#define NITEMS ((NBITS + 31u) / 32u)
public:
// Alias to improve readability.
using bitmap_type = std::array<uint32_t, NITEMS>;
BitmapRange() noexcept
: base_()
, range_max_(base_ + (NBITS - 1))
, bitmap_()
, num_bits_(0u)
{
}
explicit BitmapRange(
T base) noexcept
: BitmapRange(base, NBITS - 1)
{
}
BitmapRange(
T base,
uint32_t max_bits) noexcept
: base_(base)
, range_max_(base_ + (std::min)(max_bits, NBITS - 1))
, bitmap_()
, num_bits_(0u)
{
}
// We don't need to define copy/move constructors/assignment operators as the default ones would be enough
T base() const noexcept
{
return base_;
}
void base(
T base) noexcept
{
base_ = base;
range_max_ = base_ + (NBITS - 1);
num_bits_ = 0;
bitmap_.fill(0u);
}
void base(
T base,
uint32_t max_bits) noexcept
{
base_ = base;
range_max_ = base_ + (std::min)(max_bits, NBITS - 1);
num_bits_ = 0;
bitmap_.fill(0u);
}
void base_update(
T base) noexcept
{
// Do nothing if base is not changing
if (base == base_)
{
return;
}
Diff d_func;
if (base > base_)
{
// Current content should move left
uint32_t n_bits = d_func(base, base_);
shift_map_left(n_bits);
}
else
{
// Current content should move right
uint32_t n_bits = d_func(base_, base);
shift_map_right(n_bits);
}
// Update base and range
base_ = base;
range_max_ = base_ + (NBITS - 1);
}
bool empty() const noexcept
{
return num_bits_ == 0u;
}
T max() const noexcept
{
return base_ + (num_bits_ - 1);
}
T min() const noexcept
{
// Traverse through the significant items on the bitmap
T item = base_;
uint32_t n_longs = (num_bits_ + 31u) / 32u;
for (uint32_t i = 0; i < n_longs; i++)
{
// Check if item has at least one bit set
uint32_t bits = bitmap_[i];
if (bits)
{
// We use an intrinsic to find the index of the highest bit set.
// Most modern CPUs have an instruction to count the leading zeroes of a word.
// The number of leading zeroes will give us the index we need.
#if _MSC_VER
unsigned long bit;
_BitScanReverse(&bit, bits);
uint32_t offset = 31u ^ bit;
#else
uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits));
#endif // if _MSC_VER
// Found first bit set in bitmap
return item + offset;
}
// There are 32 items on each bitmap item.
item = item + 32u;
}
return base_;
}
bool is_set(
const T& item) const noexcept
{
// Check item is inside the allowed range.
if ((item >= base_) && (range_max_ >= item))
{
// Calc distance from base to item, and check the corresponding bit.
Diff d_func;
uint32_t diff = d_func(item, base_);
if (diff < num_bits_)
{
uint32_t pos = diff >> 5;
diff &= 31u;
return (bitmap_[pos] & (1u << (31u - diff))) != 0;
}
}
return false;
}
bool add(
const T& item) noexcept
{
// Check item is inside the allowed range.
if ((item >= base_) && (range_max_ >= item))
{
// Calc distance from base to item, and set the corresponding bit.
Diff d_func;
uint32_t diff = d_func(item, base_);
num_bits_ = std::max(diff + 1, num_bits_);
uint32_t pos = diff >> 5;
diff &= 31u;
bitmap_[pos] |= (1u << (31u - diff));
return true;
}
return false;
}
void add_range(
const T& from,
const T& to)
{
constexpr uint32_t full_mask = std::numeric_limits<uint32_t>::max();
// Adapt incoming range to range limits
T min = (base_ >= from) ? base_ : from;
T max = (to >= base_ + NBITS) ? base_ + NBITS : to;
// Check precondition. Max should be explicitly above min.
if (min >= max)
{
return;
}
// Calc offset (distance from base) and num_bits (bits to be set)
Diff d_func;
uint32_t offset = d_func(min, base_); // Bit position from base
uint32_t n_bits = d_func(max, min); // Number of bits pending
num_bits_ = std::max(num_bits_, offset + n_bits);
uint32_t pos = offset >> 5; // Item position
offset &= 31u; // Bit position inside item
uint32_t mask = full_mask; // Mask with all bits set
mask >>= offset; // Remove first 'offset' bits from mask
uint32_t bits_in_mask = 32u - offset; // Take note of number of set bits in mask
// This loop enters whenever the whole mask should be added
while (n_bits >= bits_in_mask)
{
bitmap_[pos] |= mask; // Set whole mask of bits
pos++; // Go to next position in the array
n_bits -= bits_in_mask; // Decrease number of pending bits
mask = full_mask; // Mask with all bits set
bits_in_mask = 32u; // All bits set in mask (32)
}
// This condition will be true if the last bits of the mask should not be used
if (n_bits > 0)
{
bitmap_[pos] |= mask & (full_mask << (bits_in_mask - n_bits));
}
}
void remove(
const T& item) noexcept
{
// Check item is inside the allowed range.
T max_value = max();
if ((item >= base_) && (max_value >= item))
{
// Calc distance from base to item, and set the corresponding bit.
Diff d_func;
uint32_t diff = d_func(item, base_);
uint32_t pos = diff >> 5;
diff &= 31u;
bitmap_[pos] &= ~(1u << (31u - diff));
if (item == max_value)
{
calc_maximum_bit_set(pos + 1, 0);
}
}
}
void bitmap_get(
uint32_t& num_bits,
bitmap_type& bitmap,
uint32_t& num_longs_used) const noexcept
{
num_bits = num_bits_;
num_longs_used = (num_bits_ + 31u) / 32u;
bitmap = bitmap_;
}
void bitmap_set(
uint32_t num_bits,
const uint32_t* bitmap) noexcept
{
num_bits_ = std::min(num_bits, NBITS);
uint32_t num_items = ((num_bits_ + 31u) / 32u);
uint32_t num_bytes = num_items * static_cast<uint32_t>(sizeof(uint32_t));
bitmap_.fill(0u);
memcpy(bitmap_.data(), bitmap, num_bytes);
// trim unused bits if (0 < num_bits && num_bits % 32 != 0)
short shift = num_bits & 31u;
if (0 < num_bits && shift != 0)
{
bitmap_[num_items - 1] &= ~(std::numeric_limits<uint32_t>::max() >> shift);
}
calc_maximum_bit_set(num_items, 0);
}
template<class UnaryFunc>
void for_each(
UnaryFunc f) const
{
T item = base_;
// Traverse through the significant items on the bitmap
uint32_t n_longs = (num_bits_ + 31u) / 32u;
for (uint32_t i = 0; i < n_longs; i++)
{
// Traverse through the bits set on the item, msb first.
// Loop will stop when there are no bits set.
uint32_t bits = bitmap_[i];
while (bits)
{
// We use an intrinsic to find the index of the highest bit set.
// Most modern CPUs have an instruction to count the leading zeroes of a word.
// The number of leading zeroes will give us the index we need.
#if _MSC_VER
unsigned long bit;
_BitScanReverse(&bit, bits);
uint32_t offset = 31u ^ bit;
#else
uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits));
uint32_t bit = 31u ^ offset;
#endif // if _MSC_VER
// Call the function for the corresponding item
f(item + offset);
// Clear the most significant bit
bits &= ~(1u << bit);
}
// There are 32 items on each bitmap item.
item = item + 32u;
}
}
protected:
T base_;
T range_max_;
bitmap_type bitmap_;
uint32_t num_bits_;
private:
void shift_map_left(
uint32_t n_bits)
{
if (n_bits >= num_bits_)
{
// Shifting more than most significant. Clear whole bitmap.
num_bits_ = 0;
bitmap_.fill(0u);
}
else
{
// Significant bit will move left by n_bits
num_bits_ -= n_bits;
// Div and mod by 32
uint32_t n_items = n_bits >> 5;
n_bits &= 31u;
if (n_bits == 0)
{
// Shifting a multiple of 32 bits, just move the bitmap integers
std::copy(bitmap_.begin() + n_items, bitmap_.end(), bitmap_.begin());
std::fill_n(bitmap_.rbegin(), n_items, 0);
}
else
{
// Example. Shifting 44 bits. Should shift one complete word and 12 bits.
// Need to iterate forward and take 12 bits from next word (shifting it 20 bits).
// aaaaaaaa bbbbbbbb cccccccc dddddddd
// bbbbbccc bbbbbbbb cccccccc dddddddd
// bbbbbccc cccccddd ddddd000 dddddddd
// bbbbbccc cccccddd ddddd000 00000000
uint32_t overflow_bits = 32u - n_bits;
size_t last_index = NITEMS - 1u;
for (size_t i = 0, n = n_items; n < last_index; i++, n++)
{
bitmap_[i] = (bitmap_[n] << n_bits) | (bitmap_[n + 1] >> overflow_bits);
}
// Last one does not have next word
bitmap_[last_index - n_items] = bitmap_[last_index] << n_bits;
// Last n_items will become 0
std::fill_n(bitmap_.rbegin(), n_items, 0);
}
}
}
void shift_map_right(
uint32_t n_bits)
{
if (n_bits >= NBITS)
{
// Shifting more than total bitmap size. Clear whole bitmap.
num_bits_ = 0;
bitmap_.fill(0u);
}
else
{
// Detect if highest bit will be dropped and take note, as we will need
// to find new maximum bit in that case
uint32_t new_num_bits = num_bits_ + n_bits;
bool find_new_max = new_num_bits > NBITS;
// Div and mod by 32
uint32_t n_items = n_bits >> 5;
n_bits &= 31u;
if (n_bits == 0)
{
// Shifting a multiple of 32 bits, just move the bitmap integers
std::copy(bitmap_.rbegin() + n_items, bitmap_.rend(), bitmap_.rbegin());
std::fill_n(bitmap_.begin(), n_items, 0);
}
else
{
// Example. Shifting 44 bits. Should shift one complete word and 12 bits.
// Need to iterate backwards and take 12 bits from previous word (shifting it 20 bits).
// aaaaaaaa bbbbbbbb cccccccc dddddddd
// aaaaaaaa bbbbbbbb cccccccc bbbccccc
// aaaaaaaa bbbbbbbb aaabbbbb bbbccccc
// aaaaaaaa 000aaaaa aaabbbbb bbbccccc
// 00000000 000aaaaa aaabbbbb bbbccccc
uint32_t overflow_bits = 32u - n_bits;
size_t last_index = NITEMS - 1u;
for (size_t i = last_index, n = last_index - n_items; n > 0; i--, n--)
{
bitmap_[i] = (bitmap_[n] >> n_bits) | (bitmap_[n - 1] << overflow_bits);
}
// First item does not have previous word
bitmap_[n_items] = bitmap_[0] >> n_bits;
// First n_items will become 0
std::fill_n(bitmap_.begin(), n_items, 0);
}
num_bits_ = new_num_bits;
if (find_new_max)
{
calc_maximum_bit_set(NITEMS, n_items);
}
}
}
void calc_maximum_bit_set(
uint32_t starting_index,
uint32_t min_index)
{
num_bits_ = 0;
for (uint32_t i = starting_index; i > min_index;)
{
--i;
uint32_t bits = bitmap_[i];
if (bits != 0)
{
bits = (bits & ~(bits - 1));
#if _MSC_VER
unsigned long bit;
_BitScanReverse(&bit, bits);
uint32_t offset = (31u ^ bit) + 1;
#else
uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits)) + 1u;
#endif // if _MSC_VER
num_bits_ = (i << 5u) + offset;
break;
}
}
}
};
} // namespace fastrtps
} // namespace eprosima
#endif // DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
#if _MSC_VER
#if defined(FASTDDS_RESTORE_MIN)
#pragma pop_macro("min")
#undef FASTDDS_RESTORE_MIN
#endif // defined(FASTDDS_RESTORE_MIN)
#if defined(FASTDDS_RESTORE_MAX)
#pragma pop_macro("max")
#undef FASTDDS_RESTORE_MAX
#endif // defined(FASTDDS_RESTORE_MAX)
#endif // if _MSC_VER
#endif // FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_