MySQL 8.0.30
Source Code Documentation
sql_bitmap.h
Go to the documentation of this file.
1/* Copyright (c) 2003, 2022, 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#include "m_string.h" // longlong2str
34#include "my_bitmap.h" // MY_BITMAP
35#include "my_byteorder.h" // int8store
36
37#include "template_utils.h"
38
39template <uint default_width>
40class Bitmap {
42 uint32 buffer[(default_width + 31) / 32];
43
44 public:
45 enum { ALL_BITS = default_width };
46 Bitmap() { init(); }
47 Bitmap(const Bitmap &from) { *this = from; }
48 explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
49 void init() { bitmap_init(&map, buffer, default_width); }
50 void init(uint prefix_to_set) {
51 init();
52 set_prefix(prefix_to_set);
53 }
54 uint length() const { return default_width; }
55 Bitmap &operator=(const Bitmap &map2) {
56 init();
57 memcpy(buffer, map2.buffer, sizeof(buffer));
58 return *this;
59 }
65 void intersect(const Bitmap &map2) { bitmap_intersect(&map, &map2.map); }
66 void intersect(ulonglong map2buff) {
67 // Use a spearate temporary buffer, as bitmap_init() clears all the bits.
68 ulonglong buf2;
69 MY_BITMAP map2;
70
71 bitmap_init(&map2, (uint32 *)&buf2, sizeof(ulonglong) * 8);
72
73 // Store the original bits.
74 if (sizeof(ulonglong) >= 8) {
76 const_cast<uchar *>(static_cast<uchar *>(static_cast<void *>(&buf2))),
77 map2buff);
78 } else {
79 assert(sizeof(buffer) >= 4);
81 const_cast<uchar *>(static_cast<uchar *>(static_cast<void *>(&buf2))),
82 static_cast<uint32>(map2buff));
83 }
84
85 bitmap_intersect(&map, &map2);
86 }
87 /* Use highest bit for all bits above sizeof(ulonglong)*8. */
89 intersect(map2buff);
90 if (map.n_bits > sizeof(ulonglong) * 8)
92 (map2buff & (1LL << (sizeof(ulonglong) * 8 - 1))));
93 }
94 void subtract(const Bitmap &map2) { bitmap_subtract(&map, &map2.map); }
95 void merge(const Bitmap &map2) { bitmap_union(&map, &map2.map); }
96 bool is_set(uint n) const { return bitmap_is_set(&map, n); }
97 bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
98 bool is_clear_all() const { return bitmap_is_clear_all(&map); }
99 bool is_set_all() const { return bitmap_is_set_all(&map); }
100 bool is_subset(const Bitmap &map2) const {
101 return bitmap_is_subset(&map, &map2.map);
102 }
103 bool is_overlapping(const Bitmap &map2) const {
104 return bitmap_is_overlapping(&map, &map2.map);
105 }
106 bool operator==(const Bitmap &map2) const {
107 return bitmap_cmp(&map, &map2.map);
108 }
109 bool operator!=(const Bitmap &map2) const { return !(*this == map2); }
110 char *print(char *buf) const {
111 char *s = buf;
112 const uchar *e = pointer_cast<const uchar *>(&buffer[0]),
113 *b = e + sizeof(buffer) - 1;
114 while (!*b && b > e) b--;
115 if ((*s = _dig_vec_upper[*b >> 4]) != '0') s++;
116 *s++ = _dig_vec_upper[*b & 15];
117 while (--b >= e) {
118 *s++ = _dig_vec_upper[*b >> 4];
119 *s++ = _dig_vec_upper[*b & 15];
120 }
121 *s = 0;
122 return buf;
123 }
125 if (sizeof(buffer) >= 8)
126 return uint8korr(
127 static_cast<const uchar *>(static_cast<const void *>(buffer)));
128 assert(sizeof(buffer) >= 4);
129 return (ulonglong)uint4korr(
130 static_cast<const uchar *>(static_cast<const void *>(buffer)));
131 }
132 uint bits_set() const { return bitmap_bits_set(&map); }
134};
135
136template <>
137class Bitmap<64> {
139
140 public:
141 Bitmap<64>() { init(); }
142 enum { ALL_BITS = 64 };
143
144 explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
145 void init() { clear_all(); }
146 void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
147 uint length() const { return 64; }
148 void set_bit(uint n) {
149 assert(n < 64);
150 map |= ((ulonglong)1) << n;
151 }
153 assert(n < 64);
154 map &= ~(((ulonglong)1) << n);
155 }
157 if (n >= length())
158 set_all();
159 else
160 map = (((ulonglong)1) << n) - 1;
161 }
162 void set_all() { map = ~(ulonglong)0; }
163 void clear_all() { map = (ulonglong)0; }
164 void intersect(const Bitmap<64> &map2) { map &= map2.map; }
165 void intersect(ulonglong map2) { map &= map2; }
166 void intersect_extended(ulonglong map2) { map &= map2; }
167 void subtract(const Bitmap<64> &map2) { map &= ~map2.map; }
168 void merge(const Bitmap<64> &map2) { map |= map2.map; }
169 bool is_set(uint n) const {
170 assert(n < 64);
171 return (map & (((ulonglong)1) << n));
172 }
173 bool is_prefix(uint n) const {
174 assert(n <= 64);
175 if (n < 64)
176 return map == (((ulonglong)1) << n) - 1;
177 else
178 return map == ~(ulonglong)1;
179 }
180 bool is_clear_all() const { return map == (ulonglong)0; }
181 bool is_set_all() const { return map == ~(ulonglong)0; }
182 bool is_subset(const Bitmap<64> &map2) const { return !(map & ~map2.map); }
183 bool is_overlapping(const Bitmap<64> &map2) const {
184 return (map & map2.map) != 0;
185 }
186 bool operator==(const Bitmap<64> &map2) const { return map == map2.map; }
187 bool operator!=(const Bitmap<64> &map2) const { return !(*this == map2); }
188 char *print(char *buf) const {
189 longlong2str(map, buf, 16);
190 return buf;
191 }
192 ulonglong to_ulonglong() const { return map; }
193 uint bits_set() const {
194 uint res = 0;
195 for (uint i = 0; i < ALL_BITS; i++)
196 if (is_set(i)) res++;
197 return res;
198 }
200 for (uint i = 0; i < ALL_BITS; i++)
201 if (map & (1ULL << i)) return i;
202 return MY_BIT_NONE;
203 }
204};
205
206/* An iterator to quickly walk over bits in unlonglong bitmap. */
210
211 public:
213 int next_bit() {
214 static const char last_bit[16] = {32, 0, 1, 0, 2, 0, 1, 0,
215 3, 0, 1, 0, 2, 0, 1, 0};
216 uint bit;
217 while ((bit = last_bit[bmp & 0xF]) == 32) {
218 no += 4;
219 bmp = bmp >> 4;
220 if (!bmp) return BITMAP_END;
221 }
222 bmp &= ~(1LL << bit);
223 return no + bit;
224 }
225 enum { BITMAP_END = 64 };
226};
227
228#if MAX_INDEXES <= 64
229typedef Bitmap<64> Key_map; /* Used for finding keys */
230#elif MAX_INDEXES > 255
231#error "MAX_INDEXES values greater than 255 is not supported."
232#else
233typedef Bitmap<((MAX_INDEXES + 7) / 8 * 8)> Key_map; /* Used for finding keys */
234#endif
235
236#endif /* SQL_BITMAP_INCLUDED */
Definition: sql_bitmap.h:137
char * print(char *buf) const
Definition: sql_bitmap.h:188
bool is_set(uint n) const
Definition: sql_bitmap.h:169
void set_all()
Definition: sql_bitmap.h:162
bool operator==(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:186
void init(uint prefix_to_set)
Definition: sql_bitmap.h:146
void intersect(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:164
void clear_all()
Definition: sql_bitmap.h:163
void set_bit(uint n)
Definition: sql_bitmap.h:148
uint bits_set() const
Definition: sql_bitmap.h:193
ulonglong to_ulonglong() const
Definition: sql_bitmap.h:192
ulonglong map
Definition: sql_bitmap.h:138
bool is_subset(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:182
void intersect(ulonglong map2)
Definition: sql_bitmap.h:165
uint length() const
Definition: sql_bitmap.h:147
void set_prefix(uint n)
Definition: sql_bitmap.h:156
bool is_overlapping(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:183
bool is_clear_all() const
Definition: sql_bitmap.h:180
bool is_set_all() const
Definition: sql_bitmap.h:181
uint get_first_set() const
Definition: sql_bitmap.h:199
void intersect_extended(ulonglong map2)
Definition: sql_bitmap.h:166
bool operator!=(const Bitmap< 64 > &map2) const
Definition: sql_bitmap.h:187
void merge(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:168
void init()
Definition: sql_bitmap.h:145
void subtract(const Bitmap< 64 > &map2)
Definition: sql_bitmap.h:167
bool is_prefix(uint n) const
Definition: sql_bitmap.h:173
void clear_bit(uint n)
Definition: sql_bitmap.h:152
Definition: sql_bitmap.h:40
void intersect(const Bitmap &map2)
Definition: sql_bitmap.h:65
char * print(char *buf) const
Definition: sql_bitmap.h:110
void set_all()
Definition: sql_bitmap.h:63
Bitmap(uint prefix_to_set)
Definition: sql_bitmap.h:48
void intersect_extended(ulonglong map2buff)
Definition: sql_bitmap.h:88
void set_prefix(uint n)
Definition: sql_bitmap.h:62
void clear_all()
Definition: sql_bitmap.h:64
MY_BITMAP map
Definition: sql_bitmap.h:41
@ ALL_BITS
Definition: sql_bitmap.h:45
bool is_subset(const Bitmap &map2) const
Definition: sql_bitmap.h:100
void clear_bit(uint n)
Definition: sql_bitmap.h:61
void merge(const Bitmap &map2)
Definition: sql_bitmap.h:95
ulonglong to_ulonglong() const
Definition: sql_bitmap.h:124
bool is_set_all() const
Definition: sql_bitmap.h:99
void subtract(const Bitmap &map2)
Definition: sql_bitmap.h:94
bool is_prefix(uint n) const
Definition: sql_bitmap.h:97
Bitmap & operator=(const Bitmap &map2)
Definition: sql_bitmap.h:55
bool is_clear_all() const
Definition: sql_bitmap.h:98
uint length() const
Definition: sql_bitmap.h:54
uint get_first_set() const
Definition: sql_bitmap.h:133
uint32 buffer[(default_width+31)/32]
Definition: sql_bitmap.h:42
bool operator!=(const Bitmap &map2) const
Definition: sql_bitmap.h:109
void init()
Definition: sql_bitmap.h:49
void init(uint prefix_to_set)
Definition: sql_bitmap.h:50
bool operator==(const Bitmap &map2) const
Definition: sql_bitmap.h:106
void intersect(ulonglong map2buff)
Definition: sql_bitmap.h:66
Bitmap()
Definition: sql_bitmap.h:46
bool is_set(uint n) const
Definition: sql_bitmap.h:96
bool is_overlapping(const Bitmap &map2) const
Definition: sql_bitmap.h:103
void set_bit(uint n)
Definition: sql_bitmap.h:60
uint bits_set() const
Definition: sql_bitmap.h:132
Bitmap(const Bitmap &from)
Definition: sql_bitmap.h:47
Definition: sql_bitmap.h:207
int next_bit()
Definition: sql_bitmap.h:213
Table_map_iterator(ulonglong t)
Definition: sql_bitmap.h:212
uint no
Definition: sql_bitmap.h:209
ulonglong bmp
Definition: sql_bitmap.h:208
@ BITMAP_END
Definition: sql_bitmap.h:225
#define MAX_INDEXES
Definition: config.h:209
char * longlong2str(int64_t val, char *dst, int radix)
Definition: m_string.h:296
#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
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
const char _dig_vec_upper[]
Definition: my_hex_tools.cc:88
Definition: buf0block_hint.cc:29
Bitmap< 64 > Key_map
Definition: sql_bitmap.h:229
Definition: my_bitmap.h:42
uint n_bits
Definition: my_bitmap.h:44
unsigned int uint
Definition: uca-dump.cc:29
int n
Definition: xcom_base.cc:505