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