← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to sql/sql_bitmap.h

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/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 <my_bitmap.h>
 
25
 
 
26
template <uint default_width> class Bitmap
 
27
{
 
28
  MY_BITMAP map;
 
29
  uint32 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(ulonglong map2buff)
 
50
  {
 
51
    MY_BITMAP map2;
 
52
    bitmap_init(&map2, (uint32 *)&map2buff, sizeof(ulonglong)*8, 0);
 
53
    bitmap_intersect(&map, &map2);
 
54
  }
 
55
  /* Use highest bit for all bits above sizeof(ulonglong)*8. */
 
56
  void intersect_extended(ulonglong map2buff)
 
57
  {
 
58
    intersect(map2buff);
 
59
    if (map.n_bits > sizeof(ulonglong) * 8)
 
60
      bitmap_set_above(&map, sizeof(ulonglong),
 
61
                       test(map2buff & (LL(1) << (sizeof(ulonglong) * 8 - 1))));
 
62
  }
 
63
  void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
 
64
  void merge(Bitmap& map2) { bitmap_union(&map, &map2.map); }
 
65
  my_bool is_set(uint n) const { return bitmap_is_set(&map, n); }
 
66
  my_bool is_set() const { return !bitmap_is_clear_all(&map); }
 
67
  my_bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
 
68
  my_bool is_clear_all() const { return bitmap_is_clear_all(&map); }
 
69
  my_bool is_set_all() const { return bitmap_is_set_all(&map); }
 
70
  my_bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
 
71
  my_bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
 
72
  my_bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
 
73
  my_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
  ulonglong to_ulonglong() const
 
147
  {
 
148
    if (sizeof(buffer) >= 8)
 
149
      return uint8korr(buffer);
 
150
    DBUG_ASSERT(sizeof(buffer) >= 4);
 
151
    return (ulonglong) uint4korr(buffer);
 
152
  }
 
153
};
 
154
 
 
155
template <> class Bitmap<64>
 
156
{
 
157
  ulonglong map;
 
158
public:
 
159
  Bitmap<64>() { map= 0; }
 
160
#if defined(__NETWARE__) || defined(__MWERKS__)
 
161
  /*
 
162
    Metwork compiler gives error on Bitmap<64>
 
163
    Changed to Bitmap, since in this case also it will proper construct
 
164
    this class
 
165
  */
 
166
  explicit Bitmap(uint prefix_to_set) { set_prefix(prefix_to_set); }
 
167
#else
 
168
  explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
 
169
#endif
 
170
  void init() { }
 
171
  void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
 
172
  uint length() const { return 64; }
 
173
  void set_bit(uint n) { map|= ((ulonglong)1) << n; }
 
174
  void clear_bit(uint n) { map&= ~(((ulonglong)1) << n); }
 
175
  void set_prefix(uint n)
 
176
  {
 
177
    if (n >= length())
 
178
      set_all();
 
179
    else
 
180
      map= (((ulonglong)1) << n)-1;
 
181
  }
 
182
  void set_all() { map=~(ulonglong)0; }
 
183
  void clear_all() { map=(ulonglong)0; }
 
184
  void intersect(Bitmap<64>& map2) { map&= map2.map; }
 
185
  void intersect(ulonglong map2) { map&= map2; }
 
186
  void intersect_extended(ulonglong map2) { map&= map2; }
 
187
  void subtract(Bitmap<64>& map2) { map&= ~map2.map; }
 
188
  void merge(Bitmap<64>& map2) { map|= map2.map; }
 
189
  my_bool is_set(uint n) const { return test(map & (((ulonglong)1) << n)); }
 
190
  my_bool is_prefix(uint n) const { return map == (((ulonglong)1) << n)-1; }
 
191
  my_bool is_clear_all() const { return map == (ulonglong)0; }
 
192
  my_bool is_set_all() const { return map == ~(ulonglong)0; }
 
193
  my_bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
 
194
  my_bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
 
195
  my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
 
196
  char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
 
197
  ulonglong to_ulonglong() const { return map; }
 
198
};
 
199
 
 
200
 
 
201
/* An iterator to quickly walk over bits in unlonglong bitmap. */
 
202
class Table_map_iterator
 
203
{
 
204
  ulonglong bmp;
 
205
  uint no;
 
206
public:
 
207
  Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
 
208
  int next_bit()
 
209
  {
 
210
    static const char last_bit[16]= {32, 0, 1, 0, 
 
211
                                      2, 0, 1, 0, 
 
212
                                      3, 0, 1, 0,
 
213
                                      2, 0, 1, 0};
 
214
    uint bit;
 
215
    while ((bit= last_bit[bmp & 0xF]) == 32)
 
216
    {
 
217
      no += 4;
 
218
      bmp= bmp >> 4;
 
219
      if (!bmp)
 
220
        return BITMAP_END;
 
221
    }
 
222
    bmp &= ~(1LL << bit);
 
223
    return no + bit;
 
224
  }
 
225
  enum { BITMAP_END= 64 };
 
226
};
 
227
 
 
228
 
 
229
#if 0
 
230
void print_bits(table_map bmp)
 
231
{
 
232
  Table_map_iterator it(bmp);
 
233
  int i, first= 1;
 
234
  fprintf(stderr, "0x%llx = ", bmp);
 
235
  while ((i= it.next_bit()) != Table_map_iterator::BITMAP_END)
 
236
  {
 
237
    fprintf(stderr, " %s 2^%d", (first?"":"+"), i);
 
238
    if (first)
 
239
      first= 0;
 
240
  }
 
241
  fprintf(stderr, "\n");
 
242
}
 
243
 
 
244
int main()
 
245
{
 
246
  print_bits(1024);
 
247
  print_bits(3);
 
248
  print_bits(0xF);
 
249
  print_bits(0xF0);
 
250
  print_bits(35);
 
251
  print_bits(1LL<<63);
 
252
  print_bits(0);
 
253
  print_bits(-1LL);
 
254
}
 
255
#endif
 
256
 
 
257
#endif /* _SQL_BITMAP_H_ */