bitset.cpp

Go to the documentation of this file.

#include <data/bitset.h>

#include <memory.h>
#include <qglobal.h>
#include <boost/multiprecision/integer.hpp>

using namespace frechet;
using namespace data;

BitSet::BitSet() : BitSet(0) {}

BitSet::BitSet(int asize)
    : _size(asize), numWords(0), bits(NULL)
{
    if (_size > 0) {
        numWords = (_size+63)/64;
        bits = new uint64_t[numWords];
        clear();
    }
}

//BitSet::BitSet(BitSet&& that)
//{
//    stealBits(that);
//}

BitSet::BitSet(const BitSet& that) : bits(NULL)
{
    copyBits(that);
}

BitSet::~BitSet()
{
    delete bits;
}

BitSet& BitSet::operator=(const BitSet& that)
{
    copyBits(that);
    return *this;
}

BitSet &BitSet::swap(BitSet &that) {
    std::swap(_size,that._size);
    std::swap(numWords,that.numWords);
    std::swap(bits,that.bits);
    return *this;
}

//BitSet& BitSet::operator=(BitSet&& that) {
//    stealBits(that);
//    return *this;
//}

int BitSet::size() const { return _size; }

int BitSet::count() const
{
    int popCount = 0;
    for (int i = 0; i < numWords; ++i) {
        popCount += bitCount(bits[i]);
    }
    return popCount;
}

void BitSet::clear() {
    memset(bits,0,sizeof(uint64_t)*numWords);
}

bool BitSet::contains(int offset) const
{
    Q_ASSERT(offset>=0 && offset < _size);
    return bits[offset>>6] & ((uint64_t)1 << offset);
}

void BitSet::add(int offset)
{
    Q_ASSERT(offset>=0 && offset < _size);
    bits[offset>>6] |= ((uint64_t)1 << offset);
}

void BitSet::remove(int offset)
{
    Q_ASSERT(offset>=0 && offset < _size);
    bits[offset>>6] &= ~((uint64_t)1 << offset);
}

void BitSet::add_lf(int offset)
{
    Q_ASSERT(offset>=0 && offset < _size);
    int i = offset>>6;
    uint64_t mask = ((uint64_t)1 << offset);

    uint64_t old_value = bits[i];   //  when reading this value, do we need a memory barrier?
    for(;;) {
        uint64_t prev_value = compare_and_swap(
                    (volatile int64_t*)&bits[i],
                    (int64_t)old_value,
                    (int64_t)(old_value|mask));
        if (prev_value==old_value)
            return;
        else
            old_value=prev_value;
    }
}

void BitSet::remove_lf(int offset)
{
    Q_ASSERT(offset>=0 && offset < _size);
    int i = offset>>6;
    uint64_t mask = ~((uint64_t)1 << offset);

    uint64_t old_value = bits[i];   //  volatile, memory barrier?
    for(;;) {
        uint64_t prev_value = compare_and_swap(
                    (volatile int64_t*)&bits[i],
                    (int64_t)old_value,
                    (int64_t)(old_value&mask));
        if (prev_value==old_value)
            return;
        else
            old_value=prev_value;
    }
}


BitSet::iterator BitSet::begin() const { return iterator(this,0); }

void BitSet::copyBits(const BitSet &that)
{
    delete bits;
    _size = that._size;
    numWords = that.numWords;
    if (numWords > 0) {
        bits = new uint64_t[numWords];
        memcpy(bits,that.bits,numWords*sizeof(uint64_t));
    }
    else {
        bits = NULL;
    }
}

void BitSet::stealBits(BitSet&& that) {
    bits = that.bits;
    _size = that._size;
    numWords = that.numWords;
    that.bits = NULL;
}

int BitSet::next(int index) const
{
    if (index >= _size)
        return index;
    if (index < 0)
        index = 0;

    Q_ASSERT(index >= 0 && index < _size);
    int i = index >> 6;
    uint64_t word = bits[i] >> index;  // skip all the bits to the right of index

    if (word!=0)
        return index + numberOfTrailingZeros(word);

    while(++i < numWords) {
        word = bits[i];
        if (word != 0)
            return (i<<6) + numberOfTrailingZeros(word);
    }

    return _size;
}

