1 files changed, 49 insertions, 0 deletions
diff --git a/src/disk/bitmap.rs b/src/disk/bitmap.rs
new file mode 100644
index 0000000..a5a9cc4
--- /dev/null
+++ b/src/disk/bitmap.rs
@@ -0,0 +1,49 @@
+use crate::block_device::{BlockDevice, BLOCK_SIZE};
+use std::sync::Arc;
+
+pub struct Bitmap {
+    pub starting_block: usize,
+    pub length: usize,
+    pub device: Arc<dyn BlockDevice>,
+    pub data: Vec<u8>,
+    pub dirty_blocks: Vec<usize>,
+}
+
+impl Bitmap {
+    pub fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> Self {
+        Self {
+            starting_block,
+            length,
+            device,
+            data: vec![0u8; length * BLOCK_SIZE],
+            dirty_blocks: Vec::new(),
+        }
+    }
+    pub fn allocate(&mut self) -> usize {
+        for (i, byte) in self.data.iter_mut().enumerate() {
+            let leading_ones = byte.leading_ones();
+            if leading_ones != 8 {
+                *byte |= (1 << (7 - leading_ones)) as u8;
+                self.dirty_blocks.push(i / BLOCK_SIZE);
+                return i * 8 + leading_ones as usize;
+            }
+        }
+        panic!("No more space for allocation!")
+    }
+
+    pub fn query(&self, index: usize) -> bool {
+        self.data[index / 8] & ((1 << (7 - index % 8)) as u8) != 0
+    }
+
+    fn write_back(&mut self) {
+        for block_index_offset in self.dirty_blocks.iter() {
+            let buffer_front_index = BLOCK_SIZE * block_index_offset;
+            let buffer_back_index = BLOCK_SIZE * (block_index_offset + 1);
+            self.device.write(
+                self.starting_block + block_index_offset,
+                &self.data[buffer_front_index..buffer_back_index],
+            );
+        }
+        self.dirty_blocks = Vec::new();
+    }
+}