FD.io VPP  v20.09-64-g4f7b92f0a
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 * clib_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...
 

Variables

 a = a & ~b
 

Detailed Description

Bitmaps built as vectors of machine words.

Definition in file bitmap.h.

Macro Definition Documentation

◆ clib_bitmap_alloc

#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.

◆ clib_bitmap_bytes

#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.

◆ clib_bitmap_dup

#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.

◆ clib_bitmap_foreach

#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)
min_log2
static uword min_log2(uword x)
Definition: clib.h:161
i
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
first_set
static uword first_set(uword x)
Definition: clib.h:276
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:66

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.

◆ clib_bitmap_free

#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.

◆ clib_bitmap_validate

#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.

◆ clib_bitmap_vec_validate

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

Definition at line 112 of file bitmap.h.

◆ clib_bitmap_zero

#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

◆ clib_bitmap_t

typedef uword clib_bitmap_t

Definition at line 50 of file bitmap.h.

Function Documentation

◆ clib_bitmap_and()

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:

◆ clib_bitmap_andnot()

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:

◆ clib_bitmap_count_set_bits()

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 462 of file bitmap.h.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ clib_bitmap_dup_and()

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

◆ clib_bitmap_dup_andnot()

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

◆ clib_bitmap_dup_or()

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
+ Here is the caller graph for this function:

◆ clib_bitmap_dup_xor()

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
+ Here is the caller graph for this function:

◆ clib_bitmap_first_clear()

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 445 of file bitmap.h.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ clib_bitmap_first_set()

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:

◆ clib_bitmap_get()

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.

◆ clib_bitmap_get_multiple()

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:

◆ clib_bitmap_get_multiple_no_check()

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:

◆ clib_bitmap_get_no_check()

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:

◆ clib_bitmap_is_equal()

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.

◆ clib_bitmap_is_zero()

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:

◆ clib_bitmap_last_set()

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 423 of file bitmap.h.

+ Here is the caller graph for this function:

◆ clib_bitmap_or()

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:

◆ clib_bitmap_set()

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.

◆ clib_bitmap_set_multiple()

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:

◆ clib_bitmap_set_no_check()

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:

◆ clib_bitmap_set_region()

static uword* clib_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:

◆ clib_bitmap_xor()

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:

Variable Documentation

◆ a

a = a & ~b

Definition at line 538 of file bitmap.h.