CSY/reowolf Changeset - bc7021d551ad · Centrum Wiskunde & Informatica (CWI)

Changeset - bc7021d551ad

Parent rev.

Child rev.

[Not reviewed]

0 2 0

Christopher Esterhuyse - 5 years ago 2020-02-20 21:49:25
christopher.esterhuyse@gmail.com

bitsets are so great

2 files changed with 35 insertions and 23 deletions:

src/runtime/experimental/bits.rs

src/runtime/experimental/vec_storage.rs

0 comments (0 inline, 0 general)

src/runtime/experimental/bits.rs

➞

Show inline comments

 use crate::common::*;
 use std::alloc::Layout;
 /// Given an iterator over BitChunk Items, iterates over the indices (each represented as a u32) for which the bit is SET,
 /// treating the bits in the BitChunk as a contiguous array.
@@ @@ -107,17 +108,15 @@ impl From<[u32; 2]> for Pair { @@
+    }
+}
 struct BitMatrix {
     bounds: Pair,
     buffer: *mut usize,
     bounds: Pair,
     layout: Layout, // layout of the currently-allocated buffer
+}
 impl Drop for BitMatrix {
     fn drop(&mut self) {
         let total_chunks = Self::row_chunks(self.bounds.property as usize)
             * Self::column_chunks(self.bounds.entity as usize);
         let layout = Self::layout_for(total_chunks);
         unsafe {
             // ?
             std::alloc::dealloc(self.buffer as *mut u8, layout);
+            std::alloc::dealloc(self.buffer as *mut u8, self.layout);
+        }
+    }
+}
@@ @@ -188,18 +187,12 @@ impl BitMatrix { @@
         assert!(at.property < self.bounds.property);
+    }
-    fn layout_for(mut total_chunks: usize) -> std::alloc::Layout {
     fn layout_for(total_chunks: usize) -> std::alloc::Layout {
         unsafe {
             // this layout is ALWAYS valid:
             // 1. size is always nonzero
             // 2. size is always a multiple of 4 and 4-aligned
             if total_chunks == 0 {
                 total_chunks = 1;
+            }
             std::alloc::Layout::from_size_align_unchecked(
                 usize_bytes() * total_chunks,
                 usize_bytes(),
+            )
             Layout::from_size_align_unchecked(usize_bytes() * total_chunks.max(1), usize_bytes())
+        }
+    }
     /////////
@@ @@ -217,7 +210,7 @@ impl BitMatrix { @@
             buffer = std::alloc::alloc(layout) as *mut usize;
             buffer.write_bytes(0u8, total_chunks);
         };
         Self { buffer, bounds }
+        Self { buffer, bounds, layout }
+    }
     fn set(&mut self, at: Pair) {
         self.assert_within_bounds(at);
@@ @@ -297,12 +290,6 @@ use derive_more::*; @@
 #[repr(transparent)]
 pub struct BitChunk(usize);
 impl BitChunk {
     const fn bits() -> usize {
         Self::bytes() * 8
+    }
     const fn bytes() -> usize {
         std::mem::size_of::<Self>()
+    }
     const fn any(self) -> bool {
         self.0 != FALSE.0
+    }

src/runtime/experimental/vec_storage.rs

➞

Show inline comments

@@ @@ -47,6 +47,7 @@ impl Bitvec { @@
 // 1. does not check for the ABA problem
 // 2. imposes the object keys on the user
 // 3. allows the reservation of a space (getting the key) to precede the value being provided.
 // 4. checks for user error
 //
 // Data contains values in one of three states:
 // 1. occupied: ininitialized. will be dropped.
@@ @@ -121,6 +122,20 @@ impl<T> VecStorage<T> { @@
+        }
+    }
     //////////////
     pub fn with_reserved_range(range_end: usize) -> Self {
         let mut data = Vec::with_capacity(range_end);
         unsafe {
             // data is uninitialized, as intended
             data.set_len(range_end);
+        }
         let bitset_len = (range_end + (usize_bits() - 1)) / usize_bits();
         let chunk_iter = std::iter::repeat(0usize).take(bitset_len);
         Self {
             data,
             vacant: Bitvec(chunk_iter.clone().collect()),
             occupied: Bitvec(chunk_iter.collect()),
+        }
+    }
     pub fn clear(&mut self) {
         for i in 0..self.data.len() {
             // SAFE: bitvec bounds ensured by invariant E
@@ @@ -268,7 +283,7 @@ fn vec_storage() { @@
             println!("DROPPING FOO!");
+        }
+    }
-    let mut v = VecStorage::default();
+    let mut v = VecStorage::with_reserved_range(4);
     let i0 = v.new_occupied(Foo);
     println!("{:?}", &v);
@@ @@ -277,8 +292,13 @@ fn vec_storage() { @@
     println!("reserved {:?}", v.iter_reserved().collect::<Vec<_>>());
     let q = v.vacate(i0);
     println!("q {:?}", q);
     println!("q {:?}", v.vacate(i0));
     println!("{:?}", &v);
     println!("q {:?}", v.vacate(2));
     println!("{:?}", &v);
     println!("q {:?}", v.vacate(1));
     println!("{:?}", &v);
     v.occupy_reserved(i1, Foo);
@@ @@ -286,4 +306,9 @@ fn vec_storage() { @@
     *v.get_occupied_mut(i1).unwrap() = Foo;
     println!("{:?}", &v);
     println!("q {:?}", v.vacate(i1));
     println!("{:?}", &v);
     println!("q {:?}", v.vacate(3));
     println!("{:?}", &v);
+}

0 comments (0 inline, 0 general)