← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.h

Merge Joe, plus I updated the tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/sql_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 DRIZZLED_SQL_BITMAP_H
 
17
#define DRIZZLED_SQL_BITMAP_H
 
18
 
 
19
/*
 
20
  Implementation of a bitmap type.
 
21
  The idea with this is to be able to handle any constant number of bits but
 
22
  also be able to use 32 or 64 bits bitmaps very efficiently
 
23
*/
 
24
 
 
25
#include <drizzled/definitions.h>
 
26
#include <drizzled/util/test.h>
 
27
#include <drizzled/key_map.h>
 
28
#include <pthread.h>
 
29
 
 
30
#include <cstring>
 
31
 
 
32
namespace drizzled
 
33
{
 
34
 
 
35
typedef uint64_t table_map;          /* Used for table bits in join */
 
36
typedef uint32_t nesting_map;  /* Used for flags of nesting constructs */
 
37
 
 
38
 
 
39
static const uint32_t MY_BIT_NONE= UINT32_MAX;
 
40
 
 
41
typedef uint32_t my_bitmap_map;
 
42
 
 
43
/**
 
44
 * @class MyBitmap
 
45
 * @brief Represents a dynamically sized bitmap.
 
46
 *
 
47
 * Handling of unsigned char arrays as large bitmaps.
 
48
 *
 
49
 * API limitations (or, rather asserted safety assumptions,
 
50
 * to encourage correct programming)
 
51
 *   - the internal size is a set of 32 bit words
 
52
 *   - the number of bits specified in creation can be any number
 
53
 *     greater than 0
 
54
 *
 
55
 * Original version created by Sergei Golubchik 2001 - 2004.
 
56
 * New version written and test program added and some changes to the
 
57
 * interface was made by Mikael Ronström 2005, with assistance of Tomas
 
58
 * Ulin and Mats Kindahl.
 
59
 */
 
60
class MyBitmap
 
61
{
 
62
public:
 
63
  MyBitmap()
 
64
    :
 
65
      bitmap(NULL),
 
66
      n_bits(0),
 
67
      last_word_mask(0),
 
68
      last_word_ptr(NULL)
 
69
  {}
 
70
 
 
71
  MyBitmap(const MyBitmap& rhs);
 
72
 
 
73
  ~MyBitmap()
 
74
  {
 
75
      /*
 
76
       * We are not de-allocating memory here correctly at the moment!!!!
 
77
       * Placing a delete [] statement here causes bad bad things to
 
78
       * happen......
 
79
       * Placing this comment here in the hope that someone can help me
 
80
       * resolve this issue....
 
81
       */
 
82
      bitmap= 0;
 
83
  }
 
84
 
 
85
  MyBitmap& operator=(const MyBitmap& rhs);
 
86
 
 
87
  bool init(my_bitmap_map *buf, uint32_t num_bits);
 
88
 
 
89
  /**
 
90
   * Compare the given bitmap with this bitmap.
 
91
   *
 
92
   * @param[in] map bitmap to perform a comparison against
 
93
   * @return true if bitmaps are equal; false otherwise
 
94
   */
 
95
  bool operator==(const MyBitmap *map)
 
96
  {
 
97
    *last_word_ptr|= last_word_mask;
 
98
    *(map)->last_word_ptr|= (map)->last_word_mask;
 
99
    return memcmp(bitmap, map->getBitmap(), 4*numOfWordsInMap())==0;
 
100
  }
 
101
 
 
102
  /**
 
103
   * Test whether the specified bit is set in the bitmap
 
104
   * already and set it if it was not already set.
 
105
   *
 
106
   * @param[in] bitPos position to test and set
 
107
   * @return false if the bit was not set; true otherwise
 
108
   */
 
109
  bool testAndSet(const uint32_t bitPos);
 
110
 
 
111
  /**
 
112
   * Test whether the specified bit is set in the bitmap
 
113
   * and clear it if it was set.
 
114
   *
 
115
   * @param[in] bitPos position to test and clear
 
116
   * @return false if the bit was not set; true otherwise
 
117
   */
 
118
  bool testAndClear(const uint32_t bitPos);
 
119
 
 
120
  /**
 
121
   * Set the next bit position that is not yet set starting
 
122
   * from the beginning of the bitmap.
 
123
   *
 
124
   * @return the bit position that was set
 
125
   */
 
126
  uint32_t setNext();
 
127
 
 
128
  uint32_t getFirst();
 
129
 
 
130
  /**
 
131
   * @return the position of the first bit set.
 
132
   */
 
133
  uint32_t getFirstSet();
 
134
 
 
135
  /**
 
136
   * @return the bits set in this bitmap.
 
137
   */
 
138
  uint32_t getBitsSet();
 
139
 
 
140
  /**
 
141
   * Set/clear all bits above a bit.
 
142
   * Only full bytes can be set/cleared.
 
143
   * The function is meant for the situation that you can copy
 
144
   * a smaller bitmap to a bigger bitmap. Bitmap lengths are
 
145
   * always a multiple of 8 (byte size). Using 'from_byte' saves
 
146
   * multiplication and division by 8 during parameter passing.
 
147
   *
 
148
   * @param[in] from_byte bitmap buffer byte offset to start with
 
149
   * @param[in] use_bit bit value (1/0) to use for all upper bits
 
150
   */
 
151
  void setAbove(const uint32_t from_byte, const uint32_t use_bit);
 
152
 
 
153
 
 
154
  /**
 
155
   * Test whether all the bits in the bitmap are clear or not.
 
156
   *
 
157
   * @return true if all bits in bitmap are cleared; false otherwise
 
158
   */
 
159
  bool isClearAll() const;
 
160
 
 
161
  bool isPrefix(const uint32_t prefix_size) const;
 
162
 
 
163
  void setPrefix(uint32_t prefix_size);
 
164
 
 
165
  /**
 
166
   * Test whether all the bits in the bitmap are set or not.
 
167
   *
 
168
   * @return true if all bits in bitmap are set; false otherwise
 
169
   */
 
170
  bool isSetAll() const;
 
171
 
 
172
 
 
173
  /**
 
174
   * Test if the specified bit is set or not.
 
175
   *
 
176
   * @param[in] bit position of bit to test
 
177
   * @return true if the bit is set; false otherwise
 
178
   */
 
179
  bool isBitSet(const uint32_t bit) const
 
180
  {
 
181
     return (bool)((reinterpret_cast<unsigned char *>(bitmap))[bit / 8] &  (1 << ((bit) & 7)));
 
182
  }
 
183
 
 
184
  /**
 
185
   * Set the specified bit.
 
186
   *
 
187
   * @param[in] bit position of bit to set in bitmap
 
188
   */
 
189
  void setBit(const uint32_t bit)
 
190
  {
 
191
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]=
 
192
      static_cast<unsigned char>(
 
193
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] |
 
194
      (1 << ((bit) & 7)));
 
195
  }
 
