#ifndef included_clib_bitmap_h
#define included_clib_bitmap_h
-/* Bitmaps built as vectors of machine words. */
+/** \file
+ Bitmaps built as vectors of machine words
+*/
#include <vppinfra/vec.h>
#include <vppinfra/random.h>
#include <vppinfra/error.h>
#include <vppinfra/bitops.h> /* for count_set_bits */
-/* Returns 1 if the entire bitmap is zero, 0 otherwise */
+typedef uword clib_bitmap_t;
+
+/** predicate function; is an entire bitmap empty?
+ @param ai - pointer to a bitmap
+ @returns 1 if the entire bitmap is zero, 0 otherwise
+*/
always_inline uword
clib_bitmap_is_zero (uword * ai)
{
return 1;
}
-/* Returns 1 if two bitmaps are equal, 0 otherwise */
+/** predicate function; are two bitmaps equal?
+ @param a - pointer to a bitmap
+ @param b - pointer to a bitmap
+ @returns 1 if the bitmaps are equal, 0 otherwise
+*/
always_inline uword
clib_bitmap_is_equal (uword * a, uword * b)
{
return 1;
}
-/* Duplicate a bitmap */
+/** Duplicate a bitmap
+ @param v - pointer to a bitmap
+ @returns a duplicate of the bitmap
+*/
#define clib_bitmap_dup(v) vec_dup(v)
-/* Free a bitmap */
+/** Free a bitmap
+ @param v - pointer to the bitmap to free
+*/
#define clib_bitmap_free(v) vec_free(v)
-/* Returns the number of bytes in a bitmap */
+/** Number of bytes in a bitmap
+ @param v - pointer to the bitmap
+*/
#define clib_bitmap_bytes(v) vec_bytes(v)
-/* Clear a bitmap */
+/** Clear a bitmap
+ @param v - pointer to the bitmap to clear
+*/
#define clib_bitmap_zero(v) vec_zero(v)
-/* Allocate bitmap with given number of bits. */
+/** Allocate a bitmap with the supplied number of bits
+ @param [out] v - the resulting bitmap
+ @param n_bits - the required number of bits
+*/
+
#define clib_bitmap_alloc(v,n_bits) \
v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
return a;
}
-/* Sets the ith bit of a bitmap to new_value. Returns old value.
- No sanity checking. Be careful. */
+/** Sets the ith bit of a bitmap to new_value.
+ No sanity checking. Be careful.
+ @param a - pointer to the bitmap
+ @param i - the bit position to interrogate
+ @param new_value - new value for the bit
+ @returns the old value of the bit
+*/
always_inline uword
clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
{
ai = a[i0];
old_value = (ai & bit) != 0;
- ai &= ~ bit;
+ ai &= ~bit;
ai |= ((uword) (new_value != 0)) << i1;
a[i0] = ai;
return old_value;
}
-/* Set bit I to value (either non-zero or zero). */
+/** Sets the ith bit of a bitmap to new_value
+ Removes trailing zeros from the bitmap
+ @param ai - pointer to the bitmap
+ @param i - the bit position to interrogate
+ @param value - new value for the bit
+ @returns the old value of the bit
+*/
always_inline uword *
clib_bitmap_set (uword * ai, uword i, uword value)
{
return ai;
}
-/* Fetch bit I. */
+/** Gets the ith bit value from a bitmap
+ @param ai - pointer to the bitmap
+ @param i - the bit position to interrogate
+ @returns the indicated bit value
+*/
always_inline uword
clib_bitmap_get (uword * ai, uword i)
{
return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
}
-/* Fetch bit I.
-
- No sanity checking. Be careful.
+/** Gets the ith bit value from a bitmap
+ Does not sanity-check the bit position. Be careful.
+ @param ai - pointer to the bitmap
+ @param i - the bit position to interrogate
+ @returns the indicated bit value, or garbage if the bit position is
+ out of range.
*/
always_inline uword
clib_bitmap_get_no_check (uword * ai, uword i)
return 0 != ((ai[i0] >> i1) & 1);
}
-/* I through I + N_BITS.
-
- No sanity checking. Be careful.
-*/
always_inline uword
clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
{
return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
}
-/* Fetch bits I through I + N_BITS. */
+/** Gets the ith through ith + n_bits bit values from a bitmap
+ @param bitmap - pointer to the bitmap
+ @param i - the first bit position to retrieve
+ @param n_bits - the number of bit positions to retrieve
+ @returns the indicated range of bits
+*/
always_inline uword
clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
{
uword i0, i1, result;
uword l = vec_len (bitmap);
- ASSERT (n_bits >= 0 && n_bits <= BITS (result));
+ ASSERT (n_bits <= BITS (result));
i0 = i / BITS (bitmap[0]);
i1 = i % BITS (bitmap[0]);
if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
{
n_bits -= BITS (bitmap[0]) - i1;
- result |= (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
+ result |=
+ (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
}
return result;
}
-/* Set bits I through I + N_BITS to given value.
+/** sets the ith through ith + n_bits bits in a bitmap
+ @param bitmap - pointer to the bitmap
+ @param i - the first bit position to retrieve
+ @param value - the values to set
+ @param n_bits - the number of bit positions to set
+ @returns a pointer to the updated bitmap, which may expand and move
+*/
- New bitmap will be returned. */
always_inline uword *
clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
{
uword i0, i1, l, t, m;
- ASSERT (n_bits >= 0 && n_bits <= BITS (value));
+ ASSERT (n_bits <= BITS (value));
i0 = i / BITS (bitmap[0]);
i1 = i % BITS (bitmap[0]);
return bitmap;
}
-/* For a multi-word region set all bits to given value. */
always_inline uword *
-clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
+clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
{
uword a0, a1, b0;
uword i_end, mask;
return bitmap;
}
-/* Iterate through set bits. */
+/** Macro to iterate across set bits in a bitmap
+
+ @param i - the current set bit
+ @param ai - the bitmap
+ @param body - the expression to evaluate for each set bit
+*/
#define clib_bitmap_foreach(i,ai,body) \
do { \
uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set; \
} \
} while (0)
-/* Return lowest numbered set bit in bitmap.
- Return infinity (~0) if bitmap is zero. */
-always_inline uword clib_bitmap_first_set (uword * ai)
+/** Return the lowest numbered set bit in a bitmap
+ @param ai - pointer to the bitmap
+ @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
+*/
+always_inline uword
+clib_bitmap_first_set (uword * ai)
{
uword i;
for (i = 0; i < vec_len (ai); i++)
return ~0;
}
-/* Return lowest numbered clear bit in bitmap. */
+/** Return the higest numbered set bit in a bitmap
+ @param ai - pointer to the bitmap
+ @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
+*/
+always_inline uword
+clib_bitmap_last_set (uword * ai)
+{
+ uword i;
+
+ for (i = vec_len (ai); i > 0; i--)
+ {
+ uword x = ai[i - 1];
+ if (x != 0)
+ {
+ uword first_bit;
+ count_leading_zeros (first_bit, x);
+ return (i) * BITS (ai[0]) - first_bit - 1;
+ }
+ }
+ return ~0;
+}
+
+/** Return the lowest numbered clear bit in a bitmap
+ @param ai - pointer to the bitmap
+ @returns lowest numbered clear bit
+*/
always_inline uword
clib_bitmap_first_clear (uword * ai)
{
return i * BITS (ai[0]);
}
-/* Count number of set bits in bitmap. */
+/** Return the number of set bits in a bitmap
+ @param ai - pointer to the bitmap
+ @returns the number of set bits in the bitmap
+*/
always_inline uword
clib_bitmap_count_set_bits (uword * ai)
{
return n_set;
}
+/** Logical operator across two bitmaps
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns ai = ai and bi. ai is modified, bi is not modified
+*/
+always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
+
+/** Logical operator across two bitmaps
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns ai = ai & ~bi. ai is modified, bi is not modified
+*/
+always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
+
+/** Logical operator across two bitmaps
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns ai = ai & ~bi. ai is modified, bi is not modified
+*/
+always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
+/** Logical operator across two bitmaps
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns ai = ai or bi. ai is modified, bi is not modified
+*/
+always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
+
+/** Logical operator across two bitmaps
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns ai = ai xor bi. ai is modified, bi is not modified
+*/
+always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
+
/* ALU function definition macro for functions taking two bitmaps. */
#define _(name, body, check_zero) \
always_inline uword * \
}
/* ALU functions: */
-_ (and, a = a & b, 1)
-_ (andnot, a = a &~ b, 1)
-_ (or, a = a | b, 0)
-_ (xor, a = a ^ b, 1)
+_(and, a = a & b, 1)
+_(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
#undef _
+/** Logical operator across two bitmaps which duplicates the first bitmap
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns aiDup = ai and bi. Neither ai nor bi are modified
+*/
+ always_inline uword *
+ clib_bitmap_dup_and (uword * ai, uword * bi);
+
+/** Logical operator across two bitmaps which duplicates the first bitmap
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns aiDup = ai & ~bi. Neither ai nor bi are modified
+*/
+ always_inline uword *
+ clib_bitmap_dup_andnot (uword * ai, uword * bi);
+
+/** Logical operator across two bitmaps which duplicates the first bitmap
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns aiDup = ai or bi. Neither ai nor bi are modified
+*/
+ always_inline uword *
+ clib_bitmap_dup_or (uword * ai, uword * bi);
+
+/** Logical operator across two bitmaps which duplicates the first bitmap
+
+ @param ai - pointer to the destination bitmap
+ @param bi - pointer to the source bitmap
+ @returns aiDup = ai xor bi. Neither ai nor bi are modified
+*/
+ always_inline uword *
+ clib_bitmap_dup_xor (uword * ai, uword * bi);
-/* Define functions which duplicate first argument.
- (Normal functions over-write first argument.) */
#define _(name) \
always_inline uword * \
clib_bitmap_dup_##name (uword * ai, uword * bi) \
{ return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
-_ (and);
-_ (andnot);
-_ (or);
-_ (xor);
+_(and);
+_(andnot);
+_(or);
+_(xor);
#undef _
}
/* ALU functions immediate: */
-_ (andi, a = a & b, 1)
-_ (andnoti, a = a &~ b, 1)
-_ (ori, a = a | b, 0)
-_ (xori, a = a ^ b, 1)
-
+_(andi, a = a & b, 1)
+_(andnoti, a = a & ~b, 1) _(ori, a = a | b, 0) _(xori, a = a ^ b, 1)
#undef _
-
-/* Returns random bitmap of given length. */
-always_inline uword *
-clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
+/** Return a random bitmap of the requested length
+ @param ai - pointer to the destination bitmap
+ @param n_bits - number of bits to allocate
+ @param [in,out] seed - pointer to the random number seed
+ @returns a reasonably random bitmap based. See random.h.
+*/
+ always_inline uword *
+ clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
{
vec_reset_length (ai);
return ai;
}
-/* Returns next set bit starting at bit i (~0 if not found). */
+/** Return the next set bit in a bitmap starting at bit i
+ @param ai - pointer to the bitmap
+ @param i - first bit position to test
+ @returns first set bit position at or after i,
+ ~0 if no further set bits are found
+*/
always_inline uword
clib_bitmap_next_set (uword * ai, uword i)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
uword t;
-
+
if (i0 < vec_len (ai))
{
t = (ai[i0] >> i1) << i1;
return ~0;
}
-/* Returns next clear bit at position >= i */
+/** Return the next clear bit in a bitmap starting at bit i
+ @param ai - pointer to the bitmap
+ @param i - first bit position to test
+ @returns first clear bit position at or after i
+*/
always_inline uword
clib_bitmap_next_clear (uword * ai, uword i)
{
uword i0 = i / BITS (ai[0]);
uword i1 = i % BITS (ai[0]);
uword t;
-
+
if (i0 < vec_len (ai))
{
t = (~ai[i0] >> i1) << i1;
for (i0++; i0 < vec_len (ai); i0++)
{
- t = ~ai[i0];
+ t = ~ai[i0];
if (t)
return log2_first_set (t) + i0 * BITS (ai[0]);
}
return i;
}
-/* unformat list of bits into bitmap (eg "0-3,5-7,11" ) */
+/** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
+
+ uword * bitmap;
+ rv = unformat ("%U", unformat_bitmap_list, &bitmap);
+
+ Standard unformat_function_t arguments
+
+ @param input - pointer an unformat_input_t
+ @param va - varargs list comprising a single uword **
+ @returns 1 on success, 0 on failure
+*/
static inline uword
-unformat_bitmap_list(unformat_input_t * input, va_list * va)
+unformat_bitmap_list (unformat_input_t * input, va_list * va)
{
- uword ** bitmap_return = va_arg (* va, uword **);
- uword * bitmap = 0;
+ uword **bitmap_return = va_arg (*va, uword **);
+ uword *bitmap = 0;
- u32 a,b;
+ u32 a, b;
while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
{
int i;
if (unformat (input, "%u-%u,", &a, &b))
- ;
+ ;
else if (unformat (input, "%u,", &a))
- b = a;
+ b = a;
else if (unformat (input, "%u-%u", &a, &b))
- ;
+ ;
else if (unformat (input, "%u", &a))
- b = a;
+ b = a;
else if (bitmap)
- {
- unformat_put_input(input);
+ {
+ unformat_put_input (input);
break;
}
else
- goto error;
+ goto error;
- if ((b < a) || (b > 63))
- goto error;
+ if (b < a)
+ goto error;
for (i = a; i <= b; i++)
- bitmap = clib_bitmap_set(bitmap, i, 1);
+ bitmap = clib_bitmap_set (bitmap, i, 1);
}
*bitmap_return = bitmap;
return 1;
error:
- clib_bitmap_free(bitmap);
+ clib_bitmap_free (bitmap);
return 0;
}
+/** Format a bitmap as a string of hex bytes
+
+ uword * bitmap;
+ s = format ("%U", format_bitmap_hex, bitmap);
+
+ Standard format_function_t arguments
+
+ @param s - string under construction
+ @param args - varargs list comprising a single uword *
+ @returns string under construction
+*/
+static inline u8 *
+format_bitmap_hex (u8 * s, va_list * args)
+{
+ uword *bitmap = va_arg (*args, uword *);
+ int i, is_trailing_zero = 1;
+
+ if (!bitmap)
+ return format (s, "0");
+
+ i = vec_bytes (bitmap) * 2;
+
+ while (i > 0)
+ {
+ u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);
+
+ if (x && is_trailing_zero)
+ is_trailing_zero = 0;
+
+ if (x || !is_trailing_zero)
+ s = format (s, "%x", x);
+ }
+ return s;
+}
#endif /* included_clib_bitmap_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
Code Review / vpp.git / blobdiff