← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.h

  • Committer: Brian Aker
  • Date: 2010-05-27 01:25:56 UTC
  • mfrom: (1567.1.4 new-staging)
  • Revision ID: brian@gaz-20100527012556-5zgkirkl7swbigd6
Merge of Brian, Paul. PBXT compile issue, and test framework cleanup. 

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