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