pintos/src/lib/kernel/bitmap.c File Reference

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

Go to the source code of this file.

Data Structures

struct bitmap

Defines

#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)

Typedefs

typedef unsigned long elem_type

Functions

static size_t elem_idx (size_t bit_idx)

static elem_type bit_mask (size_t bit_idx)

static size_t elem_cnt (size_t bit_cnt)

static size_t byte_cnt (size_t bit_cnt)

static elem_type last_mask (const struct bitmap *b)

struct bitmap * bitmap_create (size_t bit_cnt)

struct bitmap * bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)

size_t bitmap_buf_size (size_t bit_cnt)

void bitmap_destroy (struct bitmap *b)

size_t bitmap_size (const struct bitmap *b)

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

void bitmap_mark (struct bitmap *b, size_t bit_idx)

void bitmap_reset (struct bitmap *b, size_t bit_idx)

void bitmap_flip (struct bitmap *b, size_t bit_idx)

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

void bitmap_set_all (struct bitmap *b, bool value)

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

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

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

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

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

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

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

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

void bitmap_dump (const struct bitmap *b)

Define Documentation

#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)

Definition at line 22 of file bitmap.c.

Referenced by bit_mask(), elem_cnt(), elem_idx(), and last_mask().

Typedef Documentation

typedef unsigned long elem_type

Definition at line 19 of file bitmap.c.

Function Documentation

static elem_type bit_mask ( size_t bit_idx ) [inline, static]

Definition at line 44 of file bitmap.c.

References ELEM_BITS.

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

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

Definition at line 285 of file bitmap.c.

References bitmap_contains().

Referenced by free_map_release(), and palloc_free_multiple().

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

Definition at line 269 of file bitmap.c.

References bitmap_contains().

size_t bitmap_buf_size ( size_t bit_cnt )

Definition at line 115 of file bitmap.c.

Referenced by bitmap_create_in_buf(), and init_pool().

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

Definition at line 252 of file bitmap.c.

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

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

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

Definition at line 234 of file bitmap.c.

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

struct bitmap* bitmap_create ( size_t bit_cnt ) [read]

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(), uhci_create_info(), and usb_register_host().

struct bitmap* bitmap_create_in_buf	(	size_t	bit_cnt,
		void *	block,
		size_t block_size	UNUSED
	)			`[read]`

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().

void bitmap_destroy ( struct bitmap * b )

Definition at line 124 of file bitmap.c.

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

Referenced by uhci_destroy_info().

void bitmap_dump ( const struct bitmap * b )

Definition at line 368 of file bitmap.c.

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

void bitmap_flip	(	struct bitmap *	b,
		size_t	bit_idx
	)

Definition at line 186 of file bitmap.c.

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

void bitmap_mark	(	struct bitmap *	b,
		size_t	bit_idx
	)

Definition at line 158 of file bitmap.c.

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

Referenced by bitmap_set(), and free_map_init().

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

Definition at line 277 of file bitmap.c.

References bitmap_contains().

void bitmap_reset	(	struct bitmap *	b,
		size_t	bit_idx
	)

Definition at line 171 of file bitmap.c.

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

Referenced by bitmap_set(), qh_free(), and uhci_release_td().

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

Definition at line 297 of file bitmap.c.

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

Referenced by bitmap_scan_and_flip(), and uhci_process_completed().

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

Definition at line 321 of file bitmap.c.

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

Referenced by free_map_allocate(), palloc_get_multiple(), qh_alloc(), uhci_acquire_td(), and usb_setup_dev_addr().

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

Definition at line 146 of file bitmap.c.

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

Referenced by bitmap_set_multiple().

void bitmap_set_all	(	struct bitmap *	b,
		bool	value
	)

Definition at line 210 of file bitmap.c.

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

Referenced by bitmap_create(), and bitmap_create_in_buf().

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

Definition at line 219 of file bitmap.c.

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

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

size_t bitmap_size ( const struct bitmap * b )

Definition at line 137 of file bitmap.c.

References bitmap::bit_cnt.

Referenced by bitmap_set_all(), and page_from_pool().

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

Definition at line 199 of file bitmap.c.

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

Referenced by bitmap_contains(), and bitmap_count().

static size_t byte_cnt ( size_t bit_cnt ) [inline, static]

Definition at line 58 of file bitmap.c.

References elem_cnt().

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

static size_t elem_cnt ( size_t bit_cnt ) [inline, static]

Definition at line 51 of file bitmap.c.

References DIV_ROUND_UP, and ELEM_BITS.

Referenced by byte_cnt().

static size_t elem_idx ( size_t bit_idx ) [inline, static]

Definition at line 36 of file bitmap.c.

References ELEM_BITS.

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

static elem_type last_mask ( const struct bitmap * b ) [inline, static]

Definition at line 66 of file bitmap.c.

References bitmap::bit_cnt, and ELEM_BITS.


Data Structures
struct	bitmap
Defines
#define	ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
Typedefs
typedef unsigned long	elem_type
Functions
static size_t	elem_idx (size_t bit_idx)
static elem_type	bit_mask (size_t bit_idx)
static size_t	elem_cnt (size_t bit_cnt)
static size_t	byte_cnt (size_t bit_cnt)
static elem_type	last_mask (const struct bitmap *b)
struct bitmap *	bitmap_create (size_t bit_cnt)
struct bitmap *	bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
size_t	bitmap_buf_size (size_t bit_cnt)
void	bitmap_destroy (struct bitmap *b)
size_t	bitmap_size (const struct bitmap *b)
void	bitmap_set (struct bitmap *b, size_t idx, bool value)
void	bitmap_mark (struct bitmap *b, size_t bit_idx)
void	bitmap_reset (struct bitmap *b, size_t bit_idx)
void	bitmap_flip (struct bitmap *b, size_t bit_idx)
bool	bitmap_test (const struct bitmap *b, size_t idx)
void	bitmap_set_all (struct bitmap *b, bool value)
void	bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
size_t	bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
bool	bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
bool	bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
bool	bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
bool	bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
size_t	bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
size_t	bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
void	bitmap_dump (const struct bitmap *b)