From ed175484592444946dd4258939180dffe6164ffb 2020-02-20 15:46:40
From: Christopher Esterhuyse <christopher.esterhuyse@gmail.com>
Date: 2020-02-20 15:46:40
Subject: [PATCH] removing btreesets

---

diff --git a/src/runtime/experimental/api.rs b/src/runtime/experimental/api.rs
index 28b5c5b0125025312f7a5afcdb6c141e02303ed5..bb8b1ff79eb5ad2c8fbf721b2362973404e3b6f3 100644
--- a/src/runtime/experimental/api.rs
+++ b/src/runtime/experimental/api.rs
@@ -2,8 +2,6 @@ use crate::common::*;
 use crate::runtime::endpoint::Endpoint;
 use crate::runtime::endpoint::EndpointExt;
 use crate::runtime::endpoint::EndpointInfo;
-use core::mem::MaybeUninit;
-use std::collections::BTreeSet;
 
 use std::net::SocketAddr;
 use std::sync::Arc;
@@ -274,222 +272,3 @@ unsafe fn as_mut_slice<'a, T>(len: usize, ptr: *mut T) -> &'a mut [T] {
 unsafe fn as_const_slice<'a, T>(len: usize, ptr: *const T) -> &'a [T] {
     std::slice::from_raw_parts(ptr, len)
 }
-
-// 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.
-struct VecStorage<T> {
-    // 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)
-    data: Vec<MaybeUninit<T>>,
-    vacant: BTreeSet<usize>,
-    reserved: BTreeSet<usize>,
-}
-impl<T> Default for VecStorage<T> {
-    fn default() -> Self {
-        Self { data: Default::default(), vacant: Default::default(), reserved: Default::default() }
-    }
-}
-impl<T> Debug for VecStorage<T>
-where
-    T: Debug,
-{
-    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
-        enum FmtT<'a, T> {
-            Vacant,
-            Reserved,
-            Occupied(&'a T),
-        };
-        impl<T> Debug for FmtT<'_, T>
-        where
-            T: Debug,
-        {
-            fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
-                match self {
-                    FmtT::Vacant => write!(f, "Vacant"),
-                    FmtT::Reserved => write!(f, "Reserved"),
-                    FmtT::Occupied(t) => write!(f, "Occupied({:?})", t),
-                }
-            }
-        }
-        let iter = (0..self.data.len()).map(|i| {
-            if self.vacant.contains(&i) {
-                FmtT::Vacant
-            } else if 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())
-                }
-            }
-        });
-        f.debug_list().entries(iter).finish()
-    }
-}
-impl<T> Drop for VecStorage<T> {
-    fn drop(&mut self) {
-        self.clear();
-    }
-}
-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) {
-            None
-        } else {
-            // 2. Invariant A => reading valid ata
-            Some(&*self.data.get_unchecked(i).as_ptr())
-        }
-    }
-    // ASSUMES that i in 0..self.data.len()
-    unsafe fn get_mut_occupied_unchecked(&mut self, i: usize) -> Option<&mut T> {
-        if self.vacant.contains(&i) || self.reserved.contains(&i) {
-            None
-        } else {
-            // 2. Invariant A => reading valid ata
-            Some(&mut *self.data.get_unchecked_mut(i).as_mut_ptr())
-        }
-    }
-    // breaks invariant A: returned index is in NO state
-    fn pop_vacant(&mut self) -> usize {
-        if let Some(i) = pop_set_arb(&mut self.vacant) {
-            i
-        } else {
-            self.data.push(MaybeUninit::uninit());
-            self.data.len() - 1
-        }
-    }
-    //////////////
-    pub fn clear(&mut self) {
-        for i in 0..self.data.len() {
-            if !self.vacant.contains(&i) && !self.reserved.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());
-                }
-            }
-        }
-        self.vacant.clear();
-        self.reserved.clear();
-    }
-    pub fn iter(&self) -> impl Iterator<Item = &T> {
-        (0..self.data.len()).filter_map(move |i| unsafe { self.get_occupied_unchecked(i) })
-    }
-    pub fn get_occupied(&self, i: usize) -> Option<&T> {
-        if i >= self.data.len() {
-            None
-        } else {
-            unsafe {
-                // index is within bounds
-                self.get_occupied_unchecked(i)
-            }
-        }
-    }
-    pub fn get_mut_occupied(&mut self, i: usize) -> Option<&mut T> {
-        if i >= self.data.len() {
-            None
-        } else {
-            unsafe {
-                // index is within bounds
-                self.get_mut_occupied_unchecked(i)
-            }
-        }
-    }
-    pub fn new_reserved(&mut self) -> usize {
-        let i = self.pop_vacant(); // breaks invariant A: i is in NO state
-        self.reserved.insert(i); // restores invariant A
-        i
-    }
-    pub fn occupy_reserved(&mut self, i: usize, t: T) {
-        assert!(self.reserved.remove(&i)); // breaks invariant A
-        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
-        };
-    }
-    pub fn new_occupied(&mut self, t: T) -> usize {
-        let i = self.pop_vacant(); // breaks invariant A: i is in NO state
-        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
-        };
-        i
-    }
-    pub fn vacate(&mut self, i: usize) -> Option<T> {
-        if i >= self.data.len() || self.vacant.contains(&i) {
-            // already vacant. nothing to do here
-            return None;
-        }
-        // i is certainly within bounds of self.data
-        let value = if self.reserved.remove(&i) {
-            // no data to drop
-            None
-        } else {
-            // invariant A => this element is OCCUPIED!
-            unsafe {
-                // 1. index is within bounds
-                // 2. i is occupied => initialized data is being dropped
-                Some(self.data.get_unchecked_mut(i).as_ptr().read())
-            }
-        };
-        // Mark as vacant...
-        if i + 1 == self.data.len() {
-            // ... by truncating self.data.
-            self.data.pop(); // truncate last data element
-            let mut walking = i;
-            while walking > 0 && self.vacant.remove(&(walking - 1)) {
-                self.data.pop(); // truncate another element
-                walking -= 1;
-            }
-        } else {
-            // ... by populating self.vacant.
-            self.vacant.insert(i);
-        }
-        value
-    }
-    pub fn iter_reserved(&self) -> impl Iterator<Item = usize> + '_ {
-        self.reserved.iter().copied()
-    }
-}
-
-fn pop_set_arb(s: &mut BTreeSet<usize>) -> Option<usize> {
-    if let Some(&x) = s.iter().next() {
-        s.remove(&x);
-        Some(x)
-    } else {
-        None
-    }
-}
-
-#[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 i0 = v.new_occupied(Foo);
-    println!("{:?}", &v);
-    let i1 = v.new_reserved();
-    println!("{:?}", &v);
-    let q = v.vacate(i0);
-    println!("q {:?}", q);
-    println!("{:?}", &v);
-    v.occupy_reserved(i1, Foo);
-    println!("{:?}", &v);
-}
diff --git a/src/runtime/experimental/mod.rs b/src/runtime/experimental/mod.rs
index c1187ad2c3d353ff7601c5d95b35bb84c6721d5c..b0a0a8a00dce44f7f0a4a67c11859b9bdbe49c15 100644
--- a/src/runtime/experimental/mod.rs
+++ b/src/runtime/experimental/mod.rs
@@ -1,2 +1,3 @@
 mod api;
 mod bits;
