← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to server/sql_bitmap.h

Merged in from trunk.

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
 
#include <mysys/my_bitmap.h>
 
24
#include <my_bitmap.h>
30
25
 
31
 
template <uint32_t default_width> class Bitmap
 
26
template <uint default_width> class Bitmap
32
27
{
33
28
  MY_BITMAP map;
34
 
  uint32_t buffer[(default_width+31)/32];
 
29
  uint32 buffer[(default_width+31)/32];
35
30
public:
36
31
  Bitmap() { init(); }
37
32
  Bitmap(const Bitmap& from) { *this=from; }
38
 
  explicit Bitmap(uint32_t prefix_to_set) { init(prefix_to_set); }
 
33
  explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
39
34
  void init() { bitmap_init(&map, buffer, default_width, 0); }
40
 
  void init(uint32_t prefix_to_set) { init(); set_prefix(prefix_to_set); }
41
 
  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; }
42
37
  Bitmap& operator=(const Bitmap& map2)
43
38
  {
44
39
    init();
45
40
    memcpy(buffer, map2.buffer, sizeof(buffer));
46
41
    return *this;
47
42
  }
48
 
  void set_bit(uint32_t n) { bitmap_set_bit(&map, n); }
49
 
  void clear_bit(uint32_t n) { bitmap_clear_bit(&map, n); }
50
 
  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); }
51
46
  void set_all() { bitmap_set_all(&map); }
52
47
  void clear_all() { bitmap_clear_all(&map); }
53
48
  void intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
54
49
  void intersect(uint64_t map2buff)
55
50
  {
56
51
    MY_BITMAP map2;
57
 
    bitmap_init(&map2, (uint32_t *)&map2buff, sizeof(uint64_t)*8, 0);
 
52
    bitmap_init(&map2, (uint32 *)&map2buff, sizeof(uint64_t)*8, 0);
58
53
    bitmap_intersect(&map, &map2);
59
54
  }
60
55
  /* Use highest bit for all bits above sizeof(uint64_t)*8. */
67
62
  }
68
63
  void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
69
64
  void merge(Bitmap& map2) { bitmap_union(&map, &map2.map); }
70
 
  bool is_set(uint32_t n) const { return bitmap_is_set(&map, n); }
71
 
  bool is_set() const { return !bitmap_is_clear_all(&map); }
72
 
  bool is_prefix(uint32_t n) const { return bitmap_is_prefix(&map, n); }
73
 
  bool is_clear_all() const { return bitmap_is_clear_all(&map); }
74
 
  bool is_set_all() const { return bitmap_is_set_all(&map); }
75
 
  bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
76
 
  bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
77
 
  bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
78
 
  bool operator!=(const Bitmap& map2) const { return !bitmap_cmp(&map, &map2.map); }
79
 
  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)
80
75
  {
81
76
    if (bitmap_is_set(&map, n))
82
77
    {
92
87
    bitmap_intersect(&map, &map2.map);
93
88
    return *this;
94
89
  }
95
 
  Bitmap operator&(uint32_t n)
 
90
  Bitmap operator&(uint n)
96
91
  {
97
92
    Bitmap bm(*this);
98
93
    bm&= n;
104
99
    bm&= map2;
105
100
    return bm;
106
101
  }
107
 
  Bitmap operator|=(uint32_t n)
 
102
  Bitmap operator|=(uint n)
108
103
  {
109
104
    bitmap_set_bit(&map, n);
110
105
    return *this;
113
108
  {
114
109
    bitmap_union(&map, &map2.map);
115
110
  }
116
 
  Bitmap operator|(uint32_t n)
 
111
  Bitmap operator|(uint n)
117
112
  {
118
113
    Bitmap bm(*this);
119
114
    bm|= n;
134
129
  char *print(char *buf) const
135
130
  {
136
131
    char *s=buf;
137
 
    const unsigned char *e=(unsigned char *)buffer, *b=e+sizeof(buffer)-1;
 
132
    const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;
138
133
    while (!*b && b>e)
139
134
      b--;
140
135
    if ((*s=_dig_vec_upper[*b >> 4]) != '0')
162
157
  uint64_t map;
163
158
public:
164
159
  Bitmap<64>() { map= 0; }
165
 
  explicit Bitmap<64>(uint32_t prefix_to_set) { set_prefix(prefix_to_set); }
 
160
  explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
166
161
  void init() { }
167
 
  void init(uint32_t prefix_to_set) { set_prefix(prefix_to_set); }
168
 
  uint32_t length() const { return 64; }
169
 
  void set_bit(uint32_t n) { map|= ((uint64_t)1) << n; }
170
 
  void clear_bit(uint32_t n) { map&= ~(((uint64_t)1) << n); }
171
 
  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|= ((uint64_t)1) << n; }
 
165
  void clear_bit(uint n) { map&= ~(((uint64_t)1) << n); }
 
166
  void set_prefix(uint n)
172
167
  {
173
168
    if (n >= length())
174
169
      set_all();
182
177
  void intersect_extended(uint64_t map2) { map&= map2; }
183
178
  void subtract(Bitmap<64>& map2) { map&= ~map2.map; }
184
179
  void merge(Bitmap<64>& map2) { map|= map2.map; }
185
 
  bool is_set(uint32_t n) const { return test(map & (((uint64_t)1) << n)); }
186
 
  bool is_prefix(uint32_t n) const { return map == (((uint64_t)1) << n)-1; }
187
 
  bool is_clear_all() const { return map == (uint64_t)0; }
188
 
  bool is_set_all() const { return map == ~(uint64_t)0; }
189
 
  bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
190
 
  bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
191
 
  bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
 
180
  my_bool is_set(uint n) const { return test(map & (((uint64_t)1) << n)); }
 
181
  my_bool is_prefix(uint n) const { return map == (((uint64_t)1) << n)-1; }
 
182
  my_bool is_clear_all() const { return map == (uint64_t)0; }
 
183
  my_bool is_set_all() const { return map == ~(uint64_t)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; }
192
187
  char *print(char *buf) const { int64_t2str(map,buf,16); return buf; }
193
188
  uint64_t to_uint64_t() const { return map; }
194
189
};
198
193
class Table_map_iterator
199
194
{
200
195
  uint64_t bmp;
201
 
  uint32_t no;
 
196
  uint no;
202
197
public:
203
198
  Table_map_iterator(uint64_t t) : bmp(t), no(0) {}
204
199
  int next_bit()
207
202
                                      2, 0, 1, 0, 
208
203
                                      3, 0, 1, 0,
209
204
                                      2, 0, 1, 0};
210
 
    uint32_t bit;
 
205
    uint bit;
211
206
    while ((bit= last_bit[bmp & 0xF]) == 32)
212
207
    {
213
208
      no += 4;