aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-08-18 17:58:08 +0200
committerDavid Robillard <d@drobilla.net>2018-09-29 14:47:06 +0200
commit563313018f06137475402f175520573d1dcfe46b (patch)
tree6469cb191f26b38e6f437a792adec5dda91687c0
parentfaa5c52caaa74761dd5e0078b5472da202e955ec (diff)
downloadchilbert-563313018f06137475402f175520573d1dcfe46b.tar.gz
chilbert-563313018f06137475402f175520573d1dcfe46b.tar.bz2
chilbert-563313018f06137475402f175520573d1dcfe46b.zip
Clean up BigBitVec
-rw-r--r--chilbert/BigBitVec.hpp95
1 files changed, 50 insertions, 45 deletions
diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp
index ea2d7bf..7302880 100644
--- a/chilbert/BigBitVec.hpp
+++ b/chilbert/BigBitVec.hpp
@@ -19,30 +19,33 @@
#ifndef CHILBERT_BIGBITVEC_HPP
#define CHILBERT_BIGBITVEC_HPP
-#include "chilbert/FixBitVec.hpp"
+#include "chilbert/Operations.hpp"
#include <algorithm>
#include <cassert>
+#include <climits>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <memory>
-#define FBVS_NEEDED(b) ((std::max(b, size_t(1)) + FBV_BITS - 1) / FBV_BITS)
-
namespace chilbert {
class CBigBitVec
{
public:
+ using Rack = uintptr_t;
+
+ static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT;
+
explicit CBigBitVec(const size_t bits)
- : m_pcRacks{make_racks(FBVS_NEEDED(bits))}
- , m_iRacks{bits == 0 ? 0 : FBVS_NEEDED(bits)}
+ : m_pcRacks{make_racks(num_racks(bits))}
+ , m_iRacks{bits == 0 ? 0 : num_racks(bits)}
{
}
- CBigBitVec(const size_t bits, const FBV_UINT value)
+ CBigBitVec(const size_t bits, const Rack value)
: CBigBitVec{bits}
{
m_pcRacks[0] = value;
@@ -53,28 +56,27 @@ public:
, m_iRacks{vec.m_iRacks}
{
if (vec.m_pcRacks) {
- memcpy(m_pcRacks.get(),
- vec.m_pcRacks.get(),
- sizeof(FBV_UINT) * m_iRacks);
+ memcpy(
+ m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks);
}
}
CBigBitVec(CBigBitVec&& vec) = default;
/// Return the size in bits
- size_t size() const { return m_iRacks * FBV_BITS; }
+ size_t size() const { return m_iRacks * bits_per_rack; }
/// Set all bits to zero
CBigBitVec& reset()
{
- memset(m_pcRacks.get(), 0, sizeof(FBV_UINT) * m_iRacks);
+ memset(m_pcRacks.get(), 0, sizeof(Rack) * m_iRacks);
return *this;
}
/// Set all bits to one
CBigBitVec& set()
{
- memset(m_pcRacks.get(), 0xFF, sizeof(FBV_UINT) * m_iRacks);
+ memset(m_pcRacks.get(), 0xFF, sizeof(Rack) * m_iRacks);
return *this;
}
@@ -88,7 +90,7 @@ public:
}
// Truncate rack that contains the split point
- m_pcRacks[ref.rack] &= FBVN1S(ref.bit);
+ m_pcRacks[ref.rack] &= ((Rack{1} << ref.bit) - 1);
for (size_t i = ref.rack + 1; i < m_iRacks; ++i) {
m_pcRacks[i] = 0;
@@ -99,10 +101,9 @@ public:
bool operator==(const CBigBitVec& vec) const
{
- return (
- rackCount() == vec.rackCount() &&
- (rackCount() == 0 ||
- !memcmp(racks(), vec.racks(), rackCount() * sizeof(FBV_UINT))));
+ return (rackCount() == vec.rackCount() &&
+ (rackCount() == 0 ||
+ !memcmp(racks(), vec.racks(), rackCount() * sizeof(Rack))));
}
bool operator!=(const CBigBitVec& vec) const { return !(*this == vec); }
@@ -128,14 +129,12 @@ public:
if (m_iRacks < vec.m_iRacks) {
m_iRacks = vec.m_iRacks;
m_pcRacks = make_racks(m_iRacks);
- memcpy(m_pcRacks.get(),
- vec.m_pcRacks.get(),
- sizeof(FBV_UINT) * m_iRacks);
+ memcpy(
+ m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks);
} else if (vec.m_iRacks > 0) {
m_iRacks = vec.m_iRacks;
- memcpy(m_pcRacks.get(),
- vec.m_pcRacks.get(),
- sizeof(FBV_UINT) * m_iRacks);
+ memcpy(
+ m_pcRacks.get(), vec.m_pcRacks.get(), sizeof(Rack) * m_iRacks);
} else {
m_iRacks = 0;
m_pcRacks.reset();
@@ -168,7 +167,7 @@ public:
{
assert(index < size());
const Ref ref(index);
- m_pcRacks[ref.rack] &= ~(FBV_UINT{1} << ref.bit);
+ m_pcRacks[ref.rack] &= ~(Rack{1} << ref.bit);
return *this;
}
@@ -186,7 +185,7 @@ public:
{
assert(index < size());
const Ref ref(index);
- m_pcRacks[ref.rack] ^= (FBV1 << ref.bit);
+ m_pcRacks[ref.rack] ^= (Rack{1} << ref.bit);
return *this;
}
@@ -277,7 +276,7 @@ public:
// Do bit shifts.
if (ref.bit > 0) {
- size_t bi = FBV_BITS - ref.bit;
+ size_t bi = bits_per_rack - ref.bit;
size_t i;
for (i = m_iRacks - 1; i >= ref.rack + 1; --i) {
m_pcRacks[i] <<= ref.bit;
@@ -326,7 +325,7 @@ public:
// Do bit shifts.
if (ref.bit > 0) {
- size_t bi = FBV_BITS - ref.bit;
+ size_t bi = bits_per_rack - ref.bit;
size_t i;
for (i = 0; i < m_iRacks - ref.rack - 1; ++i) {
m_pcRacks[i] >>= ref.bit;
@@ -416,7 +415,7 @@ public:
for (size_t i = 0; i < m_iRacks; ++i) {
const int j = ffs(m_pcRacks[i]);
if (j) {
- return (i * FBV_BITS) + static_cast<size_t>(j);
+ return (i * bits_per_rack) + static_cast<size_t>(j);
}
}
return 0;
@@ -442,12 +441,12 @@ public:
}
/// Return the first rack
- FBV_UINT& rack() { return m_pcRacks[0]; }
- FBV_UINT rack() const { return m_pcRacks[0]; }
+ Rack& rack() { return m_pcRacks[0]; }
+ Rack rack() const { return m_pcRacks[0]; }
/// Return a pointer to the racks
- FBV_UINT* racks() { return m_pcRacks.get(); }
- const FBV_UINT* racks() const { return m_pcRacks.get(); }
+ Rack* racks() { return m_pcRacks.get(); }
+ const Rack* racks() const { return m_pcRacks.get(); }
/// Return the number of racks
size_t rackCount() const { return m_iRacks; }
@@ -456,9 +455,10 @@ private:
struct Ref
{
Ref(const size_t bits)
- : rack{bits / FBV_BITS}
- , bit{bits - rack * FBV_BITS}
+ : rack{bits / bits_per_rack}
+ , bit{bits - rack * bits_per_rack}
{
+ assert(bit < bits_per_rack);
}
size_t rack;
@@ -467,14 +467,19 @@ private:
struct RacksDeleter
{
- void operator()(FBV_UINT* const racks) { free(racks); }
+ void operator()(Rack* const racks) { free(racks); }
};
- using RacksPtr = std::unique_ptr<FBV_UINT[], RacksDeleter>;
+ using RacksPtr = std::unique_ptr<Rack[], RacksDeleter>;
+
+ static size_t 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<FBV_UINT*>(calloc(n, sizeof(FBV_UINT)))};
+ return RacksPtr{static_cast<Rack*>(calloc(n, sizeof(Rack)))};
}
// Right rotates entire racks (in place).
@@ -488,9 +493,9 @@ private:
size_t c = 0;
for (size_t v = 0; c < m_iRacks; ++v) {
- size_t t = v;
- size_t tp = v + k;
- const FBV_UINT tmp = m_pcRacks[v];
+ size_t t = v;
+ size_t tp = v + k;
+ const Rack tmp = m_pcRacks[v];
c++;
while (tp != v) {
m_pcRacks[t] = m_pcRacks[tp];
@@ -513,13 +518,13 @@ template <>
void
grayCode(CBigBitVec& value)
{
- FBV_UINT s = 0;
+ CBigBitVec::Rack s = 0;
for (intptr_t i = static_cast<intptr_t>(value.rackCount() - 1); i >= 0;
--i) {
- const FBV_UINT t = value.racks()[i] & 1;
+ const auto t = value.racks()[i] & 1;
grayCode(value.racks()[i]);
- value.racks()[i] ^= (s << (FBV_BITS - 1));
+ value.racks()[i] ^= (s << (CBigBitVec::bits_per_rack - 1));
s = t;
}
}
@@ -528,11 +533,11 @@ template <>
void
grayCodeInv(CBigBitVec& value)
{
- FBV_UINT s = 0;
+ CBigBitVec::Rack s = 0;
for (intptr_t i = static_cast<intptr_t>(value.rackCount() - 1); i >= 0;
--i) {
- FBV_UINT& rack = value.racks()[i];
+ auto& rack = value.racks()[i];
grayCodeInv(rack);
if (s) {
rack = ~rack;