Loading...
Searching...
No Matches
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)
*
* License: see LICENSE.spdx (in this directory or the directories above)
*/
#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);
}
};
cxx::Bitmap_base::Bit
A writable bit in a bitmap.
Definition bitmap:59
cxx::Bitmap_base::Char
Helper abstraction for a byte contained in the bitmap.
Definition bitmap:96
cxx::Bitmap_base::Word
Helper abstraction for a word contained in the bitmap.
Definition bitmap:80
cxx::Bitmap_base
Basic bitmap abstraction.
Definition bitmap:19
cxx::Bitmap_base::chars
static long chars(long bits) noexcept
Get the number of chars that are used for the bitmap.
Definition bitmap:90
cxx::Bitmap_base::scan_zero
long scan_zero(long max_bit, long start_bit=0) const noexcept
Scan for the first zero bit.
Definition bitmap:339
cxx::Bitmap_base::atomic_clear_bit
void atomic_clear_bit(long bit) noexcept
Clear bit bit atomically.
Definition bitmap:269
cxx::Bitmap_base::atomic_get_and_clear
word_type atomic_get_and_clear(long bit) noexcept
Clear bit bit atomically and return old state.
Definition bitmap:279
cxx::Bitmap_base::W_bits
@ W_bits
number of bits in word_type
Definition bitmap:28
cxx::Bitmap_base::C_bits
@ C_bits
number of bits in char
Definition bitmap:29
cxx::Bitmap_base::atomic_set_bit
void atomic_set_bit(long bit) noexcept
Set bit bit atomically.
Definition bitmap:298
cxx::Bitmap_base::bit_index
static unsigned bit_index(unsigned bit)
Get the bit index within word_type for the given bit.
Definition bitmap:53
cxx::Bitmap_base::word_type
unsigned long word_type
Data type for each element of the bit buffer.
Definition bitmap:24
cxx::Bitmap_base::words
static long words(long bits) noexcept
Get the number of Words that are used for the bitmap.
Definition bitmap:73
cxx::Bitmap_base::word_index
static unsigned word_index(unsigned bit)
Get the word index for the given bit.
Definition bitmap:44
cxx::Bitmap_base::clear_bit
void clear_bit(long bit) noexcept
Clear bit bit.
Definition bitmap:260
cxx::Bitmap_base::set_bit
void set_bit(long bit) noexcept
Set bit bit.
Definition bitmap:289
cxx::Bitmap_base::atomic_get_and_set
word_type atomic_get_and_set(long bit) noexcept
Set bit bit atomically and return old state.
Definition bitmap:308
cxx::Bitmap_base::operator[]
word_type operator[](long bit) const noexcept
Get the bit at index bit.
Definition bitmap:181
cxx::Bitmap_base::bit
void bit(long bit, bool on) noexcept
Set the value of bit bit to on.
Definition bitmap:251
cxx::Bitmap_base::_bits
word_type * _bits
Pointer to the buffer storing the bits.
Definition bitmap:35
cxx::Bitmap
A static bitmap.
Definition bitmap:221
cxx::Bitmap::Bitmap
Bitmap() noexcept
Create a bitmap with BITS bits.
Definition bitmap:227
cxx::Bitmap::scan_zero
long scan_zero(long start_bit=0) const noexcept
Scan for the first zero bit.
Definition bitmap:365
cxx
Our C++ library.
Definition arith:11