diff options
Diffstat (limited to 'src/vppinfra/bitmap.h')
| -rw-r--r-- | src/vppinfra/bitmap.h | 101 |
1 files changed, 59 insertions, 42 deletions
diff --git a/src/vppinfra/bitmap.h b/src/vppinfra/bitmap.h index 92205bfc8e8..4ab7bcf7a7c 100644 --- a/src/vppinfra/bitmap.h +++ b/src/vppinfra/bitmap.h @@ -45,7 +45,6 @@ #include <vppinfra/vec.h> #include <vppinfra/random.h> #include <vppinfra/error.h> -#include <vppinfra/bitops.h> /* 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; @@ -316,14 +339,15 @@ clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits) always_inline uword * 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 @@ clib_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 @@ -495,37 +518,38 @@ 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) -/* *INDENT-ON* */ #undef _ /** Logical operator across two bitmaps which duplicates the first bitmap @@ -564,12 +588,10 @@ always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi); 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 @@ -592,12 +614,10 @@ 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) -/* *INDENT-ON* */ #undef _ /* ALU function definition macro for functions taking one bitmap and an @@ -618,13 +638,11 @@ clib_bitmap_##name##_notrim (uword * ai, uword i) \ } /* 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 @@ -716,8 +734,7 @@ clib_bitmap_next_clear (uword * ai, uword i) return log2_first_set (t) + i0 * BITS (ai[0]); } - /* no clear bit left in bitmap, return bit just beyond bitmap */ - return (i0 * BITS (ai[0])) + 1; + return i0 * BITS (ai[0]); } return i; } |