aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-08-19 09:28:01 +0200
committerDavid Robillard <d@drobilla.net>2018-09-29 14:47:32 +0200
commit8bf175b6739e6f84128b1783c018b5c0923670cb (patch)
treef48c796c3ab15db4b840142e5f2e60f1584d08dd
parent09f8d4a4b20f234dafcdf2ce667f220801b9210f (diff)
downloadchilbert-8bf175b6739e6f84128b1783c018b5c0923670cb.tar.gz
chilbert-8bf175b6739e6f84128b1783c018b5c0923670cb.tar.bz2
chilbert-8bf175b6739e6f84128b1783c018b5c0923670cb.zip
Factor out BitVecMask
-rw-r--r--chilbert/BigBitVec.hpp62
-rw-r--r--chilbert/BitVecMask.hpp72
2 files changed, 82 insertions, 52 deletions
diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp
index 7fe260e..7038662 100644
--- a/chilbert/BigBitVec.hpp
+++ b/chilbert/BigBitVec.hpp
@@ -19,6 +19,7 @@
#ifndef CHILBERT_BIGBITVEC_HPP
#define CHILBERT_BIGBITVEC_HPP
+#include "chilbert/BitVecMask.hpp"
#include "chilbert/Operations.hpp"
#include <algorithm>
@@ -36,53 +37,10 @@ class CBigBitVec
{
public:
using Rack = uintptr_t;
+ using Mask = BitVecMask<Rack>;
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++()
- {
- if ((m_mask <<= 1) == 0) {
- m_mask = 1;
- ++m_rack;
- }
- }
-
- void operator--()
- {
- if ((m_mask >>= 1) == 0) {
- m_mask = Rack{1} << (bits_per_rack - 1);
- --m_rack;
- }
- }
-
- bool operator==(const Mask& mask) const
- {
- return m_rack == mask.m_rack && m_mask == mask.m_mask;
- }
-
- bool operator!=(const Mask& mask) const { return !operator==(mask); }
-
- private:
- friend class CBigBitVec;
-
- Mask(const size_t index)
- : m_rack{index / bits_per_rack}
- , m_mask{Rack{1} << (index - m_rack * bits_per_rack)}
- {
- }
-
- size_t m_rack;
- Rack m_mask;
- };
-
explicit CBigBitVec(const size_t bits)
: m_pcRacks{make_racks(num_racks(bits))}
, m_size{bits}
@@ -136,9 +94,9 @@ public:
{
const Mask m = mask(bits);
- m_pcRacks[m.m_rack] &= (m.m_mask - 1);
+ m_pcRacks[m.rack] &= (m.mask - 1);
- for (size_t i = m.m_rack + 1; i < rackCount(); ++i) {
+ for (size_t i = m.rack + 1; i < rackCount(); ++i) {
m_pcRacks[i] = 0;
}
@@ -193,7 +151,7 @@ public:
/// Return the value of the bit covered by `mask`
bool test(const Mask mask) const
{
- return m_pcRacks[mask.m_rack] & mask.m_mask;
+ return m_pcRacks[mask.rack] & mask.mask;
}
/// Return the value of the `index`th bit
@@ -202,7 +160,7 @@ public:
/// Set the bit covered by `mask` to 1
CBigBitVec& set(const Mask mask)
{
- m_pcRacks[mask.m_rack] |= mask.m_mask;
+ m_pcRacks[mask.rack] |= mask.mask;
return *this;
}
@@ -212,7 +170,7 @@ public:
/// Reset the bit covered by `mask` to 0
CBigBitVec& reset(const Mask mask)
{
- m_pcRacks[mask.m_rack] &= ~mask.m_mask;
+ m_pcRacks[mask.rack] &= ~mask.mask;
return *this;
}
@@ -222,8 +180,8 @@ public:
/// Set the bit covered by `mask` to `value`
CBigBitVec& set(const Mask mask, const bool value)
{
- auto& rack = m_pcRacks[mask.m_rack];
- rack ^= (-Rack{value} ^ rack) & mask.m_mask;
+ auto& rack = m_pcRacks[mask.rack];
+ rack ^= (-Rack{value} ^ rack) & mask.mask;
return *this;
}
@@ -236,7 +194,7 @@ public:
/// Flip the value of the bit covered by `mask`
CBigBitVec& flip(const Mask mask)
{
- m_pcRacks[mask.m_rack] ^= mask.m_mask;
+ m_pcRacks[mask.rack] ^= mask.mask;
return *this;
}
diff --git a/chilbert/BitVecMask.hpp b/chilbert/BitVecMask.hpp
new file mode 100644
index 0000000..af98894
--- /dev/null
+++ b/chilbert/BitVecMask.hpp
@@ -0,0 +1,72 @@
+/*
+ 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_BITVECMASK_HPP
+#define CHILBERT_BITVECMASK_HPP
+
+#include <climits>
+#include <cstddef>
+
+namespace chilbert {
+
+/** 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.
+ */
+template <class Rack>
+struct BitVecMask
+{
+ static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT;
+
+ BitVecMask(const size_t index)
+ : rack{index / bits_per_rack}
+ , mask{Rack{1} << (index - rack * bits_per_rack)}
+ {
+ }
+
+ void operator++()
+ {
+ if ((mask <<= 1) == 0) {
+ mask = 1;
+ ++rack;
+ }
+ }
+
+ void operator--()
+ {
+ if ((mask >>= 1) == 0) {
+ mask = Rack{1} << (bits_per_rack - 1);
+ --rack;
+ }
+ }
+
+ bool operator==(const BitVecMask& rhs) const
+ {
+ return rack == rhs.rack && mask == rhs.mask;
+ }
+
+ bool operator!=(const BitVecMask& rhs) const { return !operator==(rhs); }
+
+ size_t rack;
+ Rack mask;
+};
+
+} // namespace chilbert
+
+#endif