diff options
| author | mo khan <mo@mokhan.ca> | 2025-07-15 16:37:08 -0600 |
|---|---|---|
| committer | mo khan <mo@mokhan.ca> | 2025-07-17 16:30:22 -0600 |
| commit | 45df4d0d9b577fecee798d672695fe24ff57fb1b (patch) | |
| tree | 1b99bf645035b58e0d6db08c7a83521f41f7a75b /vendor/indexmap/src/rayon | |
| parent | f94f79608393d4ab127db63cc41668445ef6b243 (diff) | |
feat: migrate from Cedar to SpiceDB authorization system
This is a major architectural change that replaces the Cedar policy-based
authorization system with SpiceDB's relation-based authorization.
Key changes:
- Migrate from Rust to Go implementation
- Replace Cedar policies with SpiceDB schema and relationships
- Switch from envoy `ext_authz` with Cedar to SpiceDB permission checks
- Update build system and dependencies for Go ecosystem
- Maintain Envoy integration for external authorization
This change enables more flexible permission modeling through SpiceDB's
Google Zanzibar inspired relation-based system, supporting complex
hierarchical permissions that were difficult to express in Cedar.
Breaking change: Existing Cedar policies and Rust-based configuration
will no longer work and need to be migrated to SpiceDB schema.
Diffstat (limited to 'vendor/indexmap/src/rayon')
| -rw-r--r-- | vendor/indexmap/src/rayon/map.rs | 663 | ||||
| -rw-r--r-- | vendor/indexmap/src/rayon/mod.rs | 16 | ||||
| -rw-r--r-- | vendor/indexmap/src/rayon/set.rs | 756 |
3 files changed, 0 insertions, 1435 deletions
diff --git a/vendor/indexmap/src/rayon/map.rs b/vendor/indexmap/src/rayon/map.rs deleted file mode 100644 index 8236cf70..00000000 --- a/vendor/indexmap/src/rayon/map.rs +++ /dev/null @@ -1,663 +0,0 @@ -//! Parallel iterator types for [`IndexMap`] with [`rayon`][::rayon]. -//! -//! You will rarely need to interact with this module directly unless you need to name one of the -//! iterator types. - -use super::collect; -use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; -use rayon::prelude::*; - -use crate::vec::Vec; -use alloc::boxed::Box; -use core::cmp::Ordering; -use core::fmt; -use core::hash::{BuildHasher, Hash}; -use core::ops::RangeBounds; - -use crate::map::Slice; -use crate::Bucket; -use crate::Entries; -use crate::IndexMap; - -impl<K, V, S> IntoParallelIterator for IndexMap<K, V, S> -where - K: Send, - V: Send, -{ - type Item = (K, V); - type Iter = IntoParIter<K, V>; - - fn into_par_iter(self) -> Self::Iter { - IntoParIter { - entries: self.into_entries(), - } - } -} - -impl<K, V> IntoParallelIterator for Box<Slice<K, V>> -where - K: Send, - V: Send, -{ - type Item = (K, V); - type Iter = IntoParIter<K, V>; - - fn into_par_iter(self) -> Self::Iter { - IntoParIter { - entries: self.into_entries(), - } - } -} - -/// A parallel owning iterator over the entries of an [`IndexMap`]. -/// -/// This `struct` is created by the [`IndexMap::into_par_iter`] method -/// (provided by rayon's [`IntoParallelIterator`] trait). See its documentation for more. -pub struct IntoParIter<K, V> { - entries: Vec<Bucket<K, V>>, -} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoParIter<K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::refs); - f.debug_list().entries(iter).finish() - } -} - -impl<K: Send, V: Send> ParallelIterator for IntoParIter<K, V> { - type Item = (K, V); - - parallel_iterator_methods!(Bucket::key_value); -} - -impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> { - indexed_parallel_iterator_methods!(Bucket::key_value); -} - -impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S> -where - K: Sync, - V: Sync, -{ - type Item = (&'a K, &'a V); - type Iter = ParIter<'a, K, V>; - - fn into_par_iter(self) -> Self::Iter { - ParIter { - entries: self.as_entries(), - } - } -} - -impl<'a, K, V> IntoParallelIterator for &'a Slice<K, V> -where - K: Sync, - V: Sync, -{ - type Item = (&'a K, &'a V); - type Iter = ParIter<'a, K, V>; - - fn into_par_iter(self) -> Self::Iter { - ParIter { - entries: &self.entries, - } - } -} - -/// A parallel iterator over the entries of an [`IndexMap`]. -/// -/// This `struct` is created by the [`IndexMap::par_iter`] method -/// (provided by rayon's [`IntoParallelRefIterator`] trait). See its documentation for more. -/// -/// [`IndexMap::par_iter`]: ../struct.IndexMap.html#method.par_iter -pub struct ParIter<'a, K, V> { - entries: &'a [Bucket<K, V>], -} - -impl<K, V> Clone for ParIter<'_, K, V> { - fn clone(&self) -> Self { - ParIter { ..*self } - } -} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::refs); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> { - type Item = (&'a K, &'a V); - - parallel_iterator_methods!(Bucket::refs); -} - -impl<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> { - indexed_parallel_iterator_methods!(Bucket::refs); -} - -impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S> -where - K: Sync + Send, - V: Send, -{ - type Item = (&'a K, &'a mut V); - type Iter = ParIterMut<'a, K, V>; - - fn into_par_iter(self) -> Self::Iter { - ParIterMut { - entries: self.as_entries_mut(), - } - } -} - -impl<'a, K, V> IntoParallelIterator for &'a mut Slice<K, V> -where - K: Sync + Send, - V: Send, -{ - type Item = (&'a K, &'a mut V); - type Iter = ParIterMut<'a, K, V>; - - fn into_par_iter(self) -> Self::Iter { - ParIterMut { - entries: &mut self.entries, - } - } -} - -/// A parallel mutable iterator over the entries of an [`IndexMap`]. -/// -/// This `struct` is created by the [`IndexMap::par_iter_mut`] method -/// (provided by rayon's [`IntoParallelRefMutIterator`] trait). See its documentation for more. -/// -/// [`IndexMap::par_iter_mut`]: ../struct.IndexMap.html#method.par_iter_mut -pub struct ParIterMut<'a, K, V> { - entries: &'a mut [Bucket<K, V>], -} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ParIterMut<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::refs); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, K: Sync + Send, V: Send> ParallelIterator for ParIterMut<'a, K, V> { - type Item = (&'a K, &'a mut V); - - parallel_iterator_methods!(Bucket::ref_mut); -} - -impl<K: Sync + Send, V: Send> IndexedParallelIterator for ParIterMut<'_, K, V> { - indexed_parallel_iterator_methods!(Bucket::ref_mut); -} - -impl<'a, K, V, S> ParallelDrainRange<usize> for &'a mut IndexMap<K, V, S> -where - K: Send, - V: Send, -{ - type Item = (K, V); - type Iter = ParDrain<'a, K, V>; - - fn par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter { - ParDrain { - entries: self.core.par_drain(range), - } - } -} - -/// A parallel draining iterator over the entries of an [`IndexMap`]. -/// -/// This `struct` is created by the [`IndexMap::par_drain`] method -/// (provided by rayon's [`ParallelDrainRange`] trait). See its documentation for more. -/// -/// [`IndexMap::par_drain`]: ../struct.IndexMap.html#method.par_drain -pub struct ParDrain<'a, K: Send, V: Send> { - entries: rayon::vec::Drain<'a, Bucket<K, V>>, -} - -impl<K: Send, V: Send> ParallelIterator for ParDrain<'_, K, V> { - type Item = (K, V); - - parallel_iterator_methods!(Bucket::key_value); -} - -impl<K: Send, V: Send> IndexedParallelIterator for ParDrain<'_, K, V> { - indexed_parallel_iterator_methods!(Bucket::key_value); -} - -/// Parallel iterator methods and other parallel methods. -/// -/// The following methods **require crate feature `"rayon"`**. -/// -/// See also the `IntoParallelIterator` implementations. -impl<K, V, S> IndexMap<K, V, S> -where - K: Sync, - V: Sync, -{ - /// Return a parallel iterator over the keys of the map. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the map is still preserved for operations like `reduce` and `collect`. - pub fn par_keys(&self) -> ParKeys<'_, K, V> { - ParKeys { - entries: self.as_entries(), - } - } - - /// Return a parallel iterator over the values of the map. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the map is still preserved for operations like `reduce` and `collect`. - pub fn par_values(&self) -> ParValues<'_, K, V> { - ParValues { - entries: self.as_entries(), - } - } -} - -/// Parallel iterator methods and other parallel methods. -/// -/// The following methods **require crate feature `"rayon"`**. -/// -/// See also the `IntoParallelIterator` implementations. -impl<K, V> Slice<K, V> -where - K: Sync, - V: Sync, -{ - /// Return a parallel iterator over the keys of the map slice. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the slice is still preserved for operations like `reduce` and `collect`. - pub fn par_keys(&self) -> ParKeys<'_, K, V> { - ParKeys { - entries: &self.entries, - } - } - - /// Return a parallel iterator over the values of the map slice. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the slice is still preserved for operations like `reduce` and `collect`. - pub fn par_values(&self) -> ParValues<'_, K, V> { - ParValues { - entries: &self.entries, - } - } -} - -impl<K, V, S> IndexMap<K, V, S> -where - K: Hash + Eq + Sync, - V: Sync, - S: BuildHasher, -{ - /// Returns `true` if `self` contains all of the same key-value pairs as `other`, - /// regardless of each map's indexed order, determined in parallel. - pub fn par_eq<V2, S2>(&self, other: &IndexMap<K, V2, S2>) -> bool - where - V: PartialEq<V2>, - V2: Sync, - S2: BuildHasher + Sync, - { - self.len() == other.len() - && self - .par_iter() - .all(move |(key, value)| other.get(key).map_or(false, |v| *value == *v)) - } -} - -/// A parallel iterator over the keys of an [`IndexMap`]. -/// -/// This `struct` is created by the [`IndexMap::par_keys`] method. -/// See its documentation for more. -pub struct ParKeys<'a, K, V> { - entries: &'a [Bucket<K, V>], -} - -impl<K, V> Clone for ParKeys<'_, K, V> { - fn clone(&self) -> Self { - ParKeys { ..*self } - } -} - -impl<K: fmt::Debug, V> fmt::Debug for ParKeys<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> { - type Item = &'a K; - - parallel_iterator_methods!(Bucket::key_ref); -} - -impl<K: Sync, V: Sync> IndexedParallelIterator for ParKeys<'_, K, V> { - indexed_parallel_iterator_methods!(Bucket::key_ref); -} - -/// A parallel iterator over the values of an [`IndexMap`]. -/// -/// This `struct` is created by the [`IndexMap::par_values`] method. -/// See its documentation for more. -pub struct ParValues<'a, K, V> { - entries: &'a [Bucket<K, V>], -} - -impl<K, V> Clone for ParValues<'_, K, V> { - fn clone(&self) -> Self { - ParValues { ..*self } - } -} - -impl<K, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::value_ref); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> { - type Item = &'a V; - - parallel_iterator_methods!(Bucket::value_ref); -} - -impl<K: Sync, V: Sync> IndexedParallelIterator for ParValues<'_, K, V> { - indexed_parallel_iterator_methods!(Bucket::value_ref); -} - -impl<K, V, S> IndexMap<K, V, S> -where - K: Send, - V: Send, -{ - /// Return a parallel iterator over mutable references to the values of the map - /// - /// While parallel iterators can process items in any order, their relative order - /// in the map is still preserved for operations like `reduce` and `collect`. - pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> { - ParValuesMut { - entries: self.as_entries_mut(), - } - } -} - -impl<K, V> Slice<K, V> -where - K: Send, - V: Send, -{ - /// Return a parallel iterator over mutable references to the the values of the map slice. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the slice is still preserved for operations like `reduce` and `collect`. - pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> { - ParValuesMut { - entries: &mut self.entries, - } - } -} - -impl<K, V, S> IndexMap<K, V, S> -where - K: Send, - V: Send, -{ - /// Sort the map’s key-value pairs in parallel, by the default ordering of the keys. - pub fn par_sort_keys(&mut self) - where - K: Ord, - { - self.with_entries(|entries| { - entries.par_sort_by(|a, b| K::cmp(&a.key, &b.key)); - }); - } - - /// Sort the map’s key-value pairs in place and in parallel, using the comparison - /// function `cmp`. - /// - /// The comparison function receives two key and value pairs to compare (you - /// can sort by keys or values or their combination as needed). - pub fn par_sort_by<F>(&mut self, cmp: F) - where - F: Fn(&K, &V, &K, &V) -> Ordering + Sync, - { - self.with_entries(|entries| { - entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); - }); - } - - /// Sort the key-value pairs of the map in parallel and return a by-value parallel - /// iterator of the key-value pairs with the result. - pub fn par_sorted_by<F>(self, cmp: F) -> IntoParIter<K, V> - where - F: Fn(&K, &V, &K, &V) -> Ordering + Sync, - { - let mut entries = self.into_entries(); - entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); - IntoParIter { entries } - } - - /// Sort the map's key-value pairs in parallel, by the default ordering of the keys. - pub fn par_sort_unstable_keys(&mut self) - where - K: Ord, - { - self.with_entries(|entries| { - entries.par_sort_unstable_by(|a, b| K::cmp(&a.key, &b.key)); - }); - } - - /// Sort the map's key-value pairs in place and in parallel, using the comparison - /// function `cmp`. - /// - /// The comparison function receives two key and value pairs to compare (you - /// can sort by keys or values or their combination as needed). - pub fn par_sort_unstable_by<F>(&mut self, cmp: F) - where - F: Fn(&K, &V, &K, &V) -> Ordering + Sync, - { - self.with_entries(|entries| { - entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); - }); - } - - /// Sort the key-value pairs of the map in parallel and return a by-value parallel - /// iterator of the key-value pairs with the result. - pub fn par_sorted_unstable_by<F>(self, cmp: F) -> IntoParIter<K, V> - where - F: Fn(&K, &V, &K, &V) -> Ordering + Sync, - { - let mut entries = self.into_entries(); - entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); - IntoParIter { entries } - } - - /// Sort the map’s key-value pairs in place and in parallel, using a sort-key extraction - /// function. - pub fn par_sort_by_cached_key<T, F>(&mut self, sort_key: F) - where - T: Ord + Send, - F: Fn(&K, &V) -> T + Sync, - { - self.with_entries(move |entries| { - entries.par_sort_by_cached_key(move |a| sort_key(&a.key, &a.value)); - }); - } -} - -/// A parallel mutable iterator over the values of an [`IndexMap`]. -/// -/// This `struct` is created by the [`IndexMap::par_values_mut`] method. -/// See its documentation for more. -pub struct ParValuesMut<'a, K, V> { - entries: &'a mut [Bucket<K, V>], -} - -impl<K, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::value_ref); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, K: Send, V: Send> ParallelIterator for ParValuesMut<'a, K, V> { - type Item = &'a mut V; - - parallel_iterator_methods!(Bucket::value_mut); -} - -impl<K: Send, V: Send> IndexedParallelIterator for ParValuesMut<'_, K, V> { - indexed_parallel_iterator_methods!(Bucket::value_mut); -} - -impl<K, V, S> FromParallelIterator<(K, V)> for IndexMap<K, V, S> -where - K: Eq + Hash + Send, - V: Send, - S: BuildHasher + Default + Send, -{ - fn from_par_iter<I>(iter: I) -> Self - where - I: IntoParallelIterator<Item = (K, V)>, - { - let list = collect(iter); - let len = list.iter().map(Vec::len).sum(); - let mut map = Self::with_capacity_and_hasher(len, S::default()); - for vec in list { - map.extend(vec); - } - map - } -} - -impl<K, V, S> ParallelExtend<(K, V)> for IndexMap<K, V, S> -where - K: Eq + Hash + Send, - V: Send, - S: BuildHasher + Send, -{ - fn par_extend<I>(&mut self, iter: I) - where - I: IntoParallelIterator<Item = (K, V)>, - { - for vec in collect(iter) { - self.extend(vec); - } - } -} - -impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for IndexMap<K, V, S> -where - K: Copy + Eq + Hash + Send + Sync, - V: Copy + Send + Sync, - S: BuildHasher + Send, -{ - fn par_extend<I>(&mut self, iter: I) - where - I: IntoParallelIterator<Item = (&'a K, &'a V)>, - { - for vec in collect(iter) { - self.extend(vec); - } - } -} - -#[cfg(test)] -mod tests { - use super::*; - use std::string::String; - - #[test] - fn insert_order() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut map = IndexMap::new(); - - for &elt in &insert { - map.insert(elt, ()); - } - - assert_eq!(map.par_keys().count(), map.len()); - assert_eq!(map.par_keys().count(), insert.len()); - insert.par_iter().zip(map.par_keys()).for_each(|(a, b)| { - assert_eq!(a, b); - }); - (0..insert.len()) - .into_par_iter() - .zip(map.par_keys()) - .for_each(|(i, k)| { - assert_eq!(map.get_index(i).unwrap().0, k); - }); - } - - #[test] - fn partial_eq_and_eq() { - let mut map_a = IndexMap::new(); - map_a.insert(1, "1"); - map_a.insert(2, "2"); - let mut map_b = map_a.clone(); - assert!(map_a.par_eq(&map_b)); - map_b.swap_remove(&1); - assert!(!map_a.par_eq(&map_b)); - map_b.insert(3, "3"); - assert!(!map_a.par_eq(&map_b)); - - let map_c: IndexMap<_, String> = - map_b.into_par_iter().map(|(k, v)| (k, v.into())).collect(); - assert!(!map_a.par_eq(&map_c)); - assert!(!map_c.par_eq(&map_a)); - } - - #[test] - fn extend() { - let mut map = IndexMap::new(); - map.par_extend(vec![(&1, &2), (&3, &4)]); - map.par_extend(vec![(5, 6)]); - assert_eq!( - map.into_par_iter().collect::<Vec<_>>(), - vec![(1, 2), (3, 4), (5, 6)] - ); - } - - #[test] - fn keys() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: IndexMap<_, _> = vec.into_par_iter().collect(); - let keys: Vec<_> = map.par_keys().copied().collect(); - assert_eq!(keys.len(), 3); - assert!(keys.contains(&1)); - assert!(keys.contains(&2)); - assert!(keys.contains(&3)); - } - - #[test] - fn values() { - let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; - let map: IndexMap<_, _> = vec.into_par_iter().collect(); - let values: Vec<_> = map.par_values().copied().collect(); - assert_eq!(values.len(), 3); - assert!(values.contains(&'a')); - assert!(values.contains(&'b')); - assert!(values.contains(&'c')); - } - - #[test] - fn values_mut() { - let vec = vec![(1, 1), (2, 2), (3, 3)]; - let mut map: IndexMap<_, _> = vec.into_par_iter().collect(); - map.par_values_mut().for_each(|value| *value *= 2); - let values: Vec<_> = map.par_values().copied().collect(); - assert_eq!(values.len(), 3); - assert!(values.contains(&2)); - assert!(values.contains(&4)); - assert!(values.contains(&6)); - } -} diff --git a/vendor/indexmap/src/rayon/mod.rs b/vendor/indexmap/src/rayon/mod.rs deleted file mode 100644 index 84ce02db..00000000 --- a/vendor/indexmap/src/rayon/mod.rs +++ /dev/null @@ -1,16 +0,0 @@ -#![cfg_attr(docsrs, doc(cfg(feature = "rayon")))] - -use rayon::prelude::*; - -use alloc::collections::LinkedList; - -use crate::vec::Vec; - -pub mod map; -pub mod set; - -// This form of intermediate collection is also how Rayon collects `HashMap`. -// Note that the order will also be preserved! -fn collect<I: IntoParallelIterator>(iter: I) -> LinkedList<Vec<I::Item>> { - iter.into_par_iter().collect_vec_list() -} diff --git a/vendor/indexmap/src/rayon/set.rs b/vendor/indexmap/src/rayon/set.rs deleted file mode 100644 index 3904234b..00000000 --- a/vendor/indexmap/src/rayon/set.rs +++ /dev/null @@ -1,756 +0,0 @@ -//! Parallel iterator types for [`IndexSet`] with [rayon][::rayon]. -//! -//! You will rarely need to interact with this module directly unless you need to name one of the -//! iterator types. - -use super::collect; -use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; -use rayon::prelude::*; - -use crate::vec::Vec; -use alloc::boxed::Box; -use core::cmp::Ordering; -use core::fmt; -use core::hash::{BuildHasher, Hash}; -use core::ops::RangeBounds; - -use crate::set::Slice; -use crate::Entries; -use crate::IndexSet; - -type Bucket<T> = crate::Bucket<T, ()>; - -impl<T, S> IntoParallelIterator for IndexSet<T, S> -where - T: Send, -{ - type Item = T; - type Iter = IntoParIter<T>; - - fn into_par_iter(self) -> Self::Iter { - IntoParIter { - entries: self.into_entries(), - } - } -} - -impl<T> IntoParallelIterator for Box<Slice<T>> -where - T: Send, -{ - type Item = T; - type Iter = IntoParIter<T>; - - fn into_par_iter(self) -> Self::Iter { - IntoParIter { - entries: self.into_entries(), - } - } -} - -/// A parallel owning iterator over the items of an [`IndexSet`]. -/// -/// This `struct` is created by the [`IndexSet::into_par_iter`] method -/// (provided by rayon's [`IntoParallelIterator`] trait). See its documentation for more. -pub struct IntoParIter<T> { - entries: Vec<Bucket<T>>, -} - -impl<T: fmt::Debug> fmt::Debug for IntoParIter<T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -impl<T: Send> ParallelIterator for IntoParIter<T> { - type Item = T; - - parallel_iterator_methods!(Bucket::key); -} - -impl<T: Send> IndexedParallelIterator for IntoParIter<T> { - indexed_parallel_iterator_methods!(Bucket::key); -} - -impl<'a, T, S> IntoParallelIterator for &'a IndexSet<T, S> -where - T: Sync, -{ - type Item = &'a T; - type Iter = ParIter<'a, T>; - - fn into_par_iter(self) -> Self::Iter { - ParIter { - entries: self.as_entries(), - } - } -} - -impl<'a, T> IntoParallelIterator for &'a Slice<T> -where - T: Sync, -{ - type Item = &'a T; - type Iter = ParIter<'a, T>; - - fn into_par_iter(self) -> Self::Iter { - ParIter { - entries: &self.entries, - } - } -} - -/// A parallel iterator over the items of an [`IndexSet`]. -/// -/// This `struct` is created by the [`IndexSet::par_iter`] method -/// (provided by rayon's [`IntoParallelRefIterator`] trait). See its documentation for more. -/// -/// [`IndexSet::par_iter`]: ../struct.IndexSet.html#method.par_iter -pub struct ParIter<'a, T> { - entries: &'a [Bucket<T>], -} - -impl<T> Clone for ParIter<'_, T> { - fn clone(&self) -> Self { - ParIter { ..*self } - } -} - -impl<T: fmt::Debug> fmt::Debug for ParIter<'_, T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let iter = self.entries.iter().map(Bucket::key_ref); - f.debug_list().entries(iter).finish() - } -} - -impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> { - type Item = &'a T; - - parallel_iterator_methods!(Bucket::key_ref); -} - -impl<T: Sync> IndexedParallelIterator for ParIter<'_, T> { - indexed_parallel_iterator_methods!(Bucket::key_ref); -} - -impl<'a, T, S> ParallelDrainRange<usize> for &'a mut IndexSet<T, S> -where - T: Send, -{ - type Item = T; - type Iter = ParDrain<'a, T>; - - fn par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter { - ParDrain { - entries: self.map.core.par_drain(range), - } - } -} - -/// A parallel draining iterator over the items of an [`IndexSet`]. -/// -/// This `struct` is created by the [`IndexSet::par_drain`] method -/// (provided by rayon's [`ParallelDrainRange`] trait). See its documentation for more. -/// -/// [`IndexSet::par_drain`]: ../struct.IndexSet.html#method.par_drain -pub struct ParDrain<'a, T: Send> { - entries: rayon::vec::Drain<'a, Bucket<T>>, -} - -impl<T: Send> ParallelIterator for ParDrain<'_, T> { - type Item = T; - - parallel_iterator_methods!(Bucket::key); -} - -impl<T: Send> IndexedParallelIterator for ParDrain<'_, T> { - indexed_parallel_iterator_methods!(Bucket::key); -} - -/// Parallel iterator methods and other parallel methods. -/// -/// The following methods **require crate feature `"rayon"`**. -/// -/// See also the `IntoParallelIterator` implementations. -impl<T, S> IndexSet<T, S> -where - T: Hash + Eq + Sync, - S: BuildHasher + Sync, -{ - /// Return a parallel iterator over the values that are in `self` but not `other`. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the `self` set is still preserved for operations like `reduce` and `collect`. - pub fn par_difference<'a, S2>( - &'a self, - other: &'a IndexSet<T, S2>, - ) -> ParDifference<'a, T, S, S2> - where - S2: BuildHasher + Sync, - { - ParDifference { - set1: self, - set2: other, - } - } - - /// Return a parallel iterator over the values that are in `self` or `other`, - /// but not in both. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the sets is still preserved for operations like `reduce` and `collect`. - /// Values from `self` are produced in their original order, followed by - /// values from `other` in their original order. - pub fn par_symmetric_difference<'a, S2>( - &'a self, - other: &'a IndexSet<T, S2>, - ) -> ParSymmetricDifference<'a, T, S, S2> - where - S2: BuildHasher + Sync, - { - ParSymmetricDifference { - set1: self, - set2: other, - } - } - - /// Return a parallel iterator over the values that are in both `self` and `other`. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the `self` set is still preserved for operations like `reduce` and `collect`. - pub fn par_intersection<'a, S2>( - &'a self, - other: &'a IndexSet<T, S2>, - ) -> ParIntersection<'a, T, S, S2> - where - S2: BuildHasher + Sync, - { - ParIntersection { - set1: self, - set2: other, - } - } - - /// Return a parallel iterator over all values that are in `self` or `other`. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the sets is still preserved for operations like `reduce` and `collect`. - /// Values from `self` are produced in their original order, followed by - /// values that are unique to `other` in their original order. - pub fn par_union<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> ParUnion<'a, T, S, S2> - where - S2: BuildHasher + Sync, - { - ParUnion { - set1: self, - set2: other, - } - } - - /// Returns `true` if `self` contains all of the same values as `other`, - /// regardless of each set's indexed order, determined in parallel. - pub fn par_eq<S2>(&self, other: &IndexSet<T, S2>) -> bool - where - S2: BuildHasher + Sync, - { - self.len() == other.len() && self.par_is_subset(other) - } - - /// Returns `true` if `self` has no elements in common with `other`, - /// determined in parallel. - pub fn par_is_disjoint<S2>(&self, other: &IndexSet<T, S2>) -> bool - where - S2: BuildHasher + Sync, - { - if self.len() <= other.len() { - self.par_iter().all(move |value| !other.contains(value)) - } else { - other.par_iter().all(move |value| !self.contains(value)) - } - } - - /// Returns `true` if all elements of `other` are contained in `self`, - /// determined in parallel. - pub fn par_is_superset<S2>(&self, other: &IndexSet<T, S2>) -> bool - where - S2: BuildHasher + Sync, - { - other.par_is_subset(self) - } - - /// Returns `true` if all elements of `self` are contained in `other`, - /// determined in parallel. - pub fn par_is_subset<S2>(&self, other: &IndexSet<T, S2>) -> bool - where - S2: BuildHasher + Sync, - { - self.len() <= other.len() && self.par_iter().all(move |value| other.contains(value)) - } -} - -/// A parallel iterator producing elements in the difference of [`IndexSet`]s. -/// -/// This `struct` is created by the [`IndexSet::par_difference`] method. -/// See its documentation for more. -pub struct ParDifference<'a, T, S1, S2> { - set1: &'a IndexSet<T, S1>, - set2: &'a IndexSet<T, S2>, -} - -impl<T, S1, S2> Clone for ParDifference<'_, T, S1, S2> { - fn clone(&self) -> Self { - ParDifference { ..*self } - } -} - -impl<T, S1, S2> fmt::Debug for ParDifference<'_, T, S1, S2> -where - T: fmt::Debug + Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list() - .entries(self.set1.difference(self.set2)) - .finish() - } -} - -impl<'a, T, S1, S2> ParallelIterator for ParDifference<'a, T, S1, S2> -where - T: Hash + Eq + Sync, - S1: BuildHasher + Sync, - S2: BuildHasher + Sync, -{ - type Item = &'a T; - - fn drive_unindexed<C>(self, consumer: C) -> C::Result - where - C: UnindexedConsumer<Self::Item>, - { - let Self { set1, set2 } = self; - - set1.par_iter() - .filter(move |&item| !set2.contains(item)) - .drive_unindexed(consumer) - } -} - -/// A parallel iterator producing elements in the intersection of [`IndexSet`]s. -/// -/// This `struct` is created by the [`IndexSet::par_intersection`] method. -/// See its documentation for more. -pub struct ParIntersection<'a, T, S1, S2> { - set1: &'a IndexSet<T, S1>, - set2: &'a IndexSet<T, S2>, -} - -impl<T, S1, S2> Clone for ParIntersection<'_, T, S1, S2> { - fn clone(&self) -> Self { - ParIntersection { ..*self } - } -} - -impl<T, S1, S2> fmt::Debug for ParIntersection<'_, T, S1, S2> -where - T: fmt::Debug + Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list() - .entries(self.set1.intersection(self.set2)) - .finish() - } -} - -impl<'a, T, S1, S2> ParallelIterator for ParIntersection<'a, T, S1, S2> -where - T: Hash + Eq + Sync, - S1: BuildHasher + Sync, - S2: BuildHasher + Sync, -{ - type Item = &'a T; - - fn drive_unindexed<C>(self, consumer: C) -> C::Result - where - C: UnindexedConsumer<Self::Item>, - { - let Self { set1, set2 } = self; - - set1.par_iter() - .filter(move |&item| set2.contains(item)) - .drive_unindexed(consumer) - } -} - -/// A parallel iterator producing elements in the symmetric difference of [`IndexSet`]s. -/// -/// This `struct` is created by the [`IndexSet::par_symmetric_difference`] method. -/// See its documentation for more. -pub struct ParSymmetricDifference<'a, T, S1, S2> { - set1: &'a IndexSet<T, S1>, - set2: &'a IndexSet<T, S2>, -} - -impl<T, S1, S2> Clone for ParSymmetricDifference<'_, T, S1, S2> { - fn clone(&self) -> Self { - ParSymmetricDifference { ..*self } - } -} - -impl<T, S1, S2> fmt::Debug for ParSymmetricDifference<'_, T, S1, S2> -where - T: fmt::Debug + Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list() - .entries(self.set1.symmetric_difference(self.set2)) - .finish() - } -} - -impl<'a, T, S1, S2> ParallelIterator for ParSymmetricDifference<'a, T, S1, S2> -where - T: Hash + Eq + Sync, - S1: BuildHasher + Sync, - S2: BuildHasher + Sync, -{ - type Item = &'a T; - - fn drive_unindexed<C>(self, consumer: C) -> C::Result - where - C: UnindexedConsumer<Self::Item>, - { - let Self { set1, set2 } = self; - - set1.par_difference(set2) - .chain(set2.par_difference(set1)) - .drive_unindexed(consumer) - } -} - -/// A parallel iterator producing elements in the union of [`IndexSet`]s. -/// -/// This `struct` is created by the [`IndexSet::par_union`] method. -/// See its documentation for more. -pub struct ParUnion<'a, T, S1, S2> { - set1: &'a IndexSet<T, S1>, - set2: &'a IndexSet<T, S2>, -} - -impl<T, S1, S2> Clone for ParUnion<'_, T, S1, S2> { - fn clone(&self) -> Self { - ParUnion { ..*self } - } -} - -impl<T, S1, S2> fmt::Debug for ParUnion<'_, T, S1, S2> -where - T: fmt::Debug + Eq + Hash, - S1: BuildHasher, - S2: BuildHasher, -{ - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.set1.union(self.set2)).finish() - } -} - -impl<'a, T, S1, S2> ParallelIterator for ParUnion<'a, T, S1, S2> -where - T: Hash + Eq + Sync, - S1: BuildHasher + Sync, - S2: BuildHasher + Sync, -{ - type Item = &'a T; - - fn drive_unindexed<C>(self, consumer: C) -> C::Result - where - C: UnindexedConsumer<Self::Item>, - { - let Self { set1, set2 } = self; - - set1.par_iter() - .chain(set2.par_difference(set1)) - .drive_unindexed(consumer) - } -} - -/// Parallel sorting methods. -/// -/// The following methods **require crate feature `"rayon"`**. -impl<T, S> IndexSet<T, S> -where - T: Send, -{ - /// Sort the set’s values in parallel by their default ordering. - pub fn par_sort(&mut self) - where - T: Ord, - { - self.with_entries(|entries| { - entries.par_sort_by(|a, b| T::cmp(&a.key, &b.key)); - }); - } - - /// Sort the set’s values in place and in parallel, using the comparison function `cmp`. - pub fn par_sort_by<F>(&mut self, cmp: F) - where - F: Fn(&T, &T) -> Ordering + Sync, - { - self.with_entries(|entries| { - entries.par_sort_by(move |a, b| cmp(&a.key, &b.key)); - }); - } - - /// Sort the values of the set in parallel and return a by-value parallel iterator of - /// the values with the result. - pub fn par_sorted_by<F>(self, cmp: F) -> IntoParIter<T> - where - F: Fn(&T, &T) -> Ordering + Sync, - { - let mut entries = self.into_entries(); - entries.par_sort_by(move |a, b| cmp(&a.key, &b.key)); - IntoParIter { entries } - } - - /// Sort the set's values in parallel by their default ordering. - pub fn par_sort_unstable(&mut self) - where - T: Ord, - { - self.with_entries(|entries| { - entries.par_sort_unstable_by(|a, b| T::cmp(&a.key, &b.key)); - }); - } - - /// Sort the set’s values in place and in parallel, using the comparison function `cmp`. - pub fn par_sort_unstable_by<F>(&mut self, cmp: F) - where - F: Fn(&T, &T) -> Ordering + Sync, - { - self.with_entries(|entries| { - entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); - }); - } - - /// Sort the values of the set in parallel and return a by-value parallel iterator of - /// the values with the result. - pub fn par_sorted_unstable_by<F>(self, cmp: F) -> IntoParIter<T> - where - F: Fn(&T, &T) -> Ordering + Sync, - { - let mut entries = self.into_entries(); - entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &b.key)); - IntoParIter { entries } - } - - /// Sort the set’s values in place and in parallel, using a key extraction function. - pub fn par_sort_by_cached_key<K, F>(&mut self, sort_key: F) - where - K: Ord + Send, - F: Fn(&T) -> K + Sync, - { - self.with_entries(move |entries| { - entries.par_sort_by_cached_key(move |a| sort_key(&a.key)); - }); - } -} - -impl<T, S> FromParallelIterator<T> for IndexSet<T, S> -where - T: Eq + Hash + Send, - S: BuildHasher + Default + Send, -{ - fn from_par_iter<I>(iter: I) -> Self - where - I: IntoParallelIterator<Item = T>, - { - let list = collect(iter); - let len = list.iter().map(Vec::len).sum(); - let mut set = Self::with_capacity_and_hasher(len, S::default()); - for vec in list { - set.extend(vec); - } - set - } -} - -impl<T, S> ParallelExtend<T> for IndexSet<T, S> -where - T: Eq + Hash + Send, - S: BuildHasher + Send, -{ - fn par_extend<I>(&mut self, iter: I) - where - I: IntoParallelIterator<Item = T>, - { - for vec in collect(iter) { - self.extend(vec); - } - } -} - -impl<'a, T: 'a, S> ParallelExtend<&'a T> for IndexSet<T, S> -where - T: Copy + Eq + Hash + Send + Sync, - S: BuildHasher + Send, -{ - fn par_extend<I>(&mut self, iter: I) - where - I: IntoParallelIterator<Item = &'a T>, - { - for vec in collect(iter) { - self.extend(vec); - } - } -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn insert_order() { - let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; - let mut set = IndexSet::new(); - - for &elt in &insert { - set.insert(elt); - } - - assert_eq!(set.par_iter().count(), set.len()); - assert_eq!(set.par_iter().count(), insert.len()); - insert.par_iter().zip(&set).for_each(|(a, b)| { - assert_eq!(a, b); - }); - (0..insert.len()) - .into_par_iter() - .zip(&set) - .for_each(|(i, v)| { - assert_eq!(set.get_index(i).unwrap(), v); - }); - } - - #[test] - fn partial_eq_and_eq() { - let mut set_a = IndexSet::new(); - set_a.insert(1); - set_a.insert(2); - let mut set_b = set_a.clone(); - assert!(set_a.par_eq(&set_b)); - set_b.swap_remove(&1); - assert!(!set_a.par_eq(&set_b)); - set_b.insert(3); - assert!(!set_a.par_eq(&set_b)); - - let set_c: IndexSet<_> = set_b.into_par_iter().collect(); - assert!(!set_a.par_eq(&set_c)); - assert!(!set_c.par_eq(&set_a)); - } - - #[test] - fn extend() { - let mut set = IndexSet::new(); - set.par_extend(vec![&1, &2, &3, &4]); - set.par_extend(vec![5, 6]); - assert_eq!( - set.into_par_iter().collect::<Vec<_>>(), - vec![1, 2, 3, 4, 5, 6] - ); - } - - #[test] - fn comparisons() { - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).collect(); - - assert!(!set_a.par_is_disjoint(&set_a)); - assert!(set_a.par_is_subset(&set_a)); - assert!(set_a.par_is_superset(&set_a)); - - assert!(set_a.par_is_disjoint(&set_b)); - assert!(set_b.par_is_disjoint(&set_a)); - assert!(!set_a.par_is_subset(&set_b)); - assert!(!set_b.par_is_subset(&set_a)); - assert!(!set_a.par_is_superset(&set_b)); - assert!(!set_b.par_is_superset(&set_a)); - - assert!(!set_a.par_is_disjoint(&set_c)); - assert!(!set_c.par_is_disjoint(&set_a)); - assert!(set_a.par_is_subset(&set_c)); - assert!(!set_c.par_is_subset(&set_a)); - assert!(!set_a.par_is_superset(&set_c)); - assert!(set_c.par_is_superset(&set_a)); - - assert!(!set_c.par_is_disjoint(&set_d)); - assert!(!set_d.par_is_disjoint(&set_c)); - assert!(!set_c.par_is_subset(&set_d)); - assert!(!set_d.par_is_subset(&set_c)); - assert!(!set_c.par_is_superset(&set_d)); - assert!(!set_d.par_is_superset(&set_c)); - } - - #[test] - fn iter_comparisons() { - use std::iter::empty; - - fn check<'a, I1, I2>(iter1: I1, iter2: I2) - where - I1: ParallelIterator<Item = &'a i32>, - I2: Iterator<Item = i32>, - { - let v1: Vec<_> = iter1.copied().collect(); - let v2: Vec<_> = iter2.collect(); - assert_eq!(v1, v2); - } - - let set_a: IndexSet<_> = (0..3).collect(); - let set_b: IndexSet<_> = (3..6).collect(); - let set_c: IndexSet<_> = (0..6).collect(); - let set_d: IndexSet<_> = (3..9).rev().collect(); - - check(set_a.par_difference(&set_a), empty()); - check(set_a.par_symmetric_difference(&set_a), empty()); - check(set_a.par_intersection(&set_a), 0..3); - check(set_a.par_union(&set_a), 0..3); - - check(set_a.par_difference(&set_b), 0..3); - check(set_b.par_difference(&set_a), 3..6); - check(set_a.par_symmetric_difference(&set_b), 0..6); - check(set_b.par_symmetric_difference(&set_a), (3..6).chain(0..3)); - check(set_a.par_intersection(&set_b), empty()); - check(set_b.par_intersection(&set_a), empty()); - check(set_a.par_union(&set_b), 0..6); - check(set_b.par_union(&set_a), (3..6).chain(0..3)); - - check(set_a.par_difference(&set_c), empty()); - check(set_c.par_difference(&set_a), 3..6); - check(set_a.par_symmetric_difference(&set_c), 3..6); - check(set_c.par_symmetric_difference(&set_a), 3..6); - check(set_a.par_intersection(&set_c), 0..3); - check(set_c.par_intersection(&set_a), 0..3); - check(set_a.par_union(&set_c), 0..6); - check(set_c.par_union(&set_a), 0..6); - - check(set_c.par_difference(&set_d), 0..3); - check(set_d.par_difference(&set_c), (6..9).rev()); - check( - set_c.par_symmetric_difference(&set_d), - (0..3).chain((6..9).rev()), - ); - check( - set_d.par_symmetric_difference(&set_c), - (6..9).rev().chain(0..3), - ); - check(set_c.par_intersection(&set_d), 3..6); - check(set_d.par_intersection(&set_c), (3..6).rev()); - check(set_c.par_union(&set_d), (0..6).chain((6..9).rev())); - check(set_d.par_union(&set_c), (3..9).rev().chain(0..3)); - } -} |
