← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.h

  • Committer: Brian Aker
  • Date: 2009-11-18 06:24:48 UTC
  • mfrom: (1220.1.15 staging)
  • Revision ID: brian@gaz-20091118062448-o36lo3yv81sc6u9z
Merge Brian + Stewart

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_bitmap.h
 
1
/* Copyright (C) 2000 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
#ifndef MYSYS_MY_BITMAP_H
 
17
#define MYSYS_MY_BITMAP_H
 
18
 
 
19
#include <pthread.h>
 
20
#include <string.h>
 
21
 
 
22
static const uint32_t MY_BIT_NONE= UINT32_MAX;
 
23
 
 
24
typedef uint32_t my_bitmap_map;
 
25
 
 
26
/**
 
27
 * @class MyBitmap
 
28
 * @brief Represents a dynamically sized bitmap.
 
29
 *
 
30
 * Handling of unsigned char arrays as large bitmaps.
 
31
 * 
 
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
 
36
 *     greater than 0
 
37
 *
 
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.
 
42
 */
 
43
class MyBitmap
 
44
{
 
45
public:
 
46
  MyBitmap()
 
47
    :
 
48
      bitmap(NULL),
 
49
      n_bits(0),
 
50
      last_word_mask(0),
 
51
      last_word_ptr(NULL)
 
52
  {}
 
53
 
 
54
  MyBitmap(const MyBitmap& rhs);
 
55
 
 
56
  ~MyBitmap()
 
57
  {
 
58
      /*
 
59
       * We are not de-allocating memory here correctly at the moment!!!!
 
60
       * Placing a delete [] statement here causes bad bad things to
 
61
       * happen......
 
62
       * Placing this comment here in the hope that someone can help me
 
63
       * resolve this issue....
 
64
       */
 
65
      bitmap= 0;
 
66
  }
 
67
 
 
68
  MyBitmap& operator=(const MyBitmap& rhs);
 
69
 
 
70
  bool init(my_bitmap_map *buf, uint32_t num_bits);
 
71
 
 
72
  /**
 
73
   * Compare the given bitmap with this bitmap.
 
74
   *
 
75
   * @param[in] map bitmap to perform a comparison against
 
76
   * @return true if bitmaps are equal; false otherwise
 
77
   */
 
78
  bool operator==(const MyBitmap *map)
 
79
  {
 
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;
 
83
  }
 
84
 
 
85
  /**
 
86
   * Test whether the specified bit is set in the bitmap
 
87
   * already and set it if it was not already set.
 
88
   *
 
89
   * @param[in] bitPos position to test and set
 
90
   * @return false if the bit was not set; true otherwise
 
91
   */
 
92
  bool testAndSet(const uint32_t bitPos);
 
93
 
 
94
  /**
 
95
   * Test whether the specified bit is set in the bitmap
 
96
   * and clear it if it was set.
 
97
   *
 
98
   * @param[in] bitPos position to test and clear
 
99
   * @return false if the bit was not set; true otherwise
 
100
   */
 
101
  bool testAndClear(const uint32_t bitPos);
 
102
 
 
103
  /**
 
104
   * Set the next bit position that is not yet set starting
 
105
   * from the beginning of the bitmap.
 
106
   *
 
107
   * @return the bit position that was set
 
108
   */
 
109
  uint32_t setNext();
 
110
 
 
111
  uint32_t getFirst();
 
112
 
 
113
  /**
 
114
   * @return the position of the first bit set.
 
115
   */
 
116
  uint32_t getFirstSet();
 
117
 
 
118
  /**
 
119
   * @return the bits set in this bitmap.
 
120
   */
 
121
  uint32_t getBitsSet();
 
122
 
 
123
  /**
 
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.
 
130
   *
 
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
 
133
   */
 
134
  void setAbove(const uint32_t from_byte, const uint32_t use_bit);
 
135
 
 
136
 
 
137
  /**
 
138
   * Test whether all the bits in the bitmap are clear or not.
 
139
   *
 
140
   * @return true if all bits in bitmap are cleared; false otherwise
 
141
   */
 
142
  bool isClearAll() const;
 
143
 
 
144
  bool isPrefix(const uint32_t prefix_size) const;
 
145
 
 
146
  void setPrefix(uint32_t prefix_size);
 
147
 
 
148
  /**
 
149
   * Test whether all the bits in the bitmap are set or not.
 
150
   *
 
151
   * @return true if all bits in bitmap are set; false otherwise
 
152
   */
 
153
  bool isSetAll() const;
 
154
 
 
155
 
 
156
  /**
 
157
   * Test if the specified bit is set or not.
 
158
   *
 
159
   * @param[in] bit position of bit to test
 
160
   * @return true if the bit is set; false otherwise
 
161
   */
 
162
  bool isBitSet(const uint32_t bit) const
 
163
  {
 
164
    return (bool)(((unsigned char *)bitmap)[bit / 8] &  (1 << ((bit) & 7)));
 
165
  }
 
166
 
 
167
  /**
 
168
   * Set the specified bit.
 
169
   *
 
170
   * @param[in] bit position of bit to set in bitmap
 
171
   */
 
172
  void setBit(const uint32_t bit)
 
173
  {
 
174
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]= 
 
175
      static_cast<unsigned char>(
 
176
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] | 
 
177
      (1 << ((bit) & 7)));
 
178
  }
 
179
 
 
180
  /**
 
181
   * Flip the specified bit.
 
182
   *
 
183
   * @param[in] bit position of bit to flip in bitmap
 
184
   */
 
185
  void flipBit(const uint32_t bit)
 
186
  {
 
187
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]= 
 
