Bitmap

Detailed Description

Macros
#define	REDUCT_BITMAP_WIDTH   64
	The number of bits in a bitmap word.
#define	REDUCT_BITMAP_INDEX_NONE   (~(uint64_t)0)
	Invalid bitmap index.
#define	REDUCT_BITMAP_SIZE(_size)   (((_size) + (REDUCT_BITMAP_WIDTH - 1)) / REDUCT_BITMAP_WIDTH)
	Calculate the number of 64-bit words needed for a bitmap of a given size.
#define	REDUCT_BITMAP_SET(_bitmap, _bit)    ((_bitmap)[(_bit) / REDUCT_BITMAP_WIDTH] |= (1ULL << ((_bit) % REDUCT_BITMAP_WIDTH)))
	Set a bit in a bitmap.
#define	REDUCT_BITMAP_CLEAR(_bitmap, _bit)    ((_bitmap)[(_bit) / REDUCT_BITMAP_WIDTH] &= ~(1ULL << ((_bit) % REDUCT_BITMAP_WIDTH)))
	Clear a bit in a bitmap.
#define	REDUCT_BITMAP_TEST(_bitmap, _bit)    (((_bitmap)[(_bit) / REDUCT_BITMAP_WIDTH] & (1ULL << ((_bit) % REDUCT_BITMAP_WIDTH))) != 0)
	Check if a bit is set in a bitmap.

Typedefs
typedef uint64_t	reduct_bitmap_t
	A single word in a bitmap.

Functions
static size_t	reduct_bitmap_set_range (reduct_bitmap_t *bitmap, size_t start, size_t count)
	Set a range of bits in a bitmap.
static size_t	reduct_bitmap_find_first_clear (const reduct_bitmap_t *bitmap, size_t size)
	Find the first clear bit in a bitmap.
static size_t	reduct_bitmap_next_set (const reduct_bitmap_t *bitmap, size_t size, size_t start)
	Find the next set bit in a bitmap starting from a given index.
static size_t	reduct_bitmap_next_clear (const reduct_bitmap_t *bitmap, size_t size, size_t start)
	Find the next clear bit in a bitmap starting from a given index.
static size_t	reduct_bitmap_find_last_set (const reduct_bitmap_t *bitmap, size_t size)
	Find the last set bit in a bitmap.

Macro Definition Documentation

REDUCT_BITMAP_WIDTH

#define REDUCT_BITMAP_WIDTH   64

The number of bits in a bitmap word.

Definition at line 16 of file bitmap.h.

REDUCT_BITMAP_INDEX_NONE

#define REDUCT_BITMAP_INDEX_NONE   (~(uint64_t)0)

Invalid bitmap index.

Definition at line 18 of file bitmap.h.

REDUCT_BITMAP_SIZE

#define REDUCT_BITMAP_SIZE

(

_size

)

(((_size) + (REDUCT_BITMAP_WIDTH - 1)) / REDUCT_BITMAP_WIDTH)

Calculate the number of 64-bit words needed for a bitmap of a given size.

Parameters

_size

The number of bits.

Definition at line 25 of file bitmap.h.

REDUCT_BITMAP_SET

#define REDUCT_BITMAP_SET	(		_bitmap,
			_bit
	)		((_bitmap)[(_bit) / REDUCT_BITMAP_WIDTH] |= (1ULL << ((_bit) % REDUCT_BITMAP_WIDTH)))

Set a bit in a bitmap.

Parameters

_bitmap	The bitmap array.
_bit	The bit index to set.

Definition at line 33 of file bitmap.h.

REDUCT_BITMAP_CLEAR

#define REDUCT_BITMAP_CLEAR	(		_bitmap,
			_bit
	)		((_bitmap)[(_bit) / REDUCT_BITMAP_WIDTH] &= ~(1ULL << ((_bit) % REDUCT_BITMAP_WIDTH)))

Clear a bit in a bitmap.

Parameters

_bitmap	The bitmap array.
_bit	The bit index to clear.

Definition at line 42 of file bitmap.h.

REDUCT_BITMAP_TEST

#define REDUCT_BITMAP_TEST	(		_bitmap,
			_bit
	)		(((_bitmap)[(_bit) / REDUCT_BITMAP_WIDTH] & (1ULL << ((_bit) % REDUCT_BITMAP_WIDTH))) != 0)

Check if a bit is set in a bitmap.

Parameters

_bitmap	The bitmap array.
_bit	The bit index to check.

Returns

Non-zero if the bit is set, zero otherwise.

Definition at line 52 of file bitmap.h.

Typedef Documentation

reduct_bitmap_t

typedef uint64_t reduct_bitmap_t

A single word in a bitmap.

Definition at line 14 of file bitmap.h.

Function Documentation

reduct_bitmap_set_range()

static size_t reduct_bitmap_set_range ( reduct_bitmap_t *  bitmap, size_t  start, size_t  count  )

inlinestatic

Set a range of bits in a bitmap.

Parameters

bitmap	The bitmap array.
start	The starting bit index to set.
count	The number of bits to set.

Returns

The starting bit index that was set.

Definition at line 63 of file bitmap.h.

reduct_bitmap_find_first_clear()

static size_t reduct_bitmap_find_first_clear ( const reduct_bitmap_t *  bitmap, size_t  size  )

inlinestatic

Find the first clear bit in a bitmap.

Parameters

bitmap	The bitmap array.
size	The number of words in the bitmap array.

Returns

The index of the first clear bit, or REDUCT_BITMAP_INDEX_NONE if all bits are set.

Definition at line 79 of file bitmap.h.

reduct_bitmap_next_set()

static size_t reduct_bitmap_next_set ( const reduct_bitmap_t *  bitmap, size_t  size, size_t  start  )

inlinestatic

Find the next set bit in a bitmap starting from a given index.

Parameters

bitmap	The bitmap array.
size	The number of words in the bitmap array.
start	The bit index to start searching from.

Returns

The index of the next set bit, or REDUCT_BITMAP_INDEX_NONE if no more bits are set.

Definition at line 105 of file bitmap.h.

reduct_bitmap_next_clear()

static size_t reduct_bitmap_next_clear ( const reduct_bitmap_t *  bitmap, size_t  size, size_t  start  )

inlinestatic

Find the next clear bit in a bitmap starting from a given index.

Parameters

bitmap	The bitmap array.
size	The number of words in the bitmap array.
start	The bit index to start searching from.

Returns

The index of the next clear bit, or REDUCT_BITMAP_INDEX_NONE if no more bits are clear.

Definition at line 152 of file bitmap.h.

reduct_bitmap_find_last_set()

static size_t reduct_bitmap_find_last_set ( const reduct_bitmap_t *  bitmap, size_t  size  )

inlinestatic

Find the last set bit in a bitmap.

Parameters

bitmap	The bitmap array.
size	The number of words in the bitmap array.

Returns

The index of the last set bit, or REDUCT_BITMAP_INDEX_NONE if all bits are clear.

Definition at line 198 of file bitmap.h.