PKUOS - Pintos
Pintos source browser for PKU Operating System course
Data Structures | Macros | Typedefs | Functions
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 bitmapbitmap_create (size_t bit_cnt)
 Creation and destruction. More...
 
struct bitmapbitmap_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.