Fast RTPS  Version 2.14.1
Fast RTPS
Loading...
Searching...
No Matches
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
46namespace eprosima {
47namespace fastrtps {
48
49using std::uint32_t;
50
51template <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
74template<class T, class Diff = DiffFunction<T>, uint32_t NBITS = 256>
76{
77 #define NITEMS ((NBITS + 31u) / 32u)
78
79public:
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
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>
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
483protected:
484
488 uint32_t num_bits_;
489
490private:
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