diff options
author | David Robillard <d@drobilla.net> | 2018-08-19 17:27:44 +0200 |
---|---|---|
committer | David Robillard <d@drobilla.net> | 2018-09-29 14:49:25 +0200 |
commit | 601c2080e9667ba686e39823c1ebd58844550002 (patch) | |
tree | bdd7fed29ff7f7ddaaad45fe6aaad5d9d4348e2c /chilbert/FixBitVec.hpp | |
parent | 0013efd3cc0c2aa9150c983babd52d3de8e32744 (diff) | |
download | chilbert-601c2080e9667ba686e39823c1ebd58844550002.tar.gz chilbert-601c2080e9667ba686e39823c1ebd58844550002.tar.bz2 chilbert-601c2080e9667ba686e39823c1ebd58844550002.zip |
Rename bit vector types
Diffstat (limited to 'chilbert/FixBitVec.hpp')
-rw-r--r-- | chilbert/FixBitVec.hpp | 384 |
1 files changed, 0 insertions, 384 deletions
diff --git a/chilbert/FixBitVec.hpp b/chilbert/FixBitVec.hpp deleted file mode 100644 index 8cd3d72..0000000 --- a/chilbert/FixBitVec.hpp +++ /dev/null @@ -1,384 +0,0 @@ -/* - Copyright (C) 2018 David Robillard <d@drobilla.net> - Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca> - - 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, see <https://www.gnu.org/licenses/>. -*/ - -#ifndef CHILBERT_FIXBITVEC_HPP -#define CHILBERT_FIXBITVEC_HPP - -#include "chilbert/Operations.hpp" - -#include <cassert> -#include <climits> -#include <cstddef> -#include <cstdint> -#include <iostream> - -namespace chilbert { - -/* This must be an unsigned integer that is either 32 or 64 bits. Otherwise, - there are places in the code that simply will not work. For speed, this - should be the native word size. */ -typedef uint64_t FBV_UINT; - -#define FBV_BITS 64 - -#define FBV1 (FBV_UINT{1}) -#define FBV1S (~FBV_UINT{0}) -#define FBVN1S(n) (n == FBV_BITS ? FBV1S : (FBV1 << n) - 1) - -class CFixBitVec -{ -public: - using Rack = uintptr_t; - - static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT; - - /** Mask for a bit that can be incremented like an index. - * - * This enables fast iteration while setting or resetting bits since it is - * internally stored as a mask which avoids repeated index math. - */ - class Mask - { - public: - void operator++() { m_mask <<= 1; } - void operator--() { m_mask >>= 1; } - - bool operator==(const Mask& mask) const - { - return m_mask == mask.m_mask; - } - - bool operator!=(const Mask& mask) const - { - return m_mask == mask.m_mask; - } - - private: - friend class CFixBitVec; - - Mask(const size_t index) - : m_mask{index < bits_per_rack ? Rack{1} << index : 0} - { - } - - Rack m_mask; - }; - - explicit CFixBitVec(const size_t bits) - : m_rack{0} - , m_size{bits} - { - assert(bits <= bits_per_rack); - } - - CFixBitVec(const size_t bits, const Rack value) - : m_rack{value} - , m_size{bits} - { - assert(bits <= bits_per_rack); - } - - /// Return the size in bits - size_t size() const { return m_size; } - - /// Set all bits to one - CFixBitVec& set() - { - m_rack = FBV1S & FBVN1S(size()); - return *this; - } - - /// Set all bits to zero - CFixBitVec& reset() - { - m_rack = 0; - return *this; - } - - /// Return the value of the bit covered by `mask` - bool test(const Mask mask) const { return m_rack & mask.m_mask; } - - /// Return the value of the `index`th bit - bool test(const size_t index) const { return test(mask(index)); } - - /// Set the bit covered by `mask` to 1 - CFixBitVec& set(const Mask mask) - { - m_rack |= mask.m_mask; - return *this; - } - - /// Set the `index`th bit to 1 - CFixBitVec& set(const size_t index) { return set(mask(index)); } - - /// Reset the bit covered by `mask` to 0 - CFixBitVec& reset(const Mask mask) - { - m_rack &= ~mask.m_mask; - return *this; - } - - /// Reset the `index`th bit to 0 - CFixBitVec& reset(const size_t index) { return reset(mask(index)); } - - /// Set the bit covered by `mask` to `value` - CFixBitVec& set(const Mask mask, const bool value) - { - m_rack ^= (-Rack{value} ^ m_rack) & mask.m_mask; - return *this; - } - - /// Set the `index`th bit to `value` - CFixBitVec& set(const size_t index, const bool value) - { - return set(mask(index), value); - } - - /// Flip the value of the bit covered by `mask` - CFixBitVec& flip(const Mask mask) - { - m_rack ^= mask.m_mask; - return *this; - } - - /// Flip the value of the `index`th bit - CFixBitVec& flip(const size_t index) { return flip(mask(index)); } - - bool operator==(const CFixBitVec& vec) const - { - return m_rack == vec.m_rack; - } - - bool operator!=(const CFixBitVec& vec) const - { - return m_rack != vec.m_rack; - } - - bool operator<(const CFixBitVec& vec) const { return m_rack < vec.m_rack; } - - CFixBitVec& operator=(const Rack i) - { - m_rack = i; - return *this; - } - - CFixBitVec& operator&=(const CFixBitVec& vec) - { - m_rack &= vec.m_rack; - return *this; - } - - CFixBitVec& operator|=(const CFixBitVec& vec) - { - m_rack |= vec.m_rack; - return *this; - } - - CFixBitVec& operator^=(const CFixBitVec& vec) - { - m_rack ^= vec.m_rack; - return *this; - } - - CFixBitVec& operator^=(const Rack i) - { - m_rack ^= i; - return *this; - } - - CFixBitVec& operator<<=(const size_t bits) - { - assert(bits < size()); - m_rack <<= bits; - return *this; - } - - CFixBitVec& operator>>=(const size_t bits) - { - assert(bits < size()); - m_rack >>= bits; - return *this; - } - - /// Right-rotate by `bits` positions - CFixBitVec& rotr(const size_t bits) - { - if (bits > 0 && bits < size()) { - assert(bits <= bits_per_rack); - m_rack &= FBVN1S(size()); - m_rack = (m_rack >> bits) | (m_rack << (size() - bits)); - m_rack &= FBVN1S(size()); - } - return *this; - } - - /// Left-rotate by `bits` positions - CFixBitVec& rotl(const size_t bits) - { - if (bits > 0 && bits < size()) { - assert(bits <= bits_per_rack); - m_rack &= FBVN1S(size()); - m_rack = (m_rack << bits) | (m_rack >> (size() - bits)); - m_rack &= FBVN1S(size()); - } - return *this; - } - - /// Return true iff all bits are zero - bool none() const { return m_rack == 0; } - - /// Return 1 + the index of the first set bit, or 0 if there are none - size_t find_first() const - { - return static_cast<size_t>(chilbert::find_first(m_rack)); - } - - /// Return the number of set bits - size_t count() const { return static_cast<size_t>(pop_count(m_rack)); } - - /// Flip all bits (one's complement) - CFixBitVec& flip() - { - m_rack = ~m_rack; - return *this; - } - - /// Return the first rack - Rack& rack() { return m_rack; } - Rack rack() const { return m_rack; } - - /// Return a raw pointer to the racks - Rack* data() { return &m_rack; } - const Rack* data() const { return &m_rack; } - - /// Return the number of racks - size_t num_racks() const { return 1; } - - template <class BitVec> - class iterator_base : public Mask - { - public: - iterator_base& operator++() - { - Mask::operator++(); - return *this; - } - - iterator_base& operator--() - { - Mask::operator--(); - return *this; - } - - bool operator==(const iterator_base& iterator_base) const - { - return m_vec == iterator_base.m_vec && - Mask::operator==(iterator_base); - } - - bool operator!=(const iterator_base& iterator_base) const - { - return !operator==(iterator_base); - } - - bool operator*() const { return m_vec->test(*this); } - - protected: - iterator_base(BitVec& vec, const size_t index) - : Mask{index} - , m_vec{&vec} - { - } - - BitVec* m_vec; - }; - - class iterator : public iterator_base<CFixBitVec> - { - public: - void set() { m_vec->set(*this); } - void reset() { m_vec->reset(*this); } - - private: - friend class CFixBitVec; - - iterator(CFixBitVec& vec, const size_t index) - : iterator_base{vec, index} - { - } - }; - - class const_iterator : public iterator_base<const CFixBitVec> - { - private: - friend class CFixBitVec; - - const_iterator(const CFixBitVec& vec, const size_t index) - : iterator_base{vec, index} - { - } - }; - - Mask mask(const size_t i = 0) const - { - assert(i <= size()); - return Mask{i}; - } - - iterator begin(const size_t i = 0) { return iterator(*this, i); } - - iterator end() { return iterator(*this, size()); } - - const_iterator begin(const size_t i = 0) const - { - return const_iterator(*this, i); - } - - const_iterator end() const { return const_iterator(*this, size()); } - -private: - static_assert(8 * sizeof(Rack) == bits_per_rack, ""); - static_assert((sizeof(Rack) == 4) || (sizeof(Rack) == 8), ""); - - Rack m_rack{}; - size_t m_size{}; -}; - -template <> -struct is_bitvec<CFixBitVec> -{ - constexpr static bool value = true; -}; - -template <> -void -gray_code(CFixBitVec& value) -{ - value.rack() ^= (value.rack() >> 1); -} - -template <> -void -gray_code_inv(CFixBitVec& value) -{ - gray_code_inv<CFixBitVec::Rack>(value.rack()); -} - -} // namespace chilbert - -#endif |