MySQL 8.4.3
Source Code Documentation
sql_bitmap.h
Go to the documentation of this file.
1/* Copyright (c) 2003, 2024, 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 designed to work 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 either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24/*
25 Implementation of a bitmap type.
26 The idea with this is to be able to handle any constant number of bits but
27 also be able to use 32 or 64 bits bitmaps very efficiently
28*/
29
30#ifndef SQL_BITMAP_INCLUDED
31#define SQL_BITMAP_INCLUDED
32
33#include <assert.h>
34
35#include "dig_vec.h"
36#include "my_bitmap.h" // MY_BITMAP
37#include "my_byteorder.h" // int8store
38#include "mysql/strings/int2str.h" // longlong2str
39
40#include "template_utils.h"
41
42template <uint default_width>
43class Bitmap {
45 uint32 buffer[(default_width + 31) / 32];
46
47 public:
48 enum { ALL_BITS = default_width };
49 Bitmap() { init(); }
50 Bitmap(const Bitmap &from) { *this = from; }
51 explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
52 void init() { bitmap_init(&map, buffer, default_width); }
53 void init(uint prefix_to_set) {
54 init();
55 set_prefix(prefix_to_set);
56 }
57 uint length() const { return default_width; }
58 Bitmap &operator=(const Bitmap &map2) {
59 init();
60 memcpy(buffer, map2.buffer, sizeof(buffer));
61 return *this;
62 }
63 void set_bit(uint n) { bitmap_set_bit(&map, n); }
64 void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
65 void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
68 void intersect(const Bitmap &map2) { bitmap_intersect(&map, &map2.map); }
69 void intersect(ulonglong map2buff) {
70 // Use a spearate temporary buffer, as bitmap_init() clears all the bits.
71 ulonglong buf2;
72 MY_BITMAP map2;
73
74 bitmap_init(&map2, (uint32 *)&buf2, sizeof(ulonglong) * 8);
75
76 // Store the original bits.
77 if (sizeof(ulonglong) >= 8) {
79 const_cast<uchar *>(static_cast<uchar *>(static_cast<void *>(&buf2))),
80 map2buff);
81 } else {
82 assert(sizeof(buffer) >= 4);
84 const_cast<uchar *>(static_cast<uchar *>(static_cast<void *>(&buf2))),
85 static_cast<uint32>(map2buff));
86 }
87
88 bitmap_intersect(&map, &map2);
89 }
90 /* Use highest bit for all bits above sizeof(ulonglong)*8. */
92 intersect(map2buff);
93 if (map.n_bits > sizeof(ulonglong) * 8)
95 (map2buff & (1LL << (sizeof(ulonglong) * 8 - 1))));
96 }
97 void subtract(const Bitmap &map2) { bitmap_subtract(&map, &map2.map); }
98 void merge(const Bitmap &map2) { bitmap_union(&map, &map2.map); }
99 bool is_set(uint n) const { return bitmap_is_set(&map, n); }
100 bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
101 bool is_clear_all() const { return bitmap_is_clear_all(&map); }
102 bool is_set_all() const { return bitmap_is_set_all(&map); }
103 bool is_subset(const Bitmap &map2) const {
104 return bitmap_is_subset(&map, &map2.map);
105 }
106 bool is_overlapping(const Bitmap &map2) const {
107 return bitmap_is_overlapping(&map, &map2.map);
108 }
109 bool operator==(const Bitmap &map2) const {
110 return bitmap_cmp(&map, &map2.map);
111 }
112 bool operator!=(const Bitmap &map2) const { return !(*this == map2); }
113 char *print(char *buf) const {
114 char *s = buf;
115 const uchar *e = pointer_cast<const uchar *>(&buffer[0]);
116 const uchar *b = e + sizeof(buffer) - 1;
117 while (*b == 0 && b > e) {
118 b--;
119 }
120 *s = dig_vec_upper[*b >> 4];
121 if (*s != '0') {
122 s++;
123 }
124 *s++ = dig_vec_upper[*b & 15];
125 while (--b >= e) {
126 *s++ = dig_vec_upper[*b >> 4];
127 *s++ = dig_vec_upper[*b & 15];
128 }
129 *s = 0;
130 return buf;
131 }
133 if (sizeof(buffer) >= 8)
134 return uint8korr(
135 static_cast<const uchar *>(static_cast<const void *>(buffer)));
136 assert(sizeof(buffer) >= 4);
137 return (ulonglong)uint4korr(
138 static_cast<const uchar *>(static_cast<const void *>(buffer)));
139 }
140 uint bits_set() const { return bitmap_bits_set(&map); }
141 uint get_first_set() const { return bitmap_get_first_set(&map); }
142
143 /**
144 Find the next set bit after 'bit_no'.
145 @param bit_no Start search at bit_no+1.
146 @returns index of next set bit, or MY_BIT_NONE.
147 */
148 uint get_next_set(uint bit_no) const {
149 return bitmap_get_next_set(&map, bit_no);
150 }
151};
152
153template <>
154class Bitmap<64> {
156
157 public:
158 Bitmap() { init(); }
159 enum { ALL_BITS = 64 };
160
161 explicit Bitmap(uint prefix_to_set) { set_prefix(prefix_to_set); }
162 void init() { clear_all(); }
163 void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
164 uint length() const { return 64; }
165 void set_bit(uint n) {
166 assert(n < 64);
167 map |= ((ulonglong)1) << n;
168 }
169 void clear_bit(uint n) {
170 assert(n < 64);
171 map &= ~(((ulonglong)1) << n);
172 }
173 void set_prefix(uint n) {
174 if (n >= length())
175 set_all();
176 else
177 map = (((ulonglong)1) << n) - 1;
178 }
179 void set_all() { map = ~(ulonglong)0; }
180 void clear_all() { map = (ulonglong)0; }
181 void intersect(const Bitmap<64> &map2) { map &= map2.map; }
182 void intersect(ulonglong map2) { map &= map2; }
183 void intersect_extended(ulonglong map2) { map &= map2; }
184 void subtract(const Bitmap<64> &map2) { map &= ~map2.map; }
185 void merge(const Bitmap<64> &map2) { map |= map2.map; }
186 bool is_set(uint n) const {
187 assert(n < 64);
188 return (map & (((ulonglong)1) << n));
189 }
190 bool is_prefix(uint n) const {
191 assert(n <= 64);
192 if (n < 64)
193 return map == (((ulonglong)1) << n) - 1;
194 else
195 return map == ~(ulonglong)1;
196 }
197 bool is_clear_all() const { return map == (ulonglong)0; }
198 bool is_set_all() const { return map == ~(ulonglong)0; }
199 bool is_subset(const Bitmap<64> &map2) const { return !(map & ~map2.map); }
200 bool is_overlapping(const Bitmap<64> &map2) const {
201 return (map & map2.map) != 0;
202 }
203 bool operator==(const Bitmap<64> &map2) const { return map == map2.map; }
204 bool operator!=(const Bitmap<64> &map2) const { return !(*this == map2); }
205 char *print(char *buf) const {
206 longlong2str(map, buf, 16);
207 return buf;
208 }
209 ulonglong to_ulonglong() const { return map; }
210 uint bits_set() const {
211 uint res = 0;
212 for (uint i = 0; i < ALL_BITS; i++)
213 if (is_set(i)) res++;
214 return res;
215 }
216 uint get_first_set() const {
217 for (uint i = 0; i < ALL_BITS; i++)
218 if (map & (1ULL << i)) return i;
219 return MY_BIT_NONE;
220 }
221
222 /**
223 Find the next set bit after 'bit_no'.
224 @param bit_no Start search at bit_no+1.
225 @returns index of next set bit, or MY_BIT_NONE.
226 */
227 uint get_next_set(uint bit_no) const {
228 for (uint i = bit_no + 1; i < ALL_BITS; i++)
229 if (map & (1ULL << i)) return i;
230 return MY_BIT_NONE;
231 }
232};
233
234#if MAX_INDEXES <= 64
235typedef Bitmap<64> Key_map; /* Used for finding keys */
236#elif MAX_INDEXES > 255
237#error "MAX_INDEXES values greater than 255 is not supported."
238#else
239typedef Bitmap<((MAX_INDEXES + 7) / 8 * 8)> Key_map; /* Used for finding keys */
240#endif
241
242#endif /* SQL_BITMAP_INCLUDED */
Definition: sql_bitmap.h:154
char * print(char *buf) const
Definition: sql_bitmap.h:205
Bitmap(uint prefix_to_set)
Definition: sql_bitmap.h:161
bool is_set(uint n) const
Definition: sql_bitmap.h:186
void set_all()
Definition: sql_bitmap.h:179
bool operator==(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:203
Bitmap()
Definition: sql_bitmap.h:158
void init(uint prefix_to_set)
Definition: sql_bitmap.h:163
void intersect(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:181
void clear_all()
Definition: sql_bitmap.h:180
void set_bit(uint n)
Definition: sql_bitmap.h:165
uint bits_set() const
Definition: sql_bitmap.h:210
ulonglong to_ulonglong() const
Definition: sql_bitmap.h:209
ulonglong map
Definition: sql_bitmap.h:155
bool is_subset(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:199
void intersect(ulonglong map2)
Definition: sql_bitmap.h:182
uint length() const
Definition: sql_bitmap.h:164
void set_prefix(uint n)
Definition: sql_bitmap.h:173
bool is_overlapping(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:200
bool is_clear_all() const
Definition: sql_bitmap.h:197
bool is_set_all() const
Definition: sql_bitmap.h:198
uint get_first_set() const
Definition: sql_bitmap.h:216
void intersect_extended(ulonglong map2)
Definition: sql_bitmap.h:183
bool operator!=(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:204
void merge(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:185
void init()
Definition: sql_bitmap.h:162
void subtract(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:184
uint get_next_set(uint bit_no) const
Find the next set bit after 'bit_no'.
Definition: sql_bitmap.h:227
bool is_prefix(uint n) const
Definition: sql_bitmap.h:190
void clear_bit(uint n)
Definition: sql_bitmap.h:169
Definition: sql_bitmap.h:43
void intersect(const Bitmap &map2)
Definition: sql_bitmap.h:68
uint get_next_set(uint bit_no) const
Find the next set bit after 'bit_no'.
Definition: sql_bitmap.h:148
char * print(char *buf) const
Definition: sql_bitmap.h:113
@ ALL_BITS
Definition: sql_bitmap.h:48
void set_all()
Definition: sql_bitmap.h:66
Bitmap(uint prefix_to_set)
Definition: sql_bitmap.h:51
void intersect_extended(ulonglong map2buff)
Definition: sql_bitmap.h:91
void set_prefix(uint n)
Definition: sql_bitmap.h:65
void clear_all()
Definition: sql_bitmap.h:67
MY_BITMAP map
Definition: sql_bitmap.h:44
bool is_subset(const Bitmap &map2) const
Definition: sql_bitmap.h:103
void clear_bit(uint n)
Definition: sql_bitmap.h:64
void merge(const Bitmap &map2)
Definition: sql_bitmap.h:98
ulonglong to_ulonglong() const
Definition: sql_bitmap.h:132
bool is_set_all() const
Definition: sql_bitmap.h:102
void subtract(const Bitmap &map2)
Definition: sql_bitmap.h:97
bool is_prefix(uint n) const
Definition: sql_bitmap.h:100
Bitmap & operator=(const Bitmap &map2)
Definition: sql_bitmap.h:58
bool is_clear_all() const
Definition: sql_bitmap.h:101
uint length() const
Definition: sql_bitmap.h:57
uint get_first_set() const
Definition: sql_bitmap.h:141
uint32 buffer[(default_width+31)/32]
Definition: sql_bitmap.h:45
bool operator!=(const Bitmap &map2) const
Definition: sql_bitmap.h:112
void init()
Definition: sql_bitmap.h:52
void init(uint prefix_to_set)
Definition: sql_bitmap.h:53
bool operator==(const Bitmap &map2) const
Definition: sql_bitmap.h:109
void intersect(ulonglong map2buff)
Definition: sql_bitmap.h:69
Bitmap()
Definition: sql_bitmap.h:49
bool is_set(uint n) const
Definition: sql_bitmap.h:99
bool is_overlapping(const Bitmap &map2) const
Definition: sql_bitmap.h:106
void set_bit(uint n)
Definition: sql_bitmap.h:63
uint bits_set() const
Definition: sql_bitmap.h:140
Bitmap(const Bitmap &from)
Definition: sql_bitmap.h:50
static char buf[MAX_BUF]
Definition: conf_to_src.cc:73
constexpr std::array< const char, 37 > dig_vec_upper
Definition: dig_vec.h:34
static char * longlong2str(int64_t val, char *dst, int radix)
Definition: int2str.h:41
#define MY_BIT_NONE
Definition: my_bitmap.h:32
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:108
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:301
static void bitmap_set_all(MY_BITMAP *map)
Definition: my_bitmap.h:128
bool bitmap_is_clear_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:268
static bool bitmap_is_set(const MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:95
bool bitmap_is_set_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:257
static void bitmap_clear_all(MY_BITMAP *map)
Definition: my_bitmap.h:121
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:380
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:416
void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from)
Definition: my_bitmap.cc:335
uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
Get the next set bit.
Definition: my_bitmap.cc:462
void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit)
Definition: my_bitmap.cc:372
uint bitmap_get_first_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:439
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits)
Definition: my_bitmap.cc:140
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:389
static void bitmap_clear_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:90
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
Set the specified number of bits in the bitmap buffer.
Definition: my_bitmap.cc:201
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:281
static void bitmap_set_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:80
bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
Definition: my_bitmap.cc:218
Functions for reading and storing in machine-independent format.
void int4store(char *pT, uint32 A)
Definition: my_byteorder.h:180
ulonglong uint8korr(const char *pT)
Definition: my_byteorder.h:164
void int8store(char *pT, ulonglong A)
Definition: my_byteorder.h:192
uint32 uint4korr(const char *pT)
Definition: my_byteorder.h:152
#define MAX_INDEXES
Definition: my_config.h:210
unsigned long long int ulonglong
Definition: my_inttypes.h:56
unsigned char uchar
Definition: my_inttypes.h:52
uint32_t uint32
Definition: my_inttypes.h:67
Definition: buf0block_hint.cc:30
Bitmap< 64 > Key_map
Definition: sql_bitmap.h:235
Definition: my_bitmap.h:43
uint n_bits
Definition: my_bitmap.h:45
int n
Definition: xcom_base.cc:509