Bitmap

A bitmap optimized using 64-bit words. More...

Collaboration diagram for Bitmap:

Detailed Description

A bitmap optimized using 64-bit words.

Data Structures
struct	bitmap_t
	Bitmap structure. More...

Macros
#define	BITMAP_BITS_TO_QWORDS(bits)   (((bits) + 63) / 64)
	Convert number of bits to number of qwords.
#define	BITMAP_BITS_TO_BYTES(bits)   (BITMAP_BITS_TO_QWORDS(bits) * sizeof(uint64_t))
	Convert number of bits to number of bytes.
#define	BITMAP_QWORDS_TO_BITS(qwords)   ((qwords) * 64)
	Convert number of qwords to number of bits.
#define	BITMAP_FOR_EACH_SET(idx, map)
	Iterate over each set bit in the bitmap.
#define	BITMAP_CREATE(name, bits)
	Define and create a bitmap and its buffer.
#define	BITMAP_CREATE_ZERO(name, bits)
	Define and create a zero-initialized bitmap and its buffer.
#define	BITMAP_DEFINE(name, bits)
	Define a bitmap and its buffer.
#define	BITMAP_DEFINE_INIT(name, bits)   bitmap_init(&(name), name##Buffer, bits);
	Initialize a bitmap defined with BITMAP_DEFINE.

Functions
void	bitmap_init (bitmap_t *map, void *buffer, uint64_t length)
	Initialize a bitmap.
bool	bitmap_is_set (bitmap_t *map, uint64_t idx)
	Check if a bit is set in the bitmap.
void	bitmap_set (bitmap_t *map, uint64_t index)
	Set a bit in the bitmap.
void	bitmap_set_range (bitmap_t *map, uint64_t low, uint64_t high)
	Set a range of bits in the bitmap.
void	bitmap_clear (bitmap_t *map, uint64_t index)
	Clear a bit in the bitmap.
void	bitmap_clear_range (bitmap_t *map, uint64_t low, uint64_t high)
	Clear a range of bits in the bitmap.
uint64_t	bitmap_find_first_clear (bitmap_t *map, uint64_t startIdx, uint64_t endIdx)
	Find the first clear bit in the bitmap.
uint64_t	bitmap_find_first_set (bitmap_t *map, uint64_t startIdx, uint64_t endIdx)
	Find the first set bit in the bitmap.
uint64_t	bitmap_find_clear_region_and_set (bitmap_t *map, uint64_t minIdx, uintptr_t maxIdx, uint64_t length, uint64_t alignment)
	Find a clear region of specified length and alignment, and set it.

Macro Definition Documentation

BITMAP_BITS_TO_QWORDS

#define BITMAP_BITS_TO_QWORDS

(

bits

)

(((bits) + 63) / 64)

Convert number of bits to number of qwords.

Parameters

bits	Number of bits.

Returns

Number of qwords.

Definition at line 34 of file bitmap.h.

BITMAP_BITS_TO_BYTES

#define BITMAP_BITS_TO_BYTES

(

bits

)

(BITMAP_BITS_TO_QWORDS(bits) * sizeof(uint64_t))

Convert number of bits to number of bytes.

Parameters

bits	Number of bits.

Returns

Number of bytes.

Definition at line 42 of file bitmap.h.

BITMAP_QWORDS_TO_BITS

#define BITMAP_QWORDS_TO_BITS

(

qwords

)

((qwords) * 64)

Convert number of qwords to number of bits.

Parameters

qwords

Number of qwords.

Returns

Number of bits.

Definition at line 50 of file bitmap.h.

BITMAP_FOR_EACH_SET

#define BITMAP_FOR_EACH_SET	(		idx,
			map
	)

Value:

    for (uint64_t qwordIdx = 0; qwordIdx < BITMAP_BITS_TO_QWORDS((map)->length); qwordIdx++) \
        for (uint64_t tempQword = (map)->buffer[qwordIdx]; tempQword != 0; tempQword &= (tempQword - 1)) \
            if (({ \
                    uint64_t bit = __builtin_ctzll(tempQword); \
                    *(idx) = qwordIdx * 64 + bit; \
                    *(idx) < (map)->length; \
                }))

Iterate over each set bit in the bitmap.

Parameters

idx	Pointer to store the current index.
map	The bitmap.

Definition at line 58 of file bitmap.h.

BITMAP_CREATE

#define BITMAP_CREATE	(		name,
			bits
	)

Value:

    uint64_t name##Buffer[BITMAP_BITS_TO_QWORDS(bits)]; \
    bitmap_t name = {.firstZeroIdx = 0, .length = (bits), .buffer = name##Buffer}

Define and create a bitmap and its buffer.

Parameters

name	Name of the bitmap.
bits	Length of the bitmap in bits.

Definition at line 73 of file bitmap.h.

BITMAP_CREATE_ZERO

#define BITMAP_CREATE_ZERO	(		name,
			bits
	)

