BitString.h

Go to the documentation of this file.

/*
 * /phoenix/include/BitString.h
 *
 * This file is a part of Phoenix operating system.
 * Copyright (c) 2011-2012, Artyom Lebedev <artyom.lebedev@gmail.com>
 * All rights reserved.
 * See COPYING file for copyright details.
 */

#ifndef BITSTRING_H_
#define BITSTRING_H_

template <size_t numBits = 0>
class BitString {
public:
    inline BitString() {
        memset(_bits, 0, sizeof(_bits));
    }

    inline void Set(size_t idx) {
        ASSERT(idx < numBits);
        _bits[idx / NBBY] |= 1 << (idx % NBBY);
    }

    inline void Clear(size_t idx) {
        ASSERT(idx < numBits);
        _bits[idx / NBBY] &= ~(1 << (idx % NBBY));
    }

    inline bool IsSet(size_t idx) {
        ASSERT(idx < numBits);
        return _bits[idx / NBBY] & (1 << (idx % NBBY));
    }

    inline bool IsClear(size_t idx) {
        ASSERT(idx < numBits);
        return !IsSet(idx);
    }

    inline bool operator[](size_t idx) {
        return IsSet(idx);
    }

    int FirstSet() {
        const size_t numWords = numBits / (sizeof(uintptr_t) * NBBY);
        for (size_t word = 0; word < numWords; word++) {
            uintptr_t x = static_cast<uintptr_t *>(static_cast<void *>(_bits))[word];
            if (x) {
                size_t bit = cpu::bsf(x);
                bit += word * sizeof(uintptr_t) * NBBY;
                return bit;
            }
        }
        /* Check remainder. */
        for (size_t idx = numWords * sizeof(uintptr_t) * NBBY;
             idx < numBits;
             idx++) {

            if (IsSet(idx)) {
                return idx;
            }
        }
        return -1;
    }

    int FirstClear() {
        const size_t numWords = numBits / (sizeof(uintptr_t) * NBBY);
        for (size_t word = 0; word < numWords; word++) {
            uintptr_t x = static_cast<uintptr_t *>(static_cast<void *>(_bits))[word];
            if (x != static_cast<uintptr_t>(~0)) {
                size_t bit = cpu::bsf(~x);
                bit += word * sizeof(uintptr_t) * NBBY;
                return bit;
            }
        }
        /* Check remainder. */
        for (size_t idx = numWords * sizeof(uintptr_t) * NBBY;
             idx < numBits;
             idx++) {

            if (IsClear(idx)) {
                return idx;
            }
        }
        return -1;
    }

    inline void ClearAll() {
        memset(_bits, 0, sizeof(_bits));
    }

    inline void SetAll() {
        memset(_bits, 0xff, sizeof(_bits));
    }

    inline void Invert() {
        const size_t numWords = numBits / (sizeof(uintptr_t) * NBBY);
        for (size_t word = 0; word < numWords; word++) {
            static_cast<uintptr_t *>(static_cast<void *>(_bits))[word] ^= ~0ul;
        }
        /* Invert remainder. */
        for (size_t idx = numWords * sizeof(uintptr_t);
             idx < (numBits + NBBY - 1) / NBBY;
             idx++) {

            _bits[idx] ^= 0xff;
        }
    }

private:
    u8 _bits[(numBits + NBBY - 1) / NBBY];
};

template <>
class BitString<0> {
public:
    inline BitString(u8 *bitmap = 0, const size_t numBits = 0) :
        _bits(bitmap),
        _numBits(numBits),
        _bitmapSize((numBits + NBBY - 1) / NBBY)
    {
        if (_bits) {
            memset(_bits, 0, _bitmapSize);
        }
    }

    inline void Set(size_t idx) {
        ASSERT(idx < _numBits);
        _bits[idx / NBBY] |= 1 << (idx % NBBY);
    }

    inline void Clear(size_t idx) {
        ASSERT(idx < _numBits);
        _bits[idx / NBBY] &= ~(1 << (idx % NBBY));
    }

    inline bool IsSet(size_t idx) {
        ASSERT(idx < _numBits);
        return _bits[idx / NBBY] & (1 << (idx % NBBY));
    }

    inline bool IsClear(size_t idx) {
        ASSERT(idx < _numBits);
        return !IsSet(idx);
    }

    inline bool operator[](size_t idx) {
        return IsSet(idx);
    }

    int FirstSet() {
        const size_t numWords = _numBits / (sizeof(uintptr_t) * NBBY);
        for (size_t word = 0; word < numWords; word++) {
            uintptr_t x = static_cast<uintptr_t *>(static_cast<void *>(_bits))[word];
            if (x) {
                size_t bit = cpu::bsf(x);
                bit += word * sizeof(uintptr_t) * NBBY;
                return bit;
            }
        }
        /* Check remainder. */
        for (size_t idx = numWords * sizeof(uintptr_t) * NBBY;
             idx < _numBits;
             idx++) {

            if (IsSet(idx)) {
                return idx;
            }
        }
        return -1;
    }

    int FirstClear() {
        const size_t numWords = _numBits / (sizeof(uintptr_t) * NBBY);
        for (size_t word = 0; word < numWords; word++) {
            uintptr_t x = static_cast<uintptr_t *>(static_cast<void *>(_bits))[word];
            if (x != static_cast<uintptr_t>(~0)) {
                size_t bit = cpu::bsf(~x);
                bit += word * sizeof(uintptr_t) * NBBY;
                return bit;
            }
        }
        /* Check remainder. */
        for (size_t idx = numWords * sizeof(uintptr_t) * NBBY;
             idx < _numBits;
             idx++) {

            if (IsClear(idx)) {
                return idx;
            }
        }
        return -1;
    }

    inline void ClearAll() {
        memset(_bits, 0, _bitmapSize);
    }

    inline void SetAll() {
        memset(_bits, 0xff, _bitmapSize);
    }

    inline void Invert() {
        const size_t numWords = _numBits / (sizeof(uintptr_t) * NBBY);
        for (size_t word = 0; word < numWords; word++) {
            static_cast<uintptr_t *>(static_cast<void *>(_bits))[word] ^= ~0ul;
        }
        /* Invert remainder. */
        for (size_t idx = numWords * sizeof(uintptr_t);
             idx < (_numBits + NBBY - 1) / NBBY;
             idx++) {

            _bits[idx] ^= 0xff;
        }
    }
private:
    u8 *_bits;
    const size_t _numBits, _bitmapSize;
};

#endif /* BITSTRING_H_ */