1/* Copyright (c) 2003, 2013, Oracle and/or its affiliates
2 Copyright (c) 2009, 2013, Monty Program Ab.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17/*
18 Implementation of a bitmap type.
19 The idea with this is to be able to handle any constant number of bits but
20 also be able to use 32 or 64 bits bitmaps very efficiently
21*/
22
23#ifndef SQL_BITMAP_INCLUDED
24#define SQL_BITMAP_INCLUDED
25
26#include <my_sys.h>
27#include <my_bitmap.h>
28
29template <uint default_width> class Bitmap
30{
31 MY_BITMAP map;
32 uint32 buffer[(default_width+31)/32];
33public:
34 Bitmap() { init(); }
35 Bitmap(const Bitmap& from) { *this=from; }
36 explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
37 void init() { my_bitmap_init(&map, buffer, default_width, 0); }
38 void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }
39 uint length() const { return default_width; }
40 Bitmap& operator=(const Bitmap& map2)
41 {
42 init();
43 memcpy(buffer, map2.buffer, sizeof(buffer));
44 return *this;
45 }
46 void set_bit(uint n) { bitmap_set_bit(&map, n); }
47 void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
48 void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
49 void set_all() { bitmap_set_all(&map); }
50 void clear_all() { bitmap_clear_all(&map); }
51 void intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
52 void intersect(ulonglong map2buff)
53 {
54 // Use a spearate temporary buffer, as bitmap_init() clears all the bits.
55 ulonglong buf2;
56 MY_BITMAP map2;
57
58 my_bitmap_init(&map2, (uint32 *) &buf2, sizeof(ulonglong) * 8, 0);
59
60 // Store the original bits.
61 if (sizeof(ulonglong) >= 8)
62 {
63 int8store(const_cast<uchar *>(static_cast<uchar *>
64 (static_cast<void *>(&buf2))),
65 map2buff);
66 }
67 else
68 {
69 DBUG_ASSERT(sizeof(buffer) >= 4);
70 int4store(const_cast<uchar *>(static_cast<uchar *>
71 (static_cast<void *>(&buf2))),
72 static_cast<uint32>(map2buff));
73 }
74
75 bitmap_intersect(&map, &map2);
76 }
77 /* Use highest bit for all bits above sizeof(ulonglong)*8. */
78 void intersect_extended(ulonglong map2buff)
79 {
80 intersect(map2buff);
81 if (map.n_bits > sizeof(ulonglong) * 8)
82 bitmap_set_above(&map, sizeof(ulonglong),
83 MY_TEST(map2buff & (1LL << (sizeof(ulonglong) * 8 - 1))));
84 }
85 void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
86 void merge(Bitmap& map2) { bitmap_union(&map, &map2.map); }
87 bool is_set(uint n) const { return bitmap_is_set(&map, n); }
88 bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
89 bool is_clear_all() const { return bitmap_is_clear_all(&map); }
90 bool is_set_all() const { return bitmap_is_set_all(&map); }
91 bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
92 bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
93 bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
94 bool operator!=(const Bitmap& map2) const { return !(*this == map2); }
95 char *print(char *buf) const
96 {
97 char *s=buf;
98 const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;
99 while (!*b && b>e)
100 b--;
101 if ((*s=_dig_vec_upper[*b >> 4]) != '0')
102 s++;
103 *s++=_dig_vec_upper[*b & 15];
104 while (--b>=e)
105 {
106 *s++=_dig_vec_upper[*b >> 4];
107 *s++=_dig_vec_upper[*b & 15];
108 }
109 *s=0;
110 return buf;
111 }
112 ulonglong to_ulonglong() const
113 {
114 if (sizeof(buffer) >= 8)
115 return uint8korr(static_cast<const uchar *>
116 (static_cast<const void *>(buffer)));
117 DBUG_ASSERT(sizeof(buffer) >= 4);
118 return (ulonglong)
119 uint4korr(static_cast<const uchar *>
120 (static_cast<const void *>(buffer)));
121 }
122 uint bits_set()
123 {
124 return bitmap_bits_set(&map);
125 }
126 class Iterator
127 {
128 Bitmap &map;
129 uint no;
130 public:
131 Iterator(Bitmap<default_width> &map2): map(map2), no(0) {}
132 int operator++(int) {
133 if (no == default_width) return BITMAP_END;
134 while (!map.is_set(no))
135 {
136 if ((++no) == default_width) return BITMAP_END;
137 }
138 return no ++;
139 }
140 enum { BITMAP_END= default_width };
141 };
142};
143
144/* An iterator to quickly walk over bits in ulonglong bitmap. */
145class Table_map_iterator
146{
147 ulonglong bmp;
148 uint no;
149public:
150 Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
151 uint next_bit()
152 {
153 static const uchar last_bit[16]= {32, 0, 1, 0,
154 2, 0, 1, 0,
155 3, 0, 1, 0,
156 2, 0, 1, 0};
157 uint bit;
158 while ((bit= last_bit[bmp & 0xF]) == 32)
159 {
160 no += 4;
161 bmp= bmp >> 4;
162 if (!bmp)
163 return BITMAP_END;
164 }
165 bmp &= ~(1ULL << bit);
166 return no + bit;
167 }
168 uint operator++(int) { return next_bit(); }
169 enum { BITMAP_END= 64 };
170};
171
172template <> class Bitmap<64>
173{
174 ulonglong map;
175public:
176 Bitmap<64>() { }
177 explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
178 void init() { }
179 void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
180 uint length() const { return 64; }
181 void set_bit(uint n) { map|= ((ulonglong)1) << n; }
182 void clear_bit(uint n) { map&= ~(((ulonglong)1) << n); }
183 void set_prefix(uint n)
184 {
185 if (n >= length())
186 set_all();
187 else
188 map= (((ulonglong)1) << n)-1;
189 }
190 void set_all() { map=~(ulonglong)0; }
191 void clear_all() { map=(ulonglong)0; }
192 void intersect(Bitmap<64>& map2) { map&= map2.map; }
193 void intersect(ulonglong map2) { map&= map2; }
194 void intersect_extended(ulonglong map2) { map&= map2; }
195 void subtract(Bitmap<64>& map2) { map&= ~map2.map; }
196 void merge(Bitmap<64>& map2) { map|= map2.map; }
197 bool is_set(uint n) const { return MY_TEST(map & (((ulonglong) 1) << n)); }
198 bool is_prefix(uint n) const { return map == (((ulonglong)1) << n)-1; }
199 bool is_clear_all() const { return map == (ulonglong)0; }
200 bool is_set_all() const { return map == ~(ulonglong)0; }
201 bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
202 bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
203 bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
204 char *print(char *buf) const {
205 longlong2str(longlong(map), buf, 16);
206 return buf;
207 }
208 ulonglong to_ulonglong() const { return map; }
209 class Iterator : public Table_map_iterator
210 {
211 public:
212 Iterator(Bitmap<64> &map2) : Table_map_iterator(map2.map) {}
213 };
214 uint bits_set()
215 {
216 //TODO: use my_count_bits()
217 uint res= 0, i= 0;
218 for (; i < 64 ; i++)
219 {
220 if (map & ((ulonglong)1<<i))
221 res++;
222 }
223 return res;
224 }
225};
226
227
228#endif /* SQL_BITMAP_INCLUDED */
229