~drizzle-trunk/drizzle/development

#ifndef _SQL_BITMAP_H_

#define _SQL_BITMAP_H_

/* Copyright (C) 2003 MySQL AB

   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License

   along with this program; if not, write to the Free Software

   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/*

  Implementation of a bitmap type.

  The idea with this is to be able to handle any constant number of bits but

  also be able to use 32 or 64 bits bitmaps very efficiently

*/

#include <my_bitmap.h>

template <uint default_width> class Bitmap

{

  MY_BITMAP map;

  uint32 buffer[(default_width+31)/32];

public:

  Bitmap() { init(); }

  Bitmap(const Bitmap& from) { *this=from; }

  explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }

  void init() { bitmap_init(&map, buffer, default_width, 0); }

  void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }

  uint length() const { return default_width; }

  Bitmap& operator=(const Bitmap& map2)

  {

    init();

    memcpy(buffer, map2.buffer, sizeof(buffer));

    return *this;

  }

  void set_bit(uint n) { bitmap_set_bit(&map, n); }

  void clear_bit(uint n) { bitmap_clear_bit(&map, n); }

  void set_prefix(uint n) { bitmap_set_prefix(&map, n); }

  void set_all() { bitmap_set_all(&map); }

  void clear_all() { bitmap_clear_all(&map); }

  void intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); }

  void intersect(uint64_t map2buff)

  {

    MY_BITMAP map2;

    bitmap_init(&map2, (uint32 *)&map2buff, sizeof(uint64_t)*8, 0);

    bitmap_intersect(&map, &map2);

  }

  /* Use highest bit for all bits above sizeof(uint64_t)*8. */

  void intersect_extended(uint64_t map2buff)

  {

    intersect(map2buff);

    if (map.n_bits > sizeof(uint64_t) * 8)

      bitmap_set_above(&map, sizeof(uint64_t),

                       test(map2buff & (1 << (sizeof(uint64_t) * 8 - 1))));

  }

  void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); }

  void merge(Bitmap& map2) { bitmap_union(&map, &map2.map); }

  bool is_set(uint n) const { return bitmap_is_set(&map, n); }

  bool is_set() const { return !bitmap_is_clear_all(&map); }

  bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }

  bool is_clear_all() const { return bitmap_is_clear_all(&map); }

  bool is_set_all() const { return bitmap_is_set_all(&map); }

  bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }

  bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }

  bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }

  bool operator!=(const Bitmap& map2) const { return !bitmap_cmp(&map, &map2.map); }

  Bitmap operator&=(uint n)

  {

    if (bitmap_is_set(&map, n))

    {

      bitmap_clear_all(&map);

      bitmap_set_bit(&map, n);

    }

    else

      bitmap_clear_all(&map);

    return *this;

  }

  Bitmap operator&=(const Bitmap& map2)

  {

    bitmap_intersect(&map, &map2.map);

    return *this;

  }

  Bitmap operator&(uint n)

  {

    Bitmap bm(*this);

    bm&= n;

    return bm;

  }

  Bitmap operator&(const Bitmap& map2)

  {

    Bitmap bm(*this);

    bm&= map2;

    return bm;

  }

  Bitmap operator|=(uint n)

  {

    bitmap_set_bit(&map, n);

    return *this;

  }

  Bitmap operator|=(const Bitmap& map2)

  {

    bitmap_union(&map, &map2.map);

  }

  Bitmap operator|(uint n)

  {

    Bitmap bm(*this);

    bm|= n;

    return bm;

  }

  Bitmap operator|(const Bitmap& map2)

  {

    Bitmap bm(*this);

    bm|= map2;

    return bm;

  }

  Bitmap operator~()

  {

    Bitmap bm(*this);

    bitmap_invert(&bm.map);

    return bm;

  }

  char *print(char *buf) const

  {

    char *s=buf;

    const uchar *e=(uchar *)buffer, *b=e+sizeof(buffer)-1;

    while (!*b && b>e)

      b--;

    if ((*s=_dig_vec_upper[*b >> 4]) != '0')

        s++;

    *s++=_dig_vec_upper[*b & 15];

    while (--b>=e)

    {

      *s++=_dig_vec_upper[*b >> 4];

      *s++=_dig_vec_upper[*b & 15];

    }

    *s=0;

    return buf;

  }

  uint64_t to_uint64_t() const

  {

    if (sizeof(buffer) >= 8)

      return uint8korr(buffer);

    assert(sizeof(buffer) >= 4);

    return (uint64_t) uint4korr(buffer);

  }

};

template <> class Bitmap<64>

{

  uint64_t map;

public:

  Bitmap<64>() { map= 0; }

  explicit Bitmap<64>(uint prefix_to_set) { set_prefix(prefix_to_set); }

  void init() { }

  void init(uint prefix_to_set) { set_prefix(prefix_to_set); }

  uint length() const { return 64; }

  void set_bit(uint n) { map|= ((uint64_t)1) << n; }

  void clear_bit(uint n) { map&= ~(((uint64_t)1) << n); }

  void set_prefix(uint n)

  {

    if (n >= length())

      set_all();

    else

      map= (((uint64_t)1) << n)-1;

  }

  void set_all() { map=~(uint64_t)0; }

  void clear_all() { map=(uint64_t)0; }

  void intersect(Bitmap<64>& map2) { map&= map2.map; }

  void intersect(uint64_t map2) { map&= map2; }

  void intersect_extended(uint64_t map2) { map&= map2; }

  void subtract(Bitmap<64>& map2) { map&= ~map2.map; }

  void merge(Bitmap<64>& map2) { map|= map2.map; }

  bool is_set(uint n) const { return test(map & (((uint64_t)1) << n)); }

  bool is_prefix(uint n) const { return map == (((uint64_t)1) << n)-1; }

  bool is_clear_all() const { return map == (uint64_t)0; }

  bool is_set_all() const { return map == ~(uint64_t)0; }

  bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }

  bool is_overlapping(const Bitmap<64>& map2) const { return (map & map2.map)!= 0; }

  bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }

  char *print(char *buf) const { int64_t2str(map,buf,16); return buf; }

  uint64_t to_uint64_t() const { return map; }

};

/* An iterator to quickly walk over bits in unint64_t bitmap. */

class Table_map_iterator

{

  uint64_t bmp;

  uint no;

public:

  Table_map_iterator(uint64_t t) : bmp(t), no(0) {}

  int next_bit()

  {

    static const char last_bit[16]= {32, 0, 1, 0, 

                                      2, 0, 1, 0, 

                                      3, 0, 1, 0,

                                      2, 0, 1, 0};

    uint bit;

    while ((bit= last_bit[bmp & 0xF]) == 32)

    {

      no += 4;

      bmp= bmp >> 4;

      if (!bmp)

        return BITMAP_END;

    }

    bmp &= ~(1 << bit);

    return no + bit;

  }

  enum { BITMAP_END= 64 };

};

#if 0

void print_bits(table_map bmp)

{

  Table_map_iterator it(bmp);

  int i, first= 1;

  fprintf(stderr, "0x%llx = ", bmp);

  while ((i= it.next_bit()) != Table_map_iterator::BITMAP_END)

  {

    fprintf(stderr, " %s 2^%d", (first?"":"+"), i);

    if (first)

      first= 0;

  }

  fprintf(stderr, "\n");

}

int main()

{

  print_bits(1024);

  print_bits(3);

  print_bits(0xF);

  print_bits(0xF0);

  print_bits(35);

  print_bits(1LL<<63);

  print_bits(0);

  print_bits(-1LL);

}

#endif

#endif /* _SQL_BITMAP_H_ */