VPP-223 Document vppinfra/bitmap.h

Change-Id: I259a5b716bd8a7abdb0e6bf778432f034338ffdc
Signed-off-by: Dave Barach <dave@barachs.net>

1 files changed, 210 insertions, 38 deletions

diff --git a/vppinfra/vppinfra/bitmap.h b/vppinfra/vppinfra/bitmap.h
index 17b72ac6..80f1b4f1 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)
 {