1 /* Copyright (c) 2003, 2013, Oracle and/or its affiliates 2 Copyright (c) 2009, 2013, Monty Program Ab. 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; version 2 of the License. 7 8 This program is distributed in the hope that it will be useful, 9 but WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 GNU General Public License for more details. 12 13 You should have received a copy of the GNU General Public License 14 along with this program; if not, write to the Free Software 15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */ 16 17 /* 18 Implementation of a bitmap type. 19 The idea with this is to be able to handle any constant number of bits but 20 also be able to use 32 or 64 bits bitmaps very efficiently 21 */ 22 23 #ifndef SQL_BITMAP_INCLUDED 24 #define SQL_BITMAP_INCLUDED 25 26 #include <my_sys.h> 27 #include <my_bitmap.h> 28 29 template <uint default_width> class Bitmap 30 { 31 MY_BITMAP map; 32 uint32 buffer[(default_width+31)/32]; 33 public: Bitmap()34 Bitmap() { init(); } Bitmap(const Bitmap & from)35 Bitmap(const Bitmap& from) { *this=from; } Bitmap(uint prefix_to_set)36 explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); } init()37 void init() { my_bitmap_init(&map, buffer, default_width, 0); } init(uint prefix_to_set)38 void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); } length()39 uint length() const { return default_width; } 40 Bitmap& operator=(const Bitmap& map2) 41 { 42 init(); 43 memcpy(buffer, map2.buffer, sizeof(buffer)); 44 return *this; 45 } set_bit(uint n)46 void set_bit(uint n) { bitmap_set_bit(&map, n); } clear_bit(uint n)47 void clear_bit(uint n) { bitmap_clear_bit(&map, n); } set_prefix(uint n)48 void set_prefix(uint n) { bitmap_set_prefix(&map, n); } set_all()49 void set_all() { bitmap_set_all(&map); } clear_all()50 void clear_all() { bitmap_clear_all(&map); } intersect(Bitmap & map2)51 void intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); } intersect(ulonglong map2buff)52 void intersect(ulonglong map2buff) 53 { 54 // Use a spearate temporary buffer, as bitmap_init() clears all the bits. 55 ulonglong buf2; 56 MY_BITMAP map2; 57 58 my_bitmap_init(&map2, (uint32 *) &buf2, sizeof(ulonglong) * 8, 0); 59 60 // Store the original bits. 61 if (sizeof(ulonglong) >= 8) 62 { 63 int8store(const_cast<uchar *>(static_cast<uchar *> 64 (static_cast<void *>(&buf2))), 65 map2buff); 66 } 67 else 68 { 69 DBUG_ASSERT(sizeof(buffer) >= 4); 70 int4store(const_cast<uchar *>(static_cast<uchar *> 71 (static_cast<void *>(&buf2))), 72 static_cast<uint32>(map2buff)); 73 } 74 75 bitmap_intersect(&map, &map2); 76 } 77 /* Use highest bit for all bits above sizeof(ulonglong)*8. */ intersect_extended(ulonglong map2buff)78 void intersect_extended(ulonglong map2buff) 79 { 80 intersect(map2buff); 81 if (map.n_bits > sizeof(ulonglong) * 8) 82 bitmap_set_above(&map, sizeof(ulonglong), 83 MY_TEST(map2buff & (1LL << (sizeof(ulonglong) * 8 - 1)))); 84 } subtract(Bitmap & map2)85 void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); } merge(Bitmap & map2)86 void merge(Bitmap& map2) { bitmap_union(&map, &map2.map); } is_set(uint n)87 bool is_set(uint n) const { return bitmap_is_set(&map, n); } is_prefix(uint n)88 bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); } is_clear_all()89 bool is_clear_all() const { return bitmap_is_clear_all(&map); } is_set_all()90 bool is_set_all() const { return bitmap_is_set_all(&map); } is_subset(const Bitmap & map2)91 bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); } is_overlapping(const Bitmap & map2)92 bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); } 93 bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); } 94 bool operator!=(const Bitmap& map2) const { return !(*this == map2); } print(char * buf)95 char *print(char *buf) const 96 { 97 char *s=buf; 98 const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1; 99 while (!*b && b>e) 100 b--; 101 if ((*s=_dig_vec_upper[*b >> 4]) != '0') 102 s++; 103 *s++=_dig_vec_upper[*b & 15]; 104 while (--b>=e) 105 { 106 *s++=_dig_vec_upper[*b >> 4]; 107 *s++=_dig_vec_upper[*b & 15]; 108 } 109 *s=0; 110 return buf; 111 } to_ulonglong()112 ulonglong to_ulonglong() const 113 { 114 if (sizeof(buffer) >= 8) 115 return uint8korr(static_cast<const uchar *> 116 (static_cast<const void *>(buffer))); 117 DBUG_ASSERT(sizeof(buffer) >= 4); 118 return (ulonglong) 119 uint4korr(static_cast<const uchar *> 120 (static_cast<const void *>(buffer))); 121 } bits_set()122 uint bits_set() 123 { 124 return bitmap_bits_set(&map); 125 } 126 class Iterator 127 { 128 Bitmap ↦ 129 uint no; 130 public: Iterator(Bitmap<default_width> & map2)131 Iterator(Bitmap<default_width> &map2): map(map2), no(0) {} 132 int operator++(int) { 133 if (no == default_width) return BITMAP_END; 134 while (!map.is_set(no)) 135 { 136 if ((++no) == default_width) return BITMAP_END; 137 } 138 return no ++; 139 } 140 enum { BITMAP_END= default_width }; 141 }; 142 }; 143 144 /* An iterator to quickly walk over bits in ulonglong bitmap. */ 145 class Table_map_iterator 146 { 147 ulonglong bmp; 148 uint no; 149 public: Table_map_iterator(ulonglong t)150 Table_map_iterator(ulonglong t) : bmp(t), no(0) {} next_bit()151 uint next_bit() 152 { 153 static const uchar last_bit[16]= {32, 0, 1, 0, 154 2, 0, 1, 0, 155 3, 0, 1, 0, 156 2, 0, 1, 0}; 157 uint bit; 158 while ((bit= last_bit[bmp & 0xF]) == 32) 159 { 160 no += 4; 161 bmp= bmp >> 4; 162 if (!bmp) 163 return BITMAP_END; 164 } 165 bmp &= ~(1ULL << bit); 166 return no + bit; 167 } 168 uint operator++(int) { return next_bit(); } 169 enum { BITMAP_END= 64 }; 170 }; 171 172 template <> class Bitmap<64> 173 { 174 ulonglong map; 175 public: 176 Bitmap<64>() { } 177 explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); } init()178 void init() { } init(uint prefix_to_set)179 void init(uint prefix_to_set) { set_prefix(prefix_to_set); } length()180 uint length() const { return 64; } set_bit(uint n)181 void set_bit(uint n) { map|= ((ulonglong)1) << n; } clear_bit(uint n)182 void clear_bit(uint n) { map&= ~(((ulonglong)1) << n); } set_prefix(uint n)183 void set_prefix(uint n) 184 { 185 if (n >= length()) 186 set_all(); 187 else 188 map= (((ulonglong)1) << n)-1; 189 } set_all()190 void set_all() { map=~(ulonglong)0; } clear_all()191 void clear_all() { map=(ulonglong)0; } intersect(Bitmap<64> & map2)192 void intersect(Bitmap<64>& map2) { map&= map2.map; } intersect(ulonglong map2)193 void intersect(ulonglong map2) { map&= map2; } intersect_extended(ulonglong map2)194 void intersect_extended(ulonglong map2) { map&= map2; } subtract(Bitmap<64> & map2)195 void subtract(Bitmap<64>& map2) { map&= ~map2.map; } merge(Bitmap<64> & map2)196 void merge(Bitmap<64>& map2) { map|= map2.map; } is_set(uint n)197 bool is_set(uint n) const { return MY_TEST(map & (((ulonglong) 1) << n)); } is_prefix(uint n)198 bool is_prefix(uint n) const { return map == (((ulonglong)1) << n)-1; } is_clear_all()199 bool is_clear_all() const { return map == (ulonglong)0; } is_set_all()200 bool is_set_all() const { return map == ~(ulonglong)0; } is_subset(const Bitmap<64> & map2)201 bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); } is_overlapping(const Bitmap<64> & map2)202 bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; } 203 bool operator==(const Bitmap<64>& map2) const { return map == map2.map; } print(char * buf)204 char *print(char *buf) const { 205 longlong2str(longlong(map), buf, 16); 206 return buf; 207 } to_ulonglong()208 ulonglong to_ulonglong() const { return map; } 209 class Iterator : public Table_map_iterator 210 { 211 public: Iterator(Bitmap<64> & map2)212 Iterator(Bitmap<64> &map2) : Table_map_iterator(map2.map) {} 213 }; bits_set()214 uint bits_set() 215 { 216 //TODO: use my_count_bits() 217 uint res= 0, i= 0; 218 for (; i < 64 ; i++) 219 { 220 if (map & ((ulonglong)1<<i)) 221 res++; 222 } 223 return res; 224 } 225 }; 226 227 228 #endif /* SQL_BITMAP_INCLUDED */ 229