flurry 0.5.2

//! A concurrent hash set.
//!
//! See `HashSet` for details.

use crate::iter::Keys;
use crate::reclaim::Guard;
use crate::HashMap;
use std::borrow::Borrow;
use std::fmt::{self, Debug, Formatter};
use std::hash::{BuildHasher, Hash};

/// A concurrent hash set implemented as a `HashMap` where the value is `()`.
///
/// # Examples
///
/// ```
/// use flurry::HashSet;
///
/// // Initialize a new hash set.
/// let books = HashSet::new();
/// let guard = books.guard();
///
/// // Add some books
/// books.insert("Fight Club", &guard);
/// books.insert("Three Men In A Raft", &guard);
/// books.insert("The Book of Dust", &guard);
/// books.insert("The Dry", &guard);
///
/// // Check for a specific one.
/// if !books.contains(&"The Drunken Botanist", &guard) {
///     println!("We don't have The Drunken Botanist.");
/// }
///
/// // Remove a book.
/// books.remove(&"Three Men In A Raft", &guard);
///
/// // Iterate over everything.
/// for book in books.iter(&guard) {
///     println!("{}", book);
/// }
/// ```
pub struct HashSet<T, S = crate::DefaultHashBuilder> {
    pub(crate) map: HashMap<T, (), S>,
}

impl<T> HashSet<T, crate::DefaultHashBuilder> {
    /// Creates an empty `HashSet`.
    ///
    /// The hash set is initially created with a capacity of 0, so it will not allocate until it
    /// is first inserted into.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    /// let set: HashSet<i32> = HashSet::new();
    /// ```
    pub fn new() -> Self {
        Self::default()
    }

    /// Creates an empty `HashSet` with the specified capacity.
    ///
    /// The hash map will be able to hold at least `capacity` elements without
    /// reallocating. If `capacity` is 0, the hash map will not allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    /// let map: HashSet<&str, _> = HashSet::with_capacity(10);
    /// ```
    ///
    /// # Notes
    ///
    /// There is no guarantee that the HashSet will not resize if `capacity`
    /// elements are inserted. The set will resize based on key collision, so
    /// bad key distribution may cause a resize before `capacity` is reached.
    /// For more information see the [`resizing behavior`] of HashMap.
    ///
    /// [`resizing behavior`]: index.html#resizing-behavior
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_and_hasher(capacity, crate::DefaultHashBuilder::default())
    }
}

impl<T, S> Default for HashSet<T, S>
where
    S: Default,
{
    fn default() -> Self {
        Self::with_hasher(S::default())
    }
}

impl<T, S> HashSet<T, S> {
    /// Creates an empty set which will use `hash_builder` to hash values.
    ///
    /// The created set has the default initial capacity.
    ///
    /// Warning: `hash_builder` is normally randomly generated, and is designed to
    /// allow the set to be resistant to attacks that cause many collisions and
    /// very poor performance. Setting it manually using this
    /// function can expose a DoS attack vector.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::{HashSet, DefaultHashBuilder};
    ///
    /// let set = HashSet::with_hasher(DefaultHashBuilder::default());
    /// let guard = set.guard();
    /// set.insert(1, &guard);
    /// ```
    pub fn with_hasher(hash_builder: S) -> Self {
        Self {
            map: HashMap::with_hasher(hash_builder),
        }
    }

    /// Creates an empty set with the specified `capacity`, using `hash_builder` to hash the
    /// values.
    ///
    /// The set will be sized to accommodate `capacity` elements with a low chance of reallocating
    /// (assuming uniformly distributed hashes). If `capacity` is 0, the call will not allocate,
    /// and is equivalent to [`HashSet::new`].
    ///
    /// Warning: `hash_builder` is normally randomly generated, and is designed to allow the set
    /// to be resistant to attacks that cause many collisions and very poor performance.
    /// Setting it manually using this function can expose a DoS attack vector.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    /// use std::collections::hash_map::RandomState;
    ///
    /// let s = RandomState::new();
    /// let set = HashSet::with_capacity_and_hasher(10, s);
    /// let guard = set.guard();
    /// set.insert(1, &guard);
    /// ```
    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
        Self {
            map: HashMap::with_capacity_and_hasher(capacity, hash_builder),
        }
    }

    /// Pin a `Guard` for use with this set.
    ///
    /// Keep in mind that for as long as you hold onto this `Guard`, you are preventing the
    /// collection of garbage generated by the set.
    pub fn guard(&self) -> Guard<'_> {
        self.map.guard()
    }

    /// Returns the number of elements in the set.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    ///
    /// let guard = set.guard();
    /// set.insert(1, &guard);
    /// set.insert(2, &guard);
    /// assert_eq!(set.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns `true` if the set is empty. Otherwise returns `false`.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    /// assert!(set.is_empty());
    /// set.insert("a", &set.guard());
    /// assert!(!set.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// An iterator visiting all elements in arbitrary order.
    ///
    /// The iterator element type is `&'g T`.
    ///
    /// See [`HashMap::keys`] for details.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    /// let guard = set.guard();
    /// set.insert(1, &guard);
    /// set.insert(2, &guard);
    ///
    /// for x in set.iter(&guard) {
    ///     println!("{}", x);
    /// }
    /// ```
    pub fn iter<'g>(&'g self, guard: &'g Guard<'_>) -> Keys<'g, T, ()> {
        self.map.keys(guard)
    }
}

impl<T, S> HashSet<T, S>
where
    T: Hash + Ord,
    S: BuildHasher,
{
    /// Returns `true` if the given value is an element of this set.
    ///
    /// The value may be any borrowed form of the set's value type, but
    /// [`Hash`] and [`Ord`] on the borrowed form *must* match those for
    /// the value type.
    ///
    /// [`Ord`]: std::cmp::Ord
    /// [`Hash`]: std::hash::Hash
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    /// let guard = set.guard();
    /// set.insert(2, &guard);
    ///
    /// assert!(set.contains(&2, &guard));
    /// assert!(!set.contains(&1, &guard));
    /// ```
    #[inline]
    pub fn contains<Q>(&self, value: &Q, guard: &Guard<'_>) -> bool
    where
        T: Borrow<Q>,
        Q: ?Sized + Hash + Ord,
    {
        self.map.contains_key(value, guard)
    }

    /// Returns a reference to the element in the set, if any, that is equal to the given value.
    ///
    /// The value may be any borrowed form of the set's value type, but
    /// [`Hash`] and [`Ord`] on the borrowed form *must* match those for
    /// the value type.
    ///
    /// [`Ord`]: std::cmp::Ord
    /// [`Hash`]: std::hash::Hash
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    /// let guard = set.guard();
    /// assert_eq!(set.get(&2, &guard), Some(&2));
    /// assert_eq!(set.get(&4, &guard), None);
    /// ```
    pub fn get<'g, Q>(&'g self, value: &Q, guard: &'g Guard<'_>) -> Option<&'g T>
    where
        T: Borrow<Q>,
        Q: ?Sized + Hash + Ord,
    {
        self.map.get_key_value(value, guard).map(|(k, _)| k)
    }

    /// Returns `true` if `self` has no elements in common with `other`.
    ///
    /// This is equivalent to checking for an empty intersection.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::iter::FromIterator;
    /// use flurry::HashSet;
    ///
    /// let a = HashSet::from_iter(&[1, 2, 3]);
    /// let b = HashSet::new();
    ///
    /// assert!(a.pin().is_disjoint(&b.pin()));
    /// b.pin().insert(4);
    /// assert!(a.pin().is_disjoint(&b.pin()));
    /// b.pin().insert(1);
    /// assert!(!a.pin().is_disjoint(&b.pin()));
    ///
    /// ```
    pub fn is_disjoint(
        &self,
        other: &HashSet<T, S>,
        our_guard: &Guard<'_>,
        their_guard: &Guard<'_>,
    ) -> bool {
        for value in self.iter(our_guard) {
            if other.contains(value, their_guard) {
                return false;
            }
        }

        true
    }

    /// Returns `true` if the set is a subset of another, i.e., `other` contains at least all the values in `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::iter::FromIterator;
    /// use flurry::HashSet;
    ///
    /// let sup = HashSet::from_iter(&[1, 2, 3]);
    /// let set = HashSet::new();
    ///
    /// assert!(set.pin().is_subset(&sup.pin()));
    /// set.pin().insert(2);
    /// assert!(set.pin().is_subset(&sup.pin()));
    /// set.pin().insert(4);
    /// assert!(!set.pin().is_subset(&sup.pin()));
    /// ```
    pub fn is_subset(
        &self,
        other: &HashSet<T, S>,
        our_guard: &Guard<'_>,
        their_guard: &Guard<'_>,
    ) -> bool {
        for value in self.iter(our_guard) {
            if !other.contains(value, their_guard) {
                return false;
            }
        }

        true
    }

    /// Returns `true` if the set is a superset of another, i.e., `self` contains at least all the values in `other`.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::iter::FromIterator;
    /// use flurry::HashSet;
    ///
    /// let sub = HashSet::from_iter(&[1, 2]);
    /// let set = HashSet::new();
    ///
    /// assert!(!set.pin().is_superset(&sub.pin()));
    ///
    /// set.pin().insert(0);
    /// set.pin().insert(1);
    /// assert!(!set.pin().is_superset(&sub.pin()));
    ///
    /// set.pin().insert(2);
    /// assert!(set.pin().is_superset(&sub.pin()));
    /// ```
    pub fn is_superset(
        &self,
        other: &HashSet<T, S>,
        our_guard: &Guard<'_>,
        their_guard: &Guard<'_>,
    ) -> bool {
        other.is_subset(self, their_guard, our_guard)
    }

    pub(crate) fn guarded_eq(
        &self,
        other: &Self,
        our_guard: &Guard<'_>,
        their_guard: &Guard<'_>,
    ) -> bool {
        self.map.guarded_eq(&other.map, our_guard, their_guard)
    }
}

