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 --- .../src/sorted_map/index_map.rs | 154 +++++++++++++++++++++ 1 file changed, 154 insertions(+) create mode 100644 compiler/rustc_data_structures/src/sorted_map/index_map.rs (limited to 'compiler/rustc_data_structures/src/sorted_map/index_map.rs') diff --git a/compiler/rustc_data_structures/src/sorted_map/index_map.rs b/compiler/rustc_data_structures/src/sorted_map/index_map.rs new file mode 100644 index 000000000..0ec32dc43 --- /dev/null +++ b/compiler/rustc_data_structures/src/sorted_map/index_map.rs @@ -0,0 +1,154 @@ +//! A variant of `SortedMap` that preserves insertion order. + +use std::hash::{Hash, Hasher}; +use std::iter::FromIterator; + +use crate::stable_hasher::{HashStable, StableHasher}; +use rustc_index::vec::{Idx, IndexVec}; + +/// An indexed multi-map that preserves insertion order while permitting both *O*(log *n*) lookup of +/// an item by key and *O*(1) lookup by index. +/// +/// This data structure is a hybrid of an [`IndexVec`] and a [`SortedMap`]. Like `IndexVec`, +/// `SortedIndexMultiMap` assigns a typed index to each item while preserving insertion order. +/// Like `SortedMap`, `SortedIndexMultiMap` has efficient lookup of items by key. However, this +/// is accomplished by sorting an array of item indices instead of the items themselves. +/// +/// Unlike `SortedMap`, this data structure can hold multiple equivalent items at once, so the +/// `get_by_key` method and its variants return an iterator instead of an `Option`. Equivalent +/// items will be yielded in insertion order. +/// +/// Unlike a general-purpose map like `BTreeSet` or `HashSet`, `SortedMap` and +/// `SortedIndexMultiMap` require *O*(*n*) time to insert a single item. This is because we may need +/// to insert into the middle of the sorted array. Users should avoid mutating this data structure +/// in-place. +/// +/// [`SortedMap`]: super::SortedMap +#[derive(Clone, Debug)] +pub struct SortedIndexMultiMap { + /// The elements of the map in insertion order. + items: IndexVec, + + /// Indices of the items in the set, sorted by the item's key. + idx_sorted_by_item_key: Vec, +} + +impl SortedIndexMultiMap { + #[inline] + pub fn new() -> Self { + SortedIndexMultiMap { items: IndexVec::new(), idx_sorted_by_item_key: Vec::new() } + } + + #[inline] + pub fn len(&self) -> usize { + self.items.len() + } + + #[inline] + pub fn is_empty(&self) -> bool { + self.items.is_empty() + } + + /// Returns an iterator over the items in the map in insertion order. + #[inline] + pub fn into_iter(self) -> impl DoubleEndedIterator { + self.items.into_iter() + } + + /// Returns an iterator over the items in the map in insertion order along with their indices. + #[inline] + pub fn into_iter_enumerated(self) -> impl DoubleEndedIterator { + self.items.into_iter_enumerated() + } + + /// Returns an iterator over the items in the map in insertion order. + #[inline] + pub fn iter(&self) -> impl '_ + DoubleEndedIterator { + self.items.iter().map(|(ref k, ref v)| (k, v)) + } + + /// Returns an iterator over the items in the map in insertion order along with their indices. + #[inline] + pub fn iter_enumerated(&self) -> impl '_ + DoubleEndedIterator { + self.items.iter_enumerated().map(|(i, (ref k, ref v))| (i, (k, v))) + } + + /// Returns the item in the map with the given index. + #[inline] + pub fn get(&self, idx: I) -> Option<&(K, V)> { + self.items.get(idx) + } + + /// Returns an iterator over the items in the map that are equal to `key`. + /// + /// If there are multiple items that are equivalent to `key`, they will be yielded in + /// insertion order. + #[inline] + pub fn get_by_key(&self, key: K) -> impl Iterator + '_ { + self.get_by_key_enumerated(key).map(|(_, v)| v) + } + + /// Returns an iterator over the items in the map that are equal to `key` along with their + /// indices. + /// + /// If there are multiple items that are equivalent to `key`, they will be yielded in + /// insertion order. + #[inline] + pub fn get_by_key_enumerated(&self, key: K) -> impl Iterator + '_ { + let lower_bound = self.idx_sorted_by_item_key.partition_point(|&i| self.items[i].0 < key); + self.idx_sorted_by_item_key[lower_bound..].iter().map_while(move |&i| { + let (k, v) = &self.items[i]; + (k == &key).then_some((i, v)) + }) + } +} + +impl Eq for SortedIndexMultiMap {} +impl PartialEq for SortedIndexMultiMap { + fn eq(&self, other: &Self) -> bool { + // No need to compare the sorted index. If the items are the same, the index will be too. + self.items == other.items + } +} + +impl Hash for SortedIndexMultiMap +where + K: Hash, + V: Hash, +{ + fn hash(&self, hasher: &mut H) { + self.items.hash(hasher) + } +} +impl HashStable for SortedIndexMultiMap +where + K: HashStable, + V: HashStable, +{ + fn hash_stable(&self, ctx: &mut C, hasher: &mut StableHasher) { + self.items.hash_stable(ctx, hasher) + } +} + +impl FromIterator<(K, V)> for SortedIndexMultiMap { + fn from_iter(iter: J) -> Self + where + J: IntoIterator, + { + let items = IndexVec::from_iter(iter); + let mut idx_sorted_by_item_key: Vec<_> = items.indices().collect(); + + // `sort_by_key` is stable, so insertion order is preserved for duplicate items. + idx_sorted_by_item_key.sort_by_key(|&idx| &items[idx].0); + + SortedIndexMultiMap { items, idx_sorted_by_item_key } + } +} + +impl std::ops::Index for SortedIndexMultiMap { + type Output = V; + + fn index(&self, idx: I) -> &Self::Output { + &self.items[idx].1 + } +} -- cgit v1.2.3