« back to all changes in this revision
Viewing changes to drizzled/sql_bitmap.h
- browse files at revision 1005.2.6
- compare with another revision
- compare with revision 383.1.33
- download diff
- download tarball
- view history from revision 1005.2.6
- Committer: Monty Taylor
- Date: 2009-05-09 22:13:47 UTC
- mto: This revision was merged to the branch mainline in revision 1009.
- Revision ID: mordred@inaugust.com-20090509221347-l712szviusbobro0
Re-added bitset<> as a replacement for Bitmap<>
- files added:
- drizzled/sql_bitmap.cc
- files modified:
- drizzled/Makefile.am
added
removed
drizzled/sql_bitmap.h
26
26
also be able to use 32 or 64 bits bitmaps very efficiently
27
27
*/
28
28
29
/// TODO: OMG FIX THIS
30
31
29
#include <mysys/my_bitmap.h>
30
#include <drizzled/definitions.h>
32
31
#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 operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
80
bool operator!=(const Bitmap& map2) const { return !bitmap_cmp(&map, &map2.map); }
81
Bitmap operator&=(uint32_t n)
82
{
83
if (bitmap_is_set(&map, n))
84
{
85
bitmap_clear_all(&map);
86
bitmap_set_bit(&map, n);
87
}
88
else
89
bitmap_clear_all(&map);
90
return *this;
91
}
92
Bitmap operator&=(const Bitmap& map2)
93
{
94
bitmap_intersect(&map, &map2.map);
95
return *this;
96
}
97
Bitmap operator&(uint32_t n)
98
{
99
Bitmap bm(*this);
100
bm&= n;
101
return bm;
102
}
103
Bitmap operator&(const Bitmap& map2)
104
{
105
Bitmap bm(*this);
106
bm&= map2;
107
return bm;
108
}
109
Bitmap operator|=(uint32_t n)
110
{
111
bitmap_set_bit(&map, n);
112
return *this;
113
}
114
Bitmap operator|=(const Bitmap& map2)
115
{
116
bitmap_union(&map, &map2.map);
117
}
118
Bitmap operator|(uint32_t n)
119
{
120
Bitmap bm(*this);
121
bm|= n;
122
return bm;
123
}
124
Bitmap operator|(const Bitmap& map2)
125
{
126
Bitmap bm(*this);
127
bm|= map2;
128
return bm;
129
}
130
Bitmap operator~()
131
{
132
Bitmap bm(*this);
133
bitmap_invert(&bm.map);
134
return bm;
135
}
136
char *print(char *buf) const
137
{
138
char *s=buf;
139
const unsigned char *e=(unsigned char *)buffer, *b=e+sizeof(buffer)-1;
140
while (!*b && b>e)
141
b--;
142
if ((*s=_dig_vec_upper[*b >> 4]) != '0')
143
s++;
144
*s++=_dig_vec_upper[*b & 15];
145
while (--b>=e)
146
{
147
*s++=_dig_vec_upper[*b >> 4];
148
*s++=_dig_vec_upper[*b & 15];
149
}
150
*s=0;
151
return buf;
152
}
153
uint64_t to_uint64_t() const
154
{
155
if (sizeof(buffer) >= 8)
156
return uint8korr(buffer);
157
assert(sizeof(buffer) >= 4);
158
return (uint64_t) uint4korr(buffer);
159
}
160
};
161
162
template <> class Bitmap<64>
163
{
164
uint64_t map;
165
public:
166
Bitmap<64>() : map(0) { }
167
explicit Bitmap<64>(uint32_t prefix_to_set) : map(0) { set_prefix(prefix_to_set); }
168
void init() { }
169
void init(uint32_t prefix_to_set) { set_prefix(prefix_to_set); }
170
uint32_t length() const { return 64; }
171
void set_bit(uint32_t n) { map|= ((uint64_t)1) << n; }
172
void clear_bit(uint32_t n) { map&= ~(((uint64_t)1) << n); }
173
void set_prefix(uint32_t n)
174
{
175
if (n >= length())
176
set_all();
177
else
178
map= (((uint64_t)1) << n)-1;
179
}
180
void set_all() { map=~(uint64_t)0; }
181
void clear_all() { map=(uint64_t)0; }
182
void intersect(Bitmap<64>& map2) { map&= map2.map; }
183
void intersect(uint64_t map2) { map&= map2; }
184
void intersect_extended(uint64_t map2) { map&= map2; }
185
void subtract(Bitmap<64>& map2) { map&= ~map2.map; }
186
void merge(Bitmap<64>& map2) { map|= map2.map; }
187
bool is_set(uint32_t n) const { return test(map & (((uint64_t)1) << n)); }
188
bool is_prefix(uint32_t n) const { return map == (((uint64_t)1) << n)-1; }
189
bool is_clear_all() const { return map == (uint64_t)0; }
190
bool is_set_all() const { return map == ~(uint64_t)0; }
191
bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
192
bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
193
bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
194
char *print(char *buf) const { int64_t2str(map,buf,16); return buf; }
195
uint64_t to_uint64_t() const { return map; }
196
};
32
#include <drizzled/key_map.h>
33
34
35
#include <bitset>
197
36
198
37
199
38
typedef uint64_t table_map; /* Used for table bits in join */
200
#if MAX_INDEXES <= 64
201
typedef Bitmap<64> key_map; /* Used for finding keys */
202
#else
203
typedef Bitmap<((MAX_INDEXES+7)/8*8)> key_map; /* Used for finding keys */
204
#endif
205
39
typedef uint32_t nesting_map; /* Used for flags of nesting constructs */
206
40
207
41
/*
211
45
*/
212
46
typedef uint64_t nested_join_map; /* Needed by sql_select.h and table.h */
213
47
214
/* useful constants */#
215
extern const key_map key_map_empty;
216
extern key_map key_map_full; /* Should be threaded as const */
48
/*
49
* Finds the first bit that is not set and sets
50
* it.
51
*
52
* @param the bitmap to work with
53
*/
54
uint32_t setNextBit(std::bitset<MAX_FIELDS> &bitmap);
55
56
/*
57
* Returns the position of the first bit in the
58
* given bitmap which is not set. If every bit is set
59
* in the bitmap, return BIT_NONE.
60
*
61
* @param the bitmap to work with
62
*/
63
uint32_t getFirstBitPos(const std::bitset<MAX_FIELDS> &bitmap);
64
65
/*
66
* Returns true if there is any overlapping bits between
67
* the 2 given bitmaps.
68
*
69
* @param the first bitmap to work with
70
* @param the second bitmap to work with
71
*/
72
bool isBitmapOverlapping(const std::bitset<MAX_FIELDS> &map1, const std::bitset<MAX_FIELDS> &map2);
73
217
74
218
75
#endif /* _SQL_BITMAP_H_ */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1