From 43e1a12b5bce11b4a28a53acca243e35c2be6d3e Mon Sep 17 00:00:00 2001
From: evuez <julien@mulga.net>
Date: Wed, 3 Apr 2024 22:43:16 +0200
Subject: Initial commit

---
 src/common/slot_map.rs | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 85 insertions(+)
 create mode 100644 src/common/slot_map.rs

(limited to 'src/common/slot_map.rs')

diff --git a/src/common/slot_map.rs b/src/common/slot_map.rs
new file mode 100644
index 0000000..110ee59
--- /dev/null
+++ b/src/common/slot_map.rs
@@ -0,0 +1,85 @@
+use std::collections::HashMap;
+
+pub struct SlotMap<T> {
+    bitmap: u64,
+    map: HashMap<u32, T>,
+}
+
+impl<T> SlotMap<T> {
+    pub fn new() -> Self {
+        Self {
+            bitmap: u64::MAX,
+            map: HashMap::new(),
+        }
+    }
+
+    pub fn insert(&mut self, value: T) -> Option<u32> {
+        let slot = self.get_free_slot()?;
+        self.map.insert(slot, value);
+        self.use_slot(slot);
+
+        Some(slot)
+    }
+
+    pub fn remove(&mut self, slot: u32) -> Option<T> {
+        let value = self.map.remove(&slot)?;
+        self.release_slot(slot);
+
+        Some(value)
+    }
+
+    pub fn get(&self, slot: u32) -> Option<&T> {
+        self.map.get(&slot)
+    }
+
+    pub fn get_mut(&mut self, slot: u32) -> Option<&mut T> {
+        self.map.get_mut(&slot)
+    }
+
+    fn get_free_slot(&self) -> Option<u32> {
+        let leading_zeros = self.bitmap.leading_zeros();
+
+        if leading_zeros > 63 {
+            None
+        } else {
+            Some(63 - leading_zeros)
+        }
+    }
+
+    fn use_slot(&mut self, slot: u32) {
+        let mask = u64::MAX;
+        println!("{:0b}", self.bitmap);
+        self.bitmap &= !(1 << slot) & mask;
+    }
+
+    fn release_slot(&mut self, slot: u32) {
+        self.bitmap |= 1 << slot;
+    }
+}
+
+#[test]
+fn releases_a_slot_after_removal() {
+    let mut slot_map = SlotMap::new();
+
+    assert_eq!(slot_map.insert(1), Some(63));
+    assert_eq!(slot_map.insert(2), Some(62));
+    assert_eq!(slot_map.insert(3), Some(61));
+
+    assert_eq!(slot_map.remove(&62), Some(2));
+
+    assert_eq!(slot_map.insert(4), Some(62));
+    assert_eq!(slot_map.insert(5), Some(60));
+}
+
+#[test]
+fn uses_all_available_slots() {
+    let mut slot_map = SlotMap::new();
+
+    for x in 0..64 {
+        assert_eq!(slot_map.insert(0), Some(63 - x));
+    }
+
+    assert_eq!(slot_map.insert(0), None);
+    assert_eq!(slot_map.remove(&43), Some(0));
+    assert_eq!(slot_map.insert(0), Some(43));
+}
-- 
cgit v1.2.3