From 3e3e70d529d8c7d7c4d7bc4fefc9f109393b9245 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:43 +0200 Subject: Merging upstream version 1.69.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/elsa/src/vec.rs | 347 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 347 insertions(+) create mode 100644 vendor/elsa/src/vec.rs (limited to 'vendor/elsa/src/vec.rs') 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 { + vec: UnsafeCell>, + // 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 FrozenVec { + /// Constructs a new, empty vector. + pub fn new() -> Self { + Self { + vec: UnsafeCell::new(Default::default()), + } + } +} + +impl FrozenVec { + // 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 FrozenVec { + /// 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 FrozenVec { + /// Returns a copy of an element. + pub fn get_copy(&self, index: usize) -> Option { + unsafe { + let vec = self.vec.get(); + (*vec).get(index).copied() + } + } +} + +impl FrozenVec { + /// 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 FrozenVec { + /// 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 { + self.into_iter() + } +} + +impl FrozenVec { + /// Converts the frozen vector into a plain vector. + pub fn into_vec(self) -> Vec { + self.vec.into_inner() + } +} + +impl FrozenVec { + // 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 + 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 + 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 + 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

(&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 std::convert::AsMut> for FrozenVec { + /// 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 { + unsafe { &mut *self.vec.get() } + } +} + +impl Default for FrozenVec { + fn default() -> Self { + FrozenVec::new() + } +} + +impl From> for FrozenVec { + fn from(vec: Vec) -> Self { + Self { + vec: UnsafeCell::new(vec), + } + } +} + +impl Index for FrozenVec { + 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 FromIterator for FrozenVec { + fn from_iter(iter: T) -> Self + where + T: IntoIterator, + { + 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, + 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 { + 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::>()); + 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 = 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 = 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); +} -- cgit v1.2.3