MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sql_bitmap.h
1 /* Copyright (c) 2003, 2010, 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 as published by
5  the Free Software Foundation; version 2 of the License.
6 
7  This program is distributed in the hope that it will be useful,
8  but WITHOUT ANY WARRANTY; without even the implied warranty of
9  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  GNU General Public License for more details.
11 
12  You should have received a copy of the GNU General Public License
13  along with this program; if not, write to the Free Software Foundation,
14  51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */
15 
16 /*
17  Implementation of a bitmap type.
18  The idea with this is to be able to handle any constant number of bits but
19  also be able to use 32 or 64 bits bitmaps very efficiently
20 */
21 
22 #ifndef SQL_BITMAP_INCLUDED
23 #define SQL_BITMAP_INCLUDED
24 
25 #include <my_sys.h>
26 #include <my_bitmap.h>
27 
28 template <uint default_width> class Bitmap
29 {
30  MY_BITMAP map;
31  uint32 buffer[(default_width+31)/32];
32 public:
33  Bitmap() { init(); }
34  Bitmap(const Bitmap& from) { *this=from; }
35  explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
36  void init() { bitmap_init(&map, buffer, default_width, 0); }
37  void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }
38  uint length() const { return default_width; }
39  Bitmap& operator=(const Bitmap& map2)
40  {
41  init();
42  memcpy(buffer, map2.buffer, sizeof(buffer));
43  return *this;
44  }
45  void set_bit(uint n) { bitmap_set_bit(&map, n); }
46  void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
47  void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
48  void set_all() { bitmap_set_all(&map); }
49  void clear_all() { bitmap_clear_all(&map); }
50  void intersect(const Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
51  void intersect(ulonglong map2buff)
52  {
53  MY_BITMAP map2;
54  bitmap_init(&map2, (uint32 *)&map2buff, sizeof(ulonglong)*8, 0);
55  bitmap_intersect(&map, &map2);
56  }
57  /* Use highest bit for all bits above sizeof(ulonglong)*8. */
58  void intersect_extended(ulonglong map2buff)
59  {
60  intersect(map2buff);
61  if (map.n_bits > sizeof(ulonglong) * 8)
62  bitmap_set_above(&map, sizeof(ulonglong),
63  test(map2buff & (LL(1) << (sizeof(ulonglong) * 8 - 1))));
64  }
65  void subtract(const Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
66  void merge(const Bitmap& map2) { bitmap_union(&map, &map2.map); }
67  my_bool is_set(uint n) const { return bitmap_is_set(&map, n); }
68  my_bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
69  my_bool is_clear_all() const { return bitmap_is_clear_all(&map); }
70  my_bool is_set_all() const { return bitmap_is_set_all(&map); }
71  my_bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
72  my_bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
73  my_bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
74  my_bool operator!=(const Bitmap& map2) const { return !(*this == map2); }
75  char *print(char *buf) const
76  {
77  char *s=buf;
78  const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;
79  while (!*b && b>e)
80  b--;
81  if ((*s=_dig_vec_upper[*b >> 4]) != '0')
82  s++;
83  *s++=_dig_vec_upper[*b & 15];
84  while (--b>=e)
85  {
86  *s++=_dig_vec_upper[*b >> 4];
87  *s++=_dig_vec_upper[*b & 15];
88  }
89  *s=0;
90  return buf;
91  }
92  ulonglong to_ulonglong() const
93  {
94  if (sizeof(buffer) >= 8)
95  return uint8korr(buffer);
96  DBUG_ASSERT(sizeof(buffer) >= 4);
97  return (ulonglong) uint4korr(buffer);
98  }
99  uint bits_set() const { return bitmap_bits_set(&map); }
100 };
101 
102 template <> class Bitmap<64>
103 {
104  ulonglong map;
105 public:
106  Bitmap<64>() { init(); }
107  enum { ALL_BITS = 64 };
108 
109 #if defined(__NETWARE__) || defined(__MWERKS__)
110  /*
111  Metwork compiler gives error on Bitmap<64>
112  Changed to Bitmap, since in this case also it will proper construct
113  this class
114  */
115  explicit Bitmap(uint prefix_to_set) { set_prefix(prefix_to_set); }
116 #else
117  explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
118 #endif
119  void init() { clear_all(); }
120  void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
121  uint length() const { return 64; }
122  void set_bit(uint n) { map|= ((ulonglong)1) << n; }
123  void clear_bit(uint n) { map&= ~(((ulonglong)1) << n); }
124  void set_prefix(uint n)
125  {
126  if (n >= length())
127  set_all();
128  else
129  map= (((ulonglong)1) << n)-1;
130  }
131  void set_all() { map=~(ulonglong)0; }
132  void clear_all() { map=(ulonglong)0; }
133  void intersect(const Bitmap<64>& map2) { map&= map2.map; }
134  void intersect(ulonglong map2) { map&= map2; }
135  void intersect_extended(ulonglong map2) { map&= map2; }
136  void subtract(const Bitmap<64>& map2) { map&= ~map2.map; }
137  void merge(const Bitmap<64>& map2) { map|= map2.map; }
138  my_bool is_set(uint n) const { return test(map & (((ulonglong)1) << n)); }
139  my_bool is_prefix(uint n) const { return map == (((ulonglong)1) << n)-1; }
140  my_bool is_clear_all() const { return map == (ulonglong)0; }
141  my_bool is_set_all() const { return map == ~(ulonglong)0; }
142  my_bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
143  my_bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
144  my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
145  my_bool operator!=(const Bitmap<64>& map2) const { return !(*this == map2); }
146  char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
147  ulonglong to_ulonglong() const { return map; }
148 };
149 
150 
151 /* An iterator to quickly walk over bits in unlonglong bitmap. */
152 class Table_map_iterator
153 {
154  ulonglong bmp;
155  uint no;
156 public:
157  Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
158  int next_bit()
159  {
160  static const char last_bit[16]= {32, 0, 1, 0,
161  2, 0, 1, 0,
162  3, 0, 1, 0,
163  2, 0, 1, 0};
164  uint bit;
165  while ((bit= last_bit[bmp & 0xF]) == 32)
166  {
167  no += 4;
168  bmp= bmp >> 4;
169  if (!bmp)
170  return BITMAP_END;
171  }
172  bmp &= ~(1LL << bit);
173  return no + bit;
174  }
175  enum { BITMAP_END= 64 };
176 };
177 #endif /* SQL_BITMAP_INCLUDED */