int BitSet::prev(int index) const
{
    Q_ASSERT(index >= 0 && index < _size);
    int i = index >> 6;
    int subIndex = index & 0x3f;  // index within the word
    uint64_t word = bits[i];  // skip all the bits to the left of index
    word <<= (63-subIndex);

    if (word != 0) {
        return (i << 6) + subIndex - numberOfLeadingZeros(word);
    }

    while (--i >= 0) {
        word = bits[i];
        if (word !=0 ) {
            return (i << 6) + 63 - numberOfLeadingZeros(word);
        }
    }
    return -1;
}


BitSet::iterator::iterator() : parent(NULL), _offset(0) { }

BitSet::iterator::iterator(const BitSet::iterator &that) : parent(that.parent), _offset(that._offset) { }

BitSet::iterator& BitSet::iterator::operator=(const BitSet::iterator &that) {
    parent = that.parent;
    _offset = that._offset;
    return *this;
}

bool BitSet::iterator::operator==(const BitSet::iterator &that) const {
    return (parent==that.parent) &&
            ((!valid() && !that.valid()) || (_offset==that._offset));
}

bool BitSet::iterator::valid() const
{
    return (_offset>=0) && (_offset < parent->_size);
}

int BitSet::iterator::operator*() const
{
    return _offset;
}

BitSet::iterator &BitSet::iterator::operator++() {
    _offset = parent->next(_offset+1);
    return *this;
}

BitSet::iterator BitSet::iterator::operator++(int) {
    iterator it = *this;
    _offset = parent->next(_offset+1);
    return it;
}

BitSet::iterator &BitSet::iterator::operator--() {
    _offset = parent->prev(_offset-1);
    return *this;
}

BitSet::iterator BitSet::iterator::operator--(int) {
    iterator it = *this;
    _offset = parent->prev(_offset-1);
    return it;
}

BitSet::iterator &BitSet::iterator::operator+=(int n) {
    while((_offset < parent->_size) && (n-- > 0))
        _offset = parent->next(_offset+1);
    return *this;
}

BitSet::iterator BitSet::iterator::operator+(int n) const {
    iterator it = *this;
    it += n;
    return it;
}

BitSet::iterator &BitSet::iterator::operator-=(int n) {
    while((_offset >= 0) && (n-- > 0))
        _offset = parent->prev(_offset-1);
    return *this;
}

BitSet::iterator BitSet::iterator::operator-(int n) {
    iterator it = *this;
    it -= n;
    return it;
}

int BitSet::iterator::operator-(const BitSet::iterator &that)
{
    Q_ASSERT(valid() && that.valid());
    Q_ASSERT(parent == that.parent);
    return _offset - that._offset;
}


BitSet::iterator::iterator(const BitSet *aparent, int start)
    : parent(aparent)
{
    if (start >= parent->_size)
        _offset = parent->_size;
    else
        _offset = parent->next(start);
}


#ifdef _MSC_VER
#include <intrin.h>
#pragma intrinsic(_BitScanForward64)
#pragma intrinsic(_BitScanReverse64)
#pragma intrinsic(__popcnt64)
#pragma intrinsic(_InterlockedCompareExchange64)
#endif

int64_t BitSet::compare_and_swap(volatile int64_t* value, int64_t old_value, int64_t update_value)
{
#if defined __GNUC__
    return __sync_val_compare_and_swap (value, old_value, update_value);
#elif defined _MSC_VER
    //  Destination = value
    //  Comparand = old_value
    //  Exchange = new value
    //  returns actual value of *Destination
    return _InterlockedCompareExchange64(value,update_value,old_value);
#else
# error
#endif
}

int BitSet::numberOfTrailingZeros(uint64_t word)
{
    if (word == 0)
        return 64;
    else
        return boost::multiprecision::lsb(word);
}

int BitSet::numberOfLeadingZeros(uint64_t word)
{
    if (word == 0)
        return 64;
    else
        return 63 - boost::multiprecision::msb(word);
}

int BitSet::bitCount(uint64_t word)
{
#if defined __GNUC__
    return __builtin_popcountll (word);
#elif defined _MSC_VER
    return __popcnt64(word);
#else
# error
#endif
}