1 /* Copyright (c) 2003, 2020, 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 {
40   MY_BITMAP map;
41   uint32 buffer[(default_width + 31) / 32];
42 
43  public:
44   enum { ALL_BITS = default_width };
Bitmap()45   Bitmap() { init(); }
Bitmap(const Bitmap & from)46   Bitmap(const Bitmap &from) { *this = from; }
Bitmap(uint prefix_to_set)47   explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
init()48   void init() { bitmap_init(&map, buffer, default_width); }
init(uint prefix_to_set)49   void init(uint prefix_to_set) {
50     init();
51     set_prefix(prefix_to_set);
52   }
length()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   }
set_bit(uint n)59   void set_bit(uint n) { bitmap_set_bit(&map, n); }
clear_bit(uint n)60   void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
set_prefix(uint n)61   void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
set_all()62   void set_all() { bitmap_set_all(&map); }
clear_all()63   void clear_all() { bitmap_clear_all(&map); }
intersect(const Bitmap & map2)64   void intersect(const Bitmap &map2) { bitmap_intersect(&map, &map2.map); }
intersect(ulonglong map2buff)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. */
intersect_extended(ulonglong map2buff)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   }
subtract(const Bitmap & map2)93   void subtract(const Bitmap &map2) { bitmap_subtract(&map, &map2.map); }
merge(const Bitmap & map2)94   void merge(const Bitmap &map2) { bitmap_union(&map, &map2.map); }
is_set(uint n)95   bool is_set(uint n) const { return bitmap_is_set(&map, n); }
is_prefix(uint n)96   bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
is_clear_all()97   bool is_clear_all() const { return bitmap_is_clear_all(&map); }
is_set_all()98   bool is_set_all() const { return bitmap_is_set_all(&map); }
is_subset(const Bitmap & map2)99   bool is_subset(const Bitmap &map2) const {
100     return bitmap_is_subset(&map, &map2.map);
101   }
is_overlapping(const Bitmap & map2)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); }
print(char * buf)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   }
to_ulonglong()123   ulonglong to_ulonglong() const {
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   }
bits_set()131   uint bits_set() const { return bitmap_bits_set(&map); }
get_first_set()132   uint get_first_set() { return bitmap_get_first_set(&map); }
133 };
134 
135 template <>
136 class Bitmap<64> {
137   ulonglong map;
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); }
init()144   void init() { clear_all(); }
init(uint prefix_to_set)145   void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
length()146   uint length() const { return 64; }
set_bit(uint n)147   void set_bit(uint n) {
148     DBUG_ASSERT(n < 64);
149     map |= ((ulonglong)1) << n;
150   }
clear_bit(uint n)151   void clear_bit(uint n) {
152     DBUG_ASSERT(n < 64);
153     map &= ~(((ulonglong)1) << n);
154   }
set_prefix(uint n)155   void set_prefix(uint n) {
156     if (n >= length())
157       set_all();
158     else
159       map = (((ulonglong)1) << n) - 1;
160   }
set_all()161   void set_all() { map = ~(ulonglong)0; }
clear_all()162   void clear_all() { map = (ulonglong)0; }
intersect(const Bitmap<64> & map2)163   void intersect(const Bitmap<64> &map2) { map &= map2.map; }
intersect(ulonglong map2)164   void intersect(ulonglong map2) { map &= map2; }
intersect_extended(ulonglong map2)165   void intersect_extended(ulonglong map2) { map &= map2; }
subtract(const Bitmap<64> & map2)166   void subtract(const Bitmap<64> &map2) { map &= ~map2.map; }
merge(const Bitmap<64> & map2)167   void merge(const Bitmap<64> &map2) { map |= map2.map; }
is_set(uint n)168   bool is_set(uint n) const {
169     DBUG_ASSERT(n < 64);
170     return (map & (((ulonglong)1) << n));
171   }
is_prefix(uint n)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   }
is_clear_all()179   bool is_clear_all() const { return map == (ulonglong)0; }
is_set_all()180   bool is_set_all() const { return map == ~(ulonglong)0; }
is_subset(const Bitmap<64> & map2)181   bool is_subset(const Bitmap<64> &map2) const { return !(map & ~map2.map); }
is_overlapping(const Bitmap<64> & map2)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); }
print(char * buf)187   char *print(char *buf) const {
188     longlong2str(map, buf, 16);
189     return buf;
190   }
to_ulonglong()191   ulonglong to_ulonglong() const { return map; }
bits_set()192   uint bits_set() const {
193     uint res = 0;
194     for (uint i = 0; i < ALL_BITS; i++)
195       if (is_set(i)) res++;
196     return res;
197   }
get_first_set()198   uint get_first_set() const {
199     for (uint i = 0; i < ALL_BITS; i++)
200       if (map & (1ULL << i)) return i;
201     return MY_BIT_NONE;
202   }
203 };
204 
205 /* An iterator to quickly walk over bits in unlonglong bitmap. */
206 class Table_map_iterator {
207   ulonglong bmp;
208   uint no;
209 
210  public:
Table_map_iterator(ulonglong t)211   Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
next_bit()212   int next_bit() {
213     static const char last_bit[16] = {32, 0, 1, 0, 2, 0, 1, 0,
214                                       3,  0, 1, 0, 2, 0, 1, 0};
215     uint bit;
216     while ((bit = last_bit[bmp & 0xF]) == 32) {
217       no += 4;
218       bmp = bmp >> 4;
219       if (!bmp) return BITMAP_END;
220     }
221     bmp &= ~(1LL << bit);
222     return no + bit;
223   }
224   enum { BITMAP_END = 64 };
225 };
226 
227 #if MAX_INDEXES <= 64
228 typedef Bitmap<64> Key_map; /* Used for finding keys */
229 #elif MAX_INDEXES > 255
230 #error "MAX_INDEXES values greater than 255 is not supported."
231 #else
232 typedef Bitmap<((MAX_INDEXES + 7) / 8 * 8)> Key_map; /* Used for finding keys */
233 #endif
234 
235 #endif /* SQL_BITMAP_INCLUDED */
236