← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.h

  • Committer: Monty Taylor
  • Date: 2011-02-13 17:26:39 UTC
  • mfrom: (2157.2.2 give-in-to-pkg-config)
  • mto: This revision was merged to the branch mainline in revision 2166.
  • Revision ID: mordred@inaugust.com-20110213172639-nhy7i72sfhoq13ms
Merged in pkg-config fixes.

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 */