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_CREATE_ONE(name, bits)
	Define and create a one-initialized bitmap and its buffer.
#define	BITMAP_DEFINE(name, bits)
	Define a bitmap and its buffer.
#define	BITMAP_DEFINE_INIT(name, bits)
	Initialize a bitmap defined with BITMAP_DEFINE.

Functions
static void	bitmap_init (bitmap_t *map, void *buffer, uint64_t length)
	Initialize a bitmap.
static bool	bitmap_is_empty (bitmap_t *map)
	Check if the bitmap is empty (all bits clear).
static bool	bitmap_is_set (bitmap_t *map, uint64_t idx)
	Check if a bit is set in the bitmap.
static void	bitmap_set (bitmap_t *map, uint64_t index)
	Set a bit in the bitmap.
static void	bitmap_set_range (bitmap_t *map, uint64_t low, uint64_t high)
	Set a range of bits in the bitmap.
static void	bitmap_clear (bitmap_t *map, uint64_t index)
	Clear a bit in the bitmap.
static void	bitmap_clear_range (bitmap_t *map, uint64_t low, uint64_t high)
	Clear a range of bits in the bitmap.
static uint64_t	bitmap_find_first_clear (bitmap_t *map, uint64_t startIdx, uint64_t endIdx)
	Find the first clear bit in the bitmap.
static uint64_t	bitmap_find_first_set (bitmap_t *map, uint64_t startIdx, uint64_t endIdx)
	Find the first set bit in the bitmap.
static 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_CREATE_ONE

#define BITMAP_CREATE_ONE	(		name,
			bits
	)

Value:

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

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

Parameters

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

Definition at line 93 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 107 of file bitmap.h.

BITMAP_DEFINE_INIT

#define BITMAP_DEFINE_INIT	(		name,
			bits
	)

Value:

    bitmap_init(&(name), name##Buffer, bits); \
    memset(name##Buffer, 0, BITMAP_BITS_TO_BYTES(bits))

Initialize a bitmap defined with BITMAP_DEFINE.

Parameters

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

Definition at line 117 of file bitmap.h.

Function Documentation

bitmap_init()

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

inlinestatic

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

bitmap_is_empty()

static bool bitmap_is_empty ( bitmap_t *  map )

inlinestatic

Check if the bitmap is empty (all bits clear).

Parameters

map	The bitmap.

Returns

true if the bitmap is empty, false otherwise.

Definition at line 141 of file bitmap.h.

Here is the caller graph for this function:

bitmap_is_set()

static bool bitmap_is_set ( bitmap_t *  map, uint64_t  idx  )

inlinestatic

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

Here is the caller graph for this function:

bitmap_set()

static void bitmap_set ( bitmap_t *  map, uint64_t  index  )

inlinestatic

Set a bit in the bitmap.

Parameters

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

Definition at line 190 of file bitmap.h.

Here is the caller graph for this function:

bitmap_set_range()

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

inlinestatic

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

Here is the caller graph for this function:

bitmap_clear()

static void bitmap_clear ( bitmap_t *  map, uint64_t  index  )

inlinestatic

Clear a bit in the bitmap.

Parameters

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

Definition at line 244 of file bitmap.h.

Here is the caller graph for this function:

bitmap_clear_range()

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

inlinestatic

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

Here is the caller graph for this function:

bitmap_find_first_clear()

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

inlinestatic

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

Here is the caller graph for this function:

bitmap_find_first_set()

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

inlinestatic

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

Here is the caller graph for this function:

bitmap_find_clear_region_and_set()

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

inlinestatic

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

Here is the call graph for this function:

Here is the caller graph for this function: