diff options
Diffstat (limited to 'src/set.rs')
| -rw-r--r-- | src/set.rs | 458 |
1 files changed, 458 insertions, 0 deletions
diff --git a/src/set.rs b/src/set.rs new file mode 100644 index 0000000..1a56177 --- /dev/null +++ b/src/set.rs @@ -0,0 +1,458 @@ +use crate::iter_set::{Iter, OwningIter}; +#[cfg(feature = "raw-api")] +use crate::lock::RwLock; +use crate::setref::one::Ref; +use crate::DashMap; +#[cfg(feature = "raw-api")] +use crate::HashMap; +use cfg_if::cfg_if; +use core::borrow::Borrow; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::iter::FromIterator; +use std::collections::hash_map::RandomState; + +/// DashSet is a thin wrapper around [`DashMap`] using `()` as the value type. It uses +/// methods and types which are more convenient to work with on a set. +/// +/// [`DashMap`]: struct.DashMap.html +pub struct DashSet<K, S = RandomState> { + pub(crate) inner: DashMap<K, (), S>, +} + +impl<K: Eq + Hash + fmt::Debug, S: BuildHasher + Clone> fmt::Debug for DashSet<K, S> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.inner, f) + } +} + +impl<K: Eq + Hash + Clone, S: Clone> Clone for DashSet<K, S> { + fn clone(&self) -> Self { + Self { + inner: self.inner.clone(), + } + } + + fn clone_from(&mut self, source: &Self) { + self.inner.clone_from(&source.inner) + } +} + +impl<K, S> Default for DashSet<K, S> +where + K: Eq + Hash, + S: Default + BuildHasher + Clone, +{ + fn default() -> Self { + Self::with_hasher(Default::default()) + } +} + +impl<'a, K: 'a + Eq + Hash> DashSet<K, RandomState> { + /// Creates a new DashSet with a capacity of 0. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let games = DashSet::new(); + /// games.insert("Veloren"); + /// ``` + pub fn new() -> Self { + Self::with_hasher(RandomState::default()) + } + + /// Creates a new DashMap with a specified starting capacity. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let numbers = DashSet::with_capacity(2); + /// numbers.insert(2); + /// numbers.insert(8); + /// ``` + pub fn with_capacity(capacity: usize) -> Self { + Self::with_capacity_and_hasher(capacity, RandomState::default()) + } +} + +impl<'a, K: 'a + Eq + Hash, S: BuildHasher + Clone> DashSet<K, S> { + /// Creates a new DashMap with a capacity of 0 and the provided hasher. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let games = DashSet::with_hasher(s); + /// games.insert("Veloren"); + /// ``` + pub fn with_hasher(hasher: S) -> Self { + Self::with_capacity_and_hasher(0, hasher) + } + + /// Creates a new DashMap with a specified starting capacity and hasher. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let numbers = DashSet::with_capacity_and_hasher(2, s); + /// numbers.insert(2); + /// numbers.insert(8); + /// ``` + pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self { + Self { + inner: DashMap::with_capacity_and_hasher(capacity, hasher), + } + } + + /// Hash a given item to produce a usize. + /// Uses the provided or default HashBuilder. + pub fn hash_usize<T: Hash>(&self, item: &T) -> usize { + self.inner.hash_usize(item) + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Allows you to peek at the inner shards that store your data. + /// You should probably not use this unless you know what you are doing. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set = DashSet::<()>::new(); + /// println!("Amount of shards: {}", set.shards().len()); + /// ``` + pub fn shards(&self) -> &[RwLock<HashMap<K, (), S>>] { + self.inner.shards() + } + } + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Finds which shard a certain key is stored in. + /// You should probably not use this unless you know what you are doing. + /// Note that shard selection is dependent on the default or provided HashBuilder. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set = DashSet::new(); + /// set.insert("coca-cola"); + /// println!("coca-cola is stored in shard: {}", set.determine_map("coca-cola")); + /// ``` + pub fn determine_map<Q>(&self, key: &Q) -> usize + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.determine_map(key) + } + } + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Finds which shard a certain hash is stored in. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set: DashSet<i32> = DashSet::new(); + /// let key = "key"; + /// let hash = set.hash_usize(&key); + /// println!("hash is stored in shard: {}", set.determine_shard(hash)); + /// ``` + pub fn determine_shard(&self, hash: usize) -> usize { + self.inner.determine_shard(hash) + } + } + } + + /// Inserts a key into the set. Returns true if the key was not already in the set. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set = DashSet::new(); + /// set.insert("I am the key!"); + /// ``` + pub fn insert(&self, key: K) -> bool { + self.inner.insert(key, ()).is_none() + } + + /// Removes an entry from the map, returning the key if it existed in the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let soccer_team = DashSet::new(); + /// soccer_team.insert("Jack"); + /// assert_eq!(soccer_team.remove("Jack").unwrap(), "Jack"); + /// ``` + pub fn remove<Q>(&self, key: &Q) -> Option<K> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.remove(key).map(|(k, _)| k) + } + + /// Removes an entry from the set, returning the key + /// if the entry existed and the provided conditional function returned true. + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let soccer_team = DashSet::new(); + /// soccer_team.insert("Sam"); + /// soccer_team.remove_if("Sam", |player| player.starts_with("Ja")); + /// assert!(soccer_team.contains("Sam")); + /// ``` + /// ``` + /// use dashmap::DashSet; + /// + /// let soccer_team = DashSet::new(); + /// soccer_team.insert("Sam"); + /// soccer_team.remove_if("Jacob", |player| player.starts_with("Ja")); + /// assert!(!soccer_team.contains("Jacob")); + /// ``` + pub fn remove_if<Q>(&self, key: &Q, f: impl FnOnce(&K) -> bool) -> Option<K> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + // TODO: Don't create another closure around f + self.inner.remove_if(key, |k, _| f(k)).map(|(k, _)| k) + } + + /// Creates an iterator over a DashMap yielding immutable references. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let words = DashSet::new(); + /// words.insert("hello"); + /// assert_eq!(words.iter().count(), 1); + /// ``` + pub fn iter(&'a self) -> Iter<'a, K, S, DashMap<K, (), S>> { + let iter = self.inner.iter(); + + Iter::new(iter) + } + + /// Get a reference to an entry in the set + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let youtubers = DashSet::new(); + /// youtubers.insert("Bosnian Bill"); + /// assert_eq!(*youtubers.get("Bosnian Bill").unwrap(), "Bosnian Bill"); + /// ``` + pub fn get<Q>(&'a self, key: &Q) -> Option<Ref<'a, K, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.get(key).map(Ref::new) + } + + /// Remove excess capacity to reduce memory usage. + pub fn shrink_to_fit(&self) { + self.inner.shrink_to_fit() + } + + /// Retain elements that whose predicates return true + /// and discard elements whose predicates return false. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Albin"); + /// people.insert("Jones"); + /// people.insert("Charlie"); + /// people.retain(|name| name.contains('i')); + /// assert_eq!(people.len(), 2); + /// ``` + pub fn retain(&self, mut f: impl FnMut(&K) -> bool) { + self.inner.retain(|k, _| f(k)) + } + + /// Fetches the total number of keys stored in the set. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Albin"); + /// people.insert("Jones"); + /// people.insert("Charlie"); + /// assert_eq!(people.len(), 3); + /// ``` + pub fn len(&self) -> usize { + self.inner.len() + } + + /// Checks if the set is empty or not. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let map = DashSet::<()>::new(); + /// assert!(map.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self.inner.is_empty() + } + + /// Removes all keys in the set. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Albin"); + /// assert!(!people.is_empty()); + /// people.clear(); + /// assert!(people.is_empty()); + /// ``` + pub fn clear(&self) { + self.inner.clear() + } + + /// Returns how many keys the set can store without reallocating. + pub fn capacity(&self) -> usize { + self.inner.capacity() + } + + /// Checks if the set contains a specific key. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Dakota Cherries"); + /// assert!(people.contains("Dakota Cherries")); + /// ``` + pub fn contains<Q>(&self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.contains_key(key) + } +} + +impl<K: Eq + Hash, S: BuildHasher + Clone> IntoIterator for DashSet<K, S> { + type Item = K; + + type IntoIter = OwningIter<K, S>; + + fn into_iter(self) -> Self::IntoIter { + OwningIter::new(self.inner.into_iter()) + } +} + +impl<K: Eq + Hash, S: BuildHasher + Clone> Extend<K> for DashSet<K, S> { + fn extend<T: IntoIterator<Item = K>>(&mut self, iter: T) { + let iter = iter.into_iter().map(|k| (k, ())); + + self.inner.extend(iter) + } +} + +impl<K: Eq + Hash, S: BuildHasher + Clone + Default> FromIterator<K> for DashSet<K, S> { + fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self { + let mut set = DashSet::default(); + + set.extend(iter); + + set + } +} + +#[cfg(test)] +mod tests { + use crate::DashSet; + + #[test] + fn test_basic() { + let set = DashSet::new(); + + set.insert(0); + + assert_eq!(set.get(&0).as_deref(), Some(&0)); + } + + #[test] + fn test_default() { + let set: DashSet<u32> = DashSet::default(); + + set.insert(0); + + assert_eq!(set.get(&0).as_deref(), Some(&0)); + } + + #[test] + fn test_multiple_hashes() { + let set = DashSet::<u32>::default(); + + for i in 0..100 { + assert!(set.insert(i)); + } + + for i in 0..100 { + assert!(!set.insert(i)); + } + + for i in 0..100 { + assert_eq!(Some(i), set.remove(&i)); + } + + for i in 0..100 { + assert_eq!(None, set.remove(&i)); + } + } +} |