my_bitmap.cc File Reference

Handling of uchar arrays as large bitmaps. More...

#include "my_bitmap.h"
#include <string.h>
#include <sys/types.h>
#include <algorithm>
#include <bit>
#include "my_byteorder.h"
#include "my_dbug.h"
#include "my_inttypes.h"
#include "my_sys.h"
#include "mysql/service_mysql_alloc.h"
#include "mysys/mysys_priv.h"

Functions
void	create_last_word_mask (MY_BITMAP *map)
static uint	get_first_set (uint32 value, uint word_pos)
static uint	get_first_not_set (uint32 value, uint word_pos)
bool	bitmap_init (MY_BITMAP *map, my_bitmap_map *buf, uint n_bits)
void	bitmap_free (MY_BITMAP *map)
bool	bitmap_test_and_set (MY_BITMAP *map, uint bitmap_bit)
uint	bitmap_set_next (MY_BITMAP *map)
void	bitmap_set_prefix (MY_BITMAP *map, uint prefix_size)
	Set the specified number of bits in the bitmap buffer. More...
bool	bitmap_is_prefix (const MY_BITMAP *map, uint prefix_size)
bool	bitmap_is_set_all (const MY_BITMAP *map)
bool	bitmap_is_clear_all (const MY_BITMAP *map)
bool	bitmap_is_subset (const MY_BITMAP *map1, const MY_BITMAP *map2)
bool	bitmap_is_overlapping (const MY_BITMAP *map1, const MY_BITMAP *map2)
bool	bitmap_is_valid (const MY_BITMAP *map)
	Check if 'map' is valid. More...
void	bitmap_intersect (MY_BITMAP *to, const MY_BITMAP *from)
void	bitmap_set_above (MY_BITMAP *map, uint from_byte, bool use_bit)
void	bitmap_subtract (MY_BITMAP *map, const MY_BITMAP *map2)
void	bitmap_union (MY_BITMAP *map, const MY_BITMAP *map2)
void	bitmap_xor (MY_BITMAP *map, const MY_BITMAP *map2)
void	bitmap_invert (MY_BITMAP *map)
uint	bitmap_bits_set (const MY_BITMAP *map)
void	bitmap_copy (MY_BITMAP *map, const MY_BITMAP *map2)
uint	bitmap_get_first_set (const MY_BITMAP *map)
uint	bitmap_get_next_set (const MY_BITMAP *map, uint bitmap_bit)
	Get the next set bit. More...
uint	bitmap_get_first (const MY_BITMAP *map)
uint	bitmap_n_copy (MY_BITMAP *dst, const MY_BITMAP *src, uint max_bits_to_copy)
	Copy as many bits as 'dst' can hold from 'src', but no more than max_bits_to_copy bits. More...

Detailed Description

Handling of uchar arrays as large bitmaps.

API limitations (or, rather asserted safety assumptions, to encourage correct programming)

the internal size is a set of 32 bit words
the number of bits specified in creation can be any number > 0
a bitmap with zero bits can be created and initialized, but not used.

TODO: Make assembler THREAD safe versions of these using test-and-set instructions

Original version created by Sergei Golubchik 2001 - 2004. New version written and test program added and some changes to the interface was made by Mikael Ronström 2005, with assistance of Tomas Ulin and Mats Kindahl.

Function Documentation

bitmap_bits_set()

uint bitmap_bits_set

(

const MY_BITMAP *

map

)

bitmap_copy()

void bitmap_copy	(	MY_BITMAP *	map,
		const MY_BITMAP *	map2
	)

bitmap_free()

void bitmap_free

(

MY_BITMAP *

map

)

bitmap_get_first()

uint bitmap_get_first

(

const MY_BITMAP *

map

)

bitmap_get_first_set()

uint bitmap_get_first_set

(

const MY_BITMAP *

map

)

bitmap_get_next_set()

uint bitmap_get_next_set	(	const MY_BITMAP *	map,
		uint	bitmap_bit
	)

Get the next set bit.

Parameters

map	Bitmap
bitmap_bit	Bit to start search from

Returns

Index to first bit set after bitmap_bit

bitmap_init()

bool bitmap_init	(	MY_BITMAP *	map,
		my_bitmap_map *	buf,
		uint	n_bits
	)

bitmap_intersect()

void bitmap_intersect	(	MY_BITMAP *	to,
		const MY_BITMAP *	from
	)

bitmap_invert()

void bitmap_invert

(

MY_BITMAP *

map

)

bitmap_is_clear_all()

bool bitmap_is_clear_all

(

const MY_BITMAP *

map

)

bitmap_is_overlapping()

bool bitmap_is_overlapping	(	const MY_BITMAP *	map1,
		const MY_BITMAP *	map2
	)

bitmap_is_prefix()

bool bitmap_is_prefix	(	const MY_BITMAP *	map,
		uint	prefix_size
	)

bitmap_is_set_all()

bool bitmap_is_set_all

(

const MY_BITMAP *

map

)

bitmap_is_subset()

bool bitmap_is_subset	(	const MY_BITMAP *	map1,
		const MY_BITMAP *	map2
	)

bitmap_is_valid()

bool bitmap_is_valid

(

const MY_BITMAP *

map

)

Check if 'map' is valid.

Parameters

map	The map that we wish to verify.

Returns

'true' if 'map' passes a consistency check.

bitmap_n_copy()

uint bitmap_n_copy	(	MY_BITMAP *	dst,
		const MY_BITMAP *	src,
		uint	max_bits_to_copy
	)

Copy as many bits as 'dst' can hold from 'src', but no more than max_bits_to_copy bits.

'src' and 'dst' should not overlap. If 'dst' and 'src' have the same size (in bits), and this is less or equal than max_bits_to_copy, this function behaves identical to bitmap_copy().

Parameters

dst	The destination bitmap.
src	The source bitmap.
max_bits_to_copy	The maximal number of bits to copy.

Returns

The number of bits copied.

bitmap_set_above()

void bitmap_set_above	(	MY_BITMAP *	map,
		uint	from_byte,
		bool	use_bit
	)

bitmap_set_next()

uint bitmap_set_next

(

MY_BITMAP *

map

)

bitmap_set_prefix()

void bitmap_set_prefix	(	MY_BITMAP *	map,
		uint	prefix_size
	)

Set the specified number of bits in the bitmap buffer.

Parameters

map	Bitmap
prefix_size	Number of bits to be set

bitmap_subtract()

void bitmap_subtract	(	MY_BITMAP *	map,
		const MY_BITMAP *	map2
	)

bitmap_test_and_set()

bool bitmap_test_and_set	(	MY_BITMAP *	map,
		uint	bitmap_bit
	)

bitmap_union()

void bitmap_union	(	MY_BITMAP *	map,
		const MY_BITMAP *	map2
	)

bitmap_xor()

void bitmap_xor	(	MY_BITMAP *	map,
		const MY_BITMAP *	map2
	)

create_last_word_mask()

void create_last_word_mask

(

MY_BITMAP *

map

)

get_first_not_set()

static uint get_first_not_set ( uint32  value, uint  word_pos  )

inlinestatic

get_first_set()

static uint get_first_set ( uint32  value, uint  word_pos  )

inlinestatic