From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_data_structures/src/vec_map.rs | 194 ++++++++++++++++++++++++++ 1 file changed, 194 insertions(+) create mode 100644 compiler/rustc_data_structures/src/vec_map.rs (limited to 'compiler/rustc_data_structures/src/vec_map.rs') diff --git a/compiler/rustc_data_structures/src/vec_map.rs b/compiler/rustc_data_structures/src/vec_map.rs new file mode 100644 index 000000000..86be0bd87 --- /dev/null +++ b/compiler/rustc_data_structures/src/vec_map.rs @@ -0,0 +1,194 @@ +use std::borrow::Borrow; +use std::fmt::Debug; +use std::iter::FromIterator; +use std::slice::Iter; +use std::vec::IntoIter; + +use crate::stable_hasher::{HashStable, StableHasher}; + +/// A map type implemented as a vector of pairs `K` (key) and `V` (value). +/// It currently provides a subset of all the map operations, the rest could be added as needed. +#[derive(Clone, Encodable, Decodable, Debug)] +pub struct VecMap(Vec<(K, V)>); + +impl VecMap +where + K: Debug + PartialEq, + V: Debug, +{ + pub fn new() -> Self { + VecMap(Default::default()) + } + + /// Sets the value of the entry, and returns the entry's old value. + pub fn insert(&mut self, k: K, v: V) -> Option { + if let Some(elem) = self.0.iter_mut().find(|(key, _)| *key == k) { + Some(std::mem::replace(&mut elem.1, v)) + } else { + self.0.push((k, v)); + None + } + } + + /// Removes the entry from the map and returns the removed value + pub fn remove(&mut self, k: &K) -> Option { + self.0.iter().position(|(k2, _)| k2 == k).map(|pos| self.0.remove(pos).1) + } + + /// Gets a reference to the value in the entry. + pub fn get(&self, k: &Q) -> Option<&V> + where + K: Borrow, + Q: Eq, + { + self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) + } + + /// Gets a mutable reference to the value in the entry. + pub fn get_mut(&mut self, k: &Q) -> Option<&mut V> + where + K: Borrow, + Q: Eq, + { + self.0.iter_mut().find(|(key, _)| k == key.borrow()).map(|elem| &mut elem.1) + } + + /// Returns the any value corresponding to the supplied predicate filter. + /// + /// The supplied predicate will be applied to each (key, value) pair and it will return a + /// reference to the values where the predicate returns `true`. + pub fn any_value_matching(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { + self.0.iter().find(|kv| predicate(kv)).map(|elem| &elem.1) + } + + /// Returns the value corresponding to the supplied predicate filter. It crashes if there's + /// more than one matching element. + /// + /// The supplied predicate will be applied to each (key, value) pair and it will return a + /// reference to the value where the predicate returns `true`. + pub fn get_value_matching(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { + let mut filter = self.0.iter().filter(|kv| predicate(kv)); + let (_, value) = filter.next()?; + // This should return just one element, otherwise it's a bug + assert!( + filter.next().is_none(), + "Collection {:#?} should have just one matching element", + self + ); + Some(value) + } + + /// Returns `true` if the map contains a value for the specified key. + /// + /// The key may be any borrowed form of the map's key type, + /// [`Eq`] on the borrowed form *must* match those for + /// the key type. + pub fn contains_key(&self, k: &Q) -> bool + where + K: Borrow, + Q: Eq, + { + self.get(k).is_some() + } + + /// Returns `true` if the map contains no elements. + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } + + pub fn iter(&self) -> Iter<'_, (K, V)> { + self.into_iter() + } + + pub fn iter_mut(&mut self) -> impl Iterator { + self.into_iter() + } + + pub fn retain(&mut self, f: impl Fn(&(K, V)) -> bool) { + self.0.retain(f) + } +} + +impl Default for VecMap { + #[inline] + fn default() -> Self { + Self(Default::default()) + } +} + +impl From> for VecMap { + fn from(vec: Vec<(K, V)>) -> Self { + Self(vec) + } +} + +impl Into> for VecMap { + fn into(self) -> Vec<(K, V)> { + self.0 + } +} + +impl FromIterator<(K, V)> for VecMap { + fn from_iter>(iter: I) -> Self { + Self(iter.into_iter().collect()) + } +} + +impl<'a, K, V> IntoIterator for &'a VecMap { + type Item = &'a (K, V); + type IntoIter = Iter<'a, (K, V)>; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.0.iter() + } +} + +impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut VecMap { + type Item = (&'a K, &'a mut V); + type IntoIter = impl Iterator; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.0.iter_mut().map(|(k, v)| (&*k, v)) + } +} + +impl IntoIterator for VecMap { + type Item = (K, V); + type IntoIter = IntoIter<(K, V)>; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.0.into_iter() + } +} + +impl Extend<(K, V)> for VecMap { + fn extend>(&mut self, iter: I) { + for (k, v) in iter { + self.insert(k, v); + } + } + + fn extend_one(&mut self, (k, v): (K, V)) { + self.insert(k, v); + } + + fn extend_reserve(&mut self, additional: usize) { + self.0.extend_reserve(additional); + } +} + +impl HashStable for VecMap +where + K: HashStable + Eq, + V: HashStable, +{ + fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { + self.0.hash_stable(hcx, hasher) + } +} + +#[cfg(test)] +mod tests; -- cgit v1.2.3