← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.h

  • Committer: Mark Atwood
  • Date: 2008-10-16 11:33:16 UTC
  • mto: (520.1.13 drizzle)
  • mto: This revision was merged to the branch mainline in revision 530.
  • Revision ID: mark@fallenpegasus.com-20081016113316-ff6jdt31ck90sjdh
an implemention of the errmsg plugin

Show diffs side-by-side

added added

removed removed

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