PKUOS - Pintos
Pintos source browser for PKU Operating System course
Macros | Functions
bitmap.h File Reference
#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:

Go to the source code of this file.

Macros

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

Functions

struct bitmapbitmap_create (size_t bit_cnt)
 Bitmap abstract data type. More...
 
struct bitmapbitmap_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 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)

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 b,
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 b,
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 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  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: