diff --git a/src/runtime/experimental/vec_storage.rs b/src/runtime/experimental/vec_storage.rs index da46bf1ab2df8acf00fd22265d666fa4e7daacfe..d229d46a9c886f675cdc52e7aa33aa6edf7fdbfb 100644 --- a/src/runtime/experimental/vec_storage.rs +++ b/src/runtime/experimental/vec_storage.rs @@ -25,6 +25,7 @@ impl Bitvec { was } // assumes read will not go out of bounds + #[inline] unsafe fn contains(&self, i: usize) -> bool { let [o_of, o_in] = Self::offsets_of(i); (*self.0.get_unchecked(o_of) & (1 << o_in)) != 0 @@ -47,23 +48,29 @@ impl Bitvec { // 2. imposes the object keys on the user // 3. allows the reservation of a space (getting the key) to precede the value being provided. // -// data contains values in one of three states: +// 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. -// invariant A: elements at indices (0..data.len()) / vacant / reserved are occupied -// invariant B: reserved & vacant = {} -// invariant C: (vacant U reserved) subset of (0..data.len) +// +// 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 +// invariant B: occupied and vacant have an empty intersection +// invariant C: (vacant U occupied) subset of (0..data.len) // invariant D: last element of data is not in VACANT state -// invariant E: number of allocated bits in vacant and reserved >= data.len() +// invariant E: number of allocated bits in vacant and occupied >= data.len() pub struct VecStorage { data: Vec>, + occupied: Bitvec, vacant: Bitvec, - reserved: Bitvec, } impl Default for VecStorage { fn default() -> Self { - Self { data: Default::default(), vacant: Default::default(), reserved: Default::default() } + Self { data: Default::default(), vacant: Default::default(), occupied: Default::default() } } } impl Debug for VecStorage { @@ -82,18 +89,17 @@ impl Debug for VecStorage { } } } - let iter = (0..self.data.len()).map(|i| { - if unsafe { self.vacant.contains(i) } { + + let iter = (0..self.data.len()).map(|i| unsafe { + // 1. data bounds are checked by construction of i. + // 2. occupied index => valid data is read. + // 3. bitset bounds are ensured by invariant E. + if self.occupied.contains(i) { + FmtT::Occupied(&*self.data.get_unchecked(i).as_ptr()) + } else if self.vacant.contains(i) { FmtT::Vacant - } else if unsafe { self.reserved.contains(i) } { - FmtT::Reserved } else { - // 2. Invariant A => reading valid ata - unsafe { - // 1. index is within bounds - // 2. i is occupied => initialized data is being dropped - FmtT::Occupied(&*self.data.get_unchecked(i).as_ptr()) - } + FmtT::Reserved } }); f.debug_list().entries(iter).finish() @@ -107,32 +113,18 @@ impl Drop for VecStorage { impl VecStorage { // ASSUMES that i in 0..self.data.len() unsafe fn get_occupied_unchecked(&self, i: usize) -> Option<&T> { - if self.vacant.contains(i) || self.reserved.contains(i) { + if self.occupied.contains(i) { None } else { // 2. Invariant A => reading valid ata Some(&*self.data.get_unchecked(i).as_ptr()) } } - // breaks invariant A: returned index is in NO state - fn pop_vacant(&mut self) -> usize { - if let Some(i) = self.vacant.pop_first() { - i - } else { - let bitsets_need_another_chunk = self.data.len() % usize_bits() == 0; - if bitsets_need_another_chunk { - self.vacant.0.push(0usize); - self.reserved.0.push(0usize); - } - self.data.push(MaybeUninit::uninit()); - self.data.len() - 1 - } - } ////////////// pub fn clear(&mut self) { for i in 0..self.data.len() { // SAFE: bitvec bounds ensured by invariant E - if unsafe { !self.vacant.contains(i) && !self.reserved.contains(i) } { + if unsafe { self.occupied.contains(i) } { // invariant A: this element is OCCUPIED unsafe { // 1. by construction, i is in bounds @@ -142,7 +134,7 @@ impl VecStorage { } } self.vacant.0.clear(); - self.reserved.0.clear(); + self.occupied.0.clear(); } pub fn iter(&self) -> impl Iterator { (0..self.data.len()).filter_map(move |i| unsafe { self.get_occupied_unchecked(i) }) @@ -150,11 +142,11 @@ impl VecStorage { pub fn iter_mut(&mut self) -> impl Iterator { (0..self.data.len()).filter_map(move |i| unsafe { // SAFE: bitvec bounds ensured by invariant E - if self.vacant.contains(i) || self.reserved.contains(i) { - None - } else { - // 2. Invariant A => reading valid ata + if self.occupied.contains(i) { + // Invariant A => reading valid data Some(&mut *self.data.get_unchecked_mut(i).as_mut_ptr()) + } else { + None } }) } @@ -170,39 +162,49 @@ impl VecStorage { } pub fn get_occupied_mut(&mut self, i: usize) -> Option<&mut T> { // SAFE: bitvec bounds ensured by invariant E - if i >= self.data.len() || unsafe { self.vacant.contains(i) || self.reserved.contains(i) } { - None - } else { + if i < self.data.len() && unsafe { self.occupied.contains(i) } { unsafe { // 1. index is within bounds // 2. Invariant A => reading valid ata Some(&mut *self.data.get_unchecked_mut(i).as_mut_ptr()) } + } else { + None } } pub fn new_reserved(&mut self) -> usize { - let i = self.pop_vacant(); // breaks invariant A: i is in NO state - // SAFE: bitvec bounds ensured by invariant E - unsafe { self.reserved.insert(i) }; // restores invariant A - i + if let Some(i) = self.vacant.pop_first() { + i + } else { + let bitsets_need_another_chunk = self.data.len() % usize_bits() == 0; + if bitsets_need_another_chunk { + self.vacant.0.push(0usize); + self.occupied.0.push(0usize); + } + self.data.push(MaybeUninit::uninit()); + self.data.len() - 1 + } } pub fn occupy_reserved(&mut self, i: usize, t: T) { // SAFE: bitvec bounds ensured by invariant E - assert!(unsafe { self.reserved.remove(i) }); // breaks invariant A + assert!(i < self.data.len()); + // element is within bounds + assert!(unsafe { !self.occupied.contains(i) && !self.vacant.contains(i) }); + // element is surely reserved unsafe { // 1. invariant C => write is within bounds // 2. i WAS reserved => no initialized data is being overwritten - self.data.get_unchecked_mut(i).as_mut_ptr().write(t) - // restores invariant A + self.data.get_unchecked_mut(i).as_mut_ptr().write(t); + self.occupied.insert(i); }; } pub fn new_occupied(&mut self, t: T) -> usize { - let i = self.pop_vacant(); // breaks invariant A: i is in NO state + let i = self.new_reserved(); unsafe { // 1. invariant C => write is within bounds // 2. i WAS reserved => no initialized data is being overwritten - self.data.get_unchecked_mut(i).as_mut_ptr().write(t) - // restores invariant A + self.data.get_unchecked_mut(i).as_mut_ptr().write(t); + self.occupied.insert(i); }; i } @@ -214,16 +216,15 @@ impl VecStorage { } // i is certainly within bounds of self.data // SAFE: bitvec bounds ensured by invariant E - let value = if unsafe { self.reserved.remove(i) } { - // no data to drop - None - } else { - // invariant A => this element is OCCUPIED! + let value = if unsafe { self.occupied.remove(i) } { unsafe { // 1. index is within bounds - // 2. i is occupied => initialized data is being dropped + // 2. i is occupied => initialized data is being read Some(self.data.get_unchecked_mut(i).as_ptr().read()) } + } else { + // reservations have no data to drop + None }; // Mark as vacant... if i + 1 == self.data.len() { @@ -252,7 +253,8 @@ impl VecStorage { value } pub fn iter_reserved(&self) -> impl Iterator + '_ { - self.reserved.iter() + BitChunkIter::new(self.occupied.0.iter().zip(self.vacant.0.iter()).map(|(&a, &b)| !(a | b))) + .take_while(move |&x| x < self.data.len()) } } @@ -272,6 +274,8 @@ fn vec_storage() { let i1 = v.new_reserved(); println!("{:?}", &v); + println!("reserved {:?}", v.iter_reserved().collect::>()); + let q = v.vacate(i0); println!("q {:?}", q); println!("{:?}", &v);