196
 
 
197
  /**
 
198
   * Flip the specified bit.
 
199
   *
 
200
   * @param[in] bit position of bit to flip in bitmap
 
201
   */
 
202
  void flipBit(const uint32_t bit)
 
203
  {
 
204
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]=
 
205
      static_cast<unsigned char>(
 
206
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] ^
 
207
      (1 << ((bit) & 7)));
 
208
  }
 
209
 
 
210
  /**
 
211
   * Clear the specified bit.
 
212
   *
 
213
   * @param[in] bit position of bit to clear in bitmap
 
214
   */
 
215
  void clearBit(const uint32_t bit)
 
216
  {
 
217
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]=
 
218
      static_cast<unsigned char>(
 
219
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] &
 
220
      ~ (1 << ((bit) & 7)));
 
221
  }
 
222
 
 
223
  /**
 
224
   * Clear all the bits in the bitmap i.e. set every
 
225
   * bit to 0.
 
226
   */
 
227
  void clearAll()
 
228
  {
 
229
     memset(bitmap, 0, 4*numOfWordsInMap());
 
230
  }
 
231
 
 
232
  /**
 
233
   * Set all the bits in the bitmap i.e. set every
 
234
   * bit to 1.
 
235
   */
 
236
  void setAll()
 
237
  {
 
238
     memset(bitmap, 0xFF, 4*numOfWordsInMap());
 
239
  }
 
240
 
 
241
  /**
 
242
   * @return the number of words in this bitmap.
 
243
   */
 
244
  uint32_t numOfWordsInMap() const
 
245
  {
 
246
    return ((n_bits + 31)/32);
 
247
  }
 
