FD.io VPP  v16.09
Vector Packet Processing
Macros | Typedefs | Functions | Variables
bitmap.h File Reference

Bitmaps built as vectors of machine words. More...

+ Include dependency graph for bitmap.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define clib_bitmap_dup(v)   vec_dup(v)
 Duplicate a bitmap. More...
 
#define clib_bitmap_free(v)   vec_free(v)
 Free a bitmap. More...
 
#define clib_bitmap_bytes(v)   vec_bytes(v)
 Number of bytes in a bitmap. More...
 
#define clib_bitmap_zero(v)   vec_zero(v)
 Clear a bitmap. More...
 
#define clib_bitmap_alloc(v, n_bits)   v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
 Allocate a bitmap with the supplied number of bits. More...
 
#define clib_bitmap_vec_validate(v, i)   vec_validate_aligned((v),(i),sizeof(uword))
 
#define clib_bitmap_validate(v, n_bits)   clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
 
#define clib_bitmap_foreach(i, ai, body)
 Macro to iterate across set bits in a bitmap. More...
 

Typedefs

typedef uword clib_bitmap_t
 

Functions

static uword clib_bitmap_is_zero (uword *ai)
 predicate function; is an entire bitmap empty? More...
 
static uword clib_bitmap_is_equal (uword *a, uword *b)
 predicate function; are two bitmaps equal? More...
 
static uword clib_bitmap_set_no_check (uword *a, uword i, uword new_value)
 Sets the ith bit of a bitmap to new_value. More...
 
static uword * clib_bitmap_set (uword *ai, uword i, uword value)
 Sets the ith bit of a bitmap to new_value Removes trailing zeros from the bitmap. More...
 
static uword clib_bitmap_get (uword *ai, uword i)
 Gets the ith bit value from a bitmap. More...
 
static uword clib_bitmap_get_no_check (uword *ai, uword i)
 Gets the ith bit value from a bitmap Does not sanity-check the bit position. More...
 
static uword clib_bitmap_get_multiple_no_check (uword *ai, uword i, uword n_bits)
 
static uword clib_bitmap_get_multiple (uword *bitmap, uword i, uword n_bits)
 Gets the ith through ith + n_bits bit values from a bitmap. More...
 
static uword * clib_bitmap_set_multiple (uword *bitmap, uword i, uword value, uword n_bits)
 sets the ith through ith + n_bits bits in a bitmap More...
 
static uword * clfib_bitmap_set_region (uword *bitmap, uword i, uword value, uword n_bits)
 
static uword clib_bitmap_first_set (uword *ai)
 Return the lowest numbered set bit in a bitmap. More...
 
static uword clib_bitmap_last_set (uword *ai)
 Return the higest numbered set bit in a bitmap. More...
 
static uword clib_bitmap_first_clear (uword *ai)
 Return the lowest numbered clear bit in a bitmap. More...
 
static uword clib_bitmap_count_set_bits (uword *ai)
 Return the number of set bits in a bitmap. More...
 
static uword * clib_bitmap_and (uword *ai, uword *bi)
 Logical operator across two bitmaps. More...
 
static uword * clib_bitmap_andnot (uword *ai, uword *bi)
 Logical operator across two bitmaps. More...
 
static uword * clib_bitmap_or (uword *ai, uword *bi)
 Logical operator across two bitmaps. More...
 
static uword * clib_bitmap_xor (uword *ai, uword *bi)
 Logical operator across two bitmaps. More...
 
static uword * clib_bitmap_dup_and (uword *ai, uword *bi)
 Logical operator across two bitmaps which duplicates the first bitmap. More...
 
static uword * clib_bitmap_dup_andnot (uword *ai, uword *bi)
 Logical operator across two bitmaps which duplicates the first bitmap. More...
 
static uword * clib_bitmap_dup_or (uword *ai, uword *bi)
 Logical operator across two bitmaps which duplicates the first bitmap. More...
 
static uword * clib_bitmap_dup_xor (uword *ai, uword *bi)
 Logical operator across two bitmaps which duplicates the first bitmap. More...
 
static uword * clib_bitmap_random (uword *ai, uword n_bits, u32 *seed)
 Return a random bitmap of the requested length. More...
 
static uword clib_bitmap_next_set (uword *ai, uword i)
 Return the next set bit in a bitmap starting at bit i. More...
 
static uword clib_bitmap_next_clear (uword *ai, uword i)
 Return the next clear bit in a bitmap starting at bit i. More...
 
static uword unformat_bitmap_list (unformat_input_t *input, va_list *va)
 unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" ) More...
 
static u8 * format_bitmap_hex (u8 *s, va_list *args)
 Format a bitmap as a string of hex bytes. More...
 

Variables

 a = a & ~b
 

Detailed Description

Bitmaps built as vectors of machine words.

Definition in file bitmap.h.

Macro Definition Documentation

#define clib_bitmap_alloc (   v,
  n_bits 
)    v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))