188
      static_cast<unsigned char>(
 
189
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] ^ 
 
190
      (1 << ((bit) & 7)));
 
191
  }
 
192
 
 
193
  /**
 
194
   * Clear the specified bit.
 
195
   *
 
196
   * @param[in] bit position of bit to clear in bitmap
 
197
   */
 
198
  void clearBit(const uint32_t bit)
 
199
  {
 
200
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]= 
 
201
      static_cast<unsigned char>(
 
202
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] & 
 
203
      ~ (1 << ((bit) & 7)));
 
204
  }
 
205
 
 
206
  /**
 
207
   * Clear all the bits in the bitmap i.e. set every
 
208
   * bit to 0.
 
209
   */
 
210
  void clearAll()
 
211
  {
 
212
     memset(bitmap, 0, 4*numOfWordsInMap());
 
213
  }
 
214
 
 
215
  /**
 
216
   * Set all the bits in the bitmap i.e. set every
 
217
   * bit to 1.
 
218
   */
 
219
  void setAll()
 
220
  {
 
221
     memset(bitmap, 0xFF, 4*numOfWordsInMap());
 
222
  }
 
223
 
 
224
  /**
 
225
   * @return the number of words in this bitmap.
 
226
   */
 
227
  uint32_t numOfWordsInMap() const
 
228
  {
 
229
    return ((n_bits + 31)/32);
 
230
  }
 
231
 
 
232
  /**
 
233
   * @return the number of bytes in this bitmap.
 
234
   */
 
235
  uint32_t numOfBytesInMap() const
 
236
  {
 
237
    return ((n_bits + 7)/8);
 
238
  }
 
239
 
 
240
  /**
 
241
   * Get the size of the bitmap in bits.
 
242
   *
 
243
   * @return the size of the bitmap in bits.
 
244
   */
 
245
  uint32_t numOfBitsInMap() const
 
246
  {
 
247
    return n_bits;
 
248
  }
 
249
 
 
250
  /**
 
251
   * @return the current bitmap
 
252
   */
 
253
  my_bitmap_map *getBitmap() const
 
254
  {
 
255
    return bitmap;
 
256
  }
 
257
 
 
258
  /**
 
259
   * Set the bitmap to the specified bitmap.
 
260
   *
 
261
   * @param[in] new_bitmap bitmap to use
 
262
   */
 
263
  void setBitmap(my_bitmap_map *new_bitmap)
 
264
  {
 
265
    bitmap= new_bitmap;
 
266
  }
 
267
 
 
268
  /**
 
269
   * Obtains the number of used bits (1..8) in the last
 
270
   * byte and creates a mask with the upper 'unused' bits
 
271
   * set and the lower 'used' bits clear. 
 
272
   */
 
273
  void createLastWordMask();
 
274
 
 
275
  /**
 
276
   * @return the last word pointer for this bitmap
 
277
   */
 
278
  my_bitmap_map *getLastWordPtr() const
 
279
  {
 
280
    return last_word_ptr;
 
281
  }
 
282
 
 
283
  void addMaskToLastWord() const
 
284
  {
 
285
    *last_word_ptr|= last_word_mask;
 
286
  }
 
287
 
 
288
  /**
 
289
   * This resets the last bits in the bitmap to 0.
 
290
   */
 
291
  void subtractMaskFromLastWord() const
 
292
  {
 
293
    *last_word_ptr&= ~last_word_mask;
 
294
  }
 
295
 
 
296
private:
 
297
 
 
298
  /**
 
299
   * The bitmap is stored in this variable.
 
300
   */
 
301
  my_bitmap_map *bitmap;
 
302
 
 
303
  /**
 
304
   * Number of bits occupied by the bitmap.
 
305
   */
 
306
  uint32_t n_bits;
 
307
 
 
308
  /**
 
309
   * A mask used for the last word in the bitmap.
 
310
   */
 
311
  my_bitmap_map last_word_mask;
 
312
 
 
313
  /**
 
314
   * A pointer to the last word in the bitmap.
 
315
   */
 
316
  my_bitmap_map *last_word_ptr;
 
317
 
 
318
};
 
319
 
 
320
bool bitmap_is_subset(const MyBitmap *map1, const MyBitmap *map2);
 
321
bool bitmap_is_overlapping(const MyBitmap *map1,
 
322
                           const MyBitmap *map2);
 
323
 
 
324
void bitmap_intersect(MyBitmap *map, const MyBitmap *map2);
 
325
void bitmap_subtract(MyBitmap *map, const MyBitmap *map2);
 
326
void bitmap_union(MyBitmap *map, const MyBitmap *map2);
 
327
void bitmap_xor(MyBitmap *map, const MyBitmap *map2);
 
328
void bitmap_invert(MyBitmap *map);
 
329
 
 
330
/* Fast, not thread safe, bitmap functions */
 
331
/* This one is a define because it gets used in an array decl */
 
332
#define bitmap_buffer_size(bits) ((bits+31)/32)*4
 
333
 
 
334
template <class T>
 
335
inline T bytes_word_aligned(T bytes)
 
336
{
 
337
  return (4*((bytes + 3)/4));
 
338
}
 
339
 
 
340
static inline bool bitmap_cmp(const MyBitmap *map1, const MyBitmap *map2)
 
341
{
 
342
  map1->addMaskToLastWord();
 
343
  map2->addMaskToLastWord();
 
344
  return memcmp((map1)->getBitmap(), 
 
345
                (map2)->getBitmap(),
 
346
                4*map1->numOfWordsInMap()) == 0;
 
347
}
 
348
 
 
349
#endif /* MYSYS_MY_BITMAP_H */