248
 
 
249
  /**
 
250
   * @return the number of bytes in this bitmap.
 
251
   */
 
252
  uint32_t numOfBytesInMap() const
 
253
  {
 
254
    return ((n_bits + 7)/8);
 
255
  }
 
256
 
 
257
  /**
 
258
   * Get the size of the bitmap in bits.
 
259
   *
 
260
   * @return the size of the bitmap in bits.
 
261
   */
 
262
  uint32_t numOfBitsInMap() const
 
263
  {
 
264
    return n_bits;
 
265
  }
 
266
 
 
267
  /**
 
268
   * @return the current bitmap
 
269
   */
 
270
  my_bitmap_map *getBitmap() const
 
271
  {
 
272
    return bitmap;
 
273
  }
 
274
 
 
275
  /**
 
276
   * Set the bitmap to the specified bitmap.
 
277
   *
 
278
   * @param[in] new_bitmap bitmap to use
 
279
   */
 
280
  void setBitmap(my_bitmap_map *new_bitmap)
 
281
  {
 
282
    bitmap= new_bitmap;
 
283
  }
 
284
 
 
285
  /**
 
286
   * Obtains the number of used bits (1..8) in the last
 
287
   * byte and creates a mask with the upper 'unused' bits
 
288
   * set and the lower 'used' bits clear.
 
289
   */
 
290
  void createLastWordMask();
 
291
 
 
292
  /**
 
293
   * @return the last word pointer for this bitmap
 
294
   */
 
295
  my_bitmap_map *getLastWordPtr() const
 
296
  {
 
297
    return last_word_ptr;
 
298
  }
 
299
 
 
300
  void addMaskToLastWord() const
 
301
  {
 
302
    *last_word_ptr|= last_word_mask;
 
303
  }
 
304
 
 
305
  /**
 
306
   * This resets the last bits in the bitmap to 0.
 
307
   */
 
308
  void subtractMaskFromLastWord() const
 
309
  {
 
310
    *last_word_ptr&= ~last_word_mask;
 
311
  }
 
312
 
 
313
private:
 
314
 
 
315
  /**
 
316
   * The bitmap is stored in this variable.
 
317
   */
 
318
  my_bitmap_map *bitmap;
 
319
 
 
320
  /**
 
321
   * Number of bits occupied by the bitmap.
 
322
   */
 
323
  uint32_t n_bits;
 
324
 
 
325
  /**
 
326
   * A mask used for the last word in the bitmap.
 
327
   */
 
328
  my_bitmap_map last_word_mask;
 
329
 
 
330
  /**
 
331
   * A pointer to the last word in the bitmap.
 
332
   */
 
333
  my_bitmap_map *last_word_ptr;
 
334
 
 
335
};
 
336
 
 
337
bool bitmap_is_subset(const MyBitmap *map1, const MyBitmap *map2);
 
338
bool bitmap_is_overlapping(const MyBitmap *map1,
 
339
                           const MyBitmap *map2);
 
340
 
 
341
void bitmap_intersect(MyBitmap *map, const MyBitmap *map2);
 
342
void bitmap_subtract(MyBitmap *map, const MyBitmap *map2);
 
343
void bitmap_union(MyBitmap *map, const MyBitmap *map2);
 
344
void bitmap_xor(MyBitmap *map, const MyBitmap *map2);
 
345
void bitmap_invert(MyBitmap *map);
 
346
 
 
347
/* Fast, not thread safe, bitmap functions */
 
348
/* This one is a define because it gets used in an array decl */
 
349
#define bitmap_buffer_size(bits) ((bits+31)/32)*4
 
350
 
 
351
template <class T>
 
352
inline T bytes_word_aligned(T bytes)
 
353
{
 
354
  return (4*((bytes + 3)/4));
 
355
}
 
356
 
 
357
static inline bool bitmap_cmp(const MyBitmap *map1, const MyBitmap *map2)
 
358
{
 
359
  map1->addMaskToLastWord();
 
360
  map2->addMaskToLastWord();
 
361
  return memcmp((map1)->getBitmap(),
 
362
                (map2)->getBitmap(),
 
363
                4*map1->numOfWordsInMap()) == 0;
 
364
}
 
365
 
 
366
} /* namespace drizzled */
 
367
 
 
368
#endif /* DRIZZLED_SQL_BITMAP_H */