← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to server/sql_bitmap.h

Merging mainline

Show diffs side-by-side

added added

removed removed

Lines of Context:
server/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
1
#ifndef _SQL_BITMAP_H_
21
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 */
22
17
 
23
18
/*
24
19
  Implementation of a bitmap type.
26
21
  also be able to use 32 or 64 bits bitmaps very efficiently
27
22
*/
28
23
 
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
 
24
#include <my_bitmap.h>
 
25
 
 
26
template <uint default_width> class Bitmap
35
27
{
36
28
  MY_BITMAP map;
37
 
  uint32_t buffer[(default_width+31)/32];
 
29
  uint32 buffer[(default_width+31)/32];
38
30
public:
39
 
  Bitmap() : map() { init(); }
40
 
  Bitmap(const Bitmap& from) : map() { *this=from; }
41
 
  explicit Bitmap(uint32_t prefix_to_set) : map(0) { init(prefix_to_set); }
 
31
  Bitmap() { init(); }
 
32
  Bitmap(const Bitmap& from) { *this=from; }
 
33
  explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
42
34
  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; }
 
35
  void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }
 
36
  uint length() const { return default_width; }
45
37
  Bitmap& operator=(const Bitmap& map2)
46
38
  {
47
39
    init();
48
40
    memcpy(buffer, map2.buffer, sizeof(buffer));
49
41
    return *this;
50
42
  }
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); }
 
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); }
54
46
  void set_all() { bitmap_set_all(&map); }
55
47
  void clear_all() { bitmap_clear_all(&map); }
56
48
  void intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
57
 
  void intersect(uint64_t map2buff)
 
49
  void intersect(ulonglong map2buff)
58
50
  {
59
51
    MY_BITMAP map2;
60
 
    bitmap_init(&map2, (uint32_t *)&map2buff, sizeof(uint64_t)*8, 0);
 
52
    bitmap_init(&map2, (uint32 *)&map2buff, sizeof(ulonglong)*8, 0);
61
53
    bitmap_intersect(&map, &map2);
62
54
  }
63
 
  /* Use highest bit for all bits above sizeof(uint64_t)*8. */
64
 
  void intersect_extended(uint64_t map2buff)
 
55
  /* Use highest bit for all bits above sizeof(ulonglong)*8. */
 
56
  void intersect_extended(ulonglong map2buff)
65
57
  {
66
58
    intersect(map2buff);
67
59
    if (map.n_bits > sizeof(uint64_t) * 8)
70
62
  }
71
63
  void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
72
64
  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)
 
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)
83
75
  {
84
76
    if (bitmap_is_set(&map, n))
85
77
    {
95
87
    bitmap_intersect(&map, &map2.map);
96
88
    return *this;
97
89
  }
98
 
  Bitmap operator&(uint32_t n)
 
90
  Bitmap operator&(uint n)
99
91
  {
100
92
    Bitmap bm(*this);
101
93
    bm&= n;
107
99
    bm&= map2;
108
100
    return bm;
109
101
  }
110
 
  Bitmap operator|=(uint32_t n)
 
102
  Bitmap operator|=(uint n)
111
103
  {
112
104
    bitmap_set_bit(&map, n);
113
105
    return *this;
116
108
  {
117
109
    bitmap_union(&map, &map2.map);
118
110
  }
119
 
  Bitmap operator|(uint32_t n)
 
111
  Bitmap operator|(uint n)
120
112
  {
121
113
    Bitmap bm(*this);
122
114
    bm|= n;
137
129
  char *print(char *buf) const
138
130
  {
139
131
    char *s=buf;
140
 
    const unsigned char *e=(unsigned char *)buffer, *b=e+sizeof(buffer)-1;
 
132
    const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;
141
133
    while (!*b && b>e)
142
134
      b--;
143
135
    if ((*s=_dig_vec_upper[*b >> 4]) != '0')
151
143
    *s=0;
152
144
    return buf;
153
145
  }
154
 
  uint64_t to_uint64_t() const
 
146
  ulonglong to_ulonglong() const
155
147
  {
156
148
    if (sizeof(buffer) >= 8)
157
149
      return uint8korr(buffer);
158
150
    assert(sizeof(buffer) >= 4);
159
 
    return (uint64_t) uint4korr(buffer);
 
151
    return (ulonglong) uint4korr(buffer);
160
152
  }
161
153
};
162
154
 
163
155
template <> class Bitmap<64>
164
156
{
165
 
  uint64_t map;
 
157
  ulonglong map;
166
158
public:
167
 
  Bitmap<64>() : map(0) { }
168
 
  explicit Bitmap<64>(uint32_t prefix_to_set) : map(0) { set_prefix(prefix_to_set); }
 
159
  Bitmap<64>() { map= 0; }
 
160
  explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
169
161
  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)
 
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|= ((ulonglong)1) << n; }
 
165
  void clear_bit(uint n) { map&= ~(((ulonglong)1) << n); }
 
166
  void set_prefix(uint n)
175
167
  {
176
168
    if (n >= length())
177
169
      set_all();
178
170
    else
179
 
      map= (((uint64_t)1) << n)-1;
 
171
      map= (((ulonglong)1) << n)-1;
180
172
  }
181
 
  void set_all() { map=~(uint64_t)0; }
182
 
  void clear_all() { map=(uint64_t)0; }
 
173
  void set_all() { map=~(ulonglong)0; }
 
174
  void clear_all() { map=(ulonglong)0; }
183
175
  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; }
 
176
  void intersect(ulonglong map2) { map&= map2; }
 
177
  void intersect_extended(ulonglong map2) { map&= map2; }
186
178
  void subtract(Bitmap<64>& map2) { map&= ~map2.map; }
187
179
  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; }
 
180
  my_bool is_set(uint n) const { return test(map & (((ulonglong)1) << n)); }
 
181
  my_bool is_prefix(uint n) const { return map == (((ulonglong)1) << n)-1; }
 
182
  my_bool is_clear_all() const { return map == (ulonglong)0; }
 
183
  my_bool is_set_all() const { return map == ~(ulonglong)0; }
 
184
  my_bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
 
185
  my_bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
 
186
  my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
 
187
  char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
 
188
  ulonglong to_ulonglong() const { return map; }
197
189
};
198
190
 
199
191
 
200
 
/* An iterator to quickly walk over bits in unint64_t bitmap. */
 
192
/* An iterator to quickly walk over bits in unlonglong bitmap. */
201
193
class Table_map_iterator
202
194
{
203
 
  uint64_t bmp;
204
 
  uint32_t no;
 
195
  ulonglong bmp;
 
196
  uint no;
205
197
public:
206
 
  Table_map_iterator(uint64_t t) : bmp(t), no(0) {}
 
198
  Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
207
199
  int next_bit()
208
200
  {
209
201
    static const char last_bit[16]= {32, 0, 1, 0, 
210
202
                                      2, 0, 1, 0, 
211
203
                                      3, 0, 1, 0,
212
204
                                      2, 0, 1, 0};
213
 
    uint32_t bit;
 
205
    uint bit;
214
206
    while ((bit= last_bit[bmp & 0xF]) == 32)
215
207
    {
216
208
      no += 4;