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:

Classes
struct	bitmap

Macros
#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)

Macro Definition Documentation

ELEM_BITS

#define ELEM_BITS   (sizeof (elem_type) * CHAR_BIT)

Typedef Documentation

elem_type

typedef unsigned long elem_type

Function Documentation

bit_mask()

static elem_type bit_mask ( size_t  bit_idx )

inlinestatic

                          {
    return (elem_type) 1 << (bit_idx % ELEM_BITS);
}

Here is the caller graph for this function:

bitmap_all()

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

                                                              {
    return !bitmap_contains (b, start, cnt, false);
}

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
	)

                                                              {
    return bitmap_contains (b, start, cnt, true);
}

Here is the call graph for this function:

bitmap_buf_size()

size_t bitmap_buf_size

(

size_t

bit_cnt

)

                                 {
    return sizeof (struct bitmap) + byte_cnt (bit_cnt);
}

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
	)

                                                                               {
    size_t i;
 
    ASSERT (b != NULL);
    ASSERT (start <= b->bit_cnt);
    ASSERT (start + cnt <= b->bit_cnt);
 
    for (i = 0; i < cnt; i++)
        if (bitmap_test (b, start + i) == value)
            return true;
    return false;
}

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
	)

                                                                            {
    size_t i, value_cnt;
 
    ASSERT (b != NULL);
    ASSERT (start <= b->bit_cnt);
    ASSERT (start + cnt <= b->bit_cnt);
 
    value_cnt = 0;
    for (i = 0; i < cnt; i++)
        if (bitmap_test (b, start + i) == value)
            value_cnt++;
    return value_cnt;
}

Here is the call graph for this function:

bitmap_create()

struct bitmap * bitmap_create

(

size_t

bit_cnt

)

                               {
    struct bitmap *b = malloc (sizeof *b);
    if (b != NULL) {
        b->bit_cnt = bit_cnt;
        b->bits = malloc (byte_cnt (bit_cnt));
        if (b->bits != NULL || bit_cnt == 0) {
            bitmap_set_all (b, false);
            return b;
        }
        free (b);
    }
    return NULL;
}

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
	)

                                                                             {
    struct bitmap *b = block;
 
    ASSERT (block_size >= bitmap_buf_size (bit_cnt));
 
    b->bit_cnt = bit_cnt;
    b->bits = (elem_type *) (b + 1);
    bitmap_set_all (b, false);
    return b;
}

Here is the call graph for this function:

bitmap_destroy()

void bitmap_destroy

(

struct bitmap *

b

)

                                  {
    if (b != NULL) {
        free (b->bits);
        free (b);
    }
}

Here is the call graph for this function:

bitmap_dump()

void bitmap_dump

(

const struct bitmap *

b

)

                                     {
    hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
}

Here is the call graph for this function:

bitmap_flip()

void bitmap_flip	(	struct bitmap *	b,
		size_t	bit_idx
	)

                                               {
    size_t idx = elem_idx (bit_idx);
    elem_type mask = bit_mask (bit_idx);
 
    /* This is equivalent to `b->bits[idx] ^= mask' except that it
       is guaranteed to be atomic on a uniprocessor machine.  See
       the description of the XOR instruction in [IA32-v2b]. */
    asm ("lock xorq %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}

Here is the call graph for this function:

bitmap_mark()

void bitmap_mark	(	struct bitmap *	b,
		size_t	bit_idx
	)

                                               {
    size_t idx = elem_idx (bit_idx);
    elem_type mask = bit_mask (bit_idx);
 
    /* This is equivalent to `b->bits[idx] |= mask' except that it
       is guaranteed to be atomic on a uniprocessor machine.  See
       the description of the OR instruction in [IA32-v2b]. */
    asm ("lock orq %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}

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
	)

                                                               {
    return !bitmap_contains (b, start, cnt, true);
}

Here is the call graph for this function:

bitmap_reset()

void bitmap_reset	(	struct bitmap *	b,
		size_t	bit_idx
	)

                                                {
    size_t idx = elem_idx (bit_idx);
    elem_type mask = bit_mask (bit_idx);
 
    /* This is equivalent to `b->bits[idx] &= ~mask' except that it
       is guaranteed to be atomic on a uniprocessor machine.  See
       the description of the AND instruction in [IA32-v2a]. */
    asm ("lock andq %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
}

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
	)

                                                                           {
    ASSERT (b != NULL);
    ASSERT (start <= b->bit_cnt);
 
    if (cnt <= b->bit_cnt) {
        size_t last = b->bit_cnt - cnt;
        size_t i;
        for (i = start; i <= last; i++)
            if (!bitmap_contains (b, i, cnt, !value))
                return i;
    }
    return BITMAP_ERROR;
}

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
	)

                                                                              {
    size_t idx = bitmap_scan (b, start, cnt, value);
    if (idx != BITMAP_ERROR)
        bitmap_set_multiple (b, idx, cnt, !value);
    return idx;
}

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
	)

                                                      {
    ASSERT (b != NULL);
    ASSERT (idx < b->bit_cnt);
    if (value)
        bitmap_mark (b, idx);
    else
        bitmap_reset (b, idx);
}

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
	)

                                              {
    ASSERT (b != NULL);
 
    bitmap_set_multiple (b, 0, bitmap_size (b), value);
}

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
	)

                                                                             {
    size_t i;
 
    ASSERT (b != NULL);
    ASSERT (start <= b->bit_cnt);
    ASSERT (start + cnt <= b->bit_cnt);
 
    for (i = 0; i < cnt; i++)
        bitmap_set (b, start + i, value);
}

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

)

                                     {
    return b->bit_cnt;
}

Here is the caller graph for this function:

bitmap_test()

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

                                                 {
    ASSERT (b != NULL);
    ASSERT (idx < b->bit_cnt);
    return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
}

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

                          {
    return sizeof (elem_type) * elem_cnt (bit_cnt);
}

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

                          {
    return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
}

Here is the caller graph for this function:

elem_idx()

static size_t elem_idx ( size_t  bit_idx )

inlinestatic

                          {
    return bit_idx / ELEM_BITS;
}

Here is the caller graph for this function:

last_mask()

static elem_type last_mask ( const struct bitmap *  b )

inlinestatic

                                   {
    int last_bits = b->bit_cnt % ELEM_BITS;
    return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
}