Value:

    uint64_t name##Buffer[BITMAP_BITS_TO_QWORDS(bits)] = {0}; \
    bitmap_t name = {.firstZeroIdx = 0, .length = (bits), .buffer = name##Buffer}

Define and create a zero-initialized bitmap and its buffer.

Parameters

name	Name of the bitmap.
bits	Length of the bitmap in bits.

Definition at line 83 of file bitmap.h.

BITMAP_DEFINE

#define BITMAP_DEFINE	(		name,
			bits
	)

Value:

    uint64_t name##Buffer[BITMAP_BITS_TO_QWORDS(bits)]; \
    bitmap_t name

Define a bitmap and its buffer.

Will not initialize the bitmap, use BITMAP_DEFINE_INIT to initialize it.

Intended to be used for struct members.

Parameters

name	Name of the bitmap.
bits	Length of the bitmap in bits.

Definition at line 97 of file bitmap.h.

BITMAP_DEFINE_INIT

#define BITMAP_DEFINE_INIT	(		name,
			bits
	)		bitmap_init(&(name), name##Buffer, bits);

Initialize a bitmap defined with BITMAP_DEFINE.

Parameters

name	Name of the bitmap.
bits	Length of the bitmap in bits.

Definition at line 107 of file bitmap.h.

Function Documentation

bitmap_init()

void bitmap_init	(	bitmap_t *	map,
		void *	buffer,
		uint64_t	length
	)

Initialize a bitmap.

Parameters

map	The bitmap.
buffer	Pointer to the buffer, must be a multiple of 8 bytes.
length	Length of the bitmap in bits.

Definition at line 3 of file bitmap_init.c.

Here is the caller graph for this function:

bitmap_is_set()

bool bitmap_is_set	(	bitmap_t *	map,
		uint64_t	idx
	)

Check if a bit is set in the bitmap.

Parameters

map	The bitmap.
idx	Index of the bit to check.

Returns

true if the bit is set, false otherwise.

Definition at line 3 of file bitmap_is_set.c.

Here is the caller graph for this function:

bitmap_set()

void bitmap_set	(	bitmap_t *	map,
		uint64_t	index
	)

Set a bit in the bitmap.

Parameters

map	Pointer to the bitmap.
index	Index of the bit to set.

Definition at line 3 of file bitmap_set.c.

Here is the caller graph for this function:

bitmap_set_range()

void bitmap_set_range	(	bitmap_t *	map,
		uint64_t	low,
		uint64_t	high
	)

Set a range of bits in the bitmap.

Parameters

map	Pointer to the bitmap.
low	Low index of the range (inclusive).
high	High index of the range (exclusive).

Definition at line 3 of file bitmap_set_range.c.

Here is the caller graph for this function:

bitmap_clear()

void bitmap_clear	(	bitmap_t *	map,
		uint64_t	index
	)

Clear a bit in the bitmap.

Parameters

map	Pointer to the bitmap.
index	Index of the bit to clear.

Definition at line 3 of file bitmap_clear.c.

Here is the caller graph for this function:

bitmap_clear_range()

void bitmap_clear_range	(	bitmap_t *	map,
		uint64_t	low,
		uint64_t	high
	)

Clear a range of bits in the bitmap.

Parameters

map	Pointer to the bitmap.
low	Low index of the range (inclusive).
high	High index of the range (exclusive).

Definition at line 3 of file bitmap_clear_range.c.

Here is the caller graph for this function:

bitmap_find_first_clear()

uint64_t bitmap_find_first_clear	(	bitmap_t *	map,
		uint64_t	startIdx,
		uint64_t	endIdx
	)

Find the first clear bit in the bitmap.

Parameters

map	The bitmap.
startIdx	Index to start searching from.
endIdx	Index to stop searching at (exclusive).

Returns

Index of the first clear bit, or map->length if none found.

Definition at line 3 of file bitmap_find_first_clear.c.

Here is the caller graph for this function:

bitmap_find_first_set()

uint64_t bitmap_find_first_set	(	bitmap_t *	map,
		uint64_t	startIdx,
		uint64_t	endIdx
	)

Find the first set bit in the bitmap.

Parameters

map	The bitmap.
startIdx	Index to start searching from.
endIdx	Index to stop searching at (exclusive).

Returns

Index of the first set bit, or map->length if none found.

Definition at line 3 of file bitmap_find_first_set.c.

Here is the caller graph for this function:

bitmap_find_clear_region_and_set()

uint64_t bitmap_find_clear_region_and_set	(	bitmap_t *	map,
		uint64_t	minIdx,
		uintptr_t	maxIdx,
		uint64_t	length,
		uint64_t	alignment
	)

Find a clear region of specified length and alignment, and set it.

Parameters

map	Pointer to the bitmap.
minIdx	Minimum index to start searching from.
maxIdx	Maximum index to search up to.
length	Length of the region to find.
alignment	Alignment of the region.

Returns

Starting index of the found region, or map->length if not found.

Definition at line 3 of file bitmap_find_clear_region_and_set.c.

Here is the call graph for this function:

Here is the caller graph for this function: