Auto merge of #77028 - andjo403:mini, r=matthewjasper

Move MiniSet to data_structures

remove the need for T to be copy from MiniSet as was done for MiniMap

MiniMap and MiniSet was added by https://github.com/rust-lang/rust/pull/72412

think that this can be used in https://github.com/rust-lang/rust/pull/68828

2 files changed, 42 insertions, 0 deletions

diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index 1f977805f5e..5990e94ab7e 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -102,6 +102,7 @@ pub mod work_queue;
 pub use atomic_ref::AtomicRef;
 pub mod frozen;
 pub mod mini_map;
+pub mod mini_set;
 pub mod tagged_ptr;
 pub mod temp_dir;
 pub mod unhash;
diff --git a/compiler/rustc_data_structures/src/mini_set.rs b/compiler/rustc_data_structures/src/mini_set.rs
new file mode 100644
index 00000000000..9d45af723de
--- /dev/null
+++ b/compiler/rustc_data_structures/src/mini_set.rs
@@ -0,0 +1,41 @@
+use crate::fx::FxHashSet;
+use arrayvec::ArrayVec;
+use std::hash::Hash;
+/// Small-storage-optimized implementation of a set.
+///
+/// Stores elements in a small array up to a certain length
+/// and switches to `HashSet` when that length is exceeded.
+pub enum MiniSet<T> {
+    Array(ArrayVec<[T; 8]>),
+    Set(FxHashSet<T>),
+}
+
+impl<T: Eq + Hash> MiniSet<T> {
+    /// Creates an empty `MiniSet`.
+    pub fn new() -> Self {
+        MiniSet::Array(ArrayVec::new())
+    }
+
+    /// Adds a value to the set.
+    ///
+    /// If the set did not have this value present, true is returned.
+    ///
+    /// If the set did have this value present, false is returned.
+    pub fn insert(&mut self, elem: T) -> bool {
+        match self {
+            MiniSet::Array(array) => {
+                if array.iter().any(|e| *e == elem) {
+                    false
+                } else {
+                    if let Err(error) = array.try_push(elem) {
+                        let mut set: FxHashSet<T> = array.drain(..).collect();
+                        set.insert(error.element());
+                        *self = MiniSet::Set(set);
+                    }
+                    true
+                }
+            }
+            MiniSet::Set(set) => set.insert(elem),
+        }
+    }
+}