bitmap

Bitmap datastructure. More...

Macros
#define	BITMAP_BITSIZE   ((int)sizeof(uintptr_t)*8)
	Number of bits in one uintptr_t.

Typedefs
typedef uintptr_t	util_bitmap_t
	The bits are stored in an uintptr_t array.

Functions
int	util_bitmap_find_free (util_bitmap_t *bitmap, int num_bits)
	Find a free index in the given bitmap. More...
static int	util_bitmap_size (int num_bits)
	Computes the size in bytes for num_elements bitmap entries. More...
static void	util_bitmap_init (util_bitmap_t *bitmap, int size)
	Initilizes the given bitmap, marks all bits as free/unused. More...
static void	util_bitmap_clear (util_bitmap_t *bitmap, int size)
	Clears the given bitmap. More...
static int	util_bitmap_is_free (util_bitmap_t *bitmap, int bitidx)
	Checks if the given bitidx is marked as free. More...
static void	util_bitmap_mark_as_free (util_bitmap_t *bitmap, int bitidx)
	Marks a bit in the bitmap as free. More...
static void	util_bitmap_mark_as_used (util_bitmap_t *bitmap, int bitidx)
	Marks a bit in the bitmap as used. More...

Detailed Description

Bitmap datastructure.

Bitmap to store multipe binary states efficiently in a small amount of memory.

Example:

int num_bits = 100;
int idx, size;
util_bitmap_t *bitmap;

// create bitmap
size = util_bitmap_size(num_bits);
bitmap = ua_malloc(size);
if (bitmap == NULL) goto error;
util_bitmap_init(bitmap, size);

// mark 5th bit (index 4) as used
util_bitmap_mark_as_used(bitmap, 4);

// find first free bit
idx = util_bitmap_find_free(bitmap, num_bits);

Function Documentation

static void util_bitmap_clear ( util_bitmap_t *  bitmap, int  size  )

inlinestatic

Clears the given bitmap.

Marks all entries as free, does not free the bitmap memory.

Parameters

bitmap	Pointer to bitmap memory.
size	Size in bytes of bitmap.

int util_bitmap_find_free	(	util_bitmap_t *	bitmap,
		int	num_bits
	)

Find a free index in the given bitmap.

Parameters

bitmap	The bitmap used for searching
num_bits	Total number of bits in the bitmap.

Returns

Bitindex of the first free element or -1 if the bitmap is full.

static void util_bitmap_init ( util_bitmap_t *  bitmap, int  size  )

inlinestatic

Initilizes the given bitmap, marks all bits as free/unused.

Parameters

bitmap	Pointer to bitmap memory.
size	Size in bytes of bitmap.

static int util_bitmap_is_free ( util_bitmap_t *  bitmap, int  bitidx  )

inlinestatic

Checks if the given bitidx is marked as free.

Returns

1 if free, 0 if not free.

static void util_bitmap_mark_as_free ( util_bitmap_t *  bitmap, int  bitidx  )

inlinestatic

Marks a bit in the bitmap as free.

Parameters

bitmap	Pointer to bitmap memory.
bitidx	Index in bits to mark as free.

static void util_bitmap_mark_as_used ( util_bitmap_t *  bitmap, int  bitidx  )

inlinestatic

Marks a bit in the bitmap as used.

Parameters

bitmap	Pointer to bitmap memory.
bitidx	Index in bits to mark as used.

static int util_bitmap_size ( int  num_bits )

inlinestatic

Computes the size in bytes for num_elements bitmap entries.

This can be used by the caller to allocate the correct amount of memory for util_bitmap_init.

Parameters

num_bits

Number of bits to store in the bitmap.

Returns

Size in bytes to be allocated for the bitmap.