diff options
Diffstat (limited to 'include/my_bitmap.h')
| -rw-r--r-- | include/my_bitmap.h | 112 |
1 files changed, 97 insertions, 15 deletions
diff --git a/include/my_bitmap.h b/include/my_bitmap.h index 8fb4327622c..488c41ffb22 100644 --- a/include/my_bitmap.h +++ b/include/my_bitmap.h @@ -16,14 +16,18 @@ #ifndef _my_bitmap_h_ #define _my_bitmap_h_ -#include <my_pthread.h> - #define MY_BIT_NONE (~(uint) 0) +#include <m_string.h> + +typedef uint32 my_bitmap_map; + typedef struct st_bitmap { - uchar *bitmap; - uint bitmap_size; /* number of bytes occupied by the above */ + my_bitmap_map *bitmap; + uint n_bits; /* number of bits occupied by the above */ + my_bitmap_map last_word_mask; + my_bitmap_map *last_word_ptr; /* mutex will be acquired for the duration of each bitmap operation if thread_safe flag in bitmap_init was set. Otherwise, we optimize by not @@ -37,33 +41,111 @@ typedef struct st_bitmap #ifdef __cplusplus extern "C" { #endif -extern my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2); -extern my_bool bitmap_init(MY_BITMAP *map, uchar *buf, uint bitmap_size, my_bool thread_safe); +extern my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits, + my_bool thread_safe); extern my_bool bitmap_is_clear_all(const MY_BITMAP *map); extern my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size); -extern my_bool bitmap_is_set(const MY_BITMAP *map, uint bitmap_bit); extern my_bool bitmap_is_set_all(const MY_BITMAP *map); extern my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2); +extern my_bool bitmap_is_overlapping(const MY_BITMAP *map1, + const MY_BITMAP *map2); extern my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit); +extern my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit); extern my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit); extern uint bitmap_set_next(MY_BITMAP *map); extern uint bitmap_get_first(const MY_BITMAP *map); +extern uint bitmap_get_first_set(const MY_BITMAP *map); extern uint bitmap_bits_set(const MY_BITMAP *map); -extern void bitmap_clear_all(MY_BITMAP *map); -extern void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit); extern void bitmap_free(MY_BITMAP *map); -extern void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2); extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit); -extern void bitmap_set_all(MY_BITMAP *map); -extern void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit); extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size); +extern void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2); extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2); extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_invert(MY_BITMAP *map); +extern void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2); +extern uint bitmap_lock_set_next(MY_BITMAP *map); +extern void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit); +#ifdef NOT_USED +extern uint bitmap_lock_bits_set(const MY_BITMAP *map); +extern my_bool bitmap_lock_is_set_all(const MY_BITMAP *map); +extern uint bitmap_lock_get_first(const MY_BITMAP *map); +extern uint bitmap_lock_get_first_set(const MY_BITMAP *map); +extern my_bool bitmap_lock_is_subset(const MY_BITMAP *map1, + const MY_BITMAP *map2); +extern my_bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size); +extern my_bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit); +extern my_bool bitmap_lock_is_clear_all(const MY_BITMAP *map); +extern my_bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2); +extern void bitmap_lock_set_all(MY_BITMAP *map); +extern void bitmap_lock_clear_all(MY_BITMAP *map); +extern void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit); +extern void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit); +extern void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size); +extern void bitmap_lock_intersect(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_subtract(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_union(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_xor(MY_BITMAP *map, const MY_BITMAP *map2); +extern void bitmap_lock_invert(MY_BITMAP *map); +#endif /* Fast, not thread safe, bitmap functions */ -#define bitmap_fast_set_bit(MAP, BIT) (MAP)->bitmap[(BIT) / 8] |= (1 << ((BIT) & 7)) -#define bitmap_fast_clear_bit(MAP, BIT) (MAP)->bitmap[(BIT) / 8] &= ~ (1 << ((BIT) & 7)) -#define bitmap_fast_is_set(MAP, BIT) (MAP)->bitmap[(BIT) / 8] & (1 << ((BIT) & 7)) +#define bitmap_buffer_size(bits) (((bits)+31)/32)*4 +#define no_bytes_in_map(map) (((map)->n_bits + 7)/8) +#define no_words_in_map(map) (((map)->n_bits + 31)/32) +#define bytes_word_aligned(bytes) (4*((bytes + 3)/4)) +#define _bitmap_set_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + |= (1 << ((BIT) & 7))) +#define _bitmap_flip_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + ^= (1 << ((BIT) & 7))) +#define _bitmap_clear_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + &= ~ (1 << ((BIT) & 7))) +#define _bitmap_is_set(MAP, BIT) (uint) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + & (1 << ((BIT) & 7))) +#ifndef DBUG_OFF +static inline void +bitmap_set_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + _bitmap_set_bit(map,bit); +} +static inline void +bitmap_flip_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + _bitmap_flip_bit(map,bit); +} +static inline void +bitmap_clear_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + _bitmap_clear_bit(map,bit); +} +static inline uint +bitmap_is_set(const MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_is_set(map,bit); +} +#else +#define bitmap_set_bit(MAP, BIT) _bitmap_set_bit(MAP, BIT) +#define bitmap_flip_bit(MAP, BIT) _bitmap_flip_bit(MAP, BIT) +#define bitmap_clear_bit(MAP, BIT) _bitmap_clear_bit(MAP, BIT) +#define bitmap_is_set(MAP, BIT) _bitmap_is_set(MAP, BIT) +#endif + +static inline my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2) +{ + *(map1)->last_word_ptr|= (map1)->last_word_mask; + *(map2)->last_word_ptr|= (map2)->last_word_mask; + return memcmp((map1)->bitmap, (map2)->bitmap, 4*no_words_in_map((map1)))==0; +} + +#define bitmap_clear_all(MAP) \ + { memset((MAP)->bitmap, 0, 4*no_words_in_map((MAP))); } +#define bitmap_set_all(MAP) \ + (memset((MAP)->bitmap, 0xFF, 4*no_words_in_map((MAP)))) #ifdef __cplusplus } |