← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.h

Fixed sql_builtin.cc.in... stupid generated files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/sql_bitmap.h
 
1
#ifndef _SQL_BITMAP_H_
 
2
#define _SQL_BITMAP_H_
 
3
/* Copyright (C) 2003 MySQL AB
 
4
 
 
5
   This program is free software; you can redistribute it and/or modify
 
6
   it under the terms of the GNU General Public License as published by
 
7
   the Free Software Foundation; version 2 of the License.
 
8
 
 
9
   This program is distributed in the hope that it will be useful,
 
10
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
12
   GNU General Public License for more details.
 
13
 
 
14
   You should have received a copy of the GNU General Public License
 
15
   along with this program; if not, write to the Free Software
 
16
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
17
 
 
18
/*
 
19
  Implementation of a bitmap type.
 
20
  The idea with this is to be able to handle any constant number of bits but
 
21
  also be able to use 32 or 64 bits bitmaps very efficiently
 
22
*/
 
23
 
 
24
#include <mysys/my_bitmap.h>
 
25
 
 
26
template <uint default_width> class Bitmap
 
27
{
 
28
  MY_BITMAP map;
 
29
  uint32_t buffer[(default_width+31)/32];
 
30
public:
 
31
  Bitmap() { init(); }
 
32
  Bitmap(const Bitmap& from) { *this=from; }
 
33
  explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
 
34
  void init() { bitmap_init(&map, buffer, default_width, 0); }
 
35
  void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }
 
36
  uint length() const { return default_width; }
 
37
  Bitmap& operator=(const Bitmap& map2)
 
38
  {
 
39
    init();
 
40
    memcpy(buffer, map2.buffer, sizeof(buffer));
 
41
    return *this;
 
42
  }
 
43
  void set_bit(uint n) { bitmap_set_bit(&map, n); }
 
44
  void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
 
45
  void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
 
46
  void set_all() { bitmap_set_all(&map); }
 
47
  void clear_all() { bitmap_clear_all(&map); }
 
48
  void intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
 
49
  void intersect(uint64_t map2buff)
 
50
  {
 
51
    MY_BITMAP map2;
 
52
    bitmap_init(&map2, (uint32_t *)&map2buff, sizeof(uint64_t)*8, 0);
 
53
    bitmap_intersect(&map, &map2);
 
54
  }
 
55
  /* Use highest bit for all bits above sizeof(uint64_t)*8. */
 
56
  void intersect_extended(uint64_t map2buff)
 
57
  {
 
58
    intersect(map2buff);
 
59
    if (map.n_bits > sizeof(uint64_t) * 8)
 
60
      bitmap_set_above(&map, sizeof(uint64_t),
 
61
                       test(map2buff & (1 << (sizeof(uint64_t) * 8 - 1))));
 
62
  }
 
63
  void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
 
64
  void merge(Bitmap& map2) { bitmap_union(&map, &map2.map); }
 
65
  bool is_set(uint n) const { return bitmap_is_set(&map, n); }
 
66
  bool is_set() const { return !bitmap_is_clear_all(&map); }
 
67
  bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
 
68
  bool is_clear_all() const { return bitmap_is_clear_all(&map); }
 
69
  bool is_set_all() const { return bitmap_is_set_all(&map); }
 
70
  bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
 
71
  bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
 
72
  bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
 
73
  bool operator!=(const Bitmap& map2) const { return !bitmap_cmp(&map, &map2.map); }
 
74
  Bitmap operator&=(uint n)
 
75
  {
 
76
    if (bitmap_is_set(&map, n))
 
77
    {
 
78
      bitmap_clear_all(&map);
 
79
      bitmap_set_bit(&map, n);
 
80
    }
 
81
    else
 
82
      bitmap_clear_all(&map);
 
83
    return *this;
 
84
  }
 
85
  Bitmap operator&=(const Bitmap& map2)
 
86
  {
 
87
    bitmap_intersect(&map, &map2.map);
 
88
    return *this;
 
89
  }
 
90
  Bitmap operator&(uint n)
 
91
  {
 
92
    Bitmap bm(*this);
 
93
    bm&= n;
 
94
    return bm;
 
95
  }
 
96
  Bitmap operator&(const Bitmap& map2)
 
97
  {
 
98
    Bitmap bm(*this);
 
99
    bm&= map2;
 
100
    return bm;
 
101
  }
 
102
  Bitmap operator|=(uint n)
 
103
  {
 
104
    bitmap_set_bit(&map, n);
 
105
    return *this;
 
106
  }
 
107
  Bitmap operator|=(const Bitmap& map2)
 
108
  {
 
109
    bitmap_union(&map, &map2.map);
 
110
  }
 
111
  Bitmap operator|(uint n)
 
112
  {
 
113
    Bitmap bm(*this);
 
114
    bm|= n;
 
115
    return bm;
 
116
  }
 
117
  Bitmap operator|(const Bitmap& map2)
 
118
  {
 
119
    Bitmap bm(*this);
 
120
    bm|= map2;
 
121
    return bm;
 
122
  }
 
