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.
 /// e.g. input [0b111000, 0b11] gives output [3, 4, 5, 32, 33].
 /// observe that the bits per chunk are ordered from least to most significant bits, yielding smaller to larger usizes.
 /// assumes chunk_iter will yield no more than std::u32::MAX / 32 chunks
@@ @@ -104,23 +105,21 @@ struct Pair { @@
 impl From<[u32; 2]> for Pair {
     fn from([entity, property]: [u32; 2]) -> Self {
         Pair { entity, property }
+    }
+}
 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);
+        }
+    }
+}
 impl Debug for BitMatrix {
     fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
         let row_chunks = Self::row_chunks(self.bounds.property as usize);
@@ @@ -185,24 +184,18 @@ impl BitMatrix { @@
+    }
     fn assert_within_bounds(&self, at: Pair) {
         assert!(at.entity < self.bounds.entity);
         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())
+        }
+    }
     /////////
     fn reshape(&mut self, bounds: Pair) {
         todo!()
@@ @@ -214,13 +207,13 @@ impl BitMatrix { @@
         let layout = Self::layout_for(total_chunks);
         let buffer;
         unsafe {
             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);
         let [o_of, o_in] = self.offsets_unchecked(at);
         unsafe { *self.buffer.add(o_of) |= 1 << o_in };
+    }
@@ @@ -294,18 +287,12 @@ use derive_more::*; @@
 #[derive(
     Debug, Copy, Clone, BitAnd, Not, BitOr, BitXor, BitAndAssign, BitOrAssign, BitXorAssign,
 )]
 #[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
+    }
     const fn all(self) -> bool {
         self.0 == TRUE.0
+    }

src/runtime/experimental/vec_storage.rs

➞

Show inline comments

@@ @@ -44,12 +44,13 @@ impl Bitvec { @@
+}
 // A T-type arena which:
 // 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.
 // 2. vacant: uninitialized. may be reused implicitly. won't be dropped.
 // 2. reserved: uninitialized. may be occupied implicitly. won't be dropped.
 //
@@ @@ -118,12 +119,26 @@ impl<T> VecStorage<T> { @@
         } else {
             // 2. Invariant A => reading valid ata
             Some(&*self.data.get_unchecked(i).as_ptr())
+        }
+    }
     //////////////
     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
             if unsafe { self.occupied.contains(i) } {
                 // invariant A: this element is OCCUPIED
                 unsafe {
@@ @@ -265,25 +280,35 @@ fn vec_storage() { @@
     struct Foo;
     impl Drop for Foo {
         fn drop(&mut self) {
             println!("DROPPING FOO!");
+        }
+    }
-    let mut v = VecStorage::default();
+    let mut v = VecStorage::with_reserved_range(4);
     let i0 = v.new_occupied(Foo);
     println!("{:?}", &v);
     let i1 = v.new_reserved();
     println!("{:?}", &v);
     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);
     println!("{:?}", &v);
     *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)