#include <stdbool.h>
#include <stddef.h>
#include <inttypes.h>

Include dependency graph for bitmap.h:

This graph shows which files directly or indirectly include this file:

Macros
#define	BITMAP_ERROR SIZE_MAX
	Finding set or unset bits. More...

Functions
struct bitmap *	bitmap_create (size_t bit_cnt)
	Bitmap abstract data type. More...

struct bitmap *	bitmap_create_in_buf (size_t bit_cnt, void *, size_t byte_cnt)

size_t	bitmap_buf_size (size_t bit_cnt)
	Returns the number of bytes required to accomodate a bitmap with BIT_CNT bits (for use with bitmap_create_in_buf()). More...

void	bitmap_destroy (struct bitmap *)
	Destroys bitmap B, freeing its storage. More...

size_t	bitmap_size (const struct bitmap *)
	Bitmap size. More...

void	bitmap_set (struct bitmap *, size_t idx, bool)
	Setting and testing single bits. More...

void	bitmap_mark (struct bitmap *, size_t idx)
	Atomically sets the bit numbered BIT_IDX in B to true. More...

void	bitmap_reset (struct bitmap *, size_t idx)
	Atomically sets the bit numbered BIT_IDX in B to false. More...

void	bitmap_flip (struct bitmap *, size_t idx)
	Atomically toggles the bit numbered IDX in B; that is, if it is true, makes it false, and if it is false, makes it true. More...

bool	bitmap_test (const struct bitmap *, size_t idx)
	Returns the value of the bit numbered IDX in B. More...

void	bitmap_set_all (struct bitmap *, bool)
	Setting and testing multiple bits. More...

void	bitmap_set_multiple (struct bitmap *, size_t start, size_t cnt, bool)
	Sets the CNT bits starting at START in B to VALUE. More...

size_t	bitmap_count (const struct bitmap *, size_t start, size_t cnt, bool)
	Returns the number of bits in B between START and START + CNT, exclusive, that are set to VALUE. More...

bool	bitmap_contains (const struct bitmap *, size_t start, size_t cnt, bool)
	Returns true if any bits in B between START and START + CNT, exclusive, are set to VALUE, and false otherwise. More...

bool	bitmap_any (const struct bitmap *, size_t start, size_t cnt)
	Returns true if any bits in B between START and START + CNT, exclusive, are set to true, and false otherwise. More...

bool	bitmap_none (const struct bitmap *, size_t start, size_t cnt)
	Returns true if no bits in B between START and START + CNT, exclusive, are set to true, and false otherwise. More...

bool	bitmap_all (const struct bitmap *, size_t start, size_t cnt)
	Returns true if every bit in B between START and START + CNT, exclusive, is set to true, and false otherwise. More...

size_t	bitmap_scan (const struct bitmap *, size_t start, size_t cnt, bool)
	Finding set or unset bits. More...

size_t	bitmap_scan_and_flip (struct bitmap *, size_t start, size_t cnt, bool)
	Finds the first group of CNT consecutive bits in B at or after START that are all set to VALUE, flips them all to !VALUE, and returns the index of the first bit in the group. More...

void	bitmap_dump (const struct bitmap *)
	File input and output. More...

Macro Definition Documentation

◆ BITMAP_ERROR

#define BITMAP_ERROR SIZE_MAX

Finding set or unset bits.

Definition at line 36 of file bitmap.h.

Function Documentation

◆ bitmap_all()

bool bitmap_all	(	const struct bitmap *	,
		size_t	start,
		size_t	cnt
	)

Returns true if every bit in B between START and START + CNT, exclusive, is set to true, and false otherwise.

Definition at line 284 of file bitmap.c.

References bitmap_contains(), and start.

Referenced by free_map_release(), and palloc_free_multiple().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitmap_any()

bool bitmap_any	(	const struct bitmap *	,
		size_t	start,
		size_t	cnt
	)

Returns true if any bits in B between START and START + CNT, exclusive, are set to true, and false otherwise.

Definition at line 268 of file bitmap.c.

References bitmap_contains(), and start.

Here is the call graph for this function:

◆ bitmap_buf_size()

size_t bitmap_buf_size ( size_t bit_cnt )

Returns the number of bytes required to accomodate a bitmap with BIT_CNT bits (for use with bitmap_create_in_buf()).

Definition at line 115 of file bitmap.c.

References bitmap::bit_cnt, and byte_cnt().

Referenced by bitmap_create_in_buf(), and init_pool().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitmap_contains()

bool bitmap_contains	(	const struct bitmap *	,
		size_t	start,
		size_t	cnt,
		bool
	)

Returns true if any bits in B between START and START + CNT, exclusive, are set to VALUE, and false otherwise.

