From 4f9fe856a25ab29345b90e7725509e9ee38a37be Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:41 +0200 Subject: Adding upstream version 1.69.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/elsa/src/index_map.rs | 215 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 215 insertions(+) create mode 100644 vendor/elsa/src/index_map.rs (limited to 'vendor/elsa/src/index_map.rs') 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 { + map: UnsafeCell>, + /// 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, +} + +// safety: UnsafeCell implies !Sync + +impl FrozenIndexMap { + pub fn new() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } +} + +impl FrozenIndexMap { + // 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(&self, k: &Q) -> Option<&V::Target> + where + K: Borrow, + 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(&self, k: &Q, f: F) -> Option + where + K: Borrow, + 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 { + 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 { + 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 From> for FrozenIndexMap { + fn from(map: IndexMap) -> Self { + Self { + map: UnsafeCell::new(map), + in_use: Cell::new(false), + } + } +} + +impl Index<&Q> for FrozenIndexMap + where + Q: Eq + Hash, + K: Eq + Hash + Borrow, + 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 FromIterator<(K, V)> for FrozenIndexMap { + fn from_iter(iter: T) -> Self + where + T: IntoIterator, + { + let map: IndexMap<_, _, _> = iter.into_iter().collect(); + map.into() + } +} + +impl Default for FrozenIndexMap { + fn default() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } +} -- cgit v1.2.3