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; \ 388 for (i = 0; i <
vec_len (ai); i++)
406 for (i =
vec_len (ai); i > 0; i--)
412 count_leading_zeros (first_bit, x);
413 return (i) *
BITS (ai[0]) - first_bit - 1;
427 for (i = 0; i <
vec_len (ai); i++)
433 return i *
BITS (ai[0]);
445 for (i = 0; i <
vec_len (ai); i++)
490 #define _(name, body, check_zero) \ 491 always_inline uword * \ 492 clib_bitmap_##name (uword * ai, uword * bi) \ 494 uword i, a, b, bi_len, n_trailing_zeros; \ 496 n_trailing_zeros = 0; \ 497 bi_len = vec_len (bi); \ 499 clib_bitmap_vec_validate (ai, bi_len - 1); \ 500 for (i = 0; i < vec_len (ai); i++) \ 503 b = i < bi_len ? bi[i] : 0; \ 504 do { body; } while (0); \ 507 n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \ 510 _vec_len (ai) -= n_trailing_zeros; \ 516 _(andnot,
a =
a & ~b, 1) _(or,
a =
a | b, 0) _(xor,
a =
a ^ b, 1)
555 always_inline uword * \ 556 clib_bitmap_dup_##name (uword * ai, uword * bi) \ 557 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); } 567 #define _(name, body, check_zero) \ 568 always_inline uword * \ 569 clib_bitmap_##name (uword * ai, uword i) \ 571 uword i0 = i / BITS (ai[0]); \ 572 uword i1 = i % BITS (ai[0]); \ 574 clib_bitmap_vec_validate (ai, i0); \ 576 b = (uword) 1 << i1; \ 577 do { body; } while (0); \ 579 if (check_zero && a == 0) \ 580 ai = _clib_bitmap_remove_trailing_zeros (ai); \ 585 _(andi,
a =
a & b, 1)
586 _(andnoti,
a =
a & ~b, 1) _(ori,
a =
a | b, 0) _(xori,
a =
a ^ b, 1)
607 i0 = i /
BITS (ai[0]);
608 i1 = i %
BITS (ai[0]);
611 for (i = 0; i <= i0; i++)
614 for (n = 0; n <
BITS (ai[i]); n += log2_rand_max)
617 if (i1 + 1 <
BITS (ai[0]))
618 ai[i0] &= (((
uword) 1 << (i1 + 1)) - 1);
638 t = (ai[i0] >> i1) << i1;
642 for (i0++; i0 <
vec_len (ai); i0++)
667 t = (~ai[i0] >> i1) << i1;
671 for (i0++; i0 <
vec_len (ai); i0++)
695 uword **bitmap_return = va_arg (*va,
uword **);
703 if (
unformat (input,
"%u-%u,", &a, &b))
705 else if (
unformat (input,
"%u,", &a))
707 else if (
unformat (input,
"%u-%u", &a, &b))
709 else if (
unformat (input,
"%u", &a))
722 for (i = a; i <= b; i++)
725 *bitmap_return = bitmap;
747 int i, is_trailing_zero = 1;
758 if (x && is_trailing_zero)
759 is_trailing_zero = 0;
761 if (x || !is_trailing_zero)
static u8 * format_bitmap_hex(u8 *s, va_list *args)
Format a bitmap as a string of hex bytes.
sll srl srl sll sra u16x4 i
static uword clib_bitmap_next_clear(uword *ai, uword i)
Return the next clear bit in a bitmap starting at bit i.
static uword log2_first_set(uword 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_random(uword *ai, uword n_bits, u32 *seed)
Return a random bitmap of the requested length.
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?
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.
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 * clfib_bitmap_set_region(uword *bitmap, uword i, uword value, uword n_bits)
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.
static uword unformat_bitmap_list(unformat_input_t *input, va_list *va)
unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
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_next_set(uword *ai, uword i)
Return the next set bit in a bitmap starting at bit i.
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".