impl<T, S> HashSet<T, S>
where
    T: Sync + Send + Clone + Hash + Ord,
    S: BuildHasher,
{
    /// 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.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    /// let guard = set.guard();
    ///
    /// assert_eq!(set.insert(2, &guard), true);
    /// assert_eq!(set.insert(2, &guard), false);
    /// assert!(set.contains(&2, &guard));
    /// ```
    pub fn insert(&self, value: T, guard: &Guard<'_>) -> bool {
        let old = self.map.insert(value, (), guard);
        old.is_none()
    }

    /// Removes a value from the set.
    ///
    /// If the set did not have this value present, `false` is returned.
    ///
    /// If the set did have this value present, `true` is returned.
    ///
    /// The value may be any borrowed form of the set's value type, but
    /// [`Hash`] and [`Ord`] on the borrowed form *must* match those for
    /// the value type.
    ///
    /// [`Ord`]: std::cmp::Ord
    /// [`Hash`]: std::hash::Hash
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    /// let guard = set.guard();
    /// set.insert(2, &guard);
    ///
    /// assert_eq!(set.remove(&2, &guard), true);
    /// assert!(!set.contains(&2, &guard));
    /// assert_eq!(set.remove(&2, &guard), false);
    /// ```
    pub fn remove<Q>(&self, value: &Q, guard: &Guard<'_>) -> bool
    where
        T: Borrow<Q>,
        Q: ?Sized + Hash + Ord,
    {
        let removed = self.map.remove(value, guard);
        removed.is_some()
    }

    /// Removes and returns the value in the set, if any, that is equal to the given one.
    ///
    /// The value may be any borrowed form of the set's value type, but
    /// [`Hash`] and [`Ord`] on the borrowed form *must* match those for
    /// the value type.
    ///
    /// [`Ord`]: std::cmp::Ord
    /// [`Hash`]: std::hash::Hash
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    /// let guard = set.guard();
    /// assert_eq!(set.take(&2, &guard), Some(&2));
    /// assert_eq!(set.take(&2, &guard), None);
    /// ```
    pub fn take<'g, Q>(&'g self, value: &Q, guard: &'g Guard<'_>) -> Option<&'g T>
    where
        T: Borrow<Q>,
        Q: ?Sized + Hash + Ord,
    {
        self.map.remove_entry(value, guard).map(|(k, _)| k)
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    ///
    /// for i in 0..8 {
    ///     set.pin().insert(i);
    /// }
    /// set.pin().retain(|&e| e % 2 == 0);
    /// assert_eq!(set.pin().len(), 4);
    /// ```
    pub fn retain<F>(&self, mut f: F, guard: &Guard<'_>)
    where
        F: FnMut(&T) -> bool,
    {
        self.map.retain(|value, ()| f(value), guard)
    }
}

impl<T, S> HashSet<T, S>
where
    T: Clone + Ord,
{
    /// Clears the set, removing all elements.
    ///
    /// # Examples
    ///
    /// ```
    /// use flurry::HashSet;
    ///
    /// let set = HashSet::new();
    ///
    /// set.pin().insert("a");
    /// set.pin().clear();
    /// assert!(set.pin().is_empty());
    /// ```
    pub fn clear(&self, guard: &Guard<'_>) {
        self.map.clear(guard)
    }

    /// Tries to reserve capacity for at least `additional` more elements to
    /// be inserted in the `HashSet`.
    ///
    /// The collection may reserve more space to avoid frequent reallocations.
    pub fn reserve(&self, additional: usize, guard: &Guard<'_>) {
        self.map.reserve(additional, guard)
    }
}

impl<T, S> PartialEq for HashSet<T, S>
where
    T: Ord + Hash,
    S: BuildHasher,
{
    fn eq(&self, other: &Self) -> bool {
        self.map == other.map
    }
}

impl<T, S> Eq for HashSet<T, S>
where
    T: Ord + Hash,
    S: BuildHasher,
{
}

impl<T, S> fmt::Debug for HashSet<T, S>
where
    T: Debug,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        let guard = self.guard();
        f.debug_set().entries(self.iter(&guard)).finish()
    }
}

impl<T, S> Extend<T> for &HashSet<T, S>
where
    T: Sync + Send + Clone + Hash + Ord,
    S: BuildHasher,
{
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        Extend::extend(&mut &self.map, iter.into_iter().map(|v| (v, ())))
    }
}

impl<'a, T, S> Extend<&'a T> for &HashSet<T, S>
where
    T: Sync + Send + Copy + Hash + Ord,
    S: BuildHasher,
{
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        Extend::extend(&mut &self.map, iter.into_iter().map(|&v| (v, ())))
    }
}

impl<T, S> FromIterator<T> for HashSet<T, S>
where
    T: Sync + Send + Clone + Hash + Ord,
    S: BuildHasher + Default,
{
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Self {
            map: iter.into_iter().map(|v| (v, ())).collect(),
        }
    }
}

impl<'a, T, S> FromIterator<&'a T> for HashSet<T, S>
where
    T: Sync + Send + Copy + Hash + Ord,
    S: BuildHasher + Default,
{
    fn from_iter<I: IntoIterator<Item = &'a T>>(iter: I) -> Self {
        Self {
            map: iter.into_iter().map(|&v| (v, ())).collect(),
        }
    }
}

impl<T, S> Clone for HashSet<T, S>
where
    T: Sync + Send + Clone + Hash + Ord,
    S: BuildHasher + Clone,
{
    fn clone(&self) -> HashSet<T, S> {
        Self {
            map: self.map.clone(),
        }
    }
}