My Project
sql_bitmap.h
00001 /* Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software Foundation,
00014    51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */
00015 
00016 /*
00017   Implementation of a bitmap type.
00018   The idea with this is to be able to handle any constant number of bits but
00019   also be able to use 32 or 64 bits bitmaps very efficiently
00020 */
00021 
00022 #ifndef SQL_BITMAP_INCLUDED
00023 #define SQL_BITMAP_INCLUDED
00024 
00025 #include <my_sys.h>
00026 #include <my_bitmap.h>
00027 
00028 template <uint default_width> class Bitmap
00029 {
00030   MY_BITMAP map;
00031   uint32 buffer[(default_width+31)/32];
00032 public:
00033   Bitmap() { init(); }
00034   Bitmap(const Bitmap& from) { *this=from; }
00035   explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
00036   void init() { bitmap_init(&map, buffer, default_width, 0); }
00037   void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }
00038   uint length() const { return default_width; }
00039   Bitmap& operator=(const Bitmap& map2)
00040   {
00041     init();
00042     memcpy(buffer, map2.buffer, sizeof(buffer));
00043     return *this;
00044   }
00045   void set_bit(uint n) { bitmap_set_bit(&map, n); }
00046   void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
00047   void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
00048   void set_all() { bitmap_set_all(&map); }
00049   void clear_all() { bitmap_clear_all(&map); }
00050   void intersect(const Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
00051   void intersect(ulonglong map2buff)
00052   {
00053     MY_BITMAP map2;
00054     bitmap_init(&map2, (uint32 *)&map2buff, sizeof(ulonglong)*8, 0);
00055     bitmap_intersect(&map, &map2);
00056   }
00057   /* Use highest bit for all bits above sizeof(ulonglong)*8. */
00058   void intersect_extended(ulonglong map2buff)
00059   {
00060     intersect(map2buff);
00061     if (map.n_bits > sizeof(ulonglong) * 8)
00062       bitmap_set_above(&map, sizeof(ulonglong),
00063                        MY_TEST(map2buff & (LL(1) << (sizeof(ulonglong) * 8 - 1))));
00064   }
00065   void subtract(const Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
00066   void merge(const Bitmap& map2) { bitmap_union(&map, &map2.map); }
00067   my_bool is_set(uint n) const { return bitmap_is_set(&map, n); }
00068   my_bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
00069   my_bool is_clear_all() const { return bitmap_is_clear_all(&map); }
00070   my_bool is_set_all() const { return bitmap_is_set_all(&map); }
00071   my_bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
00072   my_bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
00073   my_bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
00074   my_bool operator!=(const Bitmap& map2) const { return !(*this == map2); }
00075   char *print(char *buf) const
00076   {
00077     char *s=buf;
00078     const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;
00079     while (!*b && b>e)
00080       b--;
00081     if ((*s=_dig_vec_upper[*b >> 4]) != '0')
00082         s++;
00083     *s++=_dig_vec_upper[*b & 15];
00084     while (--b>=e)
00085     {
00086       *s++=_dig_vec_upper[*b >> 4];
00087       *s++=_dig_vec_upper[*b & 15];
00088     }
00089     *s=0;
00090     return buf;
00091   }
00092   ulonglong to_ulonglong() const
00093   {
00094     if (sizeof(buffer) >= 8)
00095       return uint8korr(buffer);
00096     DBUG_ASSERT(sizeof(buffer) >= 4);
00097     return (ulonglong) uint4korr(buffer);
00098   }
00099   uint bits_set() const { return bitmap_bits_set(&map); }
00100 };
00101 
00102 template <> class Bitmap<64>
00103 {
00104   ulonglong map;
00105 public:
00106   Bitmap<64>() { init(); }
00107   enum { ALL_BITS = 64 };
00108 
00109 #if defined(__NETWARE__) || defined(__MWERKS__)
00110   /*
00111     Metwork compiler gives error on Bitmap<64>
00112     Changed to Bitmap, since in this case also it will proper construct
00113     this class
00114   */
00115   explicit Bitmap(uint prefix_to_set) { set_prefix(prefix_to_set); }
00116 #else
00117   explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }
00118 #endif
00119   void init() { clear_all(); }
00120   void init(uint prefix_to_set) { set_prefix(prefix_to_set); }
00121   uint length() const { return 64; }
00122   void set_bit(uint n) { map|= ((ulonglong)1) << n; }
00123   void clear_bit(uint n) { map&= ~(((ulonglong)1) << n); }
00124   void set_prefix(uint n)
00125   {
00126     if (n >= length())
00127       set_all();
00128     else
00129       map= (((ulonglong)1) << n)-1;
00130   }
00131   void set_all() { map=~(ulonglong)0; }
00132   void clear_all() { map=(ulonglong)0; }
00133   void intersect(const Bitmap<64>& map2) { map&= map2.map; }
00134   void intersect(ulonglong map2) { map&= map2; }
00135   void intersect_extended(ulonglong map2) { map&= map2; }
00136   void subtract(const Bitmap<64>& map2) { map&= ~map2.map; }
00137   void merge(const Bitmap<64>& map2) { map|= map2.map; }
00138   my_bool is_set(uint n) const { return MY_TEST(map & (((ulonglong)1) << n)); }
00139   my_bool is_prefix(uint n) const { return map == (((ulonglong)1) << n)-1; }
00140   my_bool is_clear_all() const { return map == (ulonglong)0; }
00141   my_bool is_set_all() const { return map == ~(ulonglong)0; }
00142   my_bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
00143   my_bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }
00144   my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
00145   my_bool operator!=(const Bitmap<64>& map2) const { return !(*this == map2); }
00146   char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
00147   ulonglong to_ulonglong() const { return map; }
00148 };
00149 
00150 
00151 /* An iterator to quickly walk over bits in unlonglong bitmap. */
00152 class Table_map_iterator
00153 {
00154   ulonglong bmp;
00155   uint no;
00156 public:
00157   Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
00158   int next_bit()
00159   {
00160     static const char last_bit[16]= {32, 0, 1, 0, 
00161                                       2, 0, 1, 0, 
00162                                       3, 0, 1, 0,
00163                                       2, 0, 1, 0};
00164     uint bit;
00165     while ((bit= last_bit[bmp & 0xF]) == 32)
00166     {
00167       no += 4;
00168       bmp= bmp >> 4;
00169       if (!bmp)
00170         return BITMAP_END;
00171     }
00172     bmp &= ~(1LL << bit);
00173     return no + bit;
00174   }
00175   enum { BITMAP_END= 64 };
00176 };
00177 #endif /* SQL_BITMAP_INCLUDED */
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines