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)

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.

Here is the caller graph for this function:

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.