From 601c2080e9667ba686e39823c1ebd58844550002 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 19 Aug 2018 17:27:44 +0200 Subject: Rename bit vector types --- chilbert/BigBitVec.hpp | 148 ----------------- chilbert/DynamicBitVec.hpp | 148 +++++++++++++++++ chilbert/FixBitVec.hpp | 384 ------------------------------------------- chilbert/Hilbert.ipp | 54 +++--- chilbert/SmallBitVec.hpp | 384 +++++++++++++++++++++++++++++++++++++++++++ chilbert/StaticBitVec.hpp | 4 +- test/test_bitvec.cpp | 38 ++--- test/test_gray_code_rank.cpp | 34 ++-- test/test_hilbert.cpp | 46 +++--- test/test_utils.hpp | 4 +- 10 files changed, 623 insertions(+), 621 deletions(-) delete mode 100644 chilbert/BigBitVec.hpp create mode 100644 chilbert/DynamicBitVec.hpp delete mode 100644 chilbert/FixBitVec.hpp create mode 100644 chilbert/SmallBitVec.hpp diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp deleted file mode 100644 index be6e5e0..0000000 --- a/chilbert/BigBitVec.hpp +++ /dev/null @@ -1,148 +0,0 @@ -/* - Copyright (C) 2018 David Robillard - Copyright (C) 2006-2007 Chris Hamilton - - 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 . -*/ - -#ifndef CHILBERT_BIGBITVEC_HPP -#define CHILBERT_BIGBITVEC_HPP - -#include "chilbert/BitVecIndex.hpp" -#include "chilbert/BitVecIterator.hpp" -#include "chilbert/BitVecMask.hpp" -#include "chilbert/MultiBitVec.hpp" -#include "chilbert/Operations.hpp" - -#include -#include -#include -#include -#include - -namespace chilbert { - -class CBigBitVec : public MultiBitVec -{ -public: - struct RacksDeleter - { - void operator()(Rack* const racks) { free(racks); } - }; - - struct NullDeleter - { - void operator()(const Rack* const) {} - }; - - using RacksPtr = std::unique_ptr; - using ConstRacksPtr = std::unique_ptr; - - explicit CBigBitVec(const size_t bits) - : m_racks{make_racks(calculate_num_racks(bits))} - , m_size{bits} - { - } - - CBigBitVec(const size_t bits, const Rack value) - : CBigBitVec{bits} - { - m_racks[0] = value; - } - - CBigBitVec(const CBigBitVec& vec) - : m_racks{make_racks(vec.num_racks())} - , m_size{vec.m_size} - { - if (vec.data()) { - memcpy(data(), vec.data(), data_size()); - } - } - - CBigBitVec(CBigBitVec&& vec) = default; - - CBigBitVec& operator=(const CBigBitVec& vec) - { - if (num_racks() < vec.num_racks()) { - m_racks = make_racks(vec.num_racks()); - m_size = vec.m_size; - memcpy(data(), vec.data(), data_size()); - } else if (vec.num_racks() > 0) { - m_size = vec.m_size; - memcpy(data(), vec.data(), data_size()); - } else { - m_size = 0; - m_racks.reset(); - } - - return *this; - } - - CBigBitVec& operator=(CBigBitVec&& vec) = default; - - /// Return the size in bits - size_t size() const { return m_size; } - - /// Return a reference to the `index`th rack - const Rack& rack(const size_t index) const { return m_racks[index]; } - Rack& rack(const size_t index) { return m_racks[index]; } - - /// Return a raw pointer to the racks - Rack* data() { return m_racks.get(); } - const Rack* data() const { return m_racks.get(); } - - /// Return the total size of all racks in bytes - size_t data_size() const { return num_racks() * sizeof(Rack); } - - /// Return the number of racks - size_t num_racks() const { return calculate_num_racks(m_size); } - -private: - static size_t calculate_num_racks(const size_t bits) - { - return (std::max(bits, size_t(1)) + bits_per_rack - 1) / bits_per_rack; - } - - static RacksPtr make_racks(const size_t n) - { - return RacksPtr{static_cast(calloc(n, sizeof(Rack)))}; - } - - RacksPtr m_racks; - size_t m_size; -}; - -template <> -struct is_bitvec -{ - constexpr static bool value = true; -}; - -template <> -void -gray_code(CBigBitVec& value) -{ - gray_code(static_cast&>(value)); -} - -template <> -void -gray_code_inv(CBigBitVec& value) -{ - gray_code_inv(static_cast&>(value)); -} - -} // namespace chilbert - -#endif diff --git a/chilbert/DynamicBitVec.hpp b/chilbert/DynamicBitVec.hpp new file mode 100644 index 0000000..ab7d00b --- /dev/null +++ b/chilbert/DynamicBitVec.hpp @@ -0,0 +1,148 @@ +/* + Copyright (C) 2018 David Robillard + Copyright (C) 2006-2007 Chris Hamilton + + 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 . +*/ + +#ifndef CHILBERT_DYNAMICBITVEC_HPP +#define CHILBERT_DYNAMICBITVEC_HPP + +#include "chilbert/BitVecIndex.hpp" +#include "chilbert/BitVecIterator.hpp" +#include "chilbert/BitVecMask.hpp" +#include "chilbert/MultiBitVec.hpp" +#include "chilbert/Operations.hpp" + +#include +#include +#include +#include +#include + +namespace chilbert { + +class DynamicBitVec : public MultiBitVec +{ +public: + struct RacksDeleter + { + void operator()(Rack* const racks) { free(racks); } + }; + + struct NullDeleter + { + void operator()(const Rack* const) {} + }; + + using RacksPtr = std::unique_ptr; + using ConstRacksPtr = std::unique_ptr; + + explicit DynamicBitVec(const size_t bits) + : m_racks{make_racks(calculate_num_racks(bits))} + , m_size{bits} + { + } + + DynamicBitVec(const size_t bits, const Rack value) + : DynamicBitVec{bits} + { + m_racks[0] = value; + } + + DynamicBitVec(const DynamicBitVec& vec) + : m_racks{make_racks(vec.num_racks())} + , m_size{vec.m_size} + { + if (vec.data()) { + memcpy(data(), vec.data(), data_size()); + } + } + + DynamicBitVec(DynamicBitVec&& vec) = default; + + DynamicBitVec& operator=(const DynamicBitVec& vec) + { + if (num_racks() < vec.num_racks()) { + m_racks = make_racks(vec.num_racks()); + m_size = vec.m_size; + memcpy(data(), vec.data(), data_size()); + } else if (vec.num_racks() > 0) { + m_size = vec.m_size; + memcpy(data(), vec.data(), data_size()); + } else { + m_size = 0; + m_racks.reset(); + } + + return *this; + } + + DynamicBitVec& operator=(DynamicBitVec&& vec) = default; + + /// Return the size in bits + size_t size() const { return m_size; } + + /// Return a reference to the `index`th rack + const Rack& rack(const size_t index) const { return m_racks[index]; } + Rack& rack(const size_t index) { return m_racks[index]; } + + /// Return a raw pointer to the racks + Rack* data() { return m_racks.get(); } + const Rack* data() const { return m_racks.get(); } + + /// Return the total size of all racks in bytes + size_t data_size() const { return num_racks() * sizeof(Rack); } + + /// Return the number of racks + size_t num_racks() const { return calculate_num_racks(m_size); } + +private: + static size_t calculate_num_racks(const size_t bits) + { + return (std::max(bits, size_t(1)) + bits_per_rack - 1) / bits_per_rack; + } + + static RacksPtr make_racks(const size_t n) + { + return RacksPtr{static_cast(calloc(n, sizeof(Rack)))}; + } + + RacksPtr m_racks; + size_t m_size; +}; + +template <> +struct is_bitvec +{ + constexpr static bool value = true; +}; + +template <> +void +gray_code(DynamicBitVec& value) +{ + gray_code(static_cast&>(value)); +} + +template <> +void +gray_code_inv(DynamicBitVec& value) +{ + gray_code_inv(static_cast&>(value)); +} + +} // namespace chilbert + +#endif 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 - Copyright (C) 2006-2007 Chris Hamilton - - 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 . -*/ - -#ifndef CHILBERT_FIXBITVEC_HPP -#define CHILBERT_FIXBITVEC_HPP - -#include "chilbert/Operations.hpp" - -#include -#include -#include -#include -#include - -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(chilbert::find_first(m_rack)); - } - - /// Return the number of set bits - size_t count() const { return static_cast(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 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 - { - 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 - { - 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 -{ - 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(value.rack()); -} - -} // namespace chilbert - -#endif diff --git a/chilbert/Hilbert.ipp b/chilbert/Hilbert.ipp index 81eb7fd..0b02fba 100644 --- a/chilbert/Hilbert.ipp +++ b/chilbert/Hilbert.ipp @@ -19,10 +19,10 @@ #ifndef CHILBERT_ALGORITHM_HPP #define CHILBERT_ALGORITHM_HPP -#include "chilbert/BigBitVec.hpp" -#include "chilbert/FixBitVec.hpp" +#include "chilbert/DynamicBitVec.hpp" #include "chilbert/GrayCodeRank.hpp" #include "chilbert/Hilbert.hpp" +#include "chilbert/SmallBitVec.hpp" #include "chilbert/StaticBitVec.hpp" #include @@ -50,8 +50,8 @@ num_bits(const T&, std::enable_if_t::value>* = nullptr) template size_t num_bits(const T& vec, - std::enable_if_t::value || - std::is_same::value>* = nullptr) + std::enable_if_t::value || + std::is_same::value>* = nullptr) { return vec.size(); } @@ -316,15 +316,15 @@ coords_to_compact_index(const P* const p, size_t* const ds = new size_t[m]; if (mn > FBV_BITS) { - CBigBitVec h(mn); - detail::coords_to_index( + DynamicBitVec h(mn); + detail::coords_to_index( p, m, n, h, std::move(scratch), ds); - compact_index(ms, ds, n, m, h, hc); + compact_index(ms, ds, n, m, h, hc); } else { - CFixBitVec h(mn); - detail::coords_to_index( + SmallBitVec h(mn); + detail::coords_to_index( p, m, n, h, std::move(scratch), ds); - compact_index(ms, ds, n, m, h, hc); + compact_index(ms, ds, n, m, h, hc); } delete[] ds; @@ -415,10 +415,11 @@ coords_to_index(const P* const p, const size_t m, const size_t n, H& h) if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - detail::coords_to_index(p, m, n, h, CFixBitVec(n)); + detail::coords_to_index(p, m, n, h, SmallBitVec(n)); } else { - // Otherwise, they must be BigBitVecs - detail::coords_to_index(p, m, n, h, CBigBitVec(n)); + // Otherwise, they must be DynamicBitVecs + detail::coords_to_index( + p, m, n, h, DynamicBitVec(n)); } } @@ -433,10 +434,11 @@ index_to_coords(P* const p, const size_t m, const size_t n, const H& h) if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - detail::index_to_coords(p, m, n, h, CFixBitVec(n)); + detail::index_to_coords(p, m, n, h, SmallBitVec(n)); } else { - // Otherwise, they must be BigBitVecs - detail::index_to_coords(p, m, n, h, CBigBitVec(n)); + // Otherwise, they must be DynamicBitVecs + detail::index_to_coords( + p, m, n, h, DynamicBitVec(n)); } } @@ -453,12 +455,12 @@ coords_to_compact_index(const P* const p, if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - detail::coords_to_compact_index( - p, ms, n, hc, CFixBitVec(n), M, m); + detail::coords_to_compact_index( + p, ms, n, hc, SmallBitVec(n), M, m); } else { - // Otherwise, they must be BigBitVecs - detail::coords_to_compact_index( - p, ms, n, hc, CBigBitVec(n), M, m); + // Otherwise, they must be DynamicBitVecs + detail::coords_to_compact_index( + p, ms, n, hc, DynamicBitVec(n), M, m); } } @@ -475,13 +477,13 @@ compact_index_to_coords(P* const p, if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - CFixBitVec scratch(n); - detail::compact_index_to_coords( + SmallBitVec scratch(n); + detail::compact_index_to_coords( p, ms, n, hc, std::move(scratch), M, m); } else { - // Otherwise, they must be BigBitVecs - CBigBitVec scratch(n); - detail::compact_index_to_coords( + // Otherwise, they must be DynamicBitVecs + DynamicBitVec scratch(n); + detail::compact_index_to_coords( p, ms, n, hc, std::move(scratch), M, m); } } diff --git a/chilbert/SmallBitVec.hpp b/chilbert/SmallBitVec.hpp new file mode 100644 index 0000000..f11dab0 --- /dev/null +++ b/chilbert/SmallBitVec.hpp @@ -0,0 +1,384 @@ +/* + Copyright (C) 2018 David Robillard + Copyright (C) 2006-2007 Chris Hamilton + + 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 . +*/ + +#ifndef CHILBERT_SMALLBITVEC_HPP +#define CHILBERT_SMALLBITVEC_HPP + +#include "chilbert/Operations.hpp" + +#include +#include +#include +#include +#include + +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 SmallBitVec +{ +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 SmallBitVec; + + Mask(const size_t index) + : m_mask{index < bits_per_rack ? Rack{1} << index : 0} + { + } + + Rack m_mask; + }; + + explicit SmallBitVec(const size_t bits) + : m_rack{0} + , m_size{bits} + { + assert(bits <= bits_per_rack); + } + + SmallBitVec(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 + SmallBitVec& set() + { + m_rack = FBV1S & FBVN1S(size()); + return *this; + } + + /// Set all bits to zero + SmallBitVec& 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 + SmallBitVec& set(const Mask mask) + { + m_rack |= mask.m_mask; + return *this; + } + + /// Set the `index`th bit to 1 + SmallBitVec& set(const size_t index) { return set(mask(index)); } + + /// Reset the bit covered by `mask` to 0 + SmallBitVec& reset(const Mask mask) + { + m_rack &= ~mask.m_mask; + return *this; + } + + /// Reset the `index`th bit to 0 + SmallBitVec& reset(const size_t index) { return reset(mask(index)); } + + /// Set the bit covered by `mask` to `value` + SmallBitVec& 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` + SmallBitVec& set(const size_t index, const bool value) + { + return set(mask(index), value); + } + + /// Flip the value of the bit covered by `mask` + SmallBitVec& flip(const Mask mask) + { + m_rack ^= mask.m_mask; + return *this; + } + + /// Flip the value of the `index`th bit + SmallBitVec& flip(const size_t index) { return flip(mask(index)); } + + bool operator==(const SmallBitVec& vec) const + { + return m_rack == vec.m_rack; + } + + bool operator!=(const SmallBitVec& vec) const + { + return m_rack != vec.m_rack; + } + + bool operator<(const SmallBitVec& vec) const { return m_rack < vec.m_rack; } + + SmallBitVec& operator=(const Rack i) + { + m_rack = i; + return *this; + } + + SmallBitVec& operator&=(const SmallBitVec& vec) + { + m_rack &= vec.m_rack; + return *this; + } + + SmallBitVec& operator|=(const SmallBitVec& vec) + { + m_rack |= vec.m_rack; + return *this; + } + + SmallBitVec& operator^=(const SmallBitVec& vec) + { + m_rack ^= vec.m_rack; + return *this; + } + + SmallBitVec& operator^=(const Rack i) + { + m_rack ^= i; + return *this; + } + + SmallBitVec& operator<<=(const size_t bits) + { + assert(bits < size()); + m_rack <<= bits; + return *this; + } + + SmallBitVec& operator>>=(const size_t bits) + { + assert(bits < size()); + m_rack >>= bits; + return *this; + } + + /// Right-rotate by `bits` positions + SmallBitVec& 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 + SmallBitVec& 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(chilbert::find_first(m_rack)); + } + + /// Return the number of set bits + size_t count() const { return static_cast(pop_count(m_rack)); } + + /// Flip all bits (one's complement) + SmallBitVec& 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 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 + { + public: + void set() { m_vec->set(*this); } + void reset() { m_vec->reset(*this); } + + private: + friend class SmallBitVec; + + iterator(SmallBitVec& vec, const size_t index) + : iterator_base{vec, index} + { + } + }; + + class const_iterator : public iterator_base + { + private: + friend class SmallBitVec; + + const_iterator(const SmallBitVec& 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 +{ + constexpr static bool value = true; +}; + +template <> +void +gray_code(SmallBitVec& value) +{ + value.rack() ^= (value.rack() >> 1); +} + +template <> +void +gray_code_inv(SmallBitVec& value) +{ + gray_code_inv(value.rack()); +} + +} // namespace chilbert + +#endif diff --git a/chilbert/StaticBitVec.hpp b/chilbert/StaticBitVec.hpp index 64b8c99..24152e1 100644 --- a/chilbert/StaticBitVec.hpp +++ b/chilbert/StaticBitVec.hpp @@ -45,13 +45,13 @@ public: StaticBitVec() = default; - /// Constructor for compatibility with CBigBitVec + /// Constructor for compatibility with DynamicBitVec explicit StaticBitVec(const size_t bits) { assert(bits == size()); } - /// Constructor for compatibility with CBigBitVec + /// Constructor for compatibility with DynamicBitVec StaticBitVec(const size_t bits, const Rack value) : StaticBitVec{bits} { diff --git a/test/test_bitvec.cpp b/test/test_bitvec.cpp index fdadb19..ffdf823 100644 --- a/test/test_bitvec.cpp +++ b/test/test_bitvec.cpp @@ -19,8 +19,8 @@ #include "test_utils.hpp" -#include "chilbert/BigBitVec.hpp" -#include "chilbert/FixBitVec.hpp" +#include "chilbert/DynamicBitVec.hpp" +#include "chilbert/SmallBitVec.hpp" #include "chilbert/StaticBitVec.hpp" #include @@ -331,23 +331,23 @@ main() { Context ctx; - // test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); + // test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); test, 0>(ctx); test, 1>(ctx); diff --git a/test/test_gray_code_rank.cpp b/test/test_gray_code_rank.cpp index fa3fe3c..ed31d44 100644 --- a/test/test_gray_code_rank.cpp +++ b/test/test_gray_code_rank.cpp @@ -19,9 +19,9 @@ #include "test_utils.hpp" -#include "chilbert/BigBitVec.hpp" -#include "chilbert/FixBitVec.hpp" +#include "chilbert/DynamicBitVec.hpp" #include "chilbert/GrayCodeRank.hpp" +#include "chilbert/SmallBitVec.hpp" #include "chilbert/StaticBitVec.hpp" #include @@ -123,21 +123,21 @@ main() { Context ctx; - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); - test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); + test(ctx); test, 64, 1>(ctx); test, 64, 31>(ctx); diff --git a/test/test_hilbert.cpp b/test/test_hilbert.cpp index 0daf749..3abcdd5 100644 --- a/test/test_hilbert.cpp +++ b/test/test_hilbert.cpp @@ -19,8 +19,8 @@ #include "test_utils.hpp" -#include "chilbert/BigBitVec.hpp" -#include "chilbert/FixBitVec.hpp" +#include "chilbert/DynamicBitVec.hpp" +#include "chilbert/SmallBitVec.hpp" #include "chilbert/Hilbert.hpp" #include "chilbert/StaticBitVec.hpp" @@ -171,17 +171,17 @@ main() { Context ctx; - test_standard(ctx); - test_standard(ctx); - test_standard(ctx); - test_standard(ctx); - test_standard(ctx); - test_standard(ctx); - test_standard(ctx); + test_standard(ctx); + test_standard(ctx); + test_standard(ctx); + test_standard(ctx); + test_standard(ctx); + test_standard(ctx); + test_standard(ctx); - test_standard(ctx); - test_standard(ctx); - test_standard(ctx); + test_standard(ctx); + test_standard(ctx); + test_standard(ctx); test_standard, 4, 2>(ctx); test_standard, 32, 2>(ctx); @@ -194,17 +194,17 @@ main() test_standard, 32, 64>(ctx); test_standard, 63, 128>(ctx); - test_compact(ctx); - test_compact(ctx); - test_compact(ctx); - test_compact(ctx); - test_compact(ctx); - test_compact(ctx); - test_compact(ctx); - - test_compact(ctx); - test_compact(ctx); - test_compact(ctx); + test_compact(ctx); + test_compact(ctx); + test_compact(ctx); + test_compact(ctx); + test_compact(ctx); + test_compact(ctx); + test_compact(ctx); + + test_compact(ctx); + test_compact(ctx); + test_compact(ctx); test_compact, 4, 2>(ctx); test_compact, 32, 2>(ctx); diff --git a/test/test_utils.hpp b/test/test_utils.hpp index 37db804..7c52f56 100644 --- a/test/test_utils.hpp +++ b/test/test_utils.hpp @@ -20,8 +20,8 @@ #undef NDEBUG -#include "chilbert/BigBitVec.hpp" -#include "chilbert/FixBitVec.hpp" +#include "chilbert/DynamicBitVec.hpp" +#include "chilbert/SmallBitVec.hpp" #include #include -- cgit v1.2.1