Factor out BitVecMask

1 files changed, 72 insertions, 0 deletions

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