X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=vppinfra%2Fvppinfra%2Fbitmap.h;h=9e1ae49328556ecf31e7b67ab236aeed18cd9ebb;hb=9dd34e00ede6e5d0b32e8e0c0b26b03dee468549;hp=e69851b60be17b80379366bee2aad0175849532b;hpb=14a44d37a36d1f62897aa304922cea568ce1b577;p=vpp.git

diff --git a/vppinfra/vppinfra/bitmap.h b/vppinfra/vppinfra/bitmap.h
index e69851b60be..9e1ae493285 100644
--- a/vppinfra/vppinfra/bitmap.h
+++ b/vppinfra/vppinfra/bitmap.h
@@ -38,14 +38,21 @@
 #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)
 {
@@ -56,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)
 {
@@ -69,19 +80,32 @@ 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))
 
@@ -106,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)
 {
@@ -121,13 +150,19 @@ 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)
 {
@@ -153,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)
 {
@@ -162,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)
@@ -174,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)
 {
@@ -187,14 +225,19 @@ 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]);
@@ -213,21 +256,27 @@ clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
   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]);
@@ -264,9 +313,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;
@@ -304,7 +352,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;	\
@@ -323,10 +376,13 @@ do {									\
     }									\
 } 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++)
@@ -338,7 +394,32 @@ always_inline uword clib_bitmap_first_set (uword * ai)
   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)
 {
@@ -352,7 +433,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)
 {
@@ -363,6 +447,45 @@ 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 *						\
@@ -389,23 +512,54 @@ clib_bitmap_##name (uword * ai, uword * bi)			\
 }
 
 /* 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 _
 
@@ -428,16 +582,17 @@ clib_bitmap_##name (uword * ai, uword i)		\
 }
 
 /* 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);
 
@@ -465,14 +620,19 @@ 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)
 {
   uword i0 = i / BITS (ai[0]);
   uword i1 = i % BITS (ai[0]);
   uword t;
-  
+
   if (i0 < vec_len (ai))
     {
       t = (ai[i0] >> i1) << i1;
@@ -490,14 +650,18 @@ 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)
 {
   uword i0 = i / BITS (ai[0]);
   uword i1 = i % BITS (ai[0]);
   uword t;
-  
+
   if (i0 < vec_len (ai))
     {
       t = (~ai[i0] >> i1) << i1;
@@ -506,7 +670,7 @@ clib_bitmap_next_clear (uword * ai, uword i)
 
       for (i0++; i0 < vec_len (ai); i0++)
 	{
-          t = ~ai[i0];
+	  t = ~ai[i0];
 	  if (t)
 	    return log2_first_set (t) + i0 * BITS (ai[0]);
 	}
@@ -514,68 +678,97 @@ 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)
+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)
-        goto error;
+	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)
+format_bitmap_hex (u8 * s, va_list * args)
 {
-  uword * bitmap = va_arg (*args, uword *);
+  uword *bitmap = va_arg (*args, uword *);
   int i, is_trailing_zero = 1;
 
   if (!bitmap)
-    return format(s, "0");
+    return format (s, "0");
 
   i = vec_bytes (bitmap) * 2;
 
   while (i > 0)
     {
-      u8 x = clib_bitmap_get_multiple(bitmap, --i * 4, 4);
+      u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);
 
       if (x && is_trailing_zero)
-        is_trailing_zero = 0;
+	is_trailing_zero = 0;
 
       if (x || !is_trailing_zero)
-          s = format(s, "%x", x);
+	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:
+ */