24
24
typedef uint32_t my_bitmap_map;
26
typedef struct st_bitmap
28
* @brief Represents a dynamically sized bitmap.
30
* Handling of unsigned char arrays as large bitmaps.
32
* API limitations (or, rather asserted safety assumptions,
33
* to encourage correct programming)
34
* - the internal size is a set of 32 bit words
35
* - the number of bits specified in creation can be any number
38
* Original version created by Sergei Golubchik 2001 - 2004.
39
* New version written and test program added and some changes to the
40
* interface was made by Mikael Ronström 2005, with assistance of Tomas
41
* Ulin and Mats Kindahl.
54
MyBitmap(const MyBitmap& rhs);
59
* We are not de-allocating memory here correctly at the moment!!!!
60
* Placing a delete [] statement here causes bad bad things to
62
* Placing this comment here in the hope that someone can help me
63
* resolve this issue....
68
MyBitmap& operator=(const MyBitmap& rhs);
70
bool init(my_bitmap_map *buf, uint32_t num_bits);
73
* Compare the given bitmap with this bitmap.
75
* @param[in] map bitmap to perform a comparison against
76
* @return true if bitmaps are equal; false otherwise
78
bool operator==(const MyBitmap *map)
80
*last_word_ptr|= last_word_mask;
81
*(map)->last_word_ptr|= (map)->last_word_mask;
82
return memcmp(bitmap, map->getBitmap(), 4*numOfWordsInMap())==0;
86
* Test whether the specified bit is set in the bitmap
87
* already and set it if it was not already set.
89
* @param[in] bitPos position to test and set
90
* @return false if the bit was not set; true otherwise
92
bool testAndSet(const uint32_t bitPos);
95
* Test whether the specified bit is set in the bitmap
96
* and clear it if it was set.
98
* @param[in] bitPos position to test and clear
99
* @return false if the bit was not set; true otherwise
101
bool testAndClear(const uint32_t bitPos);
104
* Set the next bit position that is not yet set starting
105
* from the beginning of the bitmap.
107
* @return the bit position that was set
114
* @return the position of the first bit set.
116
uint32_t getFirstSet();
119
* @return the bits set in this bitmap.
121
uint32_t getBitsSet();
124
* Set/clear all bits above a bit.
125
* Only full bytes can be set/cleared.
126
* The function is meant for the situation that you can copy
127
* a smaller bitmap to a bigger bitmap. Bitmap lengths are
128
* always a multiple of 8 (byte size). Using 'from_byte' saves
129
* multiplication and division by 8 during parameter passing.
131
* @param[in] from_byte bitmap buffer byte offset to start with
132
* @param[in] use_bit bit value (1/0) to use for all upper bits
134
void setAbove(const uint32_t from_byte, const uint32_t use_bit);
138
* Test whether all the bits in the bitmap are clear or not.
140
* @return true if all bits in bitmap are cleared; false otherwise
142
bool isClearAll() const;
144
bool isPrefix(const uint32_t prefix_size) const;
146
void setPrefix(uint32_t prefix_size);
149
* Test whether all the bits in the bitmap are set or not.
151
* @return true if all bits in bitmap are set; false otherwise
153
bool isSetAll() const;
157
* Test if the specified bit is set or not.
159
* @param[in] bit position of bit to test
160
* @return true if the bit is set; false otherwise
162
bool isBitSet(const uint32_t bit) const
164
return (bool)(((unsigned char *)bitmap)[bit / 8] & (1 << ((bit) & 7)));
168
* Set the specified bit.
170
* @param[in] bit position of bit to set in bitmap
172
void setBit(const uint32_t bit)
174
((unsigned char *)bitmap)[bit / 8] |= (1 << ((bit) & 7));
178
* Flip the specified bit.
180
* @param[in] bit position of bit to flip in bitmap
182
void flipBit(const uint32_t bit)
184
((unsigned char *)bitmap)[bit / 8] ^= (1 << ((bit) & 7));
188
* Clear the specified bit.
190
* @param[in] bit position of bit to clear in bitmap
192
void clearBit(const uint32_t bit)
194
((unsigned char *)bitmap)[bit / 8] &= ~ (1 << ((bit) & 7));
198
* Clear all the bits in the bitmap i.e. set every
203
memset(bitmap, 0, 4*numOfWordsInMap());
207
* Set all the bits in the bitmap i.e. set every
212
memset(bitmap, 0xFF, 4*numOfWordsInMap());
216
* @return the number of words in this bitmap.
218
uint32_t numOfWordsInMap() const
220
return ((n_bits + 31)/32);
224
* @return the number of bytes in this bitmap.
226
uint32_t numOfBytesInMap() const
228
return ((n_bits + 7)/8);
232
* Get the size of the bitmap in bits.
234
* @return the size of the bitmap in bits.
236
uint32_t numOfBitsInMap() const
242
* @return the current bitmap
244
my_bitmap_map *getBitmap() const
250
* Set the bitmap to the specified bitmap.
252
* @param[in] new_bitmap bitmap to use
254
void setBitmap(my_bitmap_map *new_bitmap)
260
* Obtains the number of used bits (1..8) in the last
261
* byte and creates a mask with the upper 'unused' bits
262
* set and the lower 'used' bits clear.
264
void createLastWordMask();
267
* @return the last word pointer for this bitmap
269
my_bitmap_map *getLastWordPtr() const
271
return last_word_ptr;
274
void addMaskToLastWord() const
276
*last_word_ptr|= last_word_mask;
280
* This resets the last bits in the bitmap to 0.
282
void subtractMaskFromLastWord() const
284
*last_word_ptr&= ~last_word_mask;
290
* The bitmap is stored in this variable.
28
292
my_bitmap_map *bitmap;
29
uint32_t n_bits; /* number of bits occupied by the above */
295
* Number of bits occupied by the bitmap.
300
* A mask used for the last word in the bitmap.
30
302
my_bitmap_map last_word_mask;
305
* A pointer to the last word in the bitmap.
31
307
my_bitmap_map *last_word_ptr;
33
: bitmap(NULL), n_bits(0), last_word_mask(0), last_word_ptr(NULL) {}
36
void create_last_word_mask(MY_BITMAP *map);
37
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint32_t n_bits);
38
bool bitmap_is_clear_all(const MY_BITMAP *map);
39
bool bitmap_is_prefix(const MY_BITMAP *map, uint32_t prefix_size);
40
bool bitmap_is_set_all(const MY_BITMAP *map);
41
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
42
bool bitmap_is_overlapping(const MY_BITMAP *map1,
43
const MY_BITMAP *map2);
44
bool bitmap_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit);
45
bool bitmap_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit);
46
uint32_t bitmap_set_next(MY_BITMAP *map);
47
uint32_t bitmap_get_first(const MY_BITMAP *map);
48
uint32_t bitmap_get_first_set(const MY_BITMAP *map);
49
uint32_t bitmap_bits_set(const MY_BITMAP *map);
50
void bitmap_free(MY_BITMAP *map);
51
void bitmap_set_above(MY_BITMAP *map, uint32_t from_byte, uint32_t use_bit);
52
void bitmap_set_prefix(MY_BITMAP *map, uint32_t prefix_size);
53
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2);
54
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
55
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2);
56
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2);
57
void bitmap_invert(MY_BITMAP *map);
58
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2);
311
bool bitmap_is_subset(const MyBitmap *map1, const MyBitmap *map2);
312
bool bitmap_is_overlapping(const MyBitmap *map1,
313
const MyBitmap *map2);
315
void bitmap_intersect(MyBitmap *map, const MyBitmap *map2);
316
void bitmap_subtract(MyBitmap *map, const MyBitmap *map2);
317
void bitmap_union(MyBitmap *map, const MyBitmap *map2);
318
void bitmap_xor(MyBitmap *map, const MyBitmap *map2);
319
void bitmap_invert(MyBitmap *map);
61
321
/* Fast, not thread safe, bitmap functions */
62
322
/* This one is a define because it gets used in an array decl */
63
323
#define bitmap_buffer_size(bits) ((bits+31)/32)*4
65
static inline uint32_t no_bytes_in_map(const MY_BITMAP *map)
67
return ((map->n_bits + 7)/8);
70
static inline uint32_t no_words_in_map(const MY_BITMAP *map)
72
return ((map->n_bits + 31)/32);
75
325
template <class T>
76
326
inline T bytes_word_aligned(T bytes)
78
328
return (4*((bytes + 3)/4));
81
static inline void bitmap_set_bit(MY_BITMAP const *map, uint32_t bit)
83
((unsigned char *)map->bitmap)[bit / 8] |= (unsigned char)(1 << ((bit) & 7));
86
static inline void bitmap_flip_bit(MY_BITMAP const *map, uint32_t bit)
88
((unsigned char *)map->bitmap)[bit / 8] ^= (1 << ((bit) & 7));
91
static inline void bitmap_clear_bit(MY_BITMAP const *map, uint32_t bit)
93
((unsigned char *)map->bitmap)[bit / 8] &= ~ (1 << ((bit) & 7));
96
static inline bool bitmap_is_set(const MY_BITMAP *map, uint32_t bit)
98
return (bool)(((unsigned char *)map->bitmap)[bit / 8] & (1 << ((bit) & 7)));
101
static inline bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
103
*(map1)->last_word_ptr|= (map1)->last_word_mask;
104
*(map2)->last_word_ptr|= (map2)->last_word_mask;
105
return memcmp((map1)->bitmap, (map2)->bitmap, 4*no_words_in_map((map1)))==0;
108
static inline void bitmap_clear_all(MY_BITMAP const *map)
110
memset(map->bitmap, 0, 4*no_words_in_map(map));
113
static inline void bitmap_set_all(MY_BITMAP const *map)
115
memset(map->bitmap, 0xFF, 4*no_words_in_map(map));
331
static inline bool bitmap_cmp(const MyBitmap *map1, const MyBitmap *map2)
333
map1->addMaskToLastWord();
334
map2->addMaskToLastWord();
335
return memcmp((map1)->getBitmap(),
337
4*map1->numOfWordsInMap()) == 0;
118
340
#endif /* MYSYS_MY_BITMAP_H */
added
removed
mysys/my_bitmap.h
