bitmap

// vi:set ft=cpp: -*- Mode: C++ -*-
/*
 * (c) 2008-2014 Alexander Warg <warg@os.inf.tu-dresden.de>
 *     economic rights: Technische Universität Dresden (Germany)
 *
 * This file is part of TUD:OS and distributed under the terms of the
 * GNU General Public License 2.
 * Please see the COPYING-GPL-2 file for details.
 *
 * As a special exception, you may use this file as part of a free software
 * library without restriction.  Specifically, if other files instantiate
 * templates or use macros or inline functions from this file, or you compile
 * this file and link it with other files to produce an executable, this
 * file does not by itself cause the resulting executable to be covered by
 * the GNU General Public License.  This exception does not however
 * invalidate any other reasons why the executable file might be covered by
 * the GNU General Public License.
 */
 
#pragma once
 
namespace cxx {
 
class Bitmap_base
{
protected:
  typedef unsigned long word_type;
 
  enum
  {
    W_bits = sizeof(word_type) * 8, 
    C_bits = 8,                     
  };
 
  word_type *_bits;
 
  static unsigned word_index(unsigned bit) { return bit / W_bits; }
 
  static unsigned bit_index(unsigned bit) { return bit % W_bits; }
 
  class Bit
  {
    Bitmap_base *_bm;
    long _bit;
 
  public:
    Bit(Bitmap_base *bm, long bit) : _bm(bm), _bit(bit) {}
    Bit &operator = (bool val) { _bm->bit(_bit, val); return *this; }
    operator bool () const { return _bm->bit(_bit); }
  };
 
public:
  explicit Bitmap_base(void *bits) noexcept : _bits(reinterpret_cast<word_type *>(bits)) {}
 
  static long words(long bits) noexcept { return (bits + W_bits -1) / W_bits; }
  static long bit_buffer_bytes(long bits) noexcept
  { return words(bits) * W_bits / 8; }
 
  template< long BITS >
  class Word
  {
  public:
    typedef unsigned long Type;
    enum
    {
      Size = (BITS + W_bits - 1) / W_bits
    };
  };
 
  static long chars(long bits) noexcept
  { return (bits + C_bits -1) / C_bits; }
 
  template< long BITS >
  class Char
  {
  public:
    typedef unsigned char Type;
    enum
    {
      Size = (BITS + C_bits - 1) / C_bits
    };
  };
 
  void bit(long bit, bool on) noexcept;
 
  void clear_bit(long bit) noexcept;
 
  void atomic_clear_bit(long bit) noexcept;
 
  word_type atomic_get_and_clear(long bit) noexcept;
 
  void set_bit(long bit) noexcept;
 
  void atomic_set_bit(long bit) noexcept;
 
  word_type atomic_get_and_set(long bit) noexcept;
 
  word_type bit(long bit) const noexcept;
 
  word_type operator [] (long bit) const noexcept
  { return this->bit(bit); }
 
  Bit operator [] (long bit) noexcept
  { return Bit(this, bit); }
 
  long scan_zero(long max_bit, long start_bit = 0) const noexcept;
 
  void *bit_buffer() const noexcept { return _bits; }
 
protected:
  static int _bzl(unsigned long w) noexcept;
};
 
 
template<int BITS>
class Bitmap : public Bitmap_base
{
private:
  char _bits[Bitmap_base::Char<BITS>::Size];
 
public:
  Bitmap() noexcept : Bitmap_base(_bits) {}
  Bitmap(Bitmap<BITS> const &o) noexcept : Bitmap_base(_bits)
  { __builtin_memcpy(_bits, o._bits, sizeof(_bits)); }
  long scan_zero(long start_bit = 0) const noexcept;
 
  void clear_all()
  { __builtin_memset(_bits, 0, sizeof(_bits)); }
};
 
 
inline
void
Bitmap_base::bit(long bit, bool on) noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  _bits[idx] = (_bits[idx] & ~(1UL << b)) | (static_cast<unsigned long>(on) << b);
}
 
inline
void
Bitmap_base::clear_bit(long bit) noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  _bits[idx] &= ~(1UL << b);
}
 
inline
void
Bitmap_base::atomic_clear_bit(long bit) noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  word_type mask = 1UL << b;
  __atomic_and_fetch(&_bits[idx], ~mask, __ATOMIC_RELAXED);
}
 
inline
Bitmap_base::word_type
Bitmap_base::atomic_get_and_clear(long bit) noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  word_type mask = 1UL << b;
  return __atomic_fetch_and(&_bits[idx], ~mask, __ATOMIC_RELAXED) & mask;
}
 
inline
void
Bitmap_base::set_bit(long bit) noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  _bits[idx] |= (1UL << b);
}
 
inline
void
Bitmap_base::atomic_set_bit(long bit) noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  word_type mask = 1UL << b;
  __atomic_or_fetch(&_bits[idx], mask, __ATOMIC_RELAXED);
}
 
inline
Bitmap_base::word_type
Bitmap_base::atomic_get_and_set(long bit) noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  word_type mask = 1UL << b;
  return __atomic_fetch_or(&_bits[idx], mask, __ATOMIC_RELAXED) & mask;
}
 
inline
Bitmap_base::word_type
Bitmap_base::bit(long bit) const noexcept
{
  long idx = word_index(bit);
  long b   = bit_index(bit);
  return _bits[idx] & (1UL << b);
}
 
inline
int
Bitmap_base::_bzl(unsigned long w) noexcept
{
  for (int i = 0; i < W_bits; ++i, w >>= 1)
    {
      if ((w & 1) == 0)
        return i;
    }
  return -1;
}
 
inline
long
Bitmap_base::scan_zero(long max_bit, long start_bit) const noexcept
{
  if (!(operator [] (start_bit)))
    return start_bit;
 
  long idx = word_index(start_bit);
 
  max_bit -= start_bit & ~(W_bits - 1);
 
  for (; max_bit > 0; max_bit -= W_bits, ++idx)
    {
      if (_bits[idx] == 0)
        return idx * W_bits;
 
      if (_bits[idx] != ~0UL)
        {
          long zbit = _bzl(_bits[idx]);
          return zbit < max_bit ? idx * W_bits + zbit : -1;
        }
    }
 
  return -1;
}
 
template<int BITS> inline
long
Bitmap<BITS>::scan_zero(long start_bit) const noexcept
{
  return Bitmap_base::scan_zero(BITS, start_bit);
}
 
};