Allocate a bitmap with the supplied number of bits.

Parameters
[out]v- the resulting bitmap
n_bits- the required number of bits

Definition at line 109 of file bitmap.h.

#define clib_bitmap_bytes (   v)    vec_bytes(v)

Number of bytes in a bitmap.

Parameters
v- pointer to the bitmap

Definition at line 97 of file bitmap.h.

#define clib_bitmap_dup (   v)    vec_dup(v)

Duplicate a bitmap.

Parameters
v- pointer to a bitmap
Returns
a duplicate of the bitmap

Definition at line 87 of file bitmap.h.

#define clib_bitmap_foreach (   i,
  ai,
  body 
)
Value:
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)
i
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
min_log2
static uword min_log2(uword x)
Definition: clib.h:183
first_set
static uword first_set(uword x)
Definition: clib.h:284
uword
u64 uword
Definition: types.h:112
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
BITS
#define BITS(x)
Definition: clib.h:58

Macro to iterate across set bits in a bitmap.

Parameters
i- the current set bit
ai- the bitmap
body- the expression to evaluate for each set bit

Definition at line 361 of file bitmap.h.

#define clib_bitmap_free (   v)    vec_free(v)

Free a bitmap.

Parameters
v- pointer to the bitmap to free

Definition at line 92 of file bitmap.h.

#define clib_bitmap_validate (   v,
  n_bits 
)    clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))

Definition at line 115 of file bitmap.h.

#define clib_bitmap_vec_validate (   v,
  i 
)    vec_validate_aligned((v),(i),sizeof(uword))

Definition at line 112 of file bitmap.h.

#define clib_bitmap_zero (   v)    vec_zero(v)

Clear a bitmap.

Parameters
v- pointer to the bitmap to clear

Definition at line 102 of file bitmap.h.

Typedef Documentation

typedef uword clib_bitmap_t

Definition at line 50 of file bitmap.h.

Function Documentation

static uword* clfib_bitmap_set_region ( uword *  bitmap,
uword  i,
uword  value,
uword  n_bits 
)
inlinestatic

Definition at line 317 of file bitmap.h.

+ Here is the call graph for this function:

static uword* clib_bitmap_and ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
ai = ai and bi. ai is modified, bi is not modified

+ Here is the caller graph for this function:

static uword* clib_bitmap_andnot ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
ai = ai & ~bi. ai is modified, bi is not modified

+ Here is the caller graph for this function:

static uword clib_bitmap_count_set_bits ( uword *  ai)
inlinestatic

Return the number of set bits in a bitmap.

Parameters
ai- pointer to the bitmap
Returns
the number of set bits in the bitmap

Definition at line 441 of file bitmap.h.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static uword* clib_bitmap_dup_and ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps which duplicates the first bitmap.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
aiDup = ai and bi. Neither ai nor bi are modified
static uword* clib_bitmap_dup_andnot ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps which duplicates the first bitmap.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
aiDup = ai & ~bi. Neither ai nor bi are modified
static uword* clib_bitmap_dup_or ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps which duplicates the first bitmap.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
aiDup = ai or bi. Neither ai nor bi are modified
static uword* clib_bitmap_dup_xor ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps which duplicates the first bitmap.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
aiDup = ai xor bi. Neither ai nor bi are modified
static uword clib_bitmap_first_clear ( uword *  ai)
inlinestatic

Return the lowest numbered clear bit in a bitmap.

Parameters
ai- pointer to the bitmap
Returns
lowest numbered clear bit

Definition at line 424 of file bitmap.h.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static uword clib_bitmap_first_set ( uword *  ai)
inlinestatic

Return the lowest numbered set bit in a bitmap.

Parameters
ai- pointer to the bitmap
Returns
lowest numbered set bit, or ~0 if the entire bitmap is zero

Definition at line 385 of file bitmap.h.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static uword clib_bitmap_get ( uword *  ai,
uword  i 
)
inlinestatic

Gets the ith bit value from a bitmap.

Parameters
ai- pointer to the bitmap
i- the bit position to interrogate
Returns
the indicated bit value

Definition at line 197 of file bitmap.h.

+ Here is the caller graph for this function:

static uword clib_bitmap_get_multiple ( uword *  bitmap,
uword  i,
uword  n_bits 
)
inlinestatic

Gets the ith through ith + n_bits bit values from a bitmap.

Parameters
bitmap- pointer to the bitmap
i- the first bit position to retrieve
n_bits- the number of bit positions to retrieve
Returns
the indicated range of bits

Definition at line 235 of file bitmap.h.

+ Here is the caller graph for this function:

static uword clib_bitmap_get_multiple_no_check ( uword *  ai,
uword  i,
uword  n_bits 
)
inlinestatic

Definition at line 220 of file bitmap.h.

+ Here is the call graph for this function:

static uword clib_bitmap_get_no_check ( uword *  ai,
uword  i 
)
inlinestatic

Gets the ith bit value from a bitmap Does not sanity-check the bit position.

