summaryrefslogtreecommitdiff
path: root/vendor/indexmap/src/rayon
diff options
context:
space:
mode:
authormo khan <mo@mokhan.ca>2025-07-15 16:37:08 -0600
committermo khan <mo@mokhan.ca>2025-07-17 16:30:22 -0600
commit45df4d0d9b577fecee798d672695fe24ff57fb1b (patch)
tree1b99bf645035b58e0d6db08c7a83521f41f7a75b /vendor/indexmap/src/rayon
parentf94f79608393d4ab127db63cc41668445ef6b243 (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.rs663
-rw-r--r--vendor/indexmap/src/rayon/mod.rs16
-rw-r--r--vendor/indexmap/src/rayon/set.rs756
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));
- }
-}