Definition at line 251 of file bitmap.c.

References ASSERT, bitmap::bit_cnt, bitmap_test(), NULL, and start.

Referenced by bitmap_all(), bitmap_any(), bitmap_none(), and bitmap_scan().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitmap_count()

size_t bitmap_count	(	const struct bitmap *	,
		size_t	start,
		size_t	cnt,
		bool
	)

Returns the number of bits in B between START and START + CNT, exclusive, that are set to VALUE.

Definition at line 233 of file bitmap.c.

References ASSERT, bitmap::bit_cnt, bitmap_test(), NULL, and start.

Here is the call graph for this function:

◆ bitmap_create()

struct bitmap* bitmap_create ( size_t bit_cnt )

Bitmap abstract data type.

Creation and destruction.

Bitmap abstract data type.

Creates and returns a pointer to a newly allocated bitmap with room for BIT_CNT (or more) bits. Returns a null pointer if memory allocation fails. The caller is responsible for freeing the bitmap, with bitmap_destroy(), when it is no longer needed.

Definition at line 79 of file bitmap.c.

References bitmap::bit_cnt, bitmap_set_all(), bitmap::bits, byte_cnt(), free(), malloc(), and NULL.

Referenced by free_map_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitmap_create_in_buf()

struct bitmap* bitmap_create_in_buf	(	size_t	bit_cnt,
		void *	,
		size_t	byte_cnt
	)

◆ bitmap_destroy()

void bitmap_destroy ( struct bitmap * b )

Destroys bitmap B, freeing its storage.

Not for use on bitmaps created by bitmap_create_in_buf().

Definition at line 123 of file bitmap.c.

References bitmap::bits, free(), and NULL.

Here is the call graph for this function:

◆ bitmap_dump()

void bitmap_dump ( const struct bitmap * b )

File input and output.

Debugging. lib/kernel/bitmap.h

< FILESYS Debugging. Dumps the contents of B to the console as hexadecimal.

Definition at line 367 of file bitmap.c.

References bitmap::bit_cnt, bitmap::bits, byte_cnt(), and hex_dump().

Here is the call graph for this function:

◆ bitmap_flip()

void bitmap_flip	(	struct bitmap *	,
		size_t	idx
	)

Atomically toggles the bit numbered IDX in B; that is, if it is true, makes it false, and if it is false, makes it true.

Definition at line 185 of file bitmap.c.

References bit_mask(), bitmap::bits, and elem_idx().

Here is the call graph for this function:

◆ bitmap_mark()

void bitmap_mark	(	struct bitmap *	,
		size_t	idx
	)

Atomically sets the bit numbered BIT_IDX in B to true.

Definition at line 157 of file bitmap.c.

References bit_mask(), bitmap::bits, and elem_idx().

Referenced by bitmap_set(), and free_map_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitmap_none()

bool bitmap_none	(	const struct bitmap *	,
		size_t	start,
		size_t	cnt
	)

Returns true if no bits in B between START and START + CNT, exclusive, are set to true, and false otherwise.

Definition at line 276 of file bitmap.c.

References bitmap_contains(), and start.

Here is the call graph for this function:

◆ bitmap_reset()

void bitmap_reset	(	struct bitmap *	,
		size_t	idx
	)

Atomically sets the bit numbered BIT_IDX in B to false.

Definition at line 170 of file bitmap.c.

References bit_mask(), bitmap::bits, and elem_idx().

Referenced by bitmap_set().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitmap_scan()

size_t bitmap_scan	(	const struct bitmap *	b,
		size_t	start,
		size_t	cnt,
		bool	value
	)

Finding set or unset bits.

Finds and returns the starting index of the first group of CNT consecutive bits in B at or after START that are all set to VALUE. If there is no such group, returns BITMAP_ERROR.

Definition at line 296 of file bitmap.c.

References ASSERT, bitmap::bit_cnt, bitmap_contains(), BITMAP_ERROR, NULL, and start.

Referenced by bitmap_scan_and_flip().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitmap_scan_and_flip()

size_t bitmap_scan_and_flip	(	struct bitmap *	b,
		size_t	start,
		size_t	cnt,
		bool	value
	)

Finds the first group of CNT consecutive bits in B at or after START that are all set to VALUE, flips them all to !VALUE, and returns the index of the first bit in the group.

If there is no such group, returns BITMAP_ERROR. If CNT is zero, returns 0. Bits are set atomically, but testing bits is not atomic with setting them.

Definition at line 320 of file bitmap.c.

References BITMAP_ERROR, bitmap_scan(), bitmap_set_multiple(), and start.

Referenced by free_map_allocate(), and palloc_get_multiple().

Here is the call graph for this function: