bitmap.c File Reference

#include "bitmap.h"
#include <debug.h>
#include <limits.h>
#include <round.h>
#include <stdio.h>
#include "threads/malloc.h"

Include dependency graph for bitmap.c:

Go to the source code of this file.

Data Structures
struct	bitmap
	From the outside, a bitmap is an array of bits. More...

Macros
#define	ELEM_BITS   (sizeof (elem_type) * CHAR_BIT)
	Number of bits in an element. More...

Typedefs
typedef unsigned long	elem_type
	Element type. More...

Functions
static size_t	elem_idx (size_t bit_idx)
	Returns the index of the element that contains the bit numbered BIT_IDX. More...
static elem_type	bit_mask (size_t bit_idx)
	Returns an elem_type where only the bit corresponding to BIT_IDX is turned on. More...
static size_t	elem_cnt (size_t bit_cnt)
	Returns the number of elements required for BIT_CNT bits. More...
static size_t	byte_cnt (size_t bit_cnt)
	Returns the number of bytes required for BIT_CNT bits. More...
static elem_type	last_mask (const struct bitmap *b)
	Returns a bit mask in which the bits actually used in the last element of B's bits are set to 1 and the rest are set to 0. More...
struct bitmap *	bitmap_create (size_t bit_cnt)
	Creation and destruction. More...
struct bitmap *	bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
	Creates and returns a bitmap with BIT_CNT bits in the BLOCK_SIZE bytes of storage preallocated at BLOCK. More...
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 *b)
	Destroys bitmap B, freeing its storage. More...
size_t	bitmap_size (const struct bitmap *b)
	Bitmap size. More...
void	bitmap_set (struct bitmap *b, size_t idx, bool value)
	Setting and testing single bits. More...
void	bitmap_mark (struct bitmap *b, size_t bit_idx)
	Atomically sets the bit numbered BIT_IDX in B to true. More...
void	bitmap_reset (struct bitmap *b, size_t bit_idx)
	Atomically sets the bit numbered BIT_IDX in B to false. More...
void	bitmap_flip (struct bitmap *b, size_t bit_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 *b, size_t idx)
	Returns the value of the bit numbered IDX in B. More...
void	bitmap_set_all (struct bitmap *b, bool value)
	Setting and testing multiple bits. More...
void	bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
	Sets the CNT bits starting at START in B to VALUE. More...
size_t	bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
	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 *b, size_t start, size_t cnt, bool value)
	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 *b, 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 *b, 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 *b, 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 *b, size_t start, size_t cnt, bool value)
	Finding set or unset bits. More...
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. More...
void	bitmap_dump (const struct bitmap *b)
	File input and output. More...

Macro Definition Documentation

ELEM_BITS

#define ELEM_BITS   (sizeof (elem_type) * CHAR_BIT)

Number of bits in an element.

Definition at line 22 of file bitmap.c.

Typedef Documentation

elem_type

typedef unsigned long elem_type

Element type.

This must be an unsigned integer type at least as wide as int.

Each bit represents one bit in the bitmap. If bit 0 in an element represents bit K in the bitmap, then bit 1 in the element represents bit K+1 in the bitmap, and so on.

Definition at line 19 of file bitmap.c.

Function Documentation

bit_mask()

static elem_type bit_mask ( size_t  bit_idx )

inlinestatic

Returns an elem_type where only the bit corresponding to BIT_IDX is turned on.

Definition at line 44 of file bitmap.c.

References ELEM_BITS.

Referenced by bitmap_flip(), bitmap_mark(), bitmap_reset(), and bitmap_test().

Here is the caller graph for this function:

bitmap_all()

bool bitmap_all	(	const struct bitmap *	b,
		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 *	b,
		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 *	b,
		size_t	start,
		size_t	cnt,
		bool	value
	)

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 *	b,
		size_t	start,
		size_t	cnt,
		bool	value
	)

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

)

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 *	block,
		size_t block_size	UNUSED
	)

