summaryrefslogtreecommitdiffstats
path: root/vendor/elsa/src
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/elsa/src')
-rw-r--r--vendor/elsa/src/index_map.rs215
-rw-r--r--vendor/elsa/src/index_set.rs180
-rw-r--r--vendor/elsa/src/lib.rs29
-rw-r--r--vendor/elsa/src/map.rs451
-rw-r--r--vendor/elsa/src/sync.rs624
-rw-r--r--vendor/elsa/src/vec.rs347
6 files changed, 1846 insertions, 0 deletions
diff --git a/vendor/elsa/src/index_map.rs b/vendor/elsa/src/index_map.rs
new file mode 100644
index 000000000..3c97dfbaa
--- /dev/null
+++ b/vendor/elsa/src/index_map.rs
@@ -0,0 +1,215 @@
+use std::borrow::Borrow;
+use std::cell::{Cell, UnsafeCell};
+use std::collections::hash_map::RandomState;
+use std::hash::{BuildHasher, Hash};
+use std::iter::FromIterator;
+use std::ops::Index;
+
+use indexmap::IndexMap;
+use stable_deref_trait::StableDeref;
+
+/// Append-only version of `indexmap::IndexMap` where
+/// insertion does not require mutable access
+pub struct FrozenIndexMap<K, V, S = RandomState> {
+ map: UnsafeCell<IndexMap<K, V, S>>,
+ /// Eq/Hash implementations can have side-effects, and using Rc it is possible
+ /// for FrozenIndexMap::insert to be called on a key that itself contains the same
+ /// `FrozenIndexMap`, whose `eq` implementation also calls FrozenIndexMap::insert
+ ///
+ /// We use this `in_use` flag to guard against any reentrancy.
+ in_use: Cell<bool>,
+}
+
+// safety: UnsafeCell implies !Sync
+
+impl<K: Eq + Hash, V> FrozenIndexMap<K, V> {
+ pub fn new() -> Self {
+ Self {
+ map: UnsafeCell::new(Default::default()),
+ in_use: Cell::new(false),
+ }
+ }
+}
+
+impl<K: Eq + Hash, V: StableDeref, S: BuildHasher> FrozenIndexMap<K, V, S> {
+ // these should never return &K or &V
+ // these should never delete any entries
+ pub fn insert(&self, k: K, v: V) -> &V::Target {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ &*(*map).entry(k).or_insert(v)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ // these should never return &K or &V
+ // these should never delete any entries
+ pub fn insert_full(&self, k: K, v: V) -> (usize, &V::Target) {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ let entry = (*map).entry(k);
+ let index = entry.index();
+ (index, &**entry.or_insert(v))
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenIndexMap;
+ ///
+ /// let map = FrozenIndexMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.get(&1), Some(&"a"));
+ /// assert_eq!(map.get(&2), None);
+ /// ```
+ pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get(k).map(|x| &**x)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ pub fn get_index(&self, index: usize) -> Option<(&K::Target, &V::Target)>
+ where
+ K: StableDeref,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get_index(index).map(|(k, v)| (&**k, &**v))
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ /// Applies a function to the owner of the value corresponding to the key (if any).
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenIndexMap;
+ ///
+ /// let map = FrozenIndexMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
+ /// assert_eq!(map.map_get(&2, Clone::clone), None);
+ /// ```
+ pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ F: FnOnce(&V) -> T,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get(k).map(f)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ pub fn into_map(self) -> IndexMap<K, V, S> {
+ self.map.into_inner()
+ }
+
+ /// Get mutable access to the underlying [`IndexMap`].
+ ///
+ /// This is safe, as it requires a `&mut self`, ensuring nothing is using
+ /// the 'frozen' contents.
+ pub fn as_mut(&mut self) -> &mut IndexMap<K, V, S> {
+ unsafe { &mut *self.map.get() }
+ }
+
+ /// Returns true if the map contains no elements.
+ pub fn is_empty(&self) -> bool {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).is_empty()
+ };
+ self.in_use.set(false);
+ ret
+ }
+}
+
+impl<K, V, S> From<IndexMap<K, V, S>> for FrozenIndexMap<K, V, S> {
+ fn from(map: IndexMap<K, V, S>) -> Self {
+ Self {
+ map: UnsafeCell::new(map),
+ in_use: Cell::new(false),
+ }
+ }
+}
+
+impl<Q: ?Sized, K: Eq + Hash, V: StableDeref, S: BuildHasher> Index<&Q> for FrozenIndexMap<K, V, S>
+ where
+ Q: Eq + Hash,
+ K: Eq + Hash + Borrow<Q>,
+ V: StableDeref,
+ S: BuildHasher
+{
+ type Output = V::Target;
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenIndexMap;
+ ///
+ /// let map = FrozenIndexMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map[&1], "a");
+ /// ```
+ fn index(&self, idx: &Q) -> &V::Target {
+ self.get(&idx)
+ .expect("attempted to index FrozenIndexMap with unknown key")
+ }
+}
+
+impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for FrozenIndexMap<K, V, S> {
+ fn from_iter<T>(iter: T) -> Self
+ where
+ T: IntoIterator<Item = (K, V)>,
+ {
+ let map: IndexMap<_, _, _> = iter.into_iter().collect();
+ map.into()
+ }
+}
+
+impl<K: Eq + Hash, V, S: Default> Default for FrozenIndexMap<K, V, S> {
+ fn default() -> Self {
+ Self {
+ map: UnsafeCell::new(Default::default()),
+ in_use: Cell::new(false),
+ }
+ }
+}
diff --git a/vendor/elsa/src/index_set.rs b/vendor/elsa/src/index_set.rs
new file mode 100644
index 000000000..1222cde05
--- /dev/null
+++ b/vendor/elsa/src/index_set.rs
@@ -0,0 +1,180 @@
+use std::borrow::Borrow;
+use std::cell::{Cell, UnsafeCell};
+use std::collections::hash_map::RandomState;
+use std::hash::{BuildHasher, Hash};
+use std::iter::FromIterator;
+use std::ops::Index;
+
+use indexmap::IndexSet;
+use stable_deref_trait::StableDeref;
+
+/// Append-only version of `indexmap::IndexSet` where
+/// insertion does not require mutable access
+pub struct FrozenIndexSet<T, S = RandomState> {
+ set: UnsafeCell<IndexSet<T, S>>,
+ /// Eq/Hash implementations can have side-effects, and using Rc it is possible
+ /// for FrozenIndexSet::insert to be called on a key that itself contains the same
+ /// `FrozenIndexSet`, whose `eq` implementation also calls FrozenIndexSet::insert
+ ///
+ /// We use this `in_use` flag to guard against any reentrancy.
+ in_use: Cell<bool>,
+}
+
+// safety: UnsafeCell implies !Sync
+
+impl<T: Eq + Hash> FrozenIndexSet<T> {
+ pub fn new() -> Self {
+ Self::from(IndexSet::new())
+ }
+}
+
+impl<T: Eq + Hash + StableDeref, S: BuildHasher> FrozenIndexSet<T, S> {
+ // these should never return &T
+ // these should never delete any entries
+ pub fn insert(&self, value: T) -> &T::Target {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let set = self.set.get();
+ let (index, _was_vacant) = (*set).insert_full(value);
+ &*(*set)[index]
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ // these should never return &T
+ // these should never delete any entries
+ pub fn insert_full(&self, value: T) -> (usize, &T::Target) {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let set = self.set.get();
+ let (index, _was_vacant) = (*set).insert_full(value);
+ (index, &*(*set)[index])
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ // TODO implement in case the standard Entry API gets improved
+ // // TODO avoid double lookup
+ // pub fn entry<Q: ?Sized>(&self, value: &Q) -> Entry<T, Q>
+ // where Q: Hash + Equivalent<T> + ToOwned<Owned = T>
+ // {
+ // assert!(!self.in_use.get());
+ // self.in_use.set(true);
+ // unsafe {
+ // let set = self.set.get();
+ // match (*set).get_full(value) {
+ // Some((index, reference)) => {
+ // Entry::Occupied(OccupiedEntry {
+ // index,
+ // reference,
+ // set: &*set,
+ // })
+ // }
+ // None => {
+ // Entry::Vacant(VacantEntry {
+ // value: Cow::Borrowed(value),
+ // set: &*set,
+ // })
+ // }
+ // }
+ // }
+ // }
+
+ pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&T::Target>
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let set = self.set.get();
+ (*set).get(k).map(|x| &**x)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ pub fn get_full<Q: ?Sized>(&self, k: &Q) -> Option<(usize, &T::Target)>
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let set = self.set.get();
+ (*set).get_full(k).map(|(i, x)| (i, &**x))
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ pub fn get_index(&self, index: usize) -> Option<&T::Target> {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let set = self.set.get();
+ (*set).get_index(index).map(|r| &**r)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ pub fn into_set(self) -> IndexSet<T, S> {
+ self.set.into_inner()
+ }
+
+ /// Get mutable access to the underlying [`IndexSet`].
+ ///
+ /// This is safe, as it requires a `&mut self`, ensuring nothing is using
+ /// the 'frozen' contents.
+ pub fn as_mut(&mut self) -> &mut IndexSet<T, S> {
+ unsafe { &mut *self.set.get() }
+ }
+
+ // TODO add more
+}
+
+impl<T, S> From<IndexSet<T, S>> for FrozenIndexSet<T, S> {
+ fn from(set: IndexSet<T, S>) -> Self {
+ Self {
+ set: UnsafeCell::new(set),
+ in_use: Cell::new(false),
+ }
+ }
+}
+
+impl<T: Eq + Hash + StableDeref, S> Index<usize> for FrozenIndexSet<T, S> {
+ type Output = T::Target;
+ fn index(&self, idx: usize) -> &T::Target {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let set = self.set.get();
+ &*(*set)[idx]
+ };
+ self.in_use.set(false);
+ ret
+ }
+}
+
+impl<T: Eq + Hash, S: Default + BuildHasher> FromIterator<T> for FrozenIndexSet<T, S> {
+ fn from_iter<U>(iter: U) -> Self
+ where
+ U: IntoIterator<Item = T>,
+ {
+ let set: IndexSet<_, _> = iter.into_iter().collect();
+ set.into()
+ }
+}
+
+impl<T: Eq + Hash, S: Default> Default for FrozenIndexSet<T, S> {
+ fn default() -> Self {
+ Self::from(IndexSet::default())
+ }
+}
diff --git a/vendor/elsa/src/lib.rs b/vendor/elsa/src/lib.rs
new file mode 100644
index 000000000..848dceb34
--- /dev/null
+++ b/vendor/elsa/src/lib.rs
@@ -0,0 +1,29 @@
+//! _🎵 Immutability never bothered me anyway 🎶_
+//!
+//! This crate provides various "Frozen" collections.
+//!
+//! These are append-only collections where references to entries can be held
+//! on to even across insertions. This is safe because these collections only
+//! support storing data that's present behind some indirection -- i.e. `String`,
+//! `Vec<T>`, `Box<T>`, etc, and they only yield references to the data behind the
+//! allocation (`&str`, `&[T]`, and `&T` respectively)
+//!
+//! The typical use case is having a global cache of strings or other data which the rest of the program borrows from.
+
+pub mod map;
+pub mod vec;
+
+#[cfg(feature = "indexmap")]
+pub mod index_map;
+#[cfg(feature = "indexmap")]
+pub mod index_set;
+
+pub mod sync;
+
+pub use map::{FrozenBTreeMap, FrozenMap};
+pub use vec::FrozenVec;
+
+#[cfg(feature = "indexmap")]
+pub use index_map::FrozenIndexMap;
+#[cfg(feature = "indexmap")]
+pub use index_set::FrozenIndexSet;
diff --git a/vendor/elsa/src/map.rs b/vendor/elsa/src/map.rs
new file mode 100644
index 000000000..2faa19ce2
--- /dev/null
+++ b/vendor/elsa/src/map.rs
@@ -0,0 +1,451 @@
+use std::borrow::Borrow;
+use std::cell::{Cell, UnsafeCell};
+use std::collections::hash_map::RandomState;
+use std::collections::BTreeMap;
+use std::collections::HashMap;
+use std::hash::{BuildHasher, Hash};
+use std::iter::FromIterator;
+use std::ops::Index;
+
+use stable_deref_trait::StableDeref;
+
+/// Append-only version of `std::collections::HashMap` where
+/// insertion does not require mutable access
+pub struct FrozenMap<K, V, S = RandomState> {
+ map: UnsafeCell<HashMap<K, V, S>>,
+ /// Eq/Hash implementations can have side-effects, and using Rc it is possible
+ /// for FrozenMap::insert to be called on a key that itself contains the same
+ /// `FrozenMap`, whose `eq` implementation also calls FrozenMap::insert
+ ///
+ /// We use this `in_use` flag to guard against any reentrancy.
+ in_use: Cell<bool>,
+}
+
+// safety: UnsafeCell implies !Sync
+
+impl<K: Eq + Hash, V> FrozenMap<K, V> {
+ pub fn new() -> Self {
+ Self {
+ map: UnsafeCell::new(Default::default()),
+ in_use: Cell::new(false),
+ }
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// assert_eq!(map.len(), 0);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.len(), 1);
+ /// ```
+ pub fn len(&self) -> usize {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let len = unsafe {
+ let map = self.map.get();
+ (*map).len()
+ };
+ self.in_use.set(false);
+ len
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// assert_eq!(map.is_empty(), true);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.is_empty(), false);
+ /// ```
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl<K: Eq + Hash, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> {
+ // these should never return &K or &V
+ // these should never delete any entries
+ pub fn insert(&self, k: K, v: V) -> &V::Target {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ &*(*map).entry(k).or_insert(v)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.get(&1), Some(&"a"));
+ /// assert_eq!(map.get(&2), None);
+ /// ```
+ pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get(k).map(|x| &**x)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ /// Applies a function to the owner of the value corresponding to the key (if any).
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
+ /// assert_eq!(map.map_get(&2, Clone::clone), None);
+ /// ```
+ pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ F: FnOnce(&V) -> T,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get(k).map(f)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ pub fn into_map(self) -> HashMap<K, V, S> {
+ self.map.into_inner()
+ }
+
+ // TODO add more
+}
+
+impl<K: Eq + Hash + StableDeref, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> {
+ /// Returns a reference to the key and value matching a borrowed
+ /// key.
+ ///
+ /// The key argument may be any borrowed form of the map's key type,
+ /// but [`Hash`] and [`Eq`] on the borrowed form *must* match those
+ /// for the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// map.insert(Box::new("1"), Box::new("a"));
+ /// assert_eq!(map.get_key_value(&"1"), Some((&"1", &"a")));
+ /// assert_eq!(map.get_key_value(&"2"), None);
+ /// ```
+ pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K::Target, &V::Target)>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get_key_value(k).map(|(k, v)| (&**k, &**v))
+ };
+ self.in_use.set(false);
+ ret
+ }
+}
+
+impl<K, V, S> std::convert::AsMut<HashMap<K, V, S>> for FrozenMap<K, V, S> {
+ /// Get mutable access to the underlying [`HashMap`].
+ ///
+ /// This is safe, as it requires a `&mut self`, ensuring nothing is using
+ /// the 'frozen' contents.
+ fn as_mut(&mut self) -> &mut HashMap<K, V, S> {
+ unsafe { &mut *self.map.get() }
+ }
+}
+
+impl<K, V, S> From<HashMap<K, V, S>> for FrozenMap<K, V, S> {
+ fn from(map: HashMap<K, V, S>) -> Self {
+ Self {
+ map: UnsafeCell::new(map),
+ in_use: Cell::new(false),
+ }
+ }
+}
+
+impl<Q: ?Sized, K, V, S> Index<&Q> for FrozenMap<K, V, S>
+where
+ Q: Eq + Hash,
+ K: Eq + Hash + Borrow<Q>,
+ V: StableDeref,
+ S: BuildHasher,
+{
+ type Output = V::Target;
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map[&1], "a");
+ /// ```
+ fn index(&self, idx: &Q) -> &V::Target {
+ self.get(idx)
+ .expect("attempted to index FrozenMap with unknown key")
+ }
+}
+
+impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for FrozenMap<K, V, S> {
+ fn from_iter<T>(iter: T) -> Self
+ where
+ T: IntoIterator<Item = (K, V)>,
+ {
+ let map: HashMap<_, _, _> = iter.into_iter().collect();
+ map.into()
+ }
+}
+
+impl<K: Eq + Hash, V, S: Default> Default for FrozenMap<K, V, S> {
+ fn default() -> Self {
+ Self {
+ map: UnsafeCell::new(Default::default()),
+ in_use: Cell::new(false),
+ }
+ }
+}
+
+/// Append-only version of `std::collections::BTreeMap` where
+/// insertion does not require mutable access
+pub struct FrozenBTreeMap<K, V> {
+ map: UnsafeCell<BTreeMap<K, V>>,
+ /// Eq/Hash implementations can have side-effects, and using Rc it is possible
+ /// for FrozenBTreeMap::insert to be called on a key that itself contains the same
+ /// `FrozenBTreeMap`, whose `eq` implementation also calls FrozenBTreeMap::insert
+ ///
+ /// We use this `in_use` flag to guard against any reentrancy.
+ in_use: Cell<bool>,
+}
+
+// safety: UnsafeCell implies !Sync
+
+impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> {
+ pub fn new() -> Self {
+ Self {
+ map: UnsafeCell::new(Default::default()),
+ in_use: Cell::new(false),
+ }
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// assert_eq!(map.len(), 0);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.len(), 1);
+ /// ```
+ pub fn len(&self) -> usize {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let len = unsafe {
+ let map = self.map.get();
+ (*map).len()
+ };
+ self.in_use.set(false);
+ len
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// assert_eq!(map.is_empty(), true);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.is_empty(), false);
+ /// ```
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> {
+ // these should never return &K or &V
+ // these should never delete any entries
+ pub fn insert(&self, k: K, v: V) -> &V::Target {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ &*(*map).entry(k).or_insert(v)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.get(&1), Some(&"a"));
+ /// assert_eq!(map.get(&2), None);
+ /// ```
+ pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get(k).map(|x| &**x)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ /// Applies a function to the owner of the value corresponding to the key (if any).
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
+ /// assert_eq!(map.map_get(&2, Clone::clone), None);
+ /// ```
+ pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ F: FnOnce(&V) -> T,
+ {
+ assert!(!self.in_use.get());
+ self.in_use.set(true);
+ let ret = unsafe {
+ let map = self.map.get();
+ (*map).get(k).map(f)
+ };
+ self.in_use.set(false);
+ ret
+ }
+
+ pub fn into_map(self) -> BTreeMap<K, V> {
+ self.map.into_inner()
+ }
+
+ // TODO add more
+}
+
+impl<K, V> std::convert::AsMut<BTreeMap<K, V>> for FrozenBTreeMap<K, V> {
+ /// Get mutable access to the underlying [`HashMap`].
+ ///
+ /// This is safe, as it requires a `&mut self`, ensuring nothing is using
+ /// the 'frozen' contents.
+ fn as_mut(&mut self) -> &mut BTreeMap<K, V> {
+ unsafe { &mut *self.map.get() }
+ }
+}
+
+impl<K: Clone + Ord, V: StableDeref> From<BTreeMap<K, V>> for FrozenBTreeMap<K, V> {
+ fn from(map: BTreeMap<K, V>) -> Self {
+ Self {
+ map: UnsafeCell::new(map),
+ in_use: Cell::new(false),
+ }
+ }
+}
+
+impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V>
+where
+ Q: Ord,
+ K: Clone + Ord + Borrow<Q>,
+ V: StableDeref,
+{
+ type Output = V::Target;
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map[&1], "a");
+ /// ```
+ fn index(&self, idx: &Q) -> &V::Target {
+ self.get(idx)
+ .expect("attempted to index FrozenBTreeMap with unknown key")
+ }
+}
+
+impl<K: Clone + Ord, V: StableDeref> FromIterator<(K, V)> for FrozenBTreeMap<K, V> {
+ fn from_iter<T>(iter: T) -> Self
+ where
+ T: IntoIterator<Item = (K, V)>,
+ {
+ let map: BTreeMap<_, _> = iter.into_iter().collect();
+ map.into()
+ }
+}
+
+impl<K: Clone + Ord, V: StableDeref> Default for FrozenBTreeMap<K, V> {
+ fn default() -> Self {
+ Self {
+ map: UnsafeCell::new(Default::default()),
+ in_use: Cell::new(false),
+ }
+ }
+}
diff --git a/vendor/elsa/src/sync.rs b/vendor/elsa/src/sync.rs
new file mode 100644
index 000000000..afa4bb7c7
--- /dev/null
+++ b/vendor/elsa/src/sync.rs
@@ -0,0 +1,624 @@
+//! **This module is experimental**
+//!
+//! This module provides threadsafe versions of FrozenMap and FrozenVec,
+//! ideal for use as a cache.
+//!
+//! These lock internally, however locks only last as long as the method calls
+//!
+
+use stable_deref_trait::StableDeref;
+use std::alloc::Layout;
+use std::borrow::Borrow;
+use std::collections::BTreeMap;
+use std::collections::HashMap;
+use std::hash::Hash;
+use std::iter::{FromIterator, IntoIterator};
+use std::mem::MaybeUninit;
+use std::ops::Index;
+
+use std::sync::atomic::AtomicPtr;
+use std::sync::atomic::AtomicUsize;
+use std::sync::atomic::Ordering;
+use std::sync::RwLock;
+
+/// Append-only threadsafe version of `std::collections::HashMap` where
+/// insertion does not require mutable access
+pub struct FrozenMap<K, V> {
+ map: RwLock<HashMap<K, V>>,
+}
+
+impl<K, V> Default for FrozenMap<K, V> {
+ fn default() -> Self {
+ Self {
+ map: Default::default(),
+ }
+ }
+}
+
+impl<K: Eq + Hash, V: StableDeref> FrozenMap<K, V> {
+ // these should never return &K or &V
+ // these should never delete any entries
+
+ pub fn new() -> Self {
+ Self::default()
+ }
+
+ /// If the key exists in the map, returns a reference
+ /// to the corresponding value, otherwise inserts a
+ /// new entry in the map for that key and returns a
+ /// reference to the given value.
+ ///
+ /// Existing values are never overwritten.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// assert_eq!(map.insert(1, Box::new("a")), &"a");
+ /// assert_eq!(map.insert(1, Box::new("b")), &"a");
+ /// ```
+ pub fn insert(&self, k: K, v: V) -> &V::Target {
+ let mut map = self.map.write().unwrap();
+ let ret = unsafe {
+ let inserted = &**map.entry(k).or_insert(v);
+ &*(inserted as *const _)
+ };
+ ret
+ }
+
+ /// If the key exists in the map, returns a reference to the corresponding
+ /// value, otherwise inserts a new entry in the map for that key and the
+ /// value returned by the creation function, and returns a reference to the
+ /// generated value.
+ ///
+ /// Existing values are never overwritten.
+ ///
+ /// The key may be any borrowed form of the map's key type, but [`Hash`] and
+ /// [`Eq`] on the borrowed form *must* match those for the key type.
+ ///
+ /// **Note** that the write lock is held for the duration of this function’s
+ /// execution, even while the value creation function is executing (if
+ /// needed). This will block any concurrent `get` or `insert` calls.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// assert_eq!(map.insert_with(1, || Box::new("a")), &"a");
+ /// assert_eq!(map.insert_with(1, || unreachable!()), &"a");
+ /// ```
+ pub fn insert_with(&self, k: K, f: impl FnOnce() -> V) -> &V::Target {
+ let mut map = self.map.write().unwrap();
+ let ret = unsafe {
+ let inserted = &**map.entry(k).or_insert_with(f);
+ &*(inserted as *const _)
+ };
+ ret
+ }
+
+ /// If the key exists in the map, returns a reference to the corresponding
+ /// value, otherwise inserts a new entry in the map for that key and the
+ /// value returned by the creation function, and returns a reference to the
+ /// generated value.
+ ///
+ /// Existing values are never overwritten.
+ ///
+ /// The key may be any borrowed form of the map's key type, but [`Hash`] and
+ /// [`Eq`] on the borrowed form *must* match those for the key type.
+ ///
+ /// **Note** that the write lock is held for the duration of this function’s
+ /// execution, even while the value creation function is executing (if
+ /// needed). This will block any concurrent `get` or `insert` calls.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// assert_eq!(map.insert_with_key(1, |_| Box::new("a")), &"a");
+ /// assert_eq!(map.insert_with_key(1, |_| unreachable!()), &"a");
+ /// ```
+ pub fn insert_with_key(&self, k: K, f: impl FnOnce(&K) -> V) -> &V::Target {
+ let mut map = self.map.write().unwrap();
+ let ret = unsafe {
+ let inserted = &**map.entry(k).or_insert_with_key(f);
+ &*(inserted as *const _)
+ };
+ ret
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.get(&1), Some(&"a"));
+ /// assert_eq!(map.get(&2), None);
+ /// ```
+ pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ let map = self.map.read().unwrap();
+ let ret = unsafe { map.get(k).map(|x| &*(&**x as *const V::Target)) };
+ ret
+ }
+
+ /// Applies a function to the owner of the value corresponding to the key (if any).
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
+ /// assert_eq!(map.map_get(&2, Clone::clone), None);
+ /// ```
+ pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ F: FnOnce(&V) -> T,
+ {
+ let map = self.map.read().unwrap();
+ let ret = map.get(k).map(f);
+ ret
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// assert_eq!(map.len(), 0);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.len(), 1);
+ /// ```
+ pub fn len(&self) -> usize {
+ let map = self.map.read().unwrap();
+ map.len()
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenMap;
+ ///
+ /// let map = FrozenMap::new();
+ /// assert_eq!(map.is_empty(), true);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.is_empty(), false);
+ /// ```
+ pub fn is_empty(&self) -> bool {
+ let map = self.map.read().unwrap();
+ map.is_empty()
+ }
+
+ // TODO add more
+}
+
+/// Append-only threadsafe version of `std::vec::Vec` where
+/// insertion does not require mutable access
+pub struct FrozenVec<T> {
+ vec: RwLock<Vec<T>>,
+}
+
+impl<T> Default for FrozenVec<T> {
+ fn default() -> Self {
+ Self {
+ vec: Default::default(),
+ }
+ }
+}
+
+impl<T: StableDeref> FrozenVec<T> {
+ pub fn new() -> Self {
+ Default::default()
+ }
+
+ // these should never return &T
+ // these should never delete any entries
+
+ pub fn push(&self, val: T) {
+ let mut vec = self.vec.write().unwrap();
+ vec.push(val);
+ }
+
+ /// Push, immediately getting a reference to the element
+ pub fn push_get(&self, val: T) -> &T::Target {
+ let mut vec = self.vec.write().unwrap();
+ vec.push(val);
+ unsafe { &*(&**vec.get_unchecked(vec.len() - 1) as *const T::Target) }
+ }
+
+ /// Push, immediately getting a an index of the element
+ ///
+ /// Index can then be used with the `get` method
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenVec;
+ ///
+ /// let map = FrozenVec::new();
+ /// let idx = map.push_get_index(String::from("a"));
+ /// assert_eq!(map.get(idx), Some("a"));
+ /// assert_eq!(idx, 0);
+ /// assert_eq!(map.push_get_index(String::from("b")), 1);
+ /// ```
+ pub fn push_get_index(&self, val: T) -> usize {
+ let mut vec = self.vec.write().unwrap();
+ let index = vec.len();
+ vec.push(val);
+ return index;
+ }
+
+ pub fn get(&self, index: usize) -> Option<&T::Target> {
+ let vec = self.vec.read().unwrap();
+ unsafe { vec.get(index).map(|x| &*(&**x as *const T::Target)) }
+ }
+
+ // TODO add more
+}
+
+/// Append-only threadsafe version of `std::vec::Vec` where
+/// insertion does not require mutable access.
+/// Does not have locks, only allows `Copy` types and will
+/// spinlock on contention. The spinlocks are really rare as
+/// they only happen on reallocation due to a push going over
+/// the capacity.
+pub struct LockFreeFrozenVec<T: Copy> {
+ data: AtomicPtr<T>,
+ len: AtomicUsize,
+ cap: AtomicUsize,
+}
+
+impl<T: Copy> Drop for LockFreeFrozenVec<T> {
+ fn drop(&mut self) {
+ let cap = *self.cap.get_mut();
+ let layout = self.layout(cap);
+ unsafe {
+ std::alloc::dealloc((*self.data.get_mut()).cast(), layout);
+ }
+ }
+}
+
+impl<T: Copy> Default for LockFreeFrozenVec<T> {
+ fn default() -> Self {
+ Self {
+ // FIXME: use `std::ptr::invalid_mut()` once that is stable.
+ data: AtomicPtr::new(std::mem::align_of::<T>() as *mut T),
+ len: AtomicUsize::new(0),
+ cap: AtomicUsize::new(0),
+ }
+ }
+}
+
+impl<T: Copy> LockFreeFrozenVec<T> {
+ pub fn new() -> Self {
+ Default::default()
+ }
+
+ pub fn with_capacity(cap: usize) -> Self {
+ Self {
+ data: AtomicPtr::new(
+ Box::into_raw(vec![MaybeUninit::<T>::uninit(); cap].into_boxed_slice()).cast(),
+ ),
+ len: AtomicUsize::new(0),
+ cap: AtomicUsize::new(cap),
+ }
+ }
+
+ fn lock<U>(&self, f: impl FnOnce(&mut *mut T) -> U) -> U {
+ let mut ptr;
+ loop {
+ ptr = self.data.swap(std::ptr::null_mut(), Ordering::Acquire);
+ if !ptr.is_null() {
+ // Wheeeee spinlock
+ break;
+ }
+ }
+
+ let ret = f(&mut ptr);
+ self.data.store(ptr, Ordering::Release);
+ ret
+ }
+
+ fn layout(&self, cap: usize) -> Layout {
+ let num_bytes = std::mem::size_of::<T>() * cap;
+ let align = std::mem::align_of::<T>();
+ Layout::from_size_align(num_bytes, align).unwrap()
+ }
+
+ // these should never return &T
+ // these should never delete any entries
+
+ const NOT_ZST: () = if std::mem::size_of::<T>() == 0 {
+ panic!("`LockFreeFrozenVec` cannot be used with ZSTs");
+ };
+
+ pub fn push(&self, val: T) -> usize {
+ // This statement actually does something: it evaluates a constant.
+ #[allow(path_statements)]
+ {
+ Self::NOT_ZST
+ }
+ self.lock(|ptr| {
+ // These values must be consistent with the pointer we got.
+ let len = self.len.load(Ordering::Acquire);
+ let cap = self.cap.load(Ordering::Acquire);
+ if len >= cap {
+ if cap == 0 {
+ // No memory allocated yet
+ let layout = self.layout(128);
+ // SAFETY: `LockFreeFrozenVec` statically rejects zsts
+ unsafe {
+ *ptr = std::alloc::alloc(layout).cast::<T>();
+ }
+ // This is written before the end of the `lock` closure, so no one will observe this
+ // until the data pointer has been updated anyway.
+ self.cap.store(128, Ordering::Release);
+ } else {
+ // Out of memory, realloc with double the capacity
+ let layout = self.layout(cap);
+ let new_size = layout.size() * 2;
+ // SAFETY: `LockFreeFrozenVec` statically rejects zsts and the input `ptr` has always been
+ // allocated at the size stated in `cap`.
+ unsafe {
+ *ptr = std::alloc::realloc((*ptr).cast(), layout, new_size).cast::<T>();
+ }
+ // This is written before the end of the `lock` closure, so no one will observe this
+ // until the data pointer has been updated anyway.
+ self.cap.store(cap * 2, Ordering::Release);
+ }
+ assert!(!ptr.is_null());
+ }
+ unsafe {
+ ptr.add(len).write(val);
+ }
+ // This is written before updating the data pointer. Other `push` calls cannot observe this,
+ // because they are blocked on aquiring the data pointer before they ever read the `len`.
+ // `get` may read the length before actually aquiring the data pointer lock, but that is fine,
+ // as once it is able to aquire the lock, there will be actually the right number of elements
+ // stored.
+ self.len.store(len + 1, Ordering::Release);
+ len
+ })
+ }
+
+ pub fn get(&self, index: usize) -> Option<T> {
+ // The length can only grow, so just doing the length check
+ // independently of the `lock` and read is fine. Worst case we
+ // read an old length value and end up returning `None` even if
+ // another thread already inserted the value.
+ let len = self.len.load(Ordering::Relaxed);
+ if index >= len {
+ return None;
+ }
+ self.lock(|ptr| Some(unsafe { ptr.add(index).read() }))
+ }
+}
+
+#[test]
+fn test_non_lockfree() {
+ #[derive(Copy, Clone, Debug, PartialEq, Eq)]
+ struct Moo(i32);
+
+ for vec in [
+ LockFreeFrozenVec::new(),
+ LockFreeFrozenVec::with_capacity(1),
+ LockFreeFrozenVec::with_capacity(2),
+ LockFreeFrozenVec::with_capacity(1000),
+ ] {
+ assert_eq!(vec.get(1), None);
+
+ vec.push(Moo(1));
+ let i = vec.push(Moo(2));
+ vec.push(Moo(3));
+
+ assert_eq!(vec.get(i), Some(Moo(2)));
+
+ std::thread::scope(|s| {
+ s.spawn(|| {
+ for i in 0..1000 {
+ vec.push(Moo(i));
+ }
+ });
+ s.spawn(|| {
+ for i in 0..1000 {
+ vec.push(Moo(i));
+ }
+ });
+ for i in 0..2000 {
+ while vec.get(i).is_none() {}
+ }
+ });
+ }
+}
+
+/// Append-only threadsafe version of `std::collections::BTreeMap` where
+/// insertion does not require mutable access
+#[derive(Debug)]
+pub struct FrozenBTreeMap<K, V>(RwLock<BTreeMap<K, V>>);
+
+impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> {
+ pub fn new() -> Self {
+ Self(RwLock::new(BTreeMap::new()))
+ }
+
+ // these should never return &K or &V
+ // these should never delete any entries
+
+ /// Returns a reference to the value corresponding to the key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Ord`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.get(&1), Some(&"a"));
+ /// assert_eq!(map.get(&2), None);
+ /// ```
+ pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ {
+ let map = self.0.read().unwrap();
+ let ret = unsafe { map.get(k).map(|x| &*(&**x as *const V::Target)) };
+ ret
+ }
+
+ /// Insert a new value into the map. Does nothing if the key is already occupied.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.get(&1), Some(&"a"));
+ /// ```
+ pub fn insert(&self, k: K, v: V) -> &V::Target {
+ let mut map = self.0.write().unwrap();
+ let ret = unsafe {
+ let inserted = &**map.entry(k).or_insert(v);
+ &*(inserted as *const _)
+ };
+ ret
+ }
+
+ /// Applies a function to the owner of the value corresponding to the key (if any).
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Ord`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
+ /// assert_eq!(map.map_get(&2, Clone::clone), None);
+ /// ```
+ pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ F: FnOnce(&V) -> T,
+ {
+ let map = self.0.read().unwrap();
+ let ret = map.get(k).map(f);
+ ret
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// assert_eq!(map.len(), 0);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.len(), 1);
+ /// ```
+ pub fn len(&self) -> usize {
+ let map = self.0.read().unwrap();
+ map.len()
+ }
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// assert_eq!(map.is_empty(), true);
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map.is_empty(), false);
+ /// ```
+ pub fn is_empty(&self) -> bool {
+ let map = self.0.read().unwrap();
+ map.is_empty()
+ }
+}
+
+impl<K: Clone + Ord, V: StableDeref> From<BTreeMap<K, V>> for FrozenBTreeMap<K, V> {
+ fn from(map: BTreeMap<K, V>) -> Self {
+ Self(RwLock::new(map))
+ }
+}
+
+impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V>
+where
+ Q: Ord,
+ K: Clone + Ord + Borrow<Q>,
+ V: StableDeref,
+{
+ type Output = V::Target;
+
+ /// # Examples
+ ///
+ /// ```
+ /// use elsa::sync::FrozenBTreeMap;
+ ///
+ /// let map = FrozenBTreeMap::new();
+ /// map.insert(1, Box::new("a"));
+ /// assert_eq!(map[&1], "a");
+ /// ```
+ fn index(&self, idx: &Q) -> &V::Target {
+ self.get(idx)
+ .expect("attempted to index FrozenBTreeMap with unknown key")
+ }
+}
+
+impl<K: Clone + Ord, V: StableDeref> FromIterator<(K, V)> for FrozenBTreeMap<K, V> {
+ fn from_iter<T>(iter: T) -> Self
+ where
+ T: IntoIterator<Item = (K, V)>,
+ {
+ let map: BTreeMap<_, _> = iter.into_iter().collect();
+ map.into()
+ }
+}
+
+impl<K: Clone + Ord, V: StableDeref> Default for FrozenBTreeMap<K, V> {
+ fn default() -> Self {
+ Self::new()
+ }
+}
diff --git a/vendor/elsa/src/vec.rs b/vendor/elsa/src/vec.rs
new file mode 100644
index 000000000..33b6e6a50
--- /dev/null
+++ b/vendor/elsa/src/vec.rs
@@ -0,0 +1,347 @@
+use std::cell::UnsafeCell;
+use std::cmp::Ordering;
+use std::iter::FromIterator;
+use std::ops::Index;
+
+use stable_deref_trait::StableDeref;
+
+/// Append-only version of `std::vec::Vec` where
+/// insertion does not require mutable access
+pub struct FrozenVec<T> {
+ vec: UnsafeCell<Vec<T>>,
+ // XXXManishearth do we need a reentrancy guard here as well?
+ // StableDeref may not guarantee that there are no side effects
+}
+
+// safety: UnsafeCell implies !Sync
+
+impl<T> FrozenVec<T> {
+ /// Constructs a new, empty vector.
+ pub fn new() -> Self {
+ Self {
+ vec: UnsafeCell::new(Default::default()),
+ }
+ }
+}
+
+impl<T> FrozenVec<T> {
+ // these should never return &T
+ // these should never delete any entries
+
+ /// Appends an element to the back of the vector.
+ pub fn push(&self, val: T) {
+ unsafe {
+ let vec = self.vec.get();
+ (*vec).push(val)
+ }
+ }
+}
+
+impl<T: StableDeref> FrozenVec<T> {
+ /// Push, immediately getting a reference to the element
+ pub fn push_get(&self, val: T) -> &T::Target {
+ unsafe {
+ let vec = self.vec.get();
+ (*vec).push(val);
+ &*(&**(*vec).get_unchecked((*vec).len() - 1) as *const T::Target)
+ }
+ }
+
+ /// Returns a reference to an element.
+ pub fn get(&self, index: usize) -> Option<&T::Target> {
+ unsafe {
+ let vec = self.vec.get();
+ (*vec).get(index).map(|x| &**x)
+ }
+ }
+
+ /// Returns a reference to an element, without doing bounds checking.
+ ///
+ /// ## Safety
+ ///
+ /// `index` must be in bounds, i.e. it must be less than `self.len()`
+ pub unsafe fn get_unchecked(&self, index: usize) -> &T::Target {
+ let vec = self.vec.get();
+ &**(*vec).get_unchecked(index)
+ }
+}
+
+impl<T: Copy> FrozenVec<T> {
+ /// Returns a copy of an element.
+ pub fn get_copy(&self, index: usize) -> Option<T> {
+ unsafe {
+ let vec = self.vec.get();
+ (*vec).get(index).copied()
+ }
+ }
+}
+
+impl<T> FrozenVec<T> {
+ /// Returns the number of elements in the vector.
+ pub fn len(&self) -> usize {
+ unsafe {
+ let vec = self.vec.get();
+ (*vec).len()
+ }
+ }
+
+ /// Returns `true` if the vector contains no elements.
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl<T: StableDeref> FrozenVec<T> {
+ /// Returns the first element of the vector, or `None` if empty.
+ pub fn first(&self) -> Option<&T::Target> {
+ unsafe {
+ let vec = self.vec.get();
+ (*vec).first().map(|x| &**x)
+ }
+ }
+
+ /// Returns the last element of the vector, or `None` if empty.
+ pub fn last(&self) -> Option<&T::Target> {
+ unsafe {
+ let vec = self.vec.get();
+ (*vec).last().map(|x| &**x)
+ }
+ }
+ /// Returns an iterator over the vector.
+ pub fn iter(&self) -> Iter<T> {
+ self.into_iter()
+ }
+}
+
+impl<T: StableDeref> FrozenVec<T> {
+ /// Converts the frozen vector into a plain vector.
+ pub fn into_vec(self) -> Vec<T> {
+ self.vec.into_inner()
+ }
+}
+
+impl<T: StableDeref> FrozenVec<T> {
+ // binary search functions: they need to be reimplemented here to be safe (instead of calling
+ // their equivalents directly on the underlying Vec), as they run user callbacks that could
+ // reentrantly call other functions on this vector
+
+ /// Binary searches this sorted vector for a given element, analogous to [slice::binary_search].
+ pub fn binary_search(&self, x: &T::Target) -> Result<usize, usize>
+ where
+ T::Target: Ord,
+ {
+ self.binary_search_by(|p| p.cmp(x))
+ }
+
+ /// Binary searches this sorted vector with a comparator function, analogous to
+ /// [slice::binary_search_by].
+ pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
+ where
+ F: FnMut(&'a T::Target) -> Ordering,
+ {
+ let mut size = self.len();
+ let mut left = 0;
+ let mut right = size;
+ while left < right {
+ let mid = left + size / 2;
+
+ // safety: like the core algorithm, mid is always within original vector len; in
+ // pathlogical cases, user could push to the vector in the meantime, but this can only
+ // increase the length, keeping this safe
+ let cmp = f(unsafe { self.get_unchecked(mid) });
+
+ if cmp == Ordering::Less {
+ left = mid + 1;
+ } else if cmp == Ordering::Greater {
+ right = mid;
+ } else {
+ return Ok(mid);
+ }
+
+ size = right - left;
+ }
+ Err(left)
+ }
+
+ /// Binary searches this sorted vector with a key extraction function, analogous to
+ /// [slice::binary_search_by_key].
+ pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
+ where
+ F: FnMut(&'a T::Target) -> B,
+ B: Ord,
+ {
+ self.binary_search_by(|k| f(k).cmp(b))
+ }
+
+ /// Returns the index of the partition point according to the given predicate
+ /// (the index of the first element of the second partition), analogous to
+ /// [slice::partition_point].
+ pub fn partition_point<P>(&self, mut pred: P) -> usize
+ where
+ P: FnMut(&T::Target) -> bool,
+ {
+ let mut left = 0;
+ let mut right = self.len();
+
+ while left != right {
+ let mid = left + (right - left) / 2;
+ // safety: like in binary_search_by
+ let value = unsafe { self.get_unchecked(mid) };
+ if pred(value) {
+ left = mid + 1;
+ } else {
+ right = mid;
+ }
+ }
+
+ left
+ }
+
+ // TODO add more
+}
+
+impl<T> std::convert::AsMut<Vec<T>> for FrozenVec<T> {
+ /// Get mutable access to the underlying vector.
+ ///
+ /// This is safe, as it requires a `&mut self`, ensuring nothing is using
+ /// the 'frozen' contents.
+ fn as_mut(&mut self) -> &mut Vec<T> {
+ unsafe { &mut *self.vec.get() }
+ }
+}
+
+impl<T> Default for FrozenVec<T> {
+ fn default() -> Self {
+ FrozenVec::new()
+ }
+}
+
+impl<T> From<Vec<T>> for FrozenVec<T> {
+ fn from(vec: Vec<T>) -> Self {
+ Self {
+ vec: UnsafeCell::new(vec),
+ }
+ }
+}
+
+impl<T: StableDeref> Index<usize> for FrozenVec<T> {
+ type Output = T::Target;
+ fn index(&self, idx: usize) -> &T::Target {
+ self.get(idx).unwrap_or_else(|| {
+ panic!(
+ "index out of bounds: the len is {} but the index is {}",
+ self.len(),
+ idx
+ )
+ })
+ }
+}
+
+impl<A> FromIterator<A> for FrozenVec<A> {
+ fn from_iter<T>(iter: T) -> Self
+ where
+ T: IntoIterator<Item = A>,
+ {
+ let vec: Vec<_> = iter.into_iter().collect();
+ vec.into()
+ }
+}
+
+/// Iterator over FrozenVec, obtained via `.iter()`
+///
+/// It is safe to push to the vector during iteration
+pub struct Iter<'a, T> {
+ vec: &'a FrozenVec<T>,
+ idx: usize,
+}
+
+impl<'a, T: StableDeref> Iterator for Iter<'a, T> {
+ type Item = &'a T::Target;
+ fn next(&mut self) -> Option<&'a T::Target> {
+ if let Some(ret) = self.vec.get(self.idx) {
+ self.idx += 1;
+ Some(ret)
+ } else {
+ None
+ }
+ }
+}
+
+impl<'a, T: StableDeref> IntoIterator for &'a FrozenVec<T> {
+ type Item = &'a T::Target;
+ type IntoIter = Iter<'a, T>;
+ fn into_iter(self) -> Iter<'a, T> {
+ Iter { vec: self, idx: 0 }
+ }
+}
+
+#[test]
+fn test_iteration() {
+ let vec = vec!["a", "b", "c", "d"];
+ let frozen: FrozenVec<_> = vec.clone().into();
+
+ assert_eq!(vec, frozen.iter().collect::<Vec<_>>());
+ for (e1, e2) in vec.iter().zip(frozen.iter()) {
+ assert_eq!(*e1, e2);
+ }
+
+ assert_eq!(vec.len(), frozen.iter().count())
+}
+
+#[test]
+fn test_accessors() {
+ let vec: FrozenVec<String> = FrozenVec::new();
+
+ assert_eq!(vec.is_empty(), true);
+ assert_eq!(vec.len(), 0);
+ assert_eq!(vec.first(), None);
+ assert_eq!(vec.last(), None);
+ assert_eq!(vec.get(1), None);
+
+ vec.push("a".to_string());
+ vec.push("b".to_string());
+ vec.push("c".to_string());
+
+ assert_eq!(vec.is_empty(), false);
+ assert_eq!(vec.len(), 3);
+ assert_eq!(vec.first(), Some("a"));
+ assert_eq!(vec.last(), Some("c"));
+ assert_eq!(vec.get(1), Some("b"));
+}
+
+#[test]
+fn test_non_stable_deref() {
+ #[derive(Copy, Clone, Debug, PartialEq, Eq)]
+ struct Moo(i32);
+ let vec: FrozenVec<Moo> = FrozenVec::new();
+
+ assert_eq!(vec.is_empty(), true);
+ assert_eq!(vec.len(), 0);
+ assert_eq!(vec.get_copy(1), None);
+
+ vec.push(Moo(1));
+ vec.push(Moo(2));
+ vec.push(Moo(3));
+
+ assert_eq!(vec.is_empty(), false);
+ assert_eq!(vec.len(), 3);
+ assert_eq!(vec.get_copy(1), Some(Moo(2)));
+}
+
+#[test]
+fn test_binary_search() {
+ let vec: FrozenVec<_> = vec!["ab", "cde", "fghij"].into();
+
+ assert_eq!(vec.binary_search("cde"), Ok(1));
+ assert_eq!(vec.binary_search("cdf"), Err(2));
+ assert_eq!(vec.binary_search("a"), Err(0));
+ assert_eq!(vec.binary_search("g"), Err(3));
+
+ assert_eq!(vec.binary_search_by_key(&1, |x| x.len()), Err(0));
+ assert_eq!(vec.binary_search_by_key(&3, |x| x.len()), Ok(1));
+ assert_eq!(vec.binary_search_by_key(&4, |x| x.len()), Err(2));
+
+ assert_eq!(vec.partition_point(|x| x.len() < 4), 2);
+ assert_eq!(vec.partition_point(|_| false), 0);
+ assert_eq!(vec.partition_point(|_| true), 3);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-14 21:00:17 +0000