1 files changed, 59 insertions, 0 deletions
diff --git a/crates/buddy_allocator/src/bitvec.rs b/crates/buddy_allocator/src/bitvec.rs
new file mode 100644
index 0000000..856d579
--- /dev/null
+++ b/crates/buddy_allocator/src/bitvec.rs
@@ -0,0 +1,59 @@
+use contracts::requires;
+use core::{fmt, mem::transmute};
+
+/// A fixed-length vector of bits.
+pub struct BitVec([usize]);
+
+impl BitVec {
+    fn from_mut(words: &mut [usize]) -> &mut BitVec {
+        // SAFETY: The types have a newtype relationship.
+        unsafe { transmute(words) }
+    }
+
+    fn from_ref(words: &[usize]) -> &BitVec {
+        // SAFETY: The types have a newtype relationship.
+        unsafe { transmute(words) }
+    }
+
+    /// Retrieves the value of a bit from the BitVec.
+    #[requires(i < self.len())]
+    pub fn get(&self, i: usize) -> bool {
+        let word_index = i / usize::BITS as usize;
+        let subword_index = i % usize::BITS as usize;
+        let one_hot = 1 << subword_index;
+        (self.0[word_index] & one_hot) != 0
+    }
+
+    /// Returns whether the BitVec is empty.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+
+    /// Returns the number of bits in the BitVec.
+    pub fn len(&self) -> usize {
+        self.0.len() * usize::BITS as usize
+    }
+
+    /// Sets the value of a bit in the BitVec.
+    #[requires(i < self.len())]
+    pub fn set(&mut self, i: usize, value: bool) {
+        let word_index = i / usize::BITS as usize;
+        let subword_index = i % usize::BITS as usize;
+        let one_hot = 1 << subword_index;
+        if value {
+            self.0[word_index] |= one_hot;
+        } else {
+            self.0[word_index] &= !one_hot;
+        }
+    }
+}
+
+impl fmt::Debug for BitVec {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        write!(fmt, "BitVec(")?;
+        for word in &self.0 {
+            write!(fmt, "{word:064b}")?;
+        }
+        write!(fmt, ")")
+    }
+}