bitmap.c File Reference

#include "bitmap.h"
#include <string.h>
#include <stdio.h>

Include dependency graph for bitmap.c:

Go to the source code of this file.

Functions
utils_bitmap_s *	utils_bitmap_init (void *mem, size_t size_bits)
size_t	utils_bitmap_size (utils_bitmap_s *bmp)
size_t	utils_bitmap_used (utils_bitmap_s *bmp)
size_t	utils_bitmap_free (utils_bitmap_s *bmp)
static int	find_end_small (size_t bits, uint64_t *chunk)
static size_t	find_start_small (utils_bitmap_s *bmp, size_t bits, uint64_t *chunk)
static size_t	find_start_big (utils_bitmap_s *bmp, size_t bits, uint64_t *chunk)
static size_t	find_start (utils_bitmap_s *bmp, size_t bits, uint64_t *chunk)
size_t	utils_bitmap_alloc_bits (utils_bitmap_s *bmp, size_t bits)
void	utils_bitmap_free_bits (utils_bitmap_s *bmp, size_t start, size_t bits)
size_t	utils_bitmap_count_allocated (utils_bitmap_s *bmp)
void	utils_bitmap_print_bits (utils_bitmap_s *bmp)

Function Documentation

find_end_small()

static int find_end_small ( size_t bits, uint64_t * chunk )

inlinestatic

Return true if bits were free at the begining of the chunk

Definition at line 61 of file bitmap.c.

References BITMAP_NOT_FOUND.

Referenced by find_start_big(), and find_start_small().

Here is the caller graph for this function:

find_start()

static size_t find_start ( utils_bitmap_s * bmp, size_t bits, uint64_t * chunk )

inlinestatic

Definition at line 207 of file bitmap.c.

References BITMAP_NOT_FOUND, find_start_big(), and find_start_small().

Referenced by utils_bitmap_alloc_bits().

Here is the call graph for this function:

Here is the caller graph for this function:

find_start_big()

static size_t find_start_big ( utils_bitmap_s * bmp, size_t bits, uint64_t * chunk )

inlinestatic

Definition at line 137 of file bitmap.c.

References BITMAP_NOT_FOUND, utils_bitmap::bits, utils_bitmap::end, find_end_small(), and utils_bitmap::used_bits.

Referenced by find_start().

Here is the call graph for this function:

Here is the caller graph for this function:

find_start_small()

static size_t find_start_small ( utils_bitmap_s * bmp, size_t bits, uint64_t * chunk )

inlinestatic

Definition at line 76 of file bitmap.c.

References BITMAP_NOT_FOUND, utils_bitmap::bits, utils_bitmap::end, find_end_small(), utils_bitmap::size_bits, and utils_bitmap::used_bits.

Referenced by find_start().

Here is the call graph for this function:

Here is the caller graph for this function:

utils_bitmap_alloc_bits()

size_t utils_bitmap_alloc_bits	(	utils_bitmap_s *	bmp,
		size_t	bits )

Allocate bits cotiguous bits from bmp and return index of first bit.

bmp An initialized utils_bitmap_s instance.

Returns

Bit index of allocation start.

Definition at line 217 of file bitmap.c.

References BITMAP_NOT_FOUND, utils_bitmap::bits, utils_bitmap::end, find_start(), utils_bitmap::free_p, utils_bitmap::lock, utils_bitmap_free(), utils_spinlock_lock, and utils_spinlock_unlock.

Referenced by arax_mmap().

Here is the call graph for this function:

Here is the caller graph for this function:

utils_bitmap_count_allocated()

size_t utils_bitmap_count_allocated

(

utils_bitmap_s *

bmp

)

Count allocated bits of bmp.

Should always return the same value as utils_bitmap_used().

Note

This should only be used in tests, as it is very slow.

bmp An initialized utils_bitmap_s instance.

Returns

Bits allocated(set) in bits array of bmp

Definition at line 298 of file bitmap.c.

References utils_bitmap::bits, and utils_bitmap::size_bits.

utils_bitmap_free()

size_t utils_bitmap_free

(

utils_bitmap_s *

bmp

)

Returns number of unused bits in bmp.

Note

This is utils_bitmap_size() - utils_bitmap_used()

bmp An initialized utils_bitmap_s instance.

Returns

Number of free bits in bmp.

Definition at line 53 of file bitmap.c.

References utils_bitmap::size_bits, and utils_bitmap::used_bits.

Referenced by utils_bitmap_alloc_bits().

Here is the caller graph for this function:

utils_bitmap_free_bits()

void utils_bitmap_free_bits	(	utils_bitmap_s *	bmp,
		size_t	start,
		size_t	bits )

Free contiguous bits starting from start, from the bmp bitmap.

bmp An initialized utils_bitmap_s instance. start First bit index to be freed. bits Number of bits to free.

Definition at line 255 of file bitmap.c.

References arax_assert, BITMAP_NOT_FOUND, utils_bitmap::bits, utils_bitmap::lock, utils_bitmap::used_bits, utils_spinlock_lock, and utils_spinlock_unlock.

Referenced by arax_ummap().

Here is the caller graph for this function:

utils_bitmap_init()

utils_bitmap_s * utils_bitmap_init	(	void *	mem,
		size_t	size_bits )

A bit about the bitmap:

It is arranged in 'chunks' of uint64_t (8 bytes).

Initially all bits are 0, meaning free.

Allocation happens in squential order for chunks. First chunk[0] will be usedm then chunk[1], etc...

Inside a chunk bit allocation occurs in a lsb to msb order:

An initialy empty chunk: 0x0000 0000 0000 0000 After a 16bit allocation: 0x0000 0000 0000 000F After an 8bit allocation: 0x0000 0000 0000 008F

Definition at line 25 of file bitmap.c.

References utils_bitmap::bits, utils_bitmap::end, utils_bitmap::free_p, utils_bitmap::lock, utils_bitmap::size_bits, utils_bitmap::used_bits, and utils_spinlock_init.

Referenced by arch_alloc_init_once().

Here is the caller graph for this function:

utils_bitmap_print_bits()

void utils_bitmap_print_bits

(

utils_bitmap_s *

bmp

)

Print the bitmap oc bmp, in stderr.

Note

Use this for debuging

bmp An initialized utils_bitmap_s instance.

Definition at line 311 of file bitmap.c.

References utils_bitmap::bits, and utils_bitmap::size_bits.

utils_bitmap_size()

size_t utils_bitmap_size

(

utils_bitmap_s *

bmp

)

Returns number of bits bmp holds, same as the value given in utils_bitmap_init.

bmp An initialized utils_bitmap_s instance.

Returns

Bits contained in bmp

Definition at line 43 of file bitmap.c.

References utils_bitmap::size_bits.

utils_bitmap_used()

size_t utils_bitmap_used

(

utils_bitmap_s *

bmp

)

Returns number of bits currently used in bmp.

bmp An initialized utils_bitmap_s instance.

Returns

Number of allocated bits in bmp.

Definition at line 48 of file bitmap.c.

References utils_bitmap::used_bits.