Fast RTPS  Version 2.1.0
Fast RTPS
fixed_size_bitmap.hpp
1 // Copyright 2018 Proyectos y Sistemas de Mantenimiento SL (eProsima).
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
20 #ifndef FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
21 #define FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
22 
23 #include <array>
24 #include <cstdint>
25 #include <string.h>
26 #include <limits>
27 
28 #if _MSC_VER
29 #include <intrin.h>
30 #endif // if _MSC_VER
31 
32 #ifndef DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
33 namespace eprosima {
34 namespace fastrtps {
35 
36 using std::uint32_t;
37 
38 template <class T>
40 {
41  constexpr auto operator () (
42  T a,
43  T b) const
44  -> decltype(a - b)
45  {
46  return a - b;
47  }
48 
49 };
50 
61 template<class T, class Diff = DiffFunction<T>, uint32_t NBITS = 256>
63 {
64  #define NITEMS ((NBITS + 31u) / 32u)
65 
66 public:
67 
68  // Alias to improve readability.
69  using bitmap_type = std::array<uint32_t, NITEMS>;
70 
75  BitmapRange() noexcept
76  : base_()
77  , range_max_(base_ + (NBITS - 1))
78  , bitmap_()
79  , num_bits_(0u)
80  {
81  }
82 
89  explicit BitmapRange(
90  T base) noexcept
91  : base_(base)
92  , range_max_(base + (NBITS - 1))
93  , bitmap_()
94  , num_bits_(0u)
95  {
96  }
97 
98  // We don't need to define copy/move constructors/assignment operators as the default ones would be enough
99 
104  T base() const noexcept
105  {
106  return base_;
107  }
108 
115  void base(
116  T base) noexcept
117  {
118  base_ = base;
119  range_max_ = base_ + (NBITS - 1);
120  num_bits_ = 0;
121  bitmap_.fill(0u);
122  }
123 
131  T base) noexcept
132  {
133  // Do nothing if base is not changing
134  if (base == base_)
135  {
136  return;
137  }
138 
139  Diff d_func;
140  if (base > base_)
141  {
142  // Current content should move left
143  uint32_t n_bits = d_func(base, base_);
144  shift_map_left(n_bits);
145  }
146  else
147  {
148  // Current content should move right
149  uint32_t n_bits = d_func(base_, base);
150  shift_map_right(n_bits);
151  }
152 
153  // Update base and range
154  base_ = base;
155  range_max_ = base_ + (NBITS - 1);
156  }
157 
163  bool empty() const noexcept
164  {
165  return num_bits_ == 0u;
166  }
167 
173  T max() const noexcept
174  {
175  return base_ + (num_bits_ - 1);
176  }
177 
183  T min() const noexcept
184  {
185  // Traverse through the significant items on the bitmap
186  T item = base_;
187  uint32_t n_longs = (num_bits_ + 31u) / 32u;
188  for (uint32_t i = 0; i < n_longs; i++)
189  {
190  // Check if item has at least one bit set
191  uint32_t bits = bitmap_[i];
192  if (bits)
193  {
194  // We use an intrinsic to find the index of the highest bit set.
195  // Most modern CPUs have an instruction to count the leading zeroes of a word.
196  // The number of leading zeroes will give us the index we need.
197 #if _MSC_VER
198  unsigned long bit;
199  _BitScanReverse(&bit, bits);
200  uint32_t offset = 31u ^ bit;
201 #else
202  uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits));
203 #endif // if _MSC_VER
204 
205  // Found first bit set in bitmap
206  return item + offset;
207  }
208 
209  // There are 32 items on each bitmap item.
210  item = item + 32u;
211  }
212 
213  return base_;
214  }
215 
223  bool is_set(
224  const T& item) const noexcept
225  {
226  // Check item is inside the allowed range.
227  if ((item >= base_) && (range_max_ >= item))
228  {
229  // Calc distance from base to item, and check the corresponding bit.
230  Diff d_func;
231  uint32_t diff = d_func(item, base_);
232  if (diff < num_bits_)
233  {
234  uint32_t pos = diff >> 5;
235  diff &= 31u;
236  return (bitmap_[pos] & (1u << (31u - diff))) != 0;
237  }
238  }
239 
240  return false;
241  }
242 
251  bool add(
252  const T& item) noexcept
253  {
254  // Check item is inside the allowed range.
255  if ((item >= base_) && (range_max_ >= item))
256  {
257  // Calc distance from base to item, and set the corresponding bit.
258  Diff d_func;
259  uint32_t diff = d_func(item, base_);
260  num_bits_ = std::max(diff + 1, num_bits_);
261  uint32_t pos = diff >> 5;
262  diff &= 31u;
263  bitmap_[pos] |= (1u << (31u - diff));
264  return true;
265  }
266 
267  return false;
268  }
269 
279  void add_range(
280  const T& from,
281  const T& to)
282  {
283  constexpr uint32_t full_mask = std::numeric_limits<uint32_t>::max();
284 
285  // Adapt incoming range to range limits
286  T min = (base_ >= from) ? base_ : from;
287  T max = (to >= base_ + NBITS) ? base_ + NBITS : to;
288 
289  // Check precondition. Max should be explicitly above min.
290  if (min >= max)
291  {
292  return;
293  }
294 
295  // Calc offset (distance from base) and num_bits (bits to be set)
296  Diff d_func;
297  uint32_t offset = d_func(min, base_); // Bit position from base
298  uint32_t n_bits = d_func(max, min); // Number of bits pending
299 
300  num_bits_ = std::max(num_bits_, offset + n_bits);
301 
302  uint32_t pos = offset >> 5; // Item position
303  offset &= 31u; // Bit position inside item
304  uint32_t mask = full_mask; // Mask with all bits set
305  mask >>= offset; // Remove first 'offset' bits from mask
306  uint32_t bits_in_mask = 32u - offset; // Take note of number of set bits in mask
307 
308  // This loop enters whenever the whole mask should be added
309  while (n_bits >= bits_in_mask)
310  {
311  bitmap_[pos] |= mask; // Set whole mask of bits
312  pos++; // Go to next position in the array
313  n_bits -= bits_in_mask; // Decrease number of pending bits
314  mask = full_mask; // Mask with all bits set
315  bits_in_mask = 32u; // All bits set in mask (32)
316  }
317 
318  // This condition will be true if the last bits of the mask should not be used
319  if (n_bits > 0)
320  {
321  bitmap_[pos] |= mask & (full_mask << (bits_in_mask - n_bits));
322  }
323  }
324 
331  void remove(
332  const T& item) noexcept
333  {
334  // Check item is inside the allowed range.
335  T max_value = max();
336  if ((item >= base_) && (max_value >= item))
337  {
338  // Calc distance from base to item, and set the corresponding bit.
339  Diff d_func;
340  uint32_t diff = d_func(item, base_);
341  uint32_t pos = diff >> 5;
342  diff &= 31u;
343  bitmap_[pos] &= ~(1u << (31u - diff));
344 
345  if (item == max_value)
346  {
347  calc_maximum_bit_set(pos + 1, 0);
348  }
349  }
350  }
351 
361  uint32_t& num_bits,
362  bitmap_type& bitmap,
363  uint32_t& num_longs_used) const noexcept
364  {
365  num_bits = num_bits_;
366  num_longs_used = (num_bits_ + 31u) / 32u;
367  bitmap = bitmap_;
368  }
369 
378  uint32_t num_bits,
379  const uint32_t* bitmap) noexcept
380  {
381  num_bits_ = std::min(num_bits, NBITS);
382  uint32_t num_items = ((num_bits_ + 31u) / 32u);
383  uint32_t num_bytes = num_items * static_cast<uint32_t>(sizeof(uint32_t));
384  bitmap_.fill(0u);
385  memcpy(bitmap_.data(), bitmap, num_bytes);
386  if (0 < num_bits)
387  {
388  bitmap_[num_items - 1] &= ~(std::numeric_limits<uint32_t>::max() >> (num_bits & 31u));
389  }
390  calc_maximum_bit_set(num_items, 0);
391  }
392 
398  template<class UnaryFunc>
399  void for_each(
400  UnaryFunc f) const
401  {
402  T item = base_;
403 
404  // Traverse through the significant items on the bitmap
405  uint32_t n_longs = (num_bits_ + 31u) / 32u;
406  for (uint32_t i = 0; i < n_longs; i++)
407  {
408  // Traverse through the bits set on the item, msb first.
409  // Loop will stop when there are no bits set.
410  uint32_t bits = bitmap_[i];
411  while (bits)
412  {
413  // We use an intrinsic to find the index of the highest bit set.
414  // Most modern CPUs have an instruction to count the leading zeroes of a word.
415  // The number of leading zeroes will give us the index we need.
416 #if _MSC_VER
417  unsigned long bit;
418  _BitScanReverse(&bit, bits);
419  uint32_t offset = 31u ^ bit;
420 #else
421  uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits));
422  uint32_t bit = 31u ^ offset;
423 #endif // if _MSC_VER
424 
425  // Call the function for the corresponding item
426  f(item + offset);
427 
428  // Clear the most significant bit
429  bits &= ~(1u << bit);
430  }
431 
432  // There are 32 items on each bitmap item.
433  item = item + 32u;
434  }
435  }
436 
437 protected:
438 
439  T base_;
442  uint32_t num_bits_;
443 
444 private:
445 
446  void shift_map_left(
447  uint32_t n_bits)
448  {
449  if (n_bits >= num_bits_)
450  {
451  // Shifting more than most significant. Clear whole bitmap.
452  num_bits_ = 0;
453  bitmap_.fill(0u);
454  }
455  else
456  {
457  // Significant bit will move left by n_bits
458  num_bits_ -= n_bits;
459 
460  // Div and mod by 32
461  uint32_t n_items = n_bits >> 5;
462  n_bits &= 31u;
463  if (n_bits == 0)
464  {
465  // Shifting a multiple of 32 bits, just move the bitmap integers
466  std::copy(bitmap_.begin() + n_items, bitmap_.end(), bitmap_.begin());
467  std::fill_n(bitmap_.rbegin(), n_items, 0);
468  }
469  else
470  {
471  // Example. Shifting 44 bits. Should shift one complete word and 12 bits.
472  // Need to iterate forward and take 12 bits from next word (shifting it 20 bits).
473  // aaaaaaaa bbbbbbbb cccccccc dddddddd
474  // bbbbbccc bbbbbbbb cccccccc dddddddd
475  // bbbbbccc cccccddd ddddd000 dddddddd
476  // bbbbbccc cccccddd ddddd000 00000000
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++)
480  {
481  bitmap_[i] = (bitmap_[n] << n_bits) | (bitmap_[n + 1] >> overflow_bits);
482  }
483  // Last one does not have next word
484  bitmap_[last_index - n_items] = bitmap_[last_index] << n_bits;
485  // Last n_items will become 0
486  std::fill_n(bitmap_.rbegin(), n_items, 0);
487  }
488  }
489  }
490 
491  void shift_map_right(
492  uint32_t n_bits)
493  {
494  if (n_bits >= NBITS)
495  {
496  // Shifting more than total bitmap size. Clear whole bitmap.
497  num_bits_ = 0;
498  bitmap_.fill(0u);
499  }
500  else
501  {
502  // Detect if highest bit will be dropped and take note, as we will need
503  // to find new maximum bit in that case
504  uint32_t new_num_bits = num_bits_ + n_bits;
505  bool find_new_max = new_num_bits > NBITS;
506 
507  // Div and mod by 32
508  uint32_t n_items = n_bits >> 5;
509  n_bits &= 31u;
510  if (n_bits == 0)
511  {
512  // Shifting a multiple of 32 bits, just move the bitmap integers
513  std::copy(bitmap_.rbegin() + n_items, bitmap_.rend(), bitmap_.rbegin());
514  std::fill_n(bitmap_.begin(), n_items, 0);
515  }
516  else
517  {
518  // Example. Shifting 44 bits. Should shift one complete word and 12 bits.
519  // Need to iterate backwards and take 12 bits from previous word (shifting it 20 bits).
520  // aaaaaaaa bbbbbbbb cccccccc dddddddd
521  // aaaaaaaa bbbbbbbb cccccccc bbbccccc
522  // aaaaaaaa bbbbbbbb aaabbbbb bbbccccc
523  // aaaaaaaa 000aaaaa aaabbbbb bbbccccc
524  // 00000000 000aaaaa aaabbbbb bbbccccc
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--)
528  {
529  bitmap_[i] = (bitmap_[n] >> n_bits) | (bitmap_[n - 1] << overflow_bits);
530  }
531  // First item does not have previous word
532  bitmap_[n_items] = bitmap_[0] >> n_bits;
533  // First n_items will become 0
534  std::fill_n(bitmap_.begin(), n_items, 0);
535  }
536 
537  num_bits_ = new_num_bits;
538  if (find_new_max)
539  {
540  calc_maximum_bit_set(NITEMS, n_items);
541  }
542  }
543  }
544 
545  void calc_maximum_bit_set(
546  uint32_t starting_index,
547  uint32_t min_index)
548  {
549  num_bits_ = 0;
550  for (uint32_t i = starting_index; i > min_index;)
551  {
552  --i;
553  uint32_t bits = bitmap_[i];
554  if (bits != 0)
555  {
556  bits = (bits & ~(bits - 1));
557 #if _MSC_VER
558  unsigned long bit;
559  _BitScanReverse(&bit, bits);
560  uint32_t offset = (31u ^ bit) + 1;
561 #else
562  uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits)) + 1u;
563 #endif // if _MSC_VER
564  num_bits_ = (i << 5u) + offset;
565  break;
566  }
567  }
568  }
569 
570 };
571 
572 } // namespace fastrtps
573 } // namespace eprosima
574 
575 #endif // DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
576 
577 #endif // FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
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