Bitmap

Data Structures
struct	m0_bitmap
struct	m0_bitmap_onwire

Macros
#define	M0_BITMAP_WORDS(nr)   (((nr) + (M0_BITMAP_BITS-1)) >> M0_BITMAP_BITSHIFT)
#define	M0_BITMAP_SHIFT(idx)   ((idx) >> M0_BITMAP_BITSHIFT)
#define	M0_BITMAP_MASK(idx)   (1UL << ((idx) & (M0_BITMAP_BITS-1)))

Enumerations
enum	{ M0_BITMAP_BITS = (8 * sizeof ((struct m0_bitmap *)0)->b_words[0]), M0_BITMAP_BITSHIFT = 6 }

Functions
	M0_BASSERT (M0_BITMAP_BITS==(1UL<< M0_BITMAP_BITSHIFT))
	M0_BASSERT (M0_BITMAP_WORDS(0)==0)
	M0_BASSERT (M0_BITMAP_WORDS(1)==1)
	M0_BASSERT (M0_BITMAP_WORDS(63)==1)
	M0_BASSERT (M0_BITMAP_WORDS(64)==1)
	M0_BASSERT (M0_BITMAP_WORDS(65)==2)
M0_INTERNAL int	m0_bitmap_init (struct m0_bitmap *map, size_t nr)
M0_INTERNAL void	m0_bitmap_fini (struct m0_bitmap *map)
M0_INTERNAL bool	m0_bitmap_get (const struct m0_bitmap *map, size_t idx)
M0_INTERNAL int	m0_bitmap_ffs (const struct m0_bitmap *map)
M0_INTERNAL int	m0_bitmap_ffz (const struct m0_bitmap *map)
M0_INTERNAL void	m0_bitmap_set (struct m0_bitmap *map, size_t idx, bool val)
M0_INTERNAL void	m0_bitmap_reset (struct m0_bitmap *map)
M0_INTERNAL void	m0_bitmap_copy (struct m0_bitmap *dst, const struct m0_bitmap *src)
M0_INTERNAL size_t	m0_bitmap_set_nr (const struct m0_bitmap *map)
M0_INTERNAL int	m0_bitmap_onwire_init (struct m0_bitmap_onwire *ow_map, size_t nr)
M0_INTERNAL void	m0_bitmap_onwire_fini (struct m0_bitmap_onwire *ow_map)
M0_INTERNAL void	m0_bitmap_store (const struct m0_bitmap *im_map, struct m0_bitmap_onwire *ow_map)
M0_INTERNAL void	m0_bitmap_load (const struct m0_bitmap_onwire *ow_map, struct m0_bitmap *im_map)
struct m0_bitmap_onwire	M0_XCA_DOMAIN (conf|rpc)
	M0_BASSERT (8==sizeof((struct m0_bitmap *) 0) ->b_words[0])

Detailed Description

Macro Definition Documentation

M0_BITMAP_MASK

#define M0_BITMAP_MASK

(

idx

)

(1UL << ((idx) & (M0_BITMAP_BITS-1)))

Mask off a single bit within a word. Use M0_BITMAP_SHIFT() to select the correct word, then use M0_BITMAP_MASK() to access the individual bit within that word.

Parameters

idx	bit offset into the bitmap

Definition at line 84 of file bitmap.c.

M0_BITMAP_SHIFT

#define M0_BITMAP_SHIFT

(

idx

)

((idx) >> M0_BITMAP_BITSHIFT)

Shift a m0_bitmap bit index to get the word index. Use M0_BITMAP_SHIFT() to select the correct word, then use M0_BITMAP_MASK() to access the individual bit within that word.

Parameters

idx	bit offset into the bitmap

Definition at line 75 of file bitmap.c.

M0_BITMAP_WORDS

#define M0_BITMAP_WORDS

(

nr

)

(((nr) + (M0_BITMAP_BITS-1)) >> M0_BITMAP_BITSHIFT)

Number of words needed to be allocated to store nr bits. This is an allocation macro. For indexing, M0_BITMAP_SHIFT is used.

Parameters

nr	number of bits to be allocated

Definition at line 59 of file bitmap.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Number of bits in a word (m0_bitmap.b_words). And the number of bits to shift to convert bit offset to word index.

Enumerator
M0_BITMAP_BITS
M0_BITMAP_BITSHIFT

Definition at line 41 of file bitmap.c.

Function Documentation

M0_BASSERT() [1/7]

M0_BASSERT

(

M0_BITMAP_BITS

= =(1UL<< M0_BITMAP_BITSHIFT)

)

M0_BASSERT() [2/7]

M0_BASSERT

(

M0_BITMAP_WORDS(0)

= =0

)

M0_BASSERT() [3/7]

M0_BASSERT

(

M0_BITMAP_WORDS(1)

= =1

)

M0_BASSERT() [4/7]

M0_BASSERT

(

M0_BITMAP_WORDS(63)

= =1

)

M0_BASSERT() [5/7]

M0_BASSERT

(

M0_BITMAP_WORDS(64)

= =1

)

M0_BASSERT() [6/7]

M0_BASSERT

(

M0_BITMAP_WORDS(65)

= =2

)

M0_BASSERT() [7/7]

M0_BASSERT