Be careful.

Parameters
ai- pointer to the bitmap
i- the bit position to interrogate
Returns
the indicated bit value, or garbage if the bit position is out of range.

Definition at line 212 of file bitmap.h.

+ Here is the caller graph for this function:

static uword clib_bitmap_is_equal ( uword *  a,
uword *  b 
)
inlinestatic

predicate function; are two bitmaps equal?

Parameters
a- pointer to a bitmap
b- pointer to a bitmap
Returns
1 if the bitmaps are equal, 0 otherwise

Definition at line 72 of file bitmap.h.

static uword clib_bitmap_is_zero ( uword *  ai)
inlinestatic

predicate function; is an entire bitmap empty?

Parameters
ai- pointer to a bitmap
Returns
1 if the entire bitmap is zero, 0 otherwise

Definition at line 57 of file bitmap.h.

+ Here is the caller graph for this function:

static uword clib_bitmap_last_set ( uword *  ai)
inlinestatic

Return the higest numbered set bit in a bitmap.

Parameters
ai- pointer to the bitmap
Returns
lowest numbered set bit, or ~0 if the entire bitmap is zero

Definition at line 402 of file bitmap.h.

+ Here is the caller graph for this function:

static uword clib_bitmap_next_clear ( uword *  ai,
uword  i 
)
inlinestatic

Return the next clear bit in a bitmap starting at bit i.

Parameters
ai- pointer to the bitmap
i- first bit position to test
Returns
first clear bit position at or after i

Definition at line 659 of file bitmap.h.

+ Here is the call graph for this function:

static uword clib_bitmap_next_set ( uword *  ai,
uword  i 
)
inlinestatic

Return the next set bit in a bitmap starting at bit i.

Parameters
ai- pointer to the bitmap
i- first bit position to test
Returns
first set bit position at or after i, ~0 if no further set bits are found

Definition at line 630 of file bitmap.h.

+ Here is the call graph for this function:

static uword * clib_bitmap_or ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
ai = ai & ~bi. ai is modified, bi is not modified
Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
ai = ai or bi. ai is modified, bi is not modified

+ Here is the caller graph for this function:

static uword* clib_bitmap_random ( uword *  ai,
uword  n_bits,
u32 *  seed 
)
inlinestatic

Return a random bitmap of the requested length.

Parameters
ai- pointer to the destination bitmap
n_bits- number of bits to allocate
[in,out]seed- pointer to the random number seed
Returns
a reasonably random bitmap based. See random.h.

Definition at line 595 of file bitmap.h.

+ Here is the call graph for this function:

static uword* clib_bitmap_set ( uword *  ai,
uword  i,
uword  value 
)
inlinestatic

Sets the ith bit of a bitmap to new_value Removes trailing zeros from the bitmap.

Parameters
ai- pointer to the bitmap
i- the bit position to interrogate
value- new value for the bit
Returns
the old value of the bit

Definition at line 167 of file bitmap.h.

+ Here is the caller graph for this function:

static uword* clib_bitmap_set_multiple ( uword *  bitmap,
uword  i,
uword  value,
uword  n_bits 
)
inlinestatic

sets the ith through ith + n_bits bits in a bitmap

Parameters
bitmap- pointer to the bitmap
i- the first bit position to retrieve
value- the values to set
n_bits- the number of bit positions to set
Returns
a pointer to the updated bitmap, which may expand and move

Definition at line 275 of file bitmap.h.

+ Here is the caller graph for this function:

static uword clib_bitmap_set_no_check ( uword *  a,
uword  i,
uword  new_value 
)
inlinestatic

Sets the ith bit of a bitmap to new_value.

No sanity checking. Be careful.

Parameters
a- pointer to the bitmap
i- the bit position to interrogate
new_value- new value for the bit
Returns
the old value of the bit

Definition at line 141 of file bitmap.h.

+ Here is the caller graph for this function:

static uword* clib_bitmap_xor ( uword *  ai,
uword *  bi 
)
inlinestatic

Logical operator across two bitmaps.

Parameters
ai- pointer to the destination bitmap
bi- pointer to the source bitmap
Returns
ai = ai xor bi. ai is modified, bi is not modified

+ Here is the caller graph for this function:

static u8* format_bitmap_hex ( u8 *  s,
va_list *  args 
)
inlinestatic

Format a bitmap as a string of hex bytes.

uword * bitmap; s = format ("%U", format_bitmap_hex, bitmap);

Standard format_function_t arguments

Parameters
s- string under construction
args- varargs list comprising a single uword *
Returns
string under construction

Definition at line 744 of file bitmap.h.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static uword unformat_bitmap_list ( unformat_input_t *  input,
va_list *  va 
)
inlinestatic

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

Parameters
input- pointer an unformat_input_t
va- varargs list comprising a single uword **
Returns
1 on success, 0 on failure

Definition at line 693 of file bitmap.h.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Variable Documentation

a = a & ~b

Definition at line 516 of file bitmap.h.