MySQL  8.0.27
Source Code Documentation
sql_bitmap.h
Go to the documentation of this file.
1 /* Copyright (c) 2003, 2021, 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 
39 template <uint default_width>
40 class 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  }
60  void set_bit(uint n) { bitmap_set_bit(&map, n); }
63  void set_all() { bitmap_set_all(&map); }
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) {
75  int8store(
76  const_cast<uchar *>(static_cast<uchar *>(static_cast<void *>(&buf2))),
77  map2buff);
78  } else {
79  assert(sizeof(buffer) >= 4);
80  int4store(
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. */
88  void intersect_extended(ulonglong map2buff) {
89  intersect(map2buff);
90  if (map.n_bits > sizeof(ulonglong) * 8)
91  bitmap_set_above(&map, sizeof(ulonglong),
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 
136 template <>
137 class 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  }
152  void clear_bit(uint n) {
153  assert(n < 64);
154  map &= ~(((ulonglong)1) << n);
155  }
156  void set_prefix(uint n) {
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  }
199  uint get_first_set() const {
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
229 typedef 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
233 typedef 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
bool is_set(uint n) const
Definition: sql_bitmap.h:169
void set_all()
Definition: sql_bitmap.h:162
char * print(char *buf) const
Definition: sql_bitmap.h:188
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
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
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
char * print(char *buf) const
Definition: sql_bitmap.h:110
void subtract(const Bitmap &map2)
Definition: sql_bitmap.h:94
bool is_prefix(uint n) const
Definition: sql_bitmap.h:97
bool is_clear_all() const
Definition: sql_bitmap.h:98
uint length() const
Definition: sql_bitmap.h:54
@ ALL_BITS
Definition: sql_bitmap.h:45
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
Bitmap & operator=(const Bitmap &map2)
Definition: sql_bitmap.h:55
Definition: sql_bitmap.h:207
int next_bit()
Definition: sql_bitmap.h:213
@ BITMAP_END
Definition: sql_bitmap.h:225
Table_map_iterator(ulonglong t)
Definition: sql_bitmap.h:212
uint no
Definition: sql_bitmap.h:209
ulonglong bmp
Definition: sql_bitmap.h:208
#define MAX_INDEXES
Definition: config.h:206
char * longlong2str(int64_t val, char *dst, int radix)
Definition: m_string.h:303
#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:103
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:123
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:90
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:116
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:363
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:399
void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from)
Definition: my_bitmap.cc:318
void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit)
Definition: my_bitmap.cc:355
uint bitmap_get_first_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:422
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:372
static void bitmap_clear_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:85
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:75
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:41
uint n_bits
Definition: my_bitmap.h:43
unsigned int uint
Definition: uca-dump.cc:29
int n
Definition: xcom_base.cc:505