+mod vec_storage;
diff --git a/src/runtime/experimental/vec_storage.rs b/src/runtime/experimental/vec_storage.rs
new file mode 100644
index 0000000000000000000000000000000000000000..521b5b74c2efa44d090514fb452691e48273882f
--- /dev/null
+++ b/src/runtime/experimental/vec_storage.rs
@@ -0,0 +1,231 @@
+use crate::common::*;
+use core::mem::MaybeUninit;
+use std::collections::BTreeSet;
+
+// 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.
+//
+// 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)
+// invariant D: last element of data is not in VACANT state
+pub struct VecStorage<T> {
+    data: Vec<MaybeUninit<T>>,
+    vacant: BTreeSet<usize>,
+    reserved: BTreeSet<usize>,
+}
+impl<T> Default for VecStorage<T> {
+    fn default() -> Self {
+        Self { data: Default::default(), vacant: Default::default(), reserved: Default::default() }
+    }
+}
+impl<T: Debug> Debug for VecStorage<T> {
+    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
+        enum FmtT<'a, T> {
+            Vacant,
+            Reserved,
+            Occupied(&'a T),
+        };
+        impl<T: Debug> Debug for FmtT<'_, T> {
+            fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
+                match self {
+                    FmtT::Vacant => write!(f, "Vacant"),
+                    FmtT::Reserved => write!(f, "Reserved"),
+                    FmtT::Occupied(t) => write!(f, "Occupied({:?})", t),
+                }
+            }
+        }
+        let iter = (0..self.data.len()).map(|i| {
+            if self.vacant.contains(&i) {
+                FmtT::Vacant
+            } else if 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())
+                }
+            }
+        });
+        f.debug_list().entries(iter).finish()
+    }
+}
+impl<T> Drop for VecStorage<T> {
+    fn drop(&mut self) {
+        self.clear();
+    }
+}
+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) {
+            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) = pop_set_arb(&mut self.vacant) {
+            i
+        } else {
+            self.data.push(MaybeUninit::uninit());
+            self.data.len() - 1
+        }
+    }
+    //////////////
+    pub fn clear(&mut self) {
+        for i in 0..self.data.len() {
+            if !self.vacant.contains(&i) && !self.reserved.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());
+                }
+            }
+        }
+        self.vacant.clear();
+        self.reserved.clear();
+    }
+    pub fn iter(&self) -> impl Iterator<Item = &T> {
+        (0..self.data.len()).filter_map(move |i| unsafe { self.get_occupied_unchecked(i) })
+    }
+    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
+        (0..self.data.len()).filter_map(move |i| unsafe {
+            if self.vacant.contains(&i) || self.reserved.contains(&i) {
+                None
+            } else {
+                // 2. Invariant A => reading valid ata
+                Some(&mut *self.data.get_unchecked_mut(i).as_mut_ptr())
+            }
+        })
+    }
+    pub fn get_occupied(&self, i: usize) -> Option<&T> {
+        if i >= self.data.len() {
+            None
+        } else {
+            unsafe {
+                // index is within bounds
+                self.get_occupied_unchecked(i)
+            }
+        }
+    }
+    pub fn get_mut_occupied(&mut self, i: usize) -> Option<&mut T> {
+        if i >= self.data.len() || self.vacant.contains(&i) || self.reserved.contains(&i) {
+            None
+        } else {
+            unsafe {
+                // 1. index is within bounds
+                // 2. Invariant A => reading valid ata
+                Some(&mut *self.data.get_unchecked_mut(i).as_mut_ptr())
+            }
+        }
+    }
+    pub fn new_reserved(&mut self) -> usize {
+        let i = self.pop_vacant(); // breaks invariant A: i is in NO state
+        self.reserved.insert(i); // restores invariant A
+        i
+    }
+    pub fn occupy_reserved(&mut self, i: usize, t: T) {
+        assert!(self.reserved.remove(&i)); // breaks invariant A
+        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
+        };
+    }
+    pub fn new_occupied(&mut self, t: T) -> usize {
+        let i = self.pop_vacant(); // breaks invariant A: i is in NO state
+        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
+        };
+        i
+    }
+    pub fn vacate(&mut self, i: usize) -> Option<T> {
+        if i >= self.data.len() || self.vacant.contains(&i) {
+            // already vacant. nothing to do here
+            return None;
+        }
+        // i is certainly within bounds of self.data
+        let value = if self.reserved.remove(&i) {
+            // no data to drop
+            None
+        } else {
+            // invariant A => this element is OCCUPIED!
+            unsafe {
+                // 1. index is within bounds
+                // 2. i is occupied => initialized data is being dropped
+                Some(self.data.get_unchecked_mut(i).as_ptr().read())
+            }
+        };
+        // Mark as vacant...
+        if i + 1 == self.data.len() {
+            // ... by truncating self.data.
+            // must truncate to avoid violating invariant D.
+            // pops at least once:
+            while let Some(_) = self.data.pop() {
+                let pop_next = self
+                    .data
+                    .len()
+                    .checked_sub(1)
+                    .map(|index| self.vacant.remove(&index))
+                    .unwrap_or(false);
+                if !pop_next {
+                    break;
+                }
+            }
+        } else {
+            // ... by populating self.vacant.
+            self.vacant.insert(i);
+        }
+        value
+    }
+    pub fn iter_reserved(&self) -> impl Iterator<Item = usize> + '_ {
+        self.reserved.iter().copied()
+    }
+}
+
+fn pop_set_arb(s: &mut BTreeSet<usize>) -> Option<usize> {
+    if let Some(&x) = s.iter().next() {
+        s.remove(&x);
+        Some(x)
+    } else {
+        None
+    }
+}
+
+#[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 i0 = v.new_occupied(Foo);
+    println!("{:?}", &v);
+    let i1 = v.new_reserved();
+    println!("{:?}", &v);
+    let q = v.vacate(i0);
+    println!("q {:?}", q);
+    println!("{:?}", &v);
+    v.occupy_reserved(i1, Foo);
+    println!("{:?}", &v);
+}