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

Changeset - 673b826b1a60

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Christopher Esterhuyse - 5 years ago 2020-02-20 16:50:30
christopher.esterhuyse@gmail.com

bitsets are so great

1 file changed with 61 insertions and 57 deletions:

src/runtime/experimental/vec_storage.rs

0 comments (0 inline, 0 general)

src/runtime/experimental/vec_storage.rs

➞

Show inline comments

@@ @@ -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<T> {
     data: Vec<MaybeUninit<T>>,
     occupied: Bitvec,
     vacant: Bitvec,
     reserved: Bitvec,
+}
 impl<T> Default for VecStorage<T> {
     fn default() -> Self {
-        Self { data: Default::default(), vacant: Default::default(), reserved: Default::default() }
+        Self { data: Default::default(), vacant: Default::default(), occupied: Default::default() }
+    }
+}
 impl<T: Debug> Debug for VecStorage<T> {
@@ @@ -82,18 +89,17 @@ impl<T: Debug> Debug for VecStorage<T> { @@
+                }
+            }
+        }
         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<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.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<T> VecStorage<T> { @@
+            }
+        }
         self.vacant.0.clear();
-        self.reserved.0.clear();
+        self.occupied.0.clear();
+    }
     pub fn iter(&self) -> impl Iterator<Item = &T> {
         (0..self.data.len()).filter_map(move |i| unsafe { self.get_occupied_unchecked(i) })
@@ @@ -150,11 +142,11 @@ impl<T> VecStorage<T> { @@
     pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
         (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<T> VecStorage<T> { @@
+    }
     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
         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<T> VecStorage<T> { @@
+        }
         // 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<T> VecStorage<T> { @@
         value
+    }
     pub fn iter_reserved(&self) -> impl Iterator<Item = usize> + '_ {
         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::<Vec<_>>());
     let q = v.vacate(i0);
     println!("q {:?}", q);
     println!("{:?}", &v);

0 comments (0 inline, 0 general)