Fast RTPS  Version 2.7.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 
31 #if defined(max)
32 #pragma push_macro("max")
33 #undef max
34 #define FASTDDS_RESTORE_MAX
35 #endif // defined(max)
36 
37 #if defined(min)
38 #pragma push_macro("min")
39 #undef min
40 #define FASTDDS_RESTORE_MIN
41 #endif // defined(min)
42 
43 #endif // if _MSC_VER
44 
45 #ifndef DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
46 namespace eprosima {
47 namespace fastrtps {
48 
49 using std::uint32_t;
50 
51 template <class T>
53 {
54  constexpr auto operator () (
55  T a,
56  T b) const
57  -> decltype(a - b)
58  {
59  return a - b;
60  }
61 
62 };
63 
74 template<class T, class Diff = DiffFunction<T>, uint32_t NBITS = 256>
76 {
77  #define NITEMS ((NBITS + 31u) / 32u)
78 
79 public:
80 
81  // Alias to improve readability.
82  using bitmap_type = std::array<uint32_t, NITEMS>;
83 
88  BitmapRange() noexcept
89  : base_()
90  , range_max_(base_ + (NBITS - 1))
91  , bitmap_()
92  , num_bits_(0u)
93  {
94  }
95 
102  explicit BitmapRange(
103  T base) noexcept
104  : BitmapRange(base, NBITS - 1)
105  {
106  }
107 
116  T base,
117  uint32_t max_bits) noexcept
118  : base_(base)
119  , range_max_(base_ + (std::min)(max_bits, NBITS - 1))
120  , bitmap_()
121  , num_bits_(0u)
122  {
123  }
124 
125  // We don't need to define copy/move constructors/assignment operators as the default ones would be enough
126 
131  T base() const noexcept
132  {
133  return base_;
134  }
135 
142  void base(
143  T base) noexcept
144  {
145  base_ = base;
146  range_max_ = base_ + (NBITS - 1);
147  num_bits_ = 0;
148  bitmap_.fill(0u);
149  }
150 
158  void base(
159  T base,
160  uint32_t max_bits) noexcept
161  {
162  base_ = base;
163  range_max_ = base_ + (std::min)(max_bits, NBITS - 1);
164  num_bits_ = 0;
165  bitmap_.fill(0u);
166  }
167 
175  T base) noexcept
176  {
177  // Do nothing if base is not changing
178  if (base == base_)
179  {
180  return;
181  }
182 
183  Diff d_func;
184  if (base > base_)
185  {
186  // Current content should move left
187  uint32_t n_bits = d_func(base, base_);
188  shift_map_left(n_bits);
189  }
190  else
191  {
192  // Current content should move right
193  uint32_t n_bits = d_func(base_, base);
194  shift_map_right(n_bits);
195  }
196 
197  // Update base and range
198  base_ = base;
199  range_max_ = base_ + (NBITS - 1);
200  }
201 
207  bool empty() const noexcept
208  {
209  return num_bits_ == 0u;
210  }
211 
217  T max() const noexcept
218  {
219  return base_ + (num_bits_ - 1);
220  }
221 
227  T min() const noexcept
228  {
229  // Traverse through the significant items on the bitmap
230  T item = base_;
231  uint32_t n_longs = (num_bits_ + 31u) / 32u;
232  for (uint32_t i = 0; i < n_longs; i++)
233  {
234  // Check if item has at least one bit set
235  uint32_t bits = bitmap_[i];
236  if (bits)
237  {
238  // We use an intrinsic to find the index of the highest bit set.
239  // Most modern CPUs have an instruction to count the leading zeroes of a word.
240  // The number of leading zeroes will give us the index we need.
241 #if _MSC_VER
242  unsigned long bit;
243  _BitScanReverse(&bit, bits);
244  uint32_t offset = 31u ^ bit;
245 #else
246  uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits));
247 #endif // if _MSC_VER
248 
249  // Found first bit set in bitmap
250  return item + offset;
251  }
252 
253  // There are 32 items on each bitmap item.
254  item = item + 32u;
255  }
256 
257  return base_;
258  }
259 
267  bool is_set(
268  const T& item) const noexcept
269  {
270  // Check item is inside the allowed range.
271  if ((item >= base_) && (range_max_ >= item))
272  {
273  // Calc distance from base to item, and check the corresponding bit.
274  Diff d_func;
275  uint32_t diff = d_func(item, base_);
276  if (diff < num_bits_)
277  {
278  uint32_t pos = diff >> 5;
279  diff &= 31u;
280  return (bitmap_[pos] & (1u << (31u - diff))) != 0;
281  }
282  }
283 
284  return false;
285  }
286 
295  bool add(
296  const T& item) noexcept
297  {
298  // Check item is inside the allowed range.
299  if ((item >= base_) && (range_max_ >= item))
300  {
301  // Calc distance from base to item, and set the corresponding bit.
302  Diff d_func;
303  uint32_t diff = d_func(item, base_);
304  num_bits_ = std::max(diff + 1, num_bits_);
305  uint32_t pos = diff >> 5;
306  diff &= 31u;
307  bitmap_[pos] |= (1u << (31u - diff));
308  return true;
309  }
310 
311  return false;
312  }
313 
323  void add_range(
324  const T& from,
325  const T& to)
326  {
327  constexpr uint32_t full_mask = std::numeric_limits<uint32_t>::max();
328 
329  // Adapt incoming range to range limits
330  T min = (base_ >= from) ? base_ : from;
331  T max = (to >= base_ + NBITS) ? base_ + NBITS : to;
332 
333  // Check precondition. Max should be explicitly above min.
334  if (min >= max)
335  {
336  return;
337  }
338 
339  // Calc offset (distance from base) and num_bits (bits to be set)
340  Diff d_func;
341  uint32_t offset = d_func(min, base_); // Bit position from base
342  uint32_t n_bits = d_func(max, min); // Number of bits pending
343 
344  num_bits_ = std::max(num_bits_, offset + n_bits);
345 
346  uint32_t pos = offset >> 5; // Item position
347  offset &= 31u; // Bit position inside item
348  uint32_t mask = full_mask; // Mask with all bits set
349  mask >>= offset; // Remove first 'offset' bits from mask
350  uint32_t bits_in_mask = 32u - offset; // Take note of number of set bits in mask
351 
352  // This loop enters whenever the whole mask should be added
353  while (n_bits >= bits_in_mask)
354  {
355  bitmap_[pos] |= mask; // Set whole mask of bits
356  pos++; // Go to next position in the array
357  n_bits -= bits_in_mask; // Decrease number of pending bits
358  mask = full_mask; // Mask with all bits set
359  bits_in_mask = 32u; // All bits set in mask (32)
360  }
361 
362  // This condition will be true if the last bits of the mask should not be used
363  if (n_bits > 0)
364  {
365  bitmap_[pos] |= mask & (full_mask << (bits_in_mask - n_bits));
366  }
367  }
368 
375  void remove(
376  const T& item) noexcept
377  {
378  // Check item is inside the allowed range.
379  T max_value = max();
380  if ((item >= base_) && (max_value >= item))
381  {
382  // Calc distance from base to item, and set the corresponding bit.
383  Diff d_func;
384  uint32_t diff = d_func(item, base_);
385  uint32_t pos = diff >> 5;
386  diff &= 31u;
387  bitmap_[pos] &= ~(1u << (31u - diff));
388 
389  if (item == max_value)
390  {
391  calc_maximum_bit_set(pos + 1, 0);
392  }
393  }
394  }
395 
405  uint32_t& num_bits,
406  bitmap_type& bitmap,
407  uint32_t& num_longs_used) const noexcept
408  {
409  num_bits = num_bits_;
410  num_longs_used = (num_bits_ + 31u) / 32u;
411  bitmap = bitmap_;
412  }
413 
422  uint32_t num_bits,
423  const uint32_t* bitmap) noexcept
424  {
425  num_bits_ = std::min(num_bits, NBITS);
426  uint32_t num_items = ((num_bits_ + 31u) / 32u);
427  uint32_t num_bytes = num_items * static_cast<uint32_t>(sizeof(uint32_t));
428  bitmap_.fill(0u);
429  memcpy(bitmap_.data(), bitmap, num_bytes);
430  // trim unused bits if (0 < num_bits && num_bits % 32 != 0)
431  short shift = num_bits & 31u;
432  if (0 < num_bits && shift != 0)
433  {
434  bitmap_[num_items - 1] &= ~(std::numeric_limits<uint32_t>::max() >> shift);
435  }
436  calc_maximum_bit_set(num_items, 0);
437  }
438 
444  template<class UnaryFunc>
445  void for_each(
446  UnaryFunc f) const
447  {
448  T item = base_;
449 
450  // Traverse through the significant items on the bitmap
451  uint32_t n_longs = (num_bits_ + 31u) / 32u;
452  for (uint32_t i = 0; i < n_longs; i++)
453  {
454  // Traverse through the bits set on the item, msb first.
455  // Loop will stop when there are no bits set.
456  uint32_t bits = bitmap_[i];
457  while (bits)
458  {
459  // We use an intrinsic to find the index of the highest bit set.
460  // Most modern CPUs have an instruction to count the leading zeroes of a word.
461  // The number of leading zeroes will give us the index we need.
462 #if _MSC_VER
463  unsigned long bit;
464  _BitScanReverse(&bit, bits);
465  uint32_t offset = 31u ^ bit;
466 #else
467  uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits));
468  uint32_t bit = 31u ^ offset;
469 #endif // if _MSC_VER
470 
471  // Call the function for the corresponding item
472  f(item + offset);
473 
474  // Clear the most significant bit
475  bits &= ~(1u << bit);
476  }
477 
478  // There are 32 items on each bitmap item.
479  item = item + 32u;
480  }
481  }
482 
483 protected:
484 
485  T base_;
488  uint32_t num_bits_;
489 
490 private:
491 
492  void shift_map_left(
493  uint32_t n_bits)
494  {
495  if (n_bits >= num_bits_)
496  {
497  // Shifting more than most significant. Clear whole bitmap.
498  num_bits_ = 0;
499  bitmap_.fill(0u);
500  }
501  else
502  {
503  // Significant bit will move left by n_bits
504  num_bits_ -= n_bits;
505 
506  // Div and mod by 32
507  uint32_t n_items = n_bits >> 5;
508  n_bits &= 31u;
509  if (n_bits == 0)
510  {
511  // Shifting a multiple of 32 bits, just move the bitmap integers
512  std::copy(bitmap_.begin() + n_items, bitmap_.end(), bitmap_.begin());
513  std::fill_n(bitmap_.rbegin(), n_items, 0);
514  }
515  else
516  {
517  // Example. Shifting 44 bits. Should shift one complete word and 12 bits.
518  // Need to iterate forward and take 12 bits from next word (shifting it 20 bits).
519  // aaaaaaaa bbbbbbbb cccccccc dddddddd
520  // bbbbbccc bbbbbbbb cccccccc dddddddd
521  // bbbbbccc cccccddd ddddd000 dddddddd
522  // bbbbbccc cccccddd ddddd000 00000000
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++)
526  {
527  bitmap_[i] = (bitmap_[n] << n_bits) | (bitmap_[n + 1] >> overflow_bits);
528  }
529  // Last one does not have next word
530  bitmap_[last_index - n_items] = bitmap_[last_index] << n_bits;
531  // Last n_items will become 0
532  std::fill_n(bitmap_.rbegin(), n_items, 0);
533  }
534  }
535  }
536 
537  void shift_map_right(
538  uint32_t n_bits)
539  {
540  if (n_bits >= NBITS)
541  {
542  // Shifting more than total bitmap size. Clear whole bitmap.
543  num_bits_ = 0;
544  bitmap_.fill(0u);
545  }
546  else
547  {
548  // Detect if highest bit will be dropped and take note, as we will need
549  // to find new maximum bit in that case
550  uint32_t new_num_bits = num_bits_ + n_bits;
551  bool find_new_max = new_num_bits > NBITS;
552 
553  // Div and mod by 32
554  uint32_t n_items = n_bits >> 5;
555  n_bits &= 31u;
556  if (n_bits == 0)
557  {
558  // Shifting a multiple of 32 bits, just move the bitmap integers
559  std::copy(bitmap_.rbegin() + n_items, bitmap_.rend(), bitmap_.rbegin());
560  std::fill_n(bitmap_.begin(), n_items, 0);
561  }
562  else
563  {
564  // Example. Shifting 44 bits. Should shift one complete word and 12 bits.
565  // Need to iterate backwards and take 12 bits from previous word (shifting it 20 bits).
566  // aaaaaaaa bbbbbbbb cccccccc dddddddd
567  // aaaaaaaa bbbbbbbb cccccccc bbbccccc
568  // aaaaaaaa bbbbbbbb aaabbbbb bbbccccc
569  // aaaaaaaa 000aaaaa aaabbbbb bbbccccc
570  // 00000000 000aaaaa aaabbbbb bbbccccc
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--)
574  {
575  bitmap_[i] = (bitmap_[n] >> n_bits) | (bitmap_[n - 1] << overflow_bits);
576  }
577  // First item does not have previous word
578  bitmap_[n_items] = bitmap_[0] >> n_bits;
579  // First n_items will become 0
580  std::fill_n(bitmap_.begin(), n_items, 0);
581  }
582 
583  num_bits_ = new_num_bits;
584  if (find_new_max)
585  {
586  calc_maximum_bit_set(NITEMS, n_items);
587  }
588  }
589  }
590 
591  void calc_maximum_bit_set(
592  uint32_t starting_index,
593  uint32_t min_index)
594  {
595  num_bits_ = 0;
596  for (uint32_t i = starting_index; i > min_index;)
597  {
598  --i;
599  uint32_t bits = bitmap_[i];
600  if (bits != 0)
601  {
602  bits = (bits & ~(bits - 1));
603 #if _MSC_VER
604  unsigned long bit;
605  _BitScanReverse(&bit, bits);
606  uint32_t offset = (31u ^ bit) + 1;
607 #else
608  uint32_t offset = static_cast<uint32_t>(__builtin_clz(bits)) + 1u;
609 #endif // if _MSC_VER
610  num_bits_ = (i << 5u) + offset;
611  break;
612  }
613  }
614  }
615 
616 };
617 
618 } // namespace fastrtps
619 } // namespace eprosima
620 
621 #endif // DOXYGEN_SHOULD_SKIP_THIS_PUBLIC
622 
623 #if _MSC_VER
624 
625 #if defined(FASTDDS_RESTORE_MIN)
626 #pragma pop_macro("min")
627 #undef FASTDDS_RESTORE_MIN
628 #endif // defined(FASTDDS_RESTORE_MIN)
629 
630 #if defined(FASTDDS_RESTORE_MAX)
631 #pragma pop_macro("max")
632 #undef FASTDDS_RESTORE_MAX
633 #endif // defined(FASTDDS_RESTORE_MAX)
634 
635 #endif // if _MSC_VER
636 
637 #endif // FASTRTPS_UTILS_FIXED_SIZE_BITMAP_HPP_
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