aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--vppinfra/vppinfra/bitmap.h248
1 files changed, 210 insertions, 38 deletions
diff --git a/vppinfra/vppinfra/bitmap.h b/vppinfra/vppinfra/bitmap.h
index 17b72ac6c1f..80f1b4f191b 100644
--- a/vppinfra/vppinfra/bitmap.h
+++ b/vppinfra/vppinfra/bitmap.h
@@ -38,7 +38,9 @@
#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>
@@ -47,7 +49,10 @@
typedef uword clib_bitmap_t;
-/* Returns 1 if the entire bitmap is zero, 0 otherwise */
+/** 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)
{
@@ -58,7 +63,11 @@ 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)
{
@@ -71,19 +80,32 @@ clib_bitmap_is_equal (uword * a, uword * b)
return 1;
}
-/* Duplicate a bitmap */
+/** Duplicate a bitmap
+ @param ai - 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))
@@ -108,8 +130,13 @@ _clib_bitmap_remove_trailing_zeros (uword * a)
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)
{
@@ -129,7 +156,13 @@ clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
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 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 (uword * ai, uword i, uword value)
{
@@ -155,7 +188,11 @@ 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)
{
@@ -164,9 +201,12 @@ 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)
@@ -176,10 +216,6 @@ 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)
{
@@ -189,7 +225,12 @@ 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)
{
@@ -221,9 +262,14 @@ clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
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)
{
@@ -266,9 +312,8 @@ clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
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;
@@ -306,7 +351,12 @@ clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
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; \
@@ -325,9 +375,11 @@ do { \
} \
} while (0)
-/* Return lowest numbered set bit in bitmap.
- Return infinity (~0) if bitmap is zero. */
+/** 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;
@@ -340,9 +392,10 @@ always_inline uword clib_bitmap_first_set (uword * ai)
return ~0;
}
-/* Return highest numbered set bit in bitmap.
-
- Return infinity (~0) if bitmap is zero. */
+/** 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;
@@ -360,7 +413,10 @@ always_inline uword clib_bitmap_last_set (uword * ai)
return ~0;
}
-/* Return lowest numbered clear bit in bitmap. */
+/** 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)
{
@@ -374,7 +430,10 @@ 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)
{
@@ -385,6 +444,50 @@ 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 * \
@@ -417,8 +520,42 @@ _ (or, a = a | b, 0)
_ (xor, a = a ^ b, 1)
#undef _
-/* Define functions which duplicate first argument.
- (Normal functions over-write first argument.) */
+/** 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 _(name) \
always_inline uword * \
clib_bitmap_dup_##name (uword * ai, uword * bi) \
@@ -457,7 +594,12 @@ _ (xori, a = a ^ b, 1)
#undef _
-/* Returns random bitmap of given length. */
+/** 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)
{
@@ -487,7 +629,12 @@ clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
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)
{
@@ -512,7 +659,11 @@ clib_bitmap_next_set (uword * ai, uword i)
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)
{
@@ -536,7 +687,17 @@ clib_bitmap_next_clear (uword * ai, uword i)
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)
{
@@ -577,6 +738,17 @@ error:
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)
{