(

8

= =sizeof((struct m0_bitmap *) 0) ->b_words[0]

)

m0_bitmap_copy()

M0_INTERNAL void m0_bitmap_copy	(	struct m0_bitmap *	dst,
		const struct m0_bitmap *	src
	)

Copies the bit values from one bitmap to another.

Parameters

dst	destination bitmap, must already be initialised. If dst is larger than src, bits beyond src->b_nr are cleared in dst.
src	source bitmap

Precondition

dst->b_nr >= src->b_nr

Definition at line 158 of file bitmap.c.

Here is the caller graph for this function:

m0_bitmap_ffs()

M0_INTERNAL int m0_bitmap_ffs

(

const struct m0_bitmap *

map

)

Finds the first non-zero (a.k.a. set, true) bit from a bitmap.

Parameters

map	bitmap to query

Returns

index of the first set bit. If not found, -1 is returned.

Definition at line 112 of file bitmap.c.

Here is the caller graph for this function:

m0_bitmap_ffz()

M0_INTERNAL int m0_bitmap_ffz

(

const struct m0_bitmap *

map

)

Finds the first zero (a.k.a unset, false) bit from a bitmap.

Parameters

map	bitmap to query

Returns

index of the first zero bit. If no zero bit found, -1 is returned.

Definition at line 126 of file bitmap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_bitmap_fini()

M0_INTERNAL void m0_bitmap_fini

(

struct m0_bitmap *

map

)

Finalise the bitmap. All memory associated with the bitmap is released.

Parameters

map	bitmap to finalise

Definition at line 97 of file bitmap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_bitmap_get()

M0_INTERNAL bool m0_bitmap_get	(	const struct m0_bitmap *	map,
		size_t	idx
	)

Get a bit value from a bitmap.

Precondition

idx < map->b_br

Parameters

map	bitmap to query
idx	bit offset in the bitmap to query

Returns

the bit value, true or false.

Definition at line 105 of file bitmap.c.

Here is the caller graph for this function:

m0_bitmap_init()

M0_INTERNAL int m0_bitmap_init	(	struct m0_bitmap *	map,
		size_t	nr
	)

Initialise a bitmap to hold nr bits. The array to store bits is allocated internally.

On success, the bitmap is initialised with all bits initially set to false.

Parameters

map	bitmap object to initialize
nr	size of the bitmap, in bits

Return values

0	success
!0	failure, -errno

Definition at line 86 of file bitmap.c.

Here is the call graph for this function:

m0_bitmap_load()

M0_INTERNAL void m0_bitmap_load	(	const struct m0_bitmap_onwire *	ow_map,
		struct m0_bitmap *	im_map
	)

Converts on-wire bitmap to in-memory bitmap.

Parameters

ow_map	on-wire bitmap object to be converted into in-memory bitmap.
im_map	pre-initialised in-memory bitmap object

Definition at line 213 of file bitmap.c.

Here is the caller graph for this function:

m0_bitmap_onwire_fini()

M0_INTERNAL void m0_bitmap_onwire_fini

(

struct m0_bitmap_onwire *

ow_map

)

Finalise the on-wire bitmap. All memory associated with the on-wire bitmap is released.

Parameters

ow_map

on-wire bitmap to finalise

Definition at line 192 of file bitmap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_bitmap_onwire_init()

M0_INTERNAL int m0_bitmap_onwire_init	(	struct m0_bitmap_onwire *	ow_map,
		size_t	nr
	)

Initialise an on-wire bitmap to hold nr bits. The array to store bits is allocated internally.

On success, the bitmap is initialised with all bits initially set to false.

Parameters

ow_map	on-wire bitmap object to initialise
nr	size of the bitmap, in bits

Return values

0	success
!0	failure, -errno

Definition at line 182 of file bitmap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_bitmap_reset()

M0_INTERNAL void m0_bitmap_reset

(

struct m0_bitmap *

map

)

Reset a bitmap.

Definition at line 149 of file bitmap.c.

Here is the caller graph for this function:

m0_bitmap_set()

M0_INTERNAL void m0_bitmap_set	(	struct m0_bitmap *	map,
		size_t	idx,
		bool	val
	)

Set a bit value in a bitmap.

Parameters

map	bitmap to modify
idx	bit offset to modify. Attempting to set a bit beyond the size of the bitmap results is not allowed (causes and assert to fail).
val	new bit value, true or false

Definition at line 139 of file bitmap.c.

Here is the caller graph for this function:

m0_bitmap_set_nr()

M0_INTERNAL size_t m0_bitmap_set_nr

(

const struct m0_bitmap *

map

)

Returns the number of bits that are 'true'.

Definition at line 172 of file bitmap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_bitmap_store()

M0_INTERNAL void m0_bitmap_store	(	const struct m0_bitmap *	im_map,
		struct m0_bitmap_onwire *	ow_map
	)

Converts in-memory struct m0_bitmap to on-wire struct m0_bitmap_onwire.

Parameters

im_map	in-memory bitmap object to be converted into on-wire bitmap object.
ow_map	pre-initialised on-wire bitmap object

Definition at line 200 of file bitmap.c.

Here is the caller graph for this function:

M0_XCA_DOMAIN()

struct m0_bitmap_onwire M0_XCA_DOMAIN

(

conf|

rpc

)