X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Fbitmap.h;h=99d65954d0977faa9ce3927073309ed8d4d2c9da;hb=0e2f188f7c9872d7c946c14d785c6dc7c7c68847;hp=dbf9eeb2232f27ca249243cd719238e0eb23c855;hpb=1105600416e0560cb05120a22e0a2e7359a13665;p=vpp.git diff --git a/src/vppinfra/bitmap.h b/src/vppinfra/bitmap.h index dbf9eeb2232..99d65954d09 100644 --- a/src/vppinfra/bitmap.h +++ b/src/vppinfra/bitmap.h @@ -45,7 +45,6 @@ #include #include #include -#include /* for count_set_bits */ typedef uword clib_bitmap_t; @@ -115,6 +114,24 @@ clib_bitmap_is_equal (uword * a, uword * b) #define clib_bitmap_validate(v,n_bits) \ clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword)) +/** Copy a bitmap + @param dst - copy to + @param src - copy from +*/ +static_always_inline void +clib_bitmap_copy (clib_bitmap_t **dst, const clib_bitmap_t *src) +{ + if (vec_len (src)) + { + clib_bitmap_vec_validate (*dst, vec_len (src) - 1); + vec_copy (*dst, src); + } + else + { + vec_reset_length (*dst); + } +} + /* low-level routine to remove trailing zeros from a bitmap */ always_inline uword * _clib_bitmap_remove_trailing_zeros (uword * a) @@ -125,7 +142,7 @@ _clib_bitmap_remove_trailing_zeros (uword * a) for (i = _vec_len (a) - 1; i >= 0; i--) if (a[i] != 0) break; - _vec_len (a) = i + 1; + vec_set_len (a, i + 1); } return a; } @@ -161,7 +178,7 @@ clib_bitmap_set_no_check (uword * a, uword i, uword new_value) @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 + @returns the (possibly reallocated) bitmap object pointer */ always_inline uword * clib_bitmap_set (uword * ai, uword i, uword value) @@ -188,6 +205,12 @@ clib_bitmap_set (uword * ai, uword i, uword value) return ai; } +always_inline u8 +clib_bitmap_will_expand (uword *ai, uword i) +{ + return (i / BITS (ai[0])) >= vec_max_len (ai); +} + /** Gets the ith bit value from a bitmap @param ai - pointer to the bitmap @param i - the bit position to interrogate @@ -222,7 +245,7 @@ clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits) uword i0 = i / BITS (ai[0]); uword i1 = i % BITS (ai[0]); ASSERT (i1 + n_bits <= BITS (uword)); - return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits)); + return ((ai[i0] >> i1) & pow2_mask (n_bits)); } /** Gets the ith through ith + n_bits bit values from a bitmap @@ -282,7 +305,7 @@ clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits) i1 = i % BITS (bitmap[0]); /* Allocate bitmap. */ - clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0])); + clib_bitmap_vec_validate (bitmap, (i + n_bits - 1) / BITS (bitmap[0])); l = vec_len (bitmap); m = ~0; @@ -314,16 +337,17 @@ clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits) } always_inline uword * -clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits) +clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits) { - uword a0, a1, b0; + uword a0, a1, b0, b1; uword i_end, mask; a0 = i / BITS (bitmap[0]); a1 = i % BITS (bitmap[0]); - i_end = i + n_bits; + i_end = i + n_bits - 1; b0 = i_end / BITS (bitmap[0]); + b1 = i_end % BITS (bitmap[0]); clib_bitmap_vec_validate (bitmap, b0); @@ -341,8 +365,7 @@ clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits) if (a0 == b0) { - word n_bits_left = n_bits - (BITS (bitmap[0]) - a1); - mask = pow2_mask (n_bits_left); + mask = (uword) ~0 >> (BITS (bitmap[0]) - b1 - 1); if (value) bitmap[a0] |= mask; else @@ -358,24 +381,11 @@ clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits) @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; \ - __bitmap_len = vec_len ((ai)); \ - for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++) \ - { \ - __bitmap_ai = (ai)[__bitmap_i]; \ - while (__bitmap_ai != 0) \ - { \ - __bitmap_first_set = first_set (__bitmap_ai); \ - (i) = (__bitmap_i * BITS ((ai)[0]) \ - + min_log2 (__bitmap_first_set)); \ - do { body; } while (0); \ - __bitmap_ai ^= __bitmap_first_set; \ - } \ - } \ -} while (0) - +#define clib_bitmap_foreach(i,ai) \ + if (ai) \ + for (i = clib_bitmap_first_set (ai); \ + i != ~0; \ + i = clib_bitmap_next_set (ai, i + 1)) /** Return the lowest numbered set bit in a bitmap @param ai - pointer to the bitmap @@ -384,8 +394,29 @@ do { \ always_inline uword clib_bitmap_first_set (uword * ai) { - uword i; - for (i = 0; i < vec_len (ai); i++) + uword i = 0; +#if uword_bits == 64 +#if defined(CLIB_HAVE_VEC256) + while (i + 7 < vec_len (ai)) + { + u64x4 v; + v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4); + if (!u64x4_is_all_zero (v)) + break; + i += 8; + } +#elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE) + while (i + 3 < vec_len (ai)) + { + u64x2 v; + v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2); + if (!u64x2_is_all_zero (v)) + break; + i += 4; + } +#endif +#endif + for (; i < vec_len (ai); i++) { uword x = ai[i]; if (x != 0) @@ -487,33 +518,40 @@ always_inline uword *clib_bitmap_or (uword * ai, uword * bi); 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 * \ -clib_bitmap_##name (uword * ai, uword * bi) \ -{ \ - uword i, a, b, bi_len, n_trailing_zeros; \ - \ - n_trailing_zeros = 0; \ - bi_len = vec_len (bi); \ - if (bi_len > 0) \ - clib_bitmap_vec_validate (ai, bi_len - 1); \ - for (i = 0; i < vec_len (ai); i++) \ - { \ - a = ai[i]; \ - b = i < bi_len ? bi[i] : 0; \ - do { body; } while (0); \ - ai[i] = a; \ - if (check_zero) \ - n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \ - } \ - if (check_zero) \ - _vec_len (ai) -= n_trailing_zeros; \ - return ai; \ -} +#define _(name, body, check_zero) \ + always_inline uword *clib_bitmap_##name (uword *ai, uword *bi) \ + { \ + uword i, a, b, bi_len, n_trailing_zeros; \ + \ + n_trailing_zeros = 0; \ + bi_len = vec_len (bi); \ + if (bi_len > 0) \ + clib_bitmap_vec_validate (ai, bi_len - 1); \ + for (i = 0; i < vec_len (ai); i++) \ + { \ + a = ai[i]; \ + b = i < bi_len ? bi[i] : 0; \ + do \ + { \ + body; \ + } \ + while (0); \ + ai[i] = a; \ + if (check_zero) \ + n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \ + } \ + if (check_zero) \ + vec_dec_len (ai, n_trailing_zeros); \ + return ai; \ + } /* ALU functions: */ +/* *INDENT-OFF* */ _(and, a = a & b, 1) -_(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1) +_(andnot, a = a & ~b, 1) +_(or, a = a | b, 0) +_(xor, a = a ^ b, 1) +/* *INDENT-ON* */ #undef _ /** Logical operator across two bitmaps which duplicates the first bitmap @@ -521,8 +559,7 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1) @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); +always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi); /** Logical operator across two bitmaps which duplicates the first bitmap @@ -530,8 +567,7 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1) @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); +always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi); /** Logical operator across two bitmaps which duplicates the first bitmap @@ -539,8 +575,7 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1) @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); +always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi); /** Logical operator across two bitmaps which duplicates the first bitmap @@ -548,22 +583,23 @@ _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1) @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); +always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi); #define _(name) \ always_inline uword * \ clib_bitmap_dup_##name (uword * ai, uword * bi) \ { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); } +/* *INDENT-OFF* */ _(and); _(andnot); _(or); _(xor); - +/* *INDENT-ON* */ #undef _ -/* ALU function definition macro for functions taking one bitmap and an immediate. */ +/* ALU function definition macro for functions taking one bitmap and an + * immediate. */ #define _(name, body, check_zero) \ always_inline uword * \ clib_bitmap_##name (uword * ai, uword i) \ @@ -582,17 +618,48 @@ clib_bitmap_##name (uword * ai, uword i) \ } /* ALU functions immediate: */ +/* *INDENT-OFF* */ _(andi, a = a & b, 1) -_(andnoti, a = a & ~b, 1) _(ori, a = a | b, 0) _(xori, a = a ^ b, 1) +_(andnoti, a = a & ~b, 1) +_(ori, a = a | b, 0) +_(xori, a = a ^ b, 1) +/* *INDENT-ON* */ #undef _ + +/* ALU function definition macro for functions taking one bitmap and an + * immediate. No tail trimming */ +#define _(name, body) \ +always_inline uword * \ +clib_bitmap_##name##_notrim (uword * ai, uword i) \ +{ \ + uword i0 = i / BITS (ai[0]); \ + uword i1 = i % BITS (ai[0]); \ + uword a, b; \ + clib_bitmap_vec_validate (ai, i0); \ + a = ai[i0]; \ + b = (uword) 1 << i1; \ + do { body; } while (0); \ + ai[i0] = a; \ + return ai; \ +} + +/* ALU functions immediate: */ +/* *INDENT-OFF* */ +_(andi, a = a & b) +_(andnoti, a = a & ~b) +_(ori, a = a | b) +_(xori, a = a ^ b) +#undef _ +/* *INDENT-ON* */ + /** 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) +always_inline uword * +clib_bitmap_random (uword * ai, uword n_bits, u32 * seed) { vec_reset_length (ai); @@ -674,95 +741,17 @@ clib_bitmap_next_clear (uword * ai, uword i) if (t) return log2_first_set (t) + i0 * BITS (ai[0]); } - } - return i; -} - -/** 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) -{ - uword **bitmap_return = va_arg (*va, uword **); - uword *bitmap = 0; - - 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; - else if (unformat (input, "%u-%u", &a, &b)) - ; - else if (unformat (input, "%u", &a)) - b = a; - else if (bitmap) - { - unformat_put_input (input); - break; - } - else - goto error; - - if (b < a) - goto error; - - for (i = a; i <= b; i++) - bitmap = clib_bitmap_set (bitmap, i, 1); + return i0 * BITS (ai[0]); } - *bitmap_return = bitmap; - return 1; -error: - clib_bitmap_free (bitmap); - return 0; + return i; } -/** Format a bitmap as a string of hex bytes +uword unformat_bitmap_mask (unformat_input_t *input, va_list *va); +uword unformat_bitmap_list (unformat_input_t *input, va_list *va); +u8 *format_bitmap_hex (u8 *s, va_list *args); +u8 *format_bitmap_list (u8 *s, va_list *args); - 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 */ /*