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 Foundation,
21    51 Franklin Street, Suite 500, Boston, MA 02110-1335 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 <my_sys.h>
33 #include <my_bitmap.h>
34 
35 template <uint default_width> class Bitmap
36 {
37   MY_BITMAP map;
38   uint32 buffer[(default_width+31)/32];
39 public:
40   enum { ALL_BITS= default_width };
Bitmap()41   Bitmap() { init(); }
Bitmap(const Bitmap & from)42   Bitmap(const Bitmap& from) { *this=from; }
Bitmap(uint prefix_to_set)43   explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
init()44   void init() { bitmap_init(&map, buffer, default_width, 0); }
init(uint prefix_to_set)45   void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }
length()46   uint length() const { return default_width; }
47   Bitmap& operator=(const Bitmap& map2)
48   {
49     init();
50     memcpy(buffer, map2.buffer, sizeof(buffer));
51     return *this;
52   }
set_bit(uint n)53   void set_bit(uint n) { bitmap_set_bit(&map, n); }
clear_bit(uint n)54   void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
set_prefix(uint n)55   void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
set_all()56   void set_all() { bitmap_set_all(&map); }
clear_all()57   void clear_all() { bitmap_clear_all(&map); }
intersect(const Bitmap & map2)58   void intersect(const Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
intersect(ulonglong map2buff)59   void intersect(ulonglong map2buff)
60   {
61     // Use a spearate temporary buffer, as bitmap_init() clears all the bits.
62     ulonglong buf2;
63     MY_BITMAP map2;
64 
65     bitmap_init(&map2, (uint32 *) &buf2, sizeof(ulonglong) * 8, 0);
66 
67     // Store the original bits.
68     if (sizeof(ulonglong) >= 8) {
69       int8store(const_cast<uchar *>(static_cast<uchar *>
70                                     (static_cast<void *>(&buf2))),
71                 map2buff);
72     } else {
73       assert(sizeof(buffer) >= 4);
74       int4store(const_cast<uchar *>(static_cast<uchar *>
75                                     (static_cast<void *>(&buf2))),
76                 static_cast<uint32>(map2buff));
77     }
78 
79     bitmap_intersect(&map, &map2);
80   }
81   /* Use highest bit for all bits above sizeof(ulonglong)*8. */
intersect_extended(ulonglong map2buff)82   void intersect_extended(ulonglong map2buff)
83   {
84     intersect(map2buff);
85     if (map.n_bits > sizeof(ulonglong) * 8)
86       bitmap_set_above(&map, sizeof(ulonglong),
87                        MY_TEST(map2buff & (1LL << (sizeof(ulonglong) * 8 - 1))));
88   }
subtract(const Bitmap & map2)89   void subtract(const Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
merge(const Bitmap & map2)90   void merge(const Bitmap& map2) { bitmap_union(&map, &map2.map); }
is_set(uint n)91   my_bool is_set(uint n) const { return bitmap_is_set(&map, n); }
is_prefix(uint n)92   my_bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
is_clear_all()93   my_bool is_clear_all() const { return bitmap_is_clear_all(&map); }
is_set_all()94   my_bool is_set_all() const { return bitmap_is_set_all(&map); }
is_subset(const Bitmap & map2)95   my_bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
is_overlapping(const Bitmap & map2)96   my_bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
97   my_bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
98   my_bool operator!=(const Bitmap& map2) const { return !(*this == map2); }
print(char * buf)99   char *print(char *buf) const
100   {
101     char *s=buf;
102     const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;
103     while (!*b && b>e)
104       b--;
105     if ((*s=_dig_vec_upper[*b >> 4]) != '0')
106         s++;
107     *s++=_dig_vec_upper[*b & 15];
108     while (--b>=e)
109     {
110       *s++=_dig_vec_upper[*b >> 4];
111       *s++=_dig_vec_upper[*b & 15];
112     }
113     *s=0;
114     return buf;
115   }
to_ulonglong()116   ulonglong to_ulonglong() const
117   {
118     if (sizeof(buffer) >= 8)
119       return uint8korr(static_cast<const uchar *>
120                        (static_cast<const void *>(buffer)));
121     assert(sizeof(buffer) >= 4);
122     return (ulonglong)
123       uint4korr(static_cast<const uchar *>
124                 (static_cast<const void *>(buffer)));
125   }
bits_set()126   uint bits_set() const { return bitmap_bits_set(&map); }
127 };
128 
129 template <> class Bitmap<64>
130 {
131   ulonglong map;
132 public:
133   Bitmap<64>() { init(); }
134   enum { ALL_BITS = 64 };
135 
136   explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
init()137   void init() { clear_all(); }
init(uint prefix_to_set)138   void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
length()139   uint length() const { return 64; }
set_bit(uint n)140   void set_bit(uint n) { assert(n < 64); map|= ((ulonglong)1) << n; }
clear_bit(uint n)141   void clear_bit(uint n) { assert(n < 64); map&= ~(((ulonglong)1) << n); }
set_prefix(uint n)142   void set_prefix(uint n)
143   {
144     if (n >= length())
145       set_all();
146     else
147       map= (((ulonglong)1) << n)-1;
148   }
set_all()149   void set_all() { map=~(ulonglong)0; }
clear_all()150   void clear_all() { map=(ulonglong)0; }
intersect(const Bitmap<64> & map2)151   void intersect(const Bitmap<64>& map2) { map&= map2.map; }
intersect(ulonglong map2)152   void intersect(ulonglong map2) { map&= map2; }
intersect_extended(ulonglong map2)153   void intersect_extended(ulonglong map2) { map&= map2; }
subtract(const Bitmap<64> & map2)154   void subtract(const Bitmap<64>& map2) { map&= ~map2.map; }
merge(const Bitmap<64> & map2)155   void merge(const Bitmap<64>& map2) { map|= map2.map; }
is_set(uint n)156   my_bool is_set(uint n) const
157   { assert(n < 64); return MY_TEST(map & (((ulonglong)1) << n)); }
is_prefix(uint n)158   my_bool is_prefix(uint n) const
159   {
160     assert(n <= 64);
161     if (n < 64)
162       return map == (((ulonglong)1) << n)-1;
163     else
164       return map == ~(ulonglong)1;
165   }
is_clear_all()166   my_bool is_clear_all() const { return map == (ulonglong)0; }
is_set_all()167   my_bool is_set_all() const { return map == ~(ulonglong)0; }
is_subset(const Bitmap<64> & map2)168   my_bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
is_overlapping(const Bitmap<64> & map2)169   my_bool is_overlapping(const Bitmap<64>& map2) const
170   { return (map & map2.map)!= 0; }
171   my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
172   my_bool operator!=(const Bitmap<64>& map2) const { return !(*this == map2); }
print(char * buf)173   char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
to_ulonglong()174   ulonglong to_ulonglong() const { return map; }
175 };
176 
177 
178 /* An iterator to quickly walk over bits in unlonglong bitmap. */
179 class Table_map_iterator
180 {
181   ulonglong bmp;
182   uint no;
183 public:
Table_map_iterator(ulonglong t)184   Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
next_bit()185   int next_bit()
186   {
187     static const char last_bit[16]= {32, 0, 1, 0,
188                                       2, 0, 1, 0,
189                                       3, 0, 1, 0,
190                                       2, 0, 1, 0};
191     uint bit;
192     while ((bit= last_bit[bmp & 0xF]) == 32)
193     {
194       no += 4;
195       bmp= bmp >> 4;
196       if (!bmp)
197         return BITMAP_END;
198     }
199     bmp &= ~(1LL << bit);
200     return no + bit;
201   }
202   enum { BITMAP_END= 64 };
203 };
204 #endif /* SQL_BITMAP_INCLUDED */
205