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:

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)
	Macro to iterate across set bits in a bitmap. More...

#define	clib_bitmap_foreach_old(i, ai, body)

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
	)

Value:

if (ai)                                                         \
    for (i = clib_bitmap_first_set (ai);                                \
         i != ~0;                                                       \
         i = clib_bitmap_next_set (ai, i + 1))

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_foreach_old

#define clib_bitmap_foreach_old	(	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)

Definition at line 367 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 468 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 451 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 391 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 429 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 544 of file bitmap.h.

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ clib_bitmap_alloc

◆ clib_bitmap_bytes

◆ clib_bitmap_dup

◆ clib_bitmap_foreach

◆ clib_bitmap_foreach_old

◆ clib_bitmap_free

◆ clib_bitmap_validate

◆ clib_bitmap_vec_validate

◆ clib_bitmap_zero

Typedef Documentation

◆ clib_bitmap_t

Function Documentation

◆ clib_bitmap_and()

◆ clib_bitmap_andnot()

◆ clib_bitmap_count_set_bits()

◆ clib_bitmap_dup_and()

◆ clib_bitmap_dup_andnot()

◆ clib_bitmap_dup_or()

◆ clib_bitmap_dup_xor()

◆ clib_bitmap_first_clear()

◆ clib_bitmap_first_set()

◆ clib_bitmap_get()

◆ clib_bitmap_get_multiple()

◆ clib_bitmap_get_multiple_no_check()

◆ clib_bitmap_get_no_check()

◆ clib_bitmap_is_equal()

◆ clib_bitmap_is_zero()

◆ clib_bitmap_last_set()

◆ clib_bitmap_or()

◆ clib_bitmap_set()

◆ clib_bitmap_set_multiple()

◆ clib_bitmap_set_no_check()

◆ clib_bitmap_set_region()

◆ clib_bitmap_xor()

Variable Documentation

◆ a