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