Changeset - bc7021d551ad
[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:
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)