bk commit into 5.1 tree (mats:1.1789)

[Mats Kindahl]

Below is the list of changes that have just been committed into a local
5.1 repository of mats. When mats does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html

ChangeSet
  1.1789 05/03/17 10:08:46 mats@stripped +1 -0
  Added new bitvector class.

  sql/bitvector.h
    1.1 05/03/17 10:08:41 mats@stripped +175 -0

  sql/bitvector.h
    1.0 05/03/17 10:08:41 mats@stripped +0 -0
    BitKeeper file /home/bk/bv-mysql-5.1/sql/bitvector.h

# This is a BitKeeper patch.  What follows are the unified diffs for the
# set of deltas contained in the patch.  The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User:	mats
# Host:	romeo.kindahl.net
# Root:	/home/bk/bv-mysql-5.1
--- New file ---
+++ sql/bitvector.h	05/03/17 10:08:41
/* Copyright (C) 2005 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; either version 2 of the License, or
   (at your option) any later version.

   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 */

#ifndef BITVECTOR_H
#define BITVECTOR_H

#include "my_global.h"
#include "my_sys.h"
#include <cstring>
#include <climits>

namespace {
    template <class T> 
    inline void my_swap(T& x, T& y) { 
	T t(x); x = y; y = t; 
    }
}

/*
  A dynamic bitvector for storing bits.

  Right now, the vector cannot change size. It's only used as a replacement
  for using an array of bytes and a counter. If you want to change the size of
  the vector, construct a new bitvector and assign it to the vector, e.g.:

    bitvector new_bv(new_size);
    old_bv = new_bv;

  An alternative is to use the swap member function to replace the instance:

    bitvector new_bv(new_size);
    old_bv.swap(new_bv);

*/

class bitvector {
private:
  // Helper classes
  struct flip_bit_op { 
    void operator()(byte* p, byte m) { *p ^= m; }
  };

  struct set_bit_op { 
    void operator()(byte* p, byte m) { *p |= m; }
  };

  struct clear_bit_op { 
    void operator()(byte* p, byte m) { *p &= ~m; }
  };

  struct test_bit_op { 
    bool operator()(byte* p, byte m) { return *p & m; }
  };

  static inline size_t byte_size(size_t bits) { 
    int const byte_bits = sizeof(byte) * CHAR_BIT;
    return (bits + (byte_bits-1)) / byte_bits; 
  }

  template <class ReturnType, class Func>
  inline ReturnType apply_to_byte(size_t const pos, Func op) const
  {
    ptrdiff_t const byte_pos = pos >> 3;
    byte const mask = (1 << (pos & 0x7U));
    return op(&m_data[byte_pos], mask);
  }

public:
  bitvector() 
    : m_size(0), m_data(0)
  {
  }

  explicit bitvector(size_t size, bool value = false) 
    : m_size(size), m_data(my_malloc(byte_size(size), MYF(0)))
  {
    if (value)
      set_all();
    else
      clear_all();
  }

  // Constructor to create a bitvector from data. Observe that 'size' is the
  // number of *bits* in the bitvector. 
  explicit bitvector(byte const* data, size_t size)
    : m_size(size), m_data(my_malloc(byte_size(size), MYF(0)))
  {
    // std::copy(data, data + byte_size(size), m_data);
    memcpy(m_data, data, byte_size(size));
  }

  bitvector(bitvector const& other) 
    : m_size(other.size()), m_data(my_malloc(other.bytes(), MYF(0)))
  {
    // std::copy(other.m_data, other.m_data + other.bytes(), m_data);
    memcpy(m_data, other.data(), other.bytes());
  }

  // Assignment operator
  bitvector& operator=(bitvector other) {
    swap(other);
    return *this;
  }

  ~bitvector() 
  {
    my_free(m_data, MYF(0));
  }

  // Swap the guts of this instance with another instance.
  void swap(bitvector& other) {
    my_swap(m_size, other.m_size);
    my_swap(m_data, other.m_data);
  }

  // A pointer to the bytes representing the bits
  byte const *data() const { return m_data; }

  // The size of the data in *bytes*
  size_t bytes() const { return byte_size(m_size); }

  // The number of bits in the bit vector
  size_t size() const { return m_size; }

  // Set all bits in the vector
  void set_all() { 
    // I would really like to use std::fill() here, but I'm not sure it's
    // allowed.
    // std::fill(m_data, m_data + bytes(), 255);
    memset(m_data, 255, bytes()); 
  }

  // Set a bit to a value
  void set_bit(size_t pos) {
    apply_to_byte<void>(pos, set_bit_op());
  }

  // Reset (clear) all bits in the vector
  void clear_all() { 
    // std::fill(m_data, m_data + bytes(), 0);
    memset(m_data, 0, bytes()); 
  }

  // Reset one bit in the vector
  void clear_bit(size_t pos) {
    apply_to_byte<void>(pos, clear_bit_op());
  }

  void flip_bit(size_t pos) {
    apply_to_byte<void>(pos, flip_bit_op());
  }

  bool get_bit(size_t pos) const {
    return apply_to_byte<bool>(pos, test_bit_op());
  };

private:
  size_t m_size;
  byte *m_data;
};

#endif // BITVECTOR_H