Creates and returns a bitmap with BIT_CNT bits in the BLOCK_SIZE bytes of storage preallocated at BLOCK.

BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT).

Definition at line 100 of file bitmap.c.

References ASSERT, bitmap::bit_cnt, bitmap_buf_size(), bitmap_set_all(), bitmap::bits, and block_size().

Referenced by init_pool().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

< 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 *	b,
		size_t	bit_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 *	b,
		size_t	bit_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 *	b,
		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 *	b,
		size_t	bit_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:

Here is the caller graph for this function:

bitmap_set()

void bitmap_set	(	struct bitmap *	b,
		size_t	idx,
		bool	value
	)

Setting and testing single bits.

Atomically sets the bit numbered IDX in B to VALUE.

Definition at line 145 of file bitmap.c.

References ASSERT, bitmap::bit_cnt, bitmap_mark(), bitmap_reset(), and NULL.

Referenced by bitmap_set_multiple().

Here is the call graph for this function:

Here is the caller graph for this function:

bitmap_set_all()

void bitmap_set_all	(	struct bitmap *	b,
		bool	value
	)

Setting and testing multiple bits.

Sets all bits in B to VALUE.

Definition at line 209 of file bitmap.c.

References ASSERT, bitmap_set_multiple(), bitmap_size(), and NULL.

Referenced by bitmap_create(), and bitmap_create_in_buf().

Here is the call graph for this function:

Here is the caller graph for this function:

bitmap_set_multiple()

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

Sets the CNT bits starting at START in B to VALUE.

Definition at line 218 of file bitmap.c.

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

Referenced by bitmap_scan_and_flip(), bitmap_set_all(), free_map_allocate(), free_map_release(), and palloc_free_multiple().

Here is the call graph for this function:

Here is the caller graph for this function:

bitmap_size()

size_t bitmap_size

(

const struct bitmap *

b

)

Bitmap size.

Returns the number of bits in B.

Definition at line 136 of file bitmap.c.

References bitmap::bit_cnt.

Referenced by bitmap_set_all(), and page_from_pool().

Here is the caller graph for this function:

bitmap_test()

bool bitmap_test	(	const struct bitmap *	b,
		size_t	idx
	)

Returns the value of the bit numbered IDX in B.

Definition at line 198 of file bitmap.c.

References ASSERT, bitmap::bit_cnt, bit_mask(), bitmap::bits, elem_idx(), and NULL.

Referenced by bitmap_contains(), and bitmap_count().

Here is the call graph for this function:

Here is the caller graph for this function:

byte_cnt()

static size_t byte_cnt ( size_t  bit_cnt )

inlinestatic

Returns the number of bytes required for BIT_CNT bits.

Definition at line 58 of file bitmap.c.

References elem_cnt().

Referenced by bitmap_buf_size(), bitmap_create(), bitmap_dump(), and test_main().

Here is the call graph for this function:

Here is the caller graph for this function:

elem_cnt()

static size_t elem_cnt ( size_t  bit_cnt )

inlinestatic

Returns the number of elements required for BIT_CNT bits.

Definition at line 51 of file bitmap.c.

References DIV_ROUND_UP, and ELEM_BITS.

Referenced by byte_cnt().

Here is the caller graph for this function:

elem_idx()

static size_t elem_idx ( size_t  bit_idx )

inlinestatic

Returns the index of the element that contains the bit numbered BIT_IDX.

Definition at line 36 of file bitmap.c.

References ELEM_BITS.

Referenced by bitmap_flip(), bitmap_mark(), bitmap_reset(), and bitmap_test().

Here is the caller graph for this function:

last_mask()

static elem_type last_mask ( const struct bitmap *  b )

inlinestatic

Returns a bit mask in which the bits actually used in the last element of B's bits are set to 1 and the rest are set to 0.

Definition at line 66 of file bitmap.c.

References bitmap::bit_cnt, and ELEM_BITS.