123
  Bitmap operator~()
 
124
  {
 
125
    Bitmap bm(*this);
 
126
    bitmap_invert(&bm.map);
 
127
    return bm;
 
128
  }
 
129
  char *print(char *buf) const
 
130
  {
 
131
    char *s=buf;
 
132
    const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;
 
133
    while (!*b && b>e)
 
134
      b--;
 
135
    if ((*s=_dig_vec_upper[*b >> 4]) != '0')
 
136
        s++;
 
137
    *s++=_dig_vec_upper[*b & 15];
 
138
    while (--b>=e)
 
139
    {
 
140
      *s++=_dig_vec_upper[*b >> 4];
 
141
      *s++=_dig_vec_upper[*b & 15];
 
142
    }
 
143
    *s=0;
 
144
    return buf;
 
145
  }
 
146
  uint64_t to_uint64_t() const
 
147
  {
 
148
    if (sizeof(buffer) >= 8)
 
149
      return uint8korr(buffer);
 
150
    assert(sizeof(buffer) >= 4);
 
151
    return (uint64_t) uint4korr(buffer);
 
152
  }
 
153
};
 
154
 
 
155
template <> class Bitmap<64>
 
156
{
 
157
  uint64_t map;
 
158
public:
 
159
  Bitmap<64>() { map= 0; }
 
160
  explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
 
161
  void init() { }
 
162
  void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
 
163
  uint length() const { return 64; }
 
164
  void set_bit(uint n) { map|= ((uint64_t)1) << n; }
 
165
  void clear_bit(uint n) { map&= ~(((uint64_t)1) << n); }
 
166
  void set_prefix(uint n)
 
167
  {
 
168
    if (n >= length())
 
169
      set_all();
 
170
    else
 
171
      map= (((uint64_t)1) << n)-1;
 
172
  }
 
173
  void set_all() { map=~(uint64_t)0; }
 
174
  void clear_all() { map=(uint64_t)0; }
 
175
  void intersect(Bitmap<64>& map2) { map&= map2.map; }
 
176
  void intersect(uint64_t map2) { map&= map2; }
 
177
  void intersect_extended(uint64_t map2) { map&= map2; }
 
178
  void subtract(Bitmap<64>& map2) { map&= ~map2.map; }
 
179
  void merge(Bitmap<64>& map2) { map|= map2.map; }
 
180
  bool is_set(uint n) const { return test(map & (((uint64_t)1) << n)); }
 
181
  bool is_prefix(uint n) const { return map == (((uint64_t)1) << n)-1; }
 
182
  bool is_clear_all() const { return map == (uint64_t)0; }
 
183
  bool is_set_all() const { return map == ~(uint64_t)0; }
 
184
  bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
 
185
  bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
 
186
  bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
 
187
  char *print(char *buf) const { int64_t2str(map,buf,16); return buf; }
 
188
  uint64_t to_uint64_t() const { return map; }
 
189
};
 
190
 
 
191
 
 
192
/* An iterator to quickly walk over bits in unint64_t bitmap. */
 
193
class Table_map_iterator
 
194
{
 
195
  uint64_t bmp;
 
196
  uint no;
 
197
public:
 
198
  Table_map_iterator(uint64_t t) : bmp(t), no(0) {}
 
199
  int next_bit()
 
200
  {
 
201
    static const char last_bit[16]= {32, 0, 1, 0, 
 
202
                                      2, 0, 1, 0, 
 
203
                                      3, 0, 1, 0,
 
204
                                      2, 0, 1, 0};
 
205
    uint bit;
 
206
    while ((bit= last_bit[bmp & 0xF]) == 32)
 
207
    {
 
208
      no += 4;
 
209
      bmp= bmp >> 4;
 
210
      if (!bmp)
 
211
        return BITMAP_END;
 
212
    }
 
213
    bmp &= ~(1 << bit);
 
214
    return no + bit;
 
215
  }
 
216
  enum { BITMAP_END= 64 };
 
217
};
 
218
 
 
219
 
 
220
#if 0
 
221
void print_bits(table_map bmp)
 
222
{
 
223
  Table_map_iterator it(bmp);
 
224
  int i, first= 1;
 
225
  fprintf(stderr, "0x%llx = ", bmp);
 
226
  while ((i= it.next_bit()) != Table_map_iterator::BITMAP_END)
 
227
  {
 
228
    fprintf(stderr, " %s 2^%d", (first?"":"+"), i);
 
229
    if (first)
 
230
      first= 0;
 
231
  }
 
232
  fprintf(stderr, "\n");
 
233
}
 
234
 
 
235
int main()
 
236
{
 
237
  print_bits(1024);
 
238
  print_bits(3);
 
239
  print_bits(0xF);
 
240
  print_bits(0xF0);
 
241
  print_bits(35);
 
242
  print_bits(1LL<<63);
 
243
  print_bits(0);
 
244
  print_bits(-1LL);
 
245
}
 
246
#endif
 
247
 
 
248
#endif /* _SQL_BITMAP_H_ */