38 #ifndef included_clib_bitmap_h 39 #define included_clib_bitmap_h 60 for (i = 0; i <
vec_len (ai); i++)
77 for (i = 0; i <
vec_len (a); i++)
87 #define clib_bitmap_dup(v) vec_dup(v) 92 #define clib_bitmap_free(v) vec_free(v) 97 #define clib_bitmap_bytes(v) vec_bytes(v) 102 #define clib_bitmap_zero(v) vec_zero(v) 109 #define clib_bitmap_alloc(v,n_bits) \ 110 v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword)) 112 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword)) 115 #define clib_bitmap_validate(v,n_bits) \ 116 clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword)) 120 _clib_bitmap_remove_trailing_zeros (
uword * a)
125 for (i = _vec_len (a) - 1; i >= 0; i--)
128 _vec_len (a) = i + 1;
152 old_value = (ai & bit) != 0;
154 ai |= ((
uword) (new_value != 0)) << i1;
174 if (value == 0 && i0 >=
vec_len (ai))
180 a &= ~((
uword) 1 << i1);
181 a |= ((
uword) (value != 0)) << i1;
186 ai = _clib_bitmap_remove_trailing_zeros (ai);
201 return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
216 return 0 != ((ai[i0] >> i1) & 1);
225 return 0 != ((ai[i0] >> i1) &
pow2_mask (n_bits));
237 uword i0, i1, result;
242 i0 = i /
BITS (bitmap[0]);
243 i1 = i %
BITS (bitmap[0]);
249 result |= (bitmap[i0] >> i1);
250 if (n_bits <
BITS (bitmap[0]))
251 result &= (((
uword) 1 << n_bits) - 1);
256 if (i1 + n_bits >
BITS (bitmap[0]) && i0 < l)
258 n_bits -=
BITS (bitmap[0]) - i1;
260 (bitmap[i0] & (((
uword) 1 << n_bits) - 1)) << (
BITS (bitmap[0]) - i1);
277 uword i0, i1, l, t, m;
281 i0 = i /
BITS (bitmap[0]);
282 i1 = i %
BITS (bitmap[0]);
289 if (n_bits <
BITS (value))
290 m = (((
uword) 1 << n_bits) - 1);
301 if (i1 + n_bits >
BITS (bitmap[0]) && i0 < l)
303 t =
BITS (bitmap[0]) - i1;
307 m = ((
uword) 1 << n_bits) - 1;
322 a0 = i /
BITS (bitmap[0]);
323 a1 = i %
BITS (bitmap[0]);
326 b0 = i_end /
BITS (bitmap[0]);
339 for (a0++; a0 < b0; a0++)
340 bitmap[a0] = value ? ~0 : 0;
344 word n_bits_left = n_bits - (
BITS (bitmap[0]) - a1);
361 #define clib_bitmap_foreach(i,ai,body) \ 363 uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set; \ 364 __bitmap_len = vec_len ((ai)); \ 365 for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++) \ 367 __bitmap_ai = (ai)[__bitmap_i]; \ 368 while (__bitmap_ai != 0) \ 370 __bitmap_first_set = first_set (__bitmap_ai); \ 371 (i) = (__bitmap_i * BITS ((ai)[0]) \ 372 + min_log2 (__bitmap_first_set)); \ 373 do { body; } while (0); \ 374 __bitmap_ai ^= __bitmap_first_set; \ 389 #if defined(CLIB_HAVE_VEC256) 393 v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
394 if (!u64x4_is_all_zero (v))
398 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE) 402 v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
403 if (!u64x2_is_all_zero (v))
427 for (i =
vec_len (ai); i > 0; i--)
434 return (i) *
BITS (ai[0]) - first_bit - 1;
448 for (i = 0; i <
vec_len (ai); i++)
454 return i *
BITS (ai[0]);
466 for (i = 0; i <
vec_len (ai); i++)
511 #define _(name, body, check_zero) \ 512 always_inline uword * \ 513 clib_bitmap_##name (uword * ai, uword * bi) \ 515 uword i, a, b, bi_len, n_trailing_zeros; \ 517 n_trailing_zeros = 0; \ 518 bi_len = vec_len (bi); \ 520 clib_bitmap_vec_validate (ai, bi_len - 1); \ 521 for (i = 0; i < vec_len (ai); i++) \ 524 b = i < bi_len ? bi[i] : 0; \ 525 do { body; } while (0); \ 528 n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \ 531 _vec_len (ai) -= n_trailing_zeros; \ 538 _(andnot, a = a & ~b, 1)
576 always_inline uword * \ 577 clib_bitmap_dup_##name (uword * ai, uword * bi) \ 578 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); } 590 #define _(name, body, check_zero) \ 591 always_inline uword * \ 592 clib_bitmap_##name (uword * ai, uword i) \ 594 uword i0 = i / BITS (ai[0]); \ 595 uword i1 = i % BITS (ai[0]); \ 597 clib_bitmap_vec_validate (ai, i0); \ 599 b = (uword) 1 << i1; \ 600 do { body; } while (0); \ 602 if (check_zero && a == 0) \ 603 ai = _clib_bitmap_remove_trailing_zeros (ai); \ 609 _(andi, a = a & b, 1)
610 _(andnoti, a = a & ~b, 1)
612 _(xori, a = a ^ b, 1)
618 #define _(name, body) \ 619 always_inline uword * \ 620 clib_bitmap_##name##_notrim (uword * ai, uword i) \ 622 uword i0 = i / BITS (ai[0]); \ 623 uword i1 = i % BITS (ai[0]); \ 625 clib_bitmap_vec_validate (ai, i0); \ 627 b = (uword) 1 << i1; \ 628 do { body; } while (0); \ 636 _(andnoti, a = a & ~b)
655 uword i = n_bits - 1;
661 i0 = i /
BITS (ai[0]);
662 i1 = i %
BITS (ai[0]);
665 for (i = 0; i <= i0; i++)
668 for (n = 0; n <
BITS (ai[i]); n += log2_rand_max)
671 if (i1 + 1 <
BITS (ai[0]))
672 ai[i0] &= (((
uword) 1 << (i1 + 1)) - 1);
692 t = (ai[i0] >> i1) << i1;
696 for (i0++; i0 <
vec_len (ai); i0++)
721 t = (~ai[i0] >> i1) << i1;
725 for (i0++; i0 <
vec_len (ai); i0++)
733 return (i0 *
BITS (ai[0])) + 1;
753 uword **bitmap_return = va_arg (*va,
uword **);
761 for (i = 0; s >= 0; i++, s--)
763 s *
BITS (v[i]), v[i],
767 *bitmap_return = bitmap;
788 uword **bitmap_return = va_arg (*va,
uword **);
796 if (
unformat (input,
"%u-%u,", &a, &b))
798 else if (
unformat (input,
"%u,", &a))
800 else if (
unformat (input,
"%u-%u", &a, &b))
802 else if (
unformat (input,
"%u", &a))
815 for (i = a; i <= b; i++)
818 *bitmap_return = bitmap;
837 format_bitmap_hex (
u8 * s, va_list * args)
840 int i, is_trailing_zero = 1;
851 if (x && is_trailing_zero)
852 is_trailing_zero = 0;
854 if (x || !is_trailing_zero)
static uword log2_first_set(uword x)
static uword * clib_bitmap_set_region(uword *bitmap, uword i, uword value, uword n_bits)
#define count_leading_zeros(x)
static uword * clib_bitmap_or(uword *ai, uword *bi)
Logical operator across two bitmaps.
static uword * clib_bitmap_set(uword *ai, uword i, uword value)
Sets the ith bit of a bitmap to new_value Removes trailing zeros from the bitmap. ...
#define vec_bytes(v)
Number of data bytes in vector.
static uword clib_bitmap_get_multiple_no_check(uword *ai, uword i, uword n_bits)
static uword clib_bitmap_get_no_check(uword *ai, uword i)
Gets the ith bit value from a bitmap Does not sanity-check the bit position.
static uword min_log2(uword x)
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
static uword clib_bitmap_set_no_check(uword *a, uword i, uword new_value)
Sets the ith bit of a bitmap to new_value.
static uword clib_bitmap_is_equal(uword *a, uword *b)
predicate function; are two bitmaps equal?
static uword pow2_mask(uword x)
static uword clib_bitmap_is_zero(uword *ai)
predicate function; is an entire bitmap empty?
epu8_epi32 epu16_epi32 u64x2
static uword clib_bitmap_first_set(uword *ai)
Return the lowest numbered set bit in a bitmap.
static uword clib_bitmap_last_set(uword *ai)
Return the higest numbered set bit in a bitmap.
static uword clib_bitmap_get_multiple(uword *bitmap, uword i, uword n_bits)
Gets the ith through ith + n_bits bit values from a bitmap.
static uword * clib_bitmap_dup_andnot(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
static uword * clib_bitmap_xor(uword *ai, uword *bi)
Logical operator across two bitmaps.
static u32 random_u32_max(void)
Maximum value returned by random_u32()
static uword * clib_bitmap_dup_xor(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
sll srl srl sll sra u16x4 i
#define vec_free(V)
Free vector's memory (no header).
static uword * clib_bitmap_dup_or(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
static uword * clib_bitmap_andnot(uword *ai, uword *bi)
Logical operator across two bitmaps.
static uword * clib_bitmap_set_multiple(uword *bitmap, uword i, uword value, uword n_bits)
sets the ith through ith + n_bits bits in a bitmap
static uword clib_bitmap_get(uword *ai, uword i)
Gets the ith bit value from a bitmap.
#define clib_bitmap_vec_validate(v, i)
#define clib_bitmap_free(v)
Free a bitmap.
static uword clib_bitmap_count_set_bits(uword *ai)
Return the number of set bits in a bitmap.
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static uword * clib_bitmap_dup_and(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
Linear Congruential Random Number Generator.
static u32 random_u32(u32 *seed)
32-bit random number generator
static uword count_set_bits(uword x)
static uword clib_bitmap_first_clear(uword *ai)
Return the lowest numbered clear bit in a bitmap.
static uword * clib_bitmap_and(uword *ai, uword *bi)
Logical operator across two bitmaps.
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".