MySQL 8.2.0
Source Code Documentation
sql_bitmap.h
Go to the documentation of this file.
1/* Copyright (c) 2003, 2023, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
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#ifndef SQL_BITMAP_INCLUDED
30#define SQL_BITMAP_INCLUDED
31
32#include <assert.h>
33
34#include "dig_vec.h"
35#include "my_bitmap.h" // MY_BITMAP
36#include "my_byteorder.h" // int8store
37#include "mysql/strings/int2str.h" // longlong2str
38
39#include "template_utils.h"
40
41template <uint default_width>
42class Bitmap {
44 uint32 buffer[(default_width + 31) / 32];
45
46 public:
47 enum { ALL_BITS = default_width };
48 Bitmap() { init(); }
49 Bitmap(const Bitmap &from) { *this = from; }
50 explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
51 void init() { bitmap_init(&map, buffer, default_width); }
52 void init(uint prefix_to_set) {
53 init();
54 set_prefix(prefix_to_set);
55 }
56 uint length() const { return default_width; }
57 Bitmap &operator=(const Bitmap &map2) {
58 init();
59 memcpy(buffer, map2.buffer, sizeof(buffer));
60 return *this;
61 }
62 void set_bit(uint n) { bitmap_set_bit(&map, n); }
63 void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
64 void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
67 void intersect(const Bitmap &map2) { bitmap_intersect(&map, &map2.map); }
68 void intersect(ulonglong map2buff) {
69 // Use a spearate temporary buffer, as bitmap_init() clears all the bits.
70 ulonglong buf2;
71 MY_BITMAP map2;
72
73 bitmap_init(&map2, (uint32 *)&buf2, sizeof(ulonglong) * 8);
74
75 // Store the original bits.
76 if (sizeof(ulonglong) >= 8) {
78 const_cast<uchar *>(static_cast<uchar *>(static_cast<void *>(&buf2))),
79 map2buff);
80 } else {
81 assert(sizeof(buffer) >= 4);
83 const_cast<uchar *>(static_cast<uchar *>(static_cast<void *>(&buf2))),
84 static_cast<uint32>(map2buff));
85 }
86
87 bitmap_intersect(&map, &map2);
88 }
89 /* Use highest bit for all bits above sizeof(ulonglong)*8. */
91 intersect(map2buff);
92 if (map.n_bits > sizeof(ulonglong) * 8)
94 (map2buff & (1LL << (sizeof(ulonglong) * 8 - 1))));
95 }
96 void subtract(const Bitmap &map2) { bitmap_subtract(&map, &map2.map); }
97 void merge(const Bitmap &map2) { bitmap_union(&map, &map2.map); }
98 bool is_set(uint n) const { return bitmap_is_set(&map, n); }
99 bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
100 bool is_clear_all() const { return bitmap_is_clear_all(&map); }
101 bool is_set_all() const { return bitmap_is_set_all(&map); }
102 bool is_subset(const Bitmap &map2) const {
103 return bitmap_is_subset(&map, &map2.map);
104 }
105 bool is_overlapping(const Bitmap &map2) const {
106 return bitmap_is_overlapping(&map, &map2.map);
107 }
108 bool operator==(const Bitmap &map2) const {
109 return bitmap_cmp(&map, &map2.map);
110 }
111 bool operator!=(const Bitmap &map2) const { return !(*this == map2); }
112 char *print(char *buf) const {
113 char *s = buf;
114 const uchar *e = pointer_cast<const uchar *>(&buffer[0]);
115 const uchar *b = e + sizeof(buffer) - 1;
116 while (*b == 0 && b > e) {
117 b--;
118 }
119 *s = dig_vec_upper[*b >> 4];
120 if (*s != '0') {
121 s++;
122 }
123 *s++ = dig_vec_upper[*b & 15];
124 while (--b >= e) {
125 *s++ = dig_vec_upper[*b >> 4];
126 *s++ = dig_vec_upper[*b & 15];
127 }
128 *s = 0;
129 return buf;
130 }
132 if (sizeof(buffer) >= 8)
133 return uint8korr(
134 static_cast<const uchar *>(static_cast<const void *>(buffer)));
135 assert(sizeof(buffer) >= 4);
136 return (ulonglong)uint4korr(
137 static_cast<const uchar *>(static_cast<const void *>(buffer)));
138 }
139 uint bits_set() const { return bitmap_bits_set(&map); }
140 uint get_first_set() const { return bitmap_get_first_set(&map); }
141
142 /**
143 Find the next set bit after 'bit_no'.
144 @param bit_no Start search at bit_no+1.
145 @returns index of next set bit, or MY_BIT_NONE.
146 */
147 uint get_next_set(uint bit_no) const {
148 return bitmap_get_next_set(&map, bit_no);
149 }
150};
151
152template <>
153class Bitmap<64> {
155
156 public:
157 Bitmap() { init(); }
158 enum { ALL_BITS = 64 };
159
160 explicit Bitmap(uint prefix_to_set) { set_prefix(prefix_to_set); }
161 void init() { clear_all(); }
162 void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
163 uint length() const { return 64; }
164 void set_bit(uint n) {
165 assert(n < 64);
166 map |= ((ulonglong)1) << n;
167 }
168 void clear_bit(uint n) {
169 assert(n < 64);
170 map &= ~(((ulonglong)1) << n);
171 }
172 void set_prefix(uint n) {
173 if (n >= length())
174 set_all();
175 else
176 map = (((ulonglong)1) << n) - 1;
177 }
178 void set_all() { map = ~(ulonglong)0; }
179 void clear_all() { map = (ulonglong)0; }
180 void intersect(const Bitmap<64> &map2) { map &= map2.map; }
181 void intersect(ulonglong map2) { map &= map2; }
182 void intersect_extended(ulonglong map2) { map &= map2; }
183 void subtract(const Bitmap<64> &map2) { map &= ~map2.map; }
184 void merge(const Bitmap<64> &map2) { map |= map2.map; }
185 bool is_set(uint n) const {
186 assert(n < 64);
187 return (map & (((ulonglong)1) << n));
188 }
189 bool is_prefix(uint n) const {
190 assert(n <= 64);
191 if (n < 64)
192 return map == (((ulonglong)1) << n) - 1;
193 else
194 return map == ~(ulonglong)1;
195 }
196 bool is_clear_all() const { return map == (ulonglong)0; }
197 bool is_set_all() const { return map == ~(ulonglong)0; }
198 bool is_subset(const Bitmap<64> &map2) const { return !(map & ~map2.map); }
199 bool is_overlapping(const Bitmap<64> &map2) const {
200 return (map & map2.map) != 0;
201 }
202 bool operator==(const Bitmap<64> &map2) const { return map == map2.map; }
203 bool operator!=(const Bitmap<64> &map2) const { return !(*this == map2); }
204 char *print(char *buf) const {
205 longlong2str(map, buf, 16);
206 return buf;
207 }
208 ulonglong to_ulonglong() const { return map; }
209 uint bits_set() const {
210 uint res = 0;
211 for (uint i = 0; i < ALL_BITS; i++)
212 if (is_set(i)) res++;
213 return res;
214 }
215 uint get_first_set() const {
216 for (uint i = 0; i < ALL_BITS; i++)
217 if (map & (1ULL << i)) return i;
218 return MY_BIT_NONE;
219 }
220
221 /**
222 Find the next set bit after 'bit_no'.
223 @param bit_no Start search at bit_no+1.
224 @returns index of next set bit, or MY_BIT_NONE.
225 */
226 uint get_next_set(uint bit_no) const {
227 for (uint i = bit_no + 1; i < ALL_BITS; i++)
228 if (map & (1ULL << i)) return i;
229 return MY_BIT_NONE;
230 }
231};
232
233/* An iterator to quickly walk over bits in unlonglong bitmap. */
236 uint no;
237
238 public:
240 int next_bit() {
241 static const char last_bit[16] = {32, 0, 1, 0, 2, 0, 1, 0,
242 3, 0, 1, 0, 2, 0, 1, 0};
243 uint bit;
244 while ((bit = last_bit[bmp & 0xF]) == 32) {
245 no += 4;
246 bmp = bmp >> 4;
247 if (!bmp) return BITMAP_END;
248 }
249 bmp &= ~(1LL << bit);
250 return no + bit;
251 }
252 enum { BITMAP_END = 64 };
253};
254
255#if MAX_INDEXES <= 64
256typedef Bitmap<64> Key_map; /* Used for finding keys */
257#elif MAX_INDEXES > 255
258#error "MAX_INDEXES values greater than 255 is not supported."
259#else
260typedef Bitmap<((MAX_INDEXES + 7) / 8 * 8)> Key_map; /* Used for finding keys */
261#endif
262
263#endif /* SQL_BITMAP_INCLUDED */
Definition: sql_bitmap.h:153
char * print(char *buf) const
Definition: sql_bitmap.h:204
Bitmap(uint prefix_to_set)
Definition: sql_bitmap.h:160
bool is_set(uint n) const
Definition: sql_bitmap.h:185
void set_all()
Definition: sql_bitmap.h:178
bool operator==(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:202
Bitmap()
Definition: sql_bitmap.h:157
void init(uint prefix_to_set)
Definition: sql_bitmap.h:162
void intersect(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:180
void clear_all()
Definition: sql_bitmap.h:179
void set_bit(uint n)
Definition: sql_bitmap.h:164
uint bits_set() const
Definition: sql_bitmap.h:209
ulonglong to_ulonglong() const
Definition: sql_bitmap.h:208
ulonglong map
Definition: sql_bitmap.h:154
bool is_subset(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:198
void intersect(ulonglong map2)
Definition: sql_bitmap.h:181
uint length() const
Definition: sql_bitmap.h:163
void set_prefix(uint n)
Definition: sql_bitmap.h:172
bool is_overlapping(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:199
bool is_clear_all() const
Definition: sql_bitmap.h:196
bool is_set_all() const
Definition: sql_bitmap.h:197
uint get_first_set() const
Definition: sql_bitmap.h:215
void intersect_extended(ulonglong map2)
Definition: sql_bitmap.h:182
bool operator!=(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:203
void merge(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:184
void init()
Definition: sql_bitmap.h:161
void subtract(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:183
uint get_next_set(uint bit_no) const
Find the next set bit after 'bit_no'.
Definition: sql_bitmap.h:226
bool is_prefix(uint n) const
Definition: sql_bitmap.h:189
void clear_bit(uint n)
Definition: sql_bitmap.h:168
Definition: sql_bitmap.h:42
void intersect(const Bitmap &map2)
Definition: sql_bitmap.h:67
uint get_next_set(uint bit_no) const
Find the next set bit after 'bit_no'.
Definition: sql_bitmap.h:147
char * print(char *buf) const
Definition: sql_bitmap.h:112
void set_all()
Definition: sql_bitmap.h:65
Bitmap(uint prefix_to_set)
Definition: sql_bitmap.h:50
void intersect_extended(ulonglong map2buff)
Definition: sql_bitmap.h:90
void set_prefix(uint n)
Definition: sql_bitmap.h:64
void clear_all()
Definition: sql_bitmap.h:66
MY_BITMAP map
Definition: sql_bitmap.h:43
@ ALL_BITS
Definition: sql_bitmap.h:47
bool is_subset(const Bitmap &map2) const
Definition: sql_bitmap.h:102
void clear_bit(uint n)
Definition: sql_bitmap.h:63
void merge(const Bitmap &map2)
Definition: sql_bitmap.h:97
ulonglong to_ulonglong() const
Definition: sql_bitmap.h:131
bool is_set_all() const
Definition: sql_bitmap.h:101
void subtract(const Bitmap &map2)
Definition: sql_bitmap.h:96
bool is_prefix(uint n) const
Definition: sql_bitmap.h:99
Bitmap & operator=(const Bitmap &map2)
Definition: sql_bitmap.h:57
bool is_clear_all() const
Definition: sql_bitmap.h:100
uint length() const
Definition: sql_bitmap.h:56
uint get_first_set() const
Definition: sql_bitmap.h:140
uint32 buffer[(default_width+31)/32]
Definition: sql_bitmap.h:44
bool operator!=(const Bitmap &map2) const
Definition: sql_bitmap.h:111
void init()
Definition: sql_bitmap.h:51
void init(uint prefix_to_set)
Definition: sql_bitmap.h:52
bool operator==(const Bitmap &map2) const
Definition: sql_bitmap.h:108
void intersect(ulonglong map2buff)
Definition: sql_bitmap.h:68
Bitmap()
Definition: sql_bitmap.h:48
bool is_set(uint n) const
Definition: sql_bitmap.h:98
bool is_overlapping(const Bitmap &map2) const
Definition: sql_bitmap.h:105
void set_bit(uint n)
Definition: sql_bitmap.h:62
uint bits_set() const
Definition: sql_bitmap.h:139
Bitmap(const Bitmap &from)
Definition: sql_bitmap.h:49
Definition: sql_bitmap.h:234
int next_bit()
Definition: sql_bitmap.h:240
Table_map_iterator(ulonglong t)
Definition: sql_bitmap.h:239
uint no
Definition: sql_bitmap.h:236
ulonglong bmp
Definition: sql_bitmap.h:235
@ BITMAP_END
Definition: sql_bitmap.h:252
static char buf[MAX_BUF]
Definition: conf_to_src.cc:72
constexpr std::array< const char, 37 > dig_vec_upper
Definition: dig_vec.h:33
#define MAX_INDEXES
Definition: config.h:209
static char * longlong2str(int64_t val, char *dst, int radix)
Definition: int2str.h:40
#define MY_BIT_NONE
Definition: my_bitmap.h:31
static bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
Quite unlike other C comparison functions ending with 'cmp', e.g.
Definition: my_bitmap.h:107
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:300
static void bitmap_set_all(MY_BITMAP *map)
Definition: my_bitmap.h:127
bool bitmap_is_clear_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:267
static bool bitmap_is_set(const MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:94
bool bitmap_is_set_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:256
static void bitmap_clear_all(MY_BITMAP *map)
Definition: my_bitmap.h:120
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:379
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:415
void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from)
Definition: my_bitmap.cc:334
uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
Get the next set bit.
Definition: my_bitmap.cc:461
void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit)
Definition: my_bitmap.cc:371
uint bitmap_get_first_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:438
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits)
Definition: my_bitmap.cc:139
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:388
static void bitmap_clear_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:89
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
Set the specified number of bits in the bitmap buffer.
Definition: my_bitmap.cc:200
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:280
static void bitmap_set_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:79
bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
Definition: my_bitmap.cc:217
Functions for reading and storing in machine-independent format.
void int4store(char *pT, uint32 A)
Definition: my_byteorder.h:172
ulonglong uint8korr(const char *pT)
Definition: my_byteorder.h:156
void int8store(char *pT, ulonglong A)
Definition: my_byteorder.h:184
uint32 uint4korr(const char *pT)
Definition: my_byteorder.h:144
unsigned long long int ulonglong
Definition: my_inttypes.h:55
unsigned char uchar
Definition: my_inttypes.h:51
uint32_t uint32
Definition: my_inttypes.h:66
Definition: buf0block_hint.cc:29
Bitmap< 64 > Key_map
Definition: sql_bitmap.h:256
Definition: my_bitmap.h:42
uint n_bits
Definition: my_bitmap.h:44
int n
Definition: xcom_base.cc:508