From 5c224a484dc6ba2a70c9cd0d73a04849f6d7aa68 Mon Sep 17 00:00:00 2001 From: Valerii Lashmanov Date: Wed, 23 Sep 2020 23:32:11 -0500 Subject: MiniSet/MiniMap moved and renamed into SsoHashSet/SsoHashMap It is a more descriptive name and with upcoming changes there will be nothing "mini" about them. --- compiler/rustc_data_structures/src/lib.rs | 3 +- compiler/rustc_data_structures/src/mini_map.rs | 61 -------------------------- compiler/rustc_data_structures/src/mini_set.rs | 41 ----------------- compiler/rustc_data_structures/src/sso/map.rs | 61 ++++++++++++++++++++++++++ compiler/rustc_data_structures/src/sso/mod.rs | 5 +++ compiler/rustc_data_structures/src/sso/set.rs | 41 +++++++++++++++++ 6 files changed, 108 insertions(+), 104 deletions(-) delete mode 100644 compiler/rustc_data_structures/src/mini_map.rs delete mode 100644 compiler/rustc_data_structures/src/mini_set.rs create mode 100644 compiler/rustc_data_structures/src/sso/map.rs create mode 100644 compiler/rustc_data_structures/src/sso/mod.rs create mode 100644 compiler/rustc_data_structures/src/sso/set.rs (limited to 'compiler/rustc_data_structures') diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index 9ded10e9c26..d0f2a4148d3 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -101,8 +101,7 @@ pub mod vec_linked_list; pub mod work_queue; pub use atomic_ref::AtomicRef; pub mod frozen; -pub mod mini_map; -pub mod mini_set; +pub mod sso; pub mod tagged_ptr; pub mod temp_dir; pub mod unhash; diff --git a/compiler/rustc_data_structures/src/mini_map.rs b/compiler/rustc_data_structures/src/mini_map.rs deleted file mode 100644 index cd3e949d383..00000000000 --- a/compiler/rustc_data_structures/src/mini_map.rs +++ /dev/null @@ -1,61 +0,0 @@ -use crate::fx::FxHashMap; -use arrayvec::ArrayVec; - -use std::hash::Hash; - -/// Small-storage-optimized implementation of a map -/// made specifically for caching results. -/// -/// Stores elements in a small array up to a certain length -/// and switches to `HashMap` when that length is exceeded. -pub enum MiniMap { - Array(ArrayVec<[(K, V); 8]>), - Map(FxHashMap), -} - -impl MiniMap { - /// Creates an empty `MiniMap`. - pub fn new() -> Self { - MiniMap::Array(ArrayVec::new()) - } - - /// Inserts or updates value in the map. - pub fn insert(&mut self, key: K, value: V) { - match self { - MiniMap::Array(array) => { - for pair in array.iter_mut() { - if pair.0 == key { - pair.1 = value; - return; - } - } - if let Err(error) = array.try_push((key, value)) { - let mut map: FxHashMap = array.drain(..).collect(); - let (key, value) = error.element(); - map.insert(key, value); - *self = MiniMap::Map(map); - } - } - MiniMap::Map(map) => { - map.insert(key, value); - } - } - } - - /// Return value by key if any. - pub fn get(&self, key: &K) -> Option<&V> { - match self { - MiniMap::Array(array) => { - for pair in array { - if pair.0 == *key { - return Some(&pair.1); - } - } - return None; - } - MiniMap::Map(map) => { - return map.get(key); - } - } - } -} diff --git a/compiler/rustc_data_structures/src/mini_set.rs b/compiler/rustc_data_structures/src/mini_set.rs deleted file mode 100644 index 9d45af723de..00000000000 --- a/compiler/rustc_data_structures/src/mini_set.rs +++ /dev/null @@ -1,41 +0,0 @@ -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 { - Array(ArrayVec<[T; 8]>), - Set(FxHashSet), -} - -impl MiniSet { - /// 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 = array.drain(..).collect(); - set.insert(error.element()); - *self = MiniSet::Set(set); - } - true - } - } - MiniSet::Set(set) => set.insert(elem), - } - } -} diff --git a/compiler/rustc_data_structures/src/sso/map.rs b/compiler/rustc_data_structures/src/sso/map.rs new file mode 100644 index 00000000000..c253e9d6616 --- /dev/null +++ b/compiler/rustc_data_structures/src/sso/map.rs @@ -0,0 +1,61 @@ +use crate::fx::FxHashMap; +use arrayvec::ArrayVec; + +use std::hash::Hash; + +/// Small-storage-optimized implementation of a map +/// made specifically for caching results. +/// +/// Stores elements in a small array up to a certain length +/// and switches to `HashMap` when that length is exceeded. +pub enum SsoHashMap { + Array(ArrayVec<[(K, V); 8]>), + Map(FxHashMap), +} + +impl SsoHashMap { + /// Creates an empty `SsoHashMap`. + pub fn new() -> Self { + SsoHashMap::Array(ArrayVec::new()) + } + + /// Inserts or updates value in the map. + pub fn insert(&mut self, key: K, value: V) { + match self { + SsoHashMap::Array(array) => { + for pair in array.iter_mut() { + if pair.0 == key { + pair.1 = value; + return; + } + } + if let Err(error) = array.try_push((key, value)) { + let mut map: FxHashMap = array.drain(..).collect(); + let (key, value) = error.element(); + map.insert(key, value); + *self = SsoHashMap::Map(map); + } + } + SsoHashMap::Map(map) => { + map.insert(key, value); + } + } + } + + /// Return value by key if any. + pub fn get(&self, key: &K) -> Option<&V> { + match self { + SsoHashMap::Array(array) => { + for pair in array { + if pair.0 == *key { + return Some(&pair.1); + } + } + return None; + } + SsoHashMap::Map(map) => { + return map.get(key); + } + } + } +} diff --git a/compiler/rustc_data_structures/src/sso/mod.rs b/compiler/rustc_data_structures/src/sso/mod.rs new file mode 100644 index 00000000000..ef634b9adce --- /dev/null +++ b/compiler/rustc_data_structures/src/sso/mod.rs @@ -0,0 +1,5 @@ +mod map; +mod set; + +pub use map::SsoHashMap; +pub use set::SsoHashSet; diff --git a/compiler/rustc_data_structures/src/sso/set.rs b/compiler/rustc_data_structures/src/sso/set.rs new file mode 100644 index 00000000000..b403c9dcc33 --- /dev/null +++ b/compiler/rustc_data_structures/src/sso/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 SsoHashSet { + Array(ArrayVec<[T; 8]>), + Set(FxHashSet), +} + +impl SsoHashSet { + /// Creates an empty `SsoHashSet`. + pub fn new() -> Self { + SsoHashSet::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 { + SsoHashSet::Array(array) => { + if array.iter().any(|e| *e == elem) { + false + } else { + if let Err(error) = array.try_push(elem) { + let mut set: FxHashSet = array.drain(..).collect(); + set.insert(error.element()); + *self = SsoHashSet::Set(set); + } + true + } + } + SsoHashSet::Set(set) => set.insert(elem), + } + } +} -- cgit 1.4.1-3-g733a5