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

Functions
struct bitmap *	bitmap_create (size_t bit_cnt)
struct bitmap *	bitmap_create_in_buf (size_t bit_cnt, void *, size_t byte_cnt)
size_t	bitmap_buf_size (size_t bit_cnt)
void	bitmap_destroy (struct bitmap *)
size_t	bitmap_size (const struct bitmap *)
void	bitmap_set (struct bitmap *, size_t idx, bool)
void	bitmap_mark (struct bitmap *, size_t idx)
void	bitmap_reset (struct bitmap *, size_t idx)
void	bitmap_flip (struct bitmap *, size_t idx)
bool	bitmap_test (const struct bitmap *, size_t idx)
void	bitmap_set_all (struct bitmap *, bool)
void	bitmap_set_multiple (struct bitmap *, size_t start, size_t cnt, bool)
size_t	bitmap_count (const struct bitmap *, size_t start, size_t cnt, bool)
bool	bitmap_contains (const struct bitmap *, size_t start, size_t cnt, bool)
bool	bitmap_any (const struct bitmap *, size_t start, size_t cnt)
bool	bitmap_none (const struct bitmap *, size_t start, size_t cnt)
bool	bitmap_all (const struct bitmap *, size_t start, size_t cnt)
size_t	bitmap_scan (const struct bitmap *, size_t start, size_t cnt, bool)
size_t	bitmap_scan_and_flip (struct bitmap *, size_t start, size_t cnt, bool)
void	bitmap_dump (const struct bitmap *)

Macro Definition Documentation

BITMAP_ERROR

#define BITMAP_ERROR   SIZE_MAX

Function Documentation

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 *	,
		size_t	byte_cnt
	)

Here is the caller 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	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	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	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: