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
 pub const fn usize_bytes() -> usize {
     std::mem::size_of::<usize>()
+}
 pub const fn usize_bits() -> usize {
     usize_bytes() * 8
 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 struct Pair {
     entity: u32,
     property: u32,
+}
 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);
         let column_chunks = Self::column_chunks(self.bounds.entity as usize);
         for property in 0..row_chunks {
             for entity_chunk in 0..column_chunks {
                 write!(f, "|")?;
                 let mut chunk = unsafe { *self.buffer.add(row_chunks * entity_chunk + property) };
                 let end = if entity_chunk + 1 == column_chunks {
@@ @@ -179,54 +178,48 @@ impl BitMatrix { @@
         let zero_prefix_len = entity_bound as usize % usize_bits();
         if zero_prefix_len == 0 {
             None
         } else {
             Some(!0 >> (usize_bits() - zero_prefix_len))
+        }
+    }
     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!()
+    }
     fn new(bounds: Pair) -> Self {
         let total_chunks = Self::row_chunks(bounds.property as usize)
             * Self::column_chunks(bounds.entity as usize);
         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 };
+    }
     fn unset(&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) };
+    }
     fn test(&self, at: Pair) -> bool {
@@ @@ -288,30 +281,24 @@ impl BitMatrix { @@
+        }
         BitChunkIter::new(buf.drain(buf_start..)).map(|x| x as u32)
+    }
+}
 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
+    }
+}
 const TRUE: BitChunk = BitChunk(!0);
 const FALSE: BitChunk = BitChunk(0);
 #[test]
 fn matrix_test() {

src/runtime/experimental/vec_storage.rs

➞

Show inline comments

@@ @@ -38,24 +38,25 @@ impl Bitvec { @@
     fn iter(&self) -> impl Iterator<Item = usize> + '_ {
         BitChunkIter::new(self.0.iter().copied()).map(|x| x as usize)
+    }
     fn first(&self) -> Option<usize> {
         self.iter().next()
+    }
+}
 // 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.
 //
 // element access is O(1)
 // removal is O(1) amortized.
 // insertion is O(N) with a small constant factor,
 //    doing at worst one linear probe through N/(word_size) contiguous words
 //
 // invariant A: data elements are inititalized <=> occupied bit is set
@@ @@ -112,24 +113,38 @@ impl<T> Drop for VecStorage<T> { @@
+}
 impl<T> VecStorage<T> {
     // ASSUMES that i in 0..self.data.len()
     unsafe fn get_occupied_unchecked(&self, i: usize) -> Option<&T> {
         if self.occupied.contains(i) {
             None
         } 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 {
                     // 1. by construction, i is in bounds
                     // 2. i is occupied => initialized data is being dropped
                     drop(self.data.get_unchecked_mut(i).as_ptr().read());
+                }
+            }
+        }
@@ @@ -259,31 +274,41 @@ impl<T> VecStorage<T> { @@
+    }
+}
 #[test]
 fn vec_storage() {
     #[derive(Debug)]
     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)