diff options
Diffstat (limited to 'include/my_bitmap.h')
| -rw-r--r-- | include/my_bitmap.h | 94 |
1 files changed, 81 insertions, 13 deletions
diff --git a/include/my_bitmap.h b/include/my_bitmap.h index f4fe28266e4..98dd49a1228 100644 --- a/include/my_bitmap.h +++ b/include/my_bitmap.h @@ -21,10 +21,13 @@ #define MY_BIT_NONE (~(uint) 0) + typedef struct st_bitmap { - uchar *bitmap; - uint bitmap_size; /* number of bytes occupied by the above */ + uint32 *bitmap; + uint n_bits; /* number of bits occupied by the above */ + uint32 last_word_mask; + uint32 *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 @@ -38,33 +41,98 @@ 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, uint32 *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_test_and_set(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 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 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) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ + & (1 << ((BIT) & 7))) +#ifndef DBUG_OFF +inline uint32 +bitmap_set_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_set_bit(map,bit); +} +inline uint32 +bitmap_flip_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_flip_bit(map,bit); +} +inline uint32 +bitmap_clear_bit(MY_BITMAP *map,uint bit) +{ + DBUG_ASSERT(bit < (map)->n_bits); + return _bitmap_clear_bit(map,bit); +} +inline uint32 +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 +#define bitmap_cmp(MAP1, MAP2) \ + (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))); \ + *(MAP)->last_word_ptr|= (MAP)->last_word_mask; } +#define bitmap_set_all(MAP) \ + (memset((MAP)->bitmap, 0xFF, 4*no_words_in_map((MAP)))) #ifdef __cplusplus } |