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