← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.h

  • Committer: Moriyoshi Koizumi
  • Date: 2008-11-15 18:36:31 UTC
  • mto: (584.1.5 devel)
  • mto: This revision was merged to the branch mainline in revision 588.
  • Revision ID: mozo@mozo.jp-20081115183631-81d0clowyot42mk7
Incorporating changes proposed by mtaylor.

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() : map() { init(); }
 
40
  Bitmap(const Bitmap& from) : map() { *this=from; }
 
41
  explicit Bitmap(uint32_t prefix_to_set) : map(0) { 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) : map(0) { 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
typedef uint64_t table_map;          /* Used for table bits in join */
 
201
#if MAX_INDEXES <= 64
 
202
typedef Bitmap<64>  key_map;          /* Used for finding keys */
 
203
#else
 
204
typedef Bitmap<((MAX_INDEXES+7)/8*8)> key_map; /* Used for finding keys */
 
205
#endif
 
206
typedef uint32_t nesting_map;  /* Used for flags of nesting constructs */
 
207
 
 
208
/*
 
209
  Used to identify NESTED_JOIN structures within a join (applicable only to
 
210
  structures that have not been simplified away and embed more the one
 
211
  element)
 
212
*/
 
213
typedef uint64_t nested_join_map; /* Needed by sql_select.h and table.h */
 
214
 
 
215
/* useful constants */#
 
216
extern const key_map key_map_empty;
 
217
extern key_map key_map_full;          /* Should be threaded as const */
 
218
extern const char *primary_key_name;
 
219
 
 
220
#endif /* _SQL_BITMAP_H_ */