Auto merge of #90145 - cjgillot:sorted-map, r=michaelwoerister

Use SortedMap in HIR.

Closes https://github.com/rust-lang/rust/issues/89788
r? `@ghost`

1 files changed, 22 insertions, 5 deletions

diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs
index 20e2a3b9696..9efea1228ab 100644
--- a/compiler/rustc_data_structures/src/sorted_map.rs
+++ b/compiler/rustc_data_structures/src/sorted_map.rs
@@ -1,3 +1,4 @@
+use crate::stable_hasher::{HashStable, StableHasher};
 use std::borrow::Borrow;
 use std::cmp::Ordering;
 use std::iter::FromIterator;
@@ -16,17 +17,26 @@ pub use index_map::SortedIndexMultiMap;
 /// stores data in a more compact way. It also supports accessing contiguous
 /// ranges of elements as a slice, and slices of already sorted elements can be
 /// inserted efficiently.
-#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug, Encodable, Decodable)]
-pub struct SortedMap<K: Ord, V> {
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Encodable, Decodable)]
+pub struct SortedMap<K, V> {
     data: Vec<(K, V)>,
 }
 
-impl<K: Ord, V> SortedMap<K, V> {
+impl<K, V> Default for SortedMap<K, V> {
+    #[inline]
+    fn default() -> SortedMap<K, V> {
+        SortedMap { data: Vec::new() }
+    }
+}
+
+impl<K, V> SortedMap<K, V> {
     #[inline]
-    pub fn new() -> SortedMap<K, V> {
-        SortedMap { data: vec![] }
+    pub const fn new() -> SortedMap<K, V> {
+        SortedMap { data: Vec::new() }
     }
+}
 
+impl<K: Ord, V> SortedMap<K, V> {
     /// Construct a `SortedMap` from a presorted set of elements. This is faster
     /// than creating an empty map and then inserting the elements individually.
     ///
@@ -281,5 +291,12 @@ impl<K: Ord, V> FromIterator<(K, V)> for SortedMap<K, V> {
     }
 }
 
+impl<K: HashStable<CTX>, V: HashStable<CTX>, CTX> HashStable<CTX> for SortedMap<K, V> {
+    #[inline]
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        self.data.hash_stable(ctx, hasher);
+    }
+}
+
 #[cfg(test)]
 mod tests;