]>
Commit | Line | Data |
---|---|---|
48663c56 XL |
1 | //! Rayon extensions for `HashMap`. |
2 | ||
6a06907d | 3 | use super::raw::{RawIntoParIter, RawParDrain, RawParIter}; |
48663c56 | 4 | use crate::hash_map::HashMap; |
6a06907d | 5 | use crate::raw::{Allocator, Global}; |
48663c56 XL |
6 | use core::fmt; |
7 | use core::hash::{BuildHasher, Hash}; | |
6a06907d | 8 | use core::marker::PhantomData; |
48663c56 XL |
9 | use rayon::iter::plumbing::UnindexedConsumer; |
10 | use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator}; | |
11 | ||
12 | /// Parallel iterator over shared references to entries in a map. | |
13 | /// | |
14 | /// This iterator is created by the [`par_iter`] method on [`HashMap`] | |
15 | /// (provided by the [`IntoParallelRefIterator`] trait). | |
16 | /// See its documentation for more. | |
17 | /// | |
18 | /// [`par_iter`]: /hashbrown/struct.HashMap.html#method.par_iter | |
19 | /// [`HashMap`]: /hashbrown/struct.HashMap.html | |
20 | /// [`IntoParallelRefIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefIterator.html | |
6a06907d XL |
21 | pub struct ParIter<'a, K, V> { |
22 | inner: RawParIter<(K, V)>, | |
23 | marker: PhantomData<(&'a K, &'a V)>, | |
48663c56 XL |
24 | } |
25 | ||
6a06907d | 26 | impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> { |
48663c56 XL |
27 | type Item = (&'a K, &'a V); |
28 | ||
e74abb32 | 29 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
30 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
31 | where | |
32 | C: UnindexedConsumer<Self::Item>, | |
33 | { | |
6a06907d | 34 | self.inner |
48663c56 XL |
35 | .map(|x| unsafe { |
36 | let r = x.as_ref(); | |
37 | (&r.0, &r.1) | |
38 | }) | |
39 | .drive_unindexed(consumer) | |
40 | } | |
41 | } | |
42 | ||
6a06907d | 43 | impl<K, V> Clone for ParIter<'_, K, V> { |
e74abb32 | 44 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 45 | fn clone(&self) -> Self { |
6a06907d XL |
46 | Self { |
47 | inner: self.inner.clone(), | |
48 | marker: PhantomData, | |
49 | } | |
48663c56 XL |
50 | } |
51 | } | |
52 | ||
6a06907d | 53 | impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> { |
48663c56 | 54 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
6a06907d XL |
55 | let iter = unsafe { self.inner.iter() }.map(|x| unsafe { |
56 | let r = x.as_ref(); | |
57 | (&r.0, &r.1) | |
58 | }); | |
59 | f.debug_list().entries(iter).finish() | |
48663c56 XL |
60 | } |
61 | } | |
62 | ||
63 | /// Parallel iterator over shared references to keys in a map. | |
64 | /// | |
65 | /// This iterator is created by the [`par_keys`] method on [`HashMap`]. | |
66 | /// See its documentation for more. | |
67 | /// | |
68 | /// [`par_keys`]: /hashbrown/struct.HashMap.html#method.par_keys | |
69 | /// [`HashMap`]: /hashbrown/struct.HashMap.html | |
6a06907d XL |
70 | pub struct ParKeys<'a, K, V> { |
71 | inner: RawParIter<(K, V)>, | |
72 | marker: PhantomData<(&'a K, &'a V)>, | |
48663c56 XL |
73 | } |
74 | ||
6a06907d | 75 | impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> { |
48663c56 XL |
76 | type Item = &'a K; |
77 | ||
e74abb32 | 78 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
79 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
80 | where | |
81 | C: UnindexedConsumer<Self::Item>, | |
82 | { | |
6a06907d | 83 | self.inner |
48663c56 XL |
84 | .map(|x| unsafe { &x.as_ref().0 }) |
85 | .drive_unindexed(consumer) | |
86 | } | |
87 | } | |
88 | ||
6a06907d | 89 | impl<K, V> Clone for ParKeys<'_, K, V> { |
e74abb32 | 90 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 91 | fn clone(&self) -> Self { |
6a06907d XL |
92 | Self { |
93 | inner: self.inner.clone(), | |
94 | marker: PhantomData, | |
95 | } | |
48663c56 XL |
96 | } |
97 | } | |
98 | ||
6a06907d | 99 | impl<K: fmt::Debug + Eq + Hash, V> fmt::Debug for ParKeys<'_, K, V> { |
48663c56 | 100 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
6a06907d XL |
101 | let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().0 }); |
102 | f.debug_list().entries(iter).finish() | |
48663c56 XL |
103 | } |
104 | } | |
105 | ||
106 | /// Parallel iterator over shared references to values in a map. | |
107 | /// | |
108 | /// This iterator is created by the [`par_values`] method on [`HashMap`]. | |
109 | /// See its documentation for more. | |
110 | /// | |
111 | /// [`par_values`]: /hashbrown/struct.HashMap.html#method.par_values | |
112 | /// [`HashMap`]: /hashbrown/struct.HashMap.html | |
6a06907d XL |
113 | pub struct ParValues<'a, K, V> { |
114 | inner: RawParIter<(K, V)>, | |
115 | marker: PhantomData<(&'a K, &'a V)>, | |
48663c56 XL |
116 | } |
117 | ||
6a06907d | 118 | impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> { |
48663c56 XL |
119 | type Item = &'a V; |
120 | ||
e74abb32 | 121 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
122 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
123 | where | |
124 | C: UnindexedConsumer<Self::Item>, | |
125 | { | |
6a06907d | 126 | self.inner |
48663c56 XL |
127 | .map(|x| unsafe { &x.as_ref().1 }) |
128 | .drive_unindexed(consumer) | |
129 | } | |
130 | } | |
131 | ||
6a06907d | 132 | impl<K, V> Clone for ParValues<'_, K, V> { |
e74abb32 | 133 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 134 | fn clone(&self) -> Self { |
6a06907d XL |
135 | Self { |
136 | inner: self.inner.clone(), | |
137 | marker: PhantomData, | |
138 | } | |
48663c56 XL |
139 | } |
140 | } | |
141 | ||
6a06907d | 142 | impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> { |
48663c56 | 143 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
6a06907d XL |
144 | let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().1 }); |
145 | f.debug_list().entries(iter).finish() | |
48663c56 XL |
146 | } |
147 | } | |
148 | ||
149 | /// Parallel iterator over mutable references to entries in a map. | |
150 | /// | |
151 | /// This iterator is created by the [`par_iter_mut`] method on [`HashMap`] | |
152 | /// (provided by the [`IntoParallelRefMutIterator`] trait). | |
153 | /// See its documentation for more. | |
154 | /// | |
155 | /// [`par_iter_mut`]: /hashbrown/struct.HashMap.html#method.par_iter_mut | |
156 | /// [`HashMap`]: /hashbrown/struct.HashMap.html | |
157 | /// [`IntoParallelRefMutIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefMutIterator.html | |
6a06907d XL |
158 | pub struct ParIterMut<'a, K, V> { |
159 | inner: RawParIter<(K, V)>, | |
160 | marker: PhantomData<(&'a K, &'a mut V)>, | |
48663c56 XL |
161 | } |
162 | ||
6a06907d | 163 | impl<'a, K: Sync, V: Send> ParallelIterator for ParIterMut<'a, K, V> { |
48663c56 XL |
164 | type Item = (&'a K, &'a mut V); |
165 | ||
e74abb32 | 166 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
167 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
168 | where | |
169 | C: UnindexedConsumer<Self::Item>, | |
170 | { | |
6a06907d | 171 | self.inner |
48663c56 XL |
172 | .map(|x| unsafe { |
173 | let r = x.as_mut(); | |
174 | (&r.0, &mut r.1) | |
175 | }) | |
176 | .drive_unindexed(consumer) | |
177 | } | |
178 | } | |
179 | ||
6a06907d | 180 | impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIterMut<'_, K, V> { |
48663c56 | 181 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
6a06907d XL |
182 | ParIter { |
183 | inner: self.inner.clone(), | |
184 | marker: PhantomData, | |
185 | } | |
186 | .fmt(f) | |
48663c56 XL |
187 | } |
188 | } | |
189 | ||
190 | /// Parallel iterator over mutable references to values in a map. | |
191 | /// | |
192 | /// This iterator is created by the [`par_values_mut`] method on [`HashMap`]. | |
193 | /// See its documentation for more. | |
194 | /// | |
195 | /// [`par_values_mut`]: /hashbrown/struct.HashMap.html#method.par_values_mut | |
196 | /// [`HashMap`]: /hashbrown/struct.HashMap.html | |
6a06907d XL |
197 | pub struct ParValuesMut<'a, K, V> { |
198 | inner: RawParIter<(K, V)>, | |
199 | marker: PhantomData<(&'a K, &'a mut V)>, | |
48663c56 XL |
200 | } |
201 | ||
6a06907d | 202 | impl<'a, K: Sync, V: Send> ParallelIterator for ParValuesMut<'a, K, V> { |
48663c56 XL |
203 | type Item = &'a mut V; |
204 | ||
e74abb32 | 205 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
206 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
207 | where | |
208 | C: UnindexedConsumer<Self::Item>, | |
209 | { | |
6a06907d | 210 | self.inner |
48663c56 XL |
211 | .map(|x| unsafe { &mut x.as_mut().1 }) |
212 | .drive_unindexed(consumer) | |
213 | } | |
214 | } | |
215 | ||
6a06907d | 216 | impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> { |
48663c56 | 217 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
6a06907d XL |
218 | ParValues { |
219 | inner: self.inner.clone(), | |
220 | marker: PhantomData, | |
221 | } | |
222 | .fmt(f) | |
48663c56 XL |
223 | } |
224 | } | |
225 | ||
226 | /// Parallel iterator over entries of a consumed map. | |
227 | /// | |
228 | /// This iterator is created by the [`into_par_iter`] method on [`HashMap`] | |
229 | /// (provided by the [`IntoParallelIterator`] trait). | |
230 | /// See its documentation for more. | |
231 | /// | |
232 | /// [`into_par_iter`]: /hashbrown/struct.HashMap.html#method.into_par_iter | |
233 | /// [`HashMap`]: /hashbrown/struct.HashMap.html | |
234 | /// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html | |
6a06907d XL |
235 | pub struct IntoParIter<K, V, A: Allocator + Clone = Global> { |
236 | inner: RawIntoParIter<(K, V), A>, | |
48663c56 XL |
237 | } |
238 | ||
6a06907d | 239 | impl<K: Send, V: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<K, V, A> { |
48663c56 XL |
240 | type Item = (K, V); |
241 | ||
e74abb32 | 242 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
243 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
244 | where | |
245 | C: UnindexedConsumer<Self::Item>, | |
246 | { | |
6a06907d | 247 | self.inner.drive_unindexed(consumer) |
48663c56 XL |
248 | } |
249 | } | |
250 | ||
6a06907d XL |
251 | impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug |
252 | for IntoParIter<K, V, A> | |
253 | { | |
48663c56 | 254 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
6a06907d XL |
255 | ParIter { |
256 | inner: unsafe { self.inner.par_iter() }, | |
257 | marker: PhantomData, | |
258 | } | |
259 | .fmt(f) | |
48663c56 XL |
260 | } |
261 | } | |
262 | ||
263 | /// Parallel draining iterator over entries of a map. | |
264 | /// | |
265 | /// This iterator is created by the [`par_drain`] method on [`HashMap`]. | |
266 | /// See its documentation for more. | |
267 | /// | |
268 | /// [`par_drain`]: /hashbrown/struct.HashMap.html#method.par_drain | |
269 | /// [`HashMap`]: /hashbrown/struct.HashMap.html | |
6a06907d XL |
270 | pub struct ParDrain<'a, K, V, A: Allocator + Clone = Global> { |
271 | inner: RawParDrain<'a, (K, V), A>, | |
48663c56 XL |
272 | } |
273 | ||
6a06907d | 274 | impl<K: Send, V: Send, A: Allocator + Clone + Sync> ParallelIterator for ParDrain<'_, K, V, A> { |
48663c56 XL |
275 | type Item = (K, V); |
276 | ||
e74abb32 | 277 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
278 | fn drive_unindexed<C>(self, consumer: C) -> C::Result |
279 | where | |
280 | C: UnindexedConsumer<Self::Item>, | |
281 | { | |
6a06907d | 282 | self.inner.drive_unindexed(consumer) |
48663c56 XL |
283 | } |
284 | } | |
285 | ||
6a06907d XL |
286 | impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug |
287 | for ParDrain<'_, K, V, A> | |
48663c56 XL |
288 | { |
289 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
6a06907d XL |
290 | ParIter { |
291 | inner: unsafe { self.inner.par_iter() }, | |
292 | marker: PhantomData, | |
293 | } | |
294 | .fmt(f) | |
48663c56 XL |
295 | } |
296 | } | |
297 | ||
6a06907d | 298 | impl<K: Sync, V: Sync, S, A: Allocator + Clone> HashMap<K, V, S, A> { |
48663c56 | 299 | /// Visits (potentially in parallel) immutably borrowed keys in an arbitrary order. |
e74abb32 | 300 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d XL |
301 | pub fn par_keys(&self) -> ParKeys<'_, K, V> { |
302 | ParKeys { | |
303 | inner: unsafe { self.table.par_iter() }, | |
304 | marker: PhantomData, | |
305 | } | |
48663c56 XL |
306 | } |
307 | ||
308 | /// Visits (potentially in parallel) immutably borrowed values in an arbitrary order. | |
e74abb32 | 309 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d XL |
310 | pub fn par_values(&self) -> ParValues<'_, K, V> { |
311 | ParValues { | |
312 | inner: unsafe { self.table.par_iter() }, | |
313 | marker: PhantomData, | |
314 | } | |
48663c56 XL |
315 | } |
316 | } | |
317 | ||
6a06907d | 318 | impl<K: Send, V: Send, S, A: Allocator + Clone> HashMap<K, V, S, A> { |
48663c56 | 319 | /// Visits (potentially in parallel) mutably borrowed values in an arbitrary order. |
e74abb32 | 320 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d XL |
321 | pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> { |
322 | ParValuesMut { | |
323 | inner: unsafe { self.table.par_iter() }, | |
324 | marker: PhantomData, | |
325 | } | |
48663c56 XL |
326 | } |
327 | ||
328 | /// Consumes (potentially in parallel) all values in an arbitrary order, | |
329 | /// while preserving the map's allocated memory for reuse. | |
e74abb32 | 330 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d XL |
331 | pub fn par_drain(&mut self) -> ParDrain<'_, K, V, A> { |
332 | ParDrain { | |
333 | inner: self.table.par_drain(), | |
334 | } | |
48663c56 XL |
335 | } |
336 | } | |
337 | ||
6a06907d | 338 | impl<K, V, S, A> HashMap<K, V, S, A> |
48663c56 XL |
339 | where |
340 | K: Eq + Hash + Sync, | |
341 | V: PartialEq + Sync, | |
342 | S: BuildHasher + Sync, | |
6a06907d | 343 | A: Allocator + Clone + Sync, |
48663c56 XL |
344 | { |
345 | /// Returns `true` if the map is equal to another, | |
346 | /// i.e. both maps contain the same keys mapped to the same values. | |
347 | /// | |
348 | /// This method runs in a potentially parallel fashion. | |
349 | pub fn par_eq(&self, other: &Self) -> bool { | |
350 | self.len() == other.len() | |
351 | && self | |
352 | .into_par_iter() | |
353 | .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) | |
354 | } | |
355 | } | |
356 | ||
6a06907d XL |
357 | impl<K: Send, V: Send, S, A: Allocator + Clone + Send> IntoParallelIterator |
358 | for HashMap<K, V, S, A> | |
359 | { | |
48663c56 | 360 | type Item = (K, V); |
6a06907d | 361 | type Iter = IntoParIter<K, V, A>; |
48663c56 | 362 | |
e74abb32 | 363 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 364 | fn into_par_iter(self) -> Self::Iter { |
6a06907d XL |
365 | IntoParIter { |
366 | inner: self.table.into_par_iter(), | |
367 | } | |
48663c56 XL |
368 | } |
369 | } | |
370 | ||
6a06907d XL |
371 | impl<'a, K: Sync, V: Sync, S, A: Allocator + Clone> IntoParallelIterator |
372 | for &'a HashMap<K, V, S, A> | |
373 | { | |
48663c56 | 374 | type Item = (&'a K, &'a V); |
6a06907d | 375 | type Iter = ParIter<'a, K, V>; |
48663c56 | 376 | |
e74abb32 | 377 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 378 | fn into_par_iter(self) -> Self::Iter { |
6a06907d XL |
379 | ParIter { |
380 | inner: unsafe { self.table.par_iter() }, | |
381 | marker: PhantomData, | |
382 | } | |
48663c56 XL |
383 | } |
384 | } | |
385 | ||
6a06907d XL |
386 | impl<'a, K: Sync, V: Send, S, A: Allocator + Clone> IntoParallelIterator |
387 | for &'a mut HashMap<K, V, S, A> | |
388 | { | |
48663c56 | 389 | type Item = (&'a K, &'a mut V); |
6a06907d | 390 | type Iter = ParIterMut<'a, K, V>; |
48663c56 | 391 | |
e74abb32 | 392 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 393 | fn into_par_iter(self) -> Self::Iter { |
6a06907d XL |
394 | ParIterMut { |
395 | inner: unsafe { self.table.par_iter() }, | |
396 | marker: PhantomData, | |
397 | } | |
48663c56 XL |
398 | } |
399 | } | |
400 | ||
401 | /// Collect (key, value) pairs from a parallel iterator into a | |
402 | /// hashmap. If multiple pairs correspond to the same key, then the | |
403 | /// ones produced earlier in the parallel iterator will be | |
404 | /// overwritten, just as with a sequential iterator. | |
6a06907d | 405 | impl<K, V, S> FromParallelIterator<(K, V)> for HashMap<K, V, S, Global> |
48663c56 XL |
406 | where |
407 | K: Eq + Hash + Send, | |
408 | V: Send, | |
409 | S: BuildHasher + Default, | |
410 | { | |
411 | fn from_par_iter<P>(par_iter: P) -> Self | |
412 | where | |
413 | P: IntoParallelIterator<Item = (K, V)>, | |
414 | { | |
415 | let mut map = HashMap::default(); | |
416 | map.par_extend(par_iter); | |
417 | map | |
418 | } | |
419 | } | |
420 | ||
421 | /// Extend a hash map with items from a parallel iterator. | |
6a06907d | 422 | impl<K, V, S, A> ParallelExtend<(K, V)> for HashMap<K, V, S, A> |
48663c56 XL |
423 | where |
424 | K: Eq + Hash + Send, | |
425 | V: Send, | |
426 | S: BuildHasher, | |
6a06907d | 427 | A: Allocator + Clone, |
48663c56 XL |
428 | { |
429 | fn par_extend<I>(&mut self, par_iter: I) | |
430 | where | |
431 | I: IntoParallelIterator<Item = (K, V)>, | |
432 | { | |
433 | extend(self, par_iter); | |
434 | } | |
435 | } | |
436 | ||
437 | /// Extend a hash map with copied items from a parallel iterator. | |
6a06907d | 438 | impl<'a, K, V, S, A> ParallelExtend<(&'a K, &'a V)> for HashMap<K, V, S, A> |
48663c56 XL |
439 | where |
440 | K: Copy + Eq + Hash + Sync, | |
441 | V: Copy + Sync, | |
442 | S: BuildHasher, | |
6a06907d | 443 | A: Allocator + Clone, |
48663c56 XL |
444 | { |
445 | fn par_extend<I>(&mut self, par_iter: I) | |
446 | where | |
447 | I: IntoParallelIterator<Item = (&'a K, &'a V)>, | |
448 | { | |
449 | extend(self, par_iter); | |
450 | } | |
451 | } | |
452 | ||
453 | // This is equal to the normal `HashMap` -- no custom advantage. | |
6a06907d | 454 | fn extend<K, V, S, A, I>(map: &mut HashMap<K, V, S, A>, par_iter: I) |
48663c56 XL |
455 | where |
456 | K: Eq + Hash, | |
457 | S: BuildHasher, | |
458 | I: IntoParallelIterator, | |
6a06907d XL |
459 | A: Allocator + Clone, |
460 | HashMap<K, V, S, A>: Extend<I::Item>, | |
48663c56 XL |
461 | { |
462 | let (list, len) = super::helpers::collect(par_iter); | |
463 | ||
464 | // Keys may be already present or show multiple times in the iterator. | |
465 | // Reserve the entire length if the map is empty. | |
466 | // Otherwise reserve half the length (rounded up), so the map | |
467 | // will only resize twice in the worst case. | |
468 | let reserve = if map.is_empty() { len } else { (len + 1) / 2 }; | |
469 | map.reserve(reserve); | |
470 | for vec in list { | |
471 | map.extend(vec); | |
472 | } | |
473 | } | |
474 | ||
475 | #[cfg(test)] | |
476 | mod test_par_map { | |
477 | use alloc::vec::Vec; | |
478 | use core::hash::{Hash, Hasher}; | |
479 | use core::sync::atomic::{AtomicUsize, Ordering}; | |
480 | ||
481 | use rayon::prelude::*; | |
482 | ||
483 | use crate::hash_map::HashMap; | |
484 | ||
485 | struct Dropable<'a> { | |
486 | k: usize, | |
487 | counter: &'a AtomicUsize, | |
488 | } | |
489 | ||
490 | impl Dropable<'_> { | |
491 | fn new(k: usize, counter: &AtomicUsize) -> Dropable<'_> { | |
492 | counter.fetch_add(1, Ordering::Relaxed); | |
493 | ||
494 | Dropable { k, counter } | |
495 | } | |
496 | } | |
497 | ||
498 | impl Drop for Dropable<'_> { | |
499 | fn drop(&mut self) { | |
500 | self.counter.fetch_sub(1, Ordering::Relaxed); | |
501 | } | |
502 | } | |
503 | ||
504 | impl Clone for Dropable<'_> { | |
505 | fn clone(&self) -> Self { | |
506 | Dropable::new(self.k, self.counter) | |
507 | } | |
508 | } | |
509 | ||
510 | impl Hash for Dropable<'_> { | |
511 | fn hash<H>(&self, state: &mut H) | |
512 | where | |
513 | H: Hasher, | |
514 | { | |
515 | self.k.hash(state) | |
516 | } | |
517 | } | |
518 | ||
519 | impl PartialEq for Dropable<'_> { | |
520 | fn eq(&self, other: &Self) -> bool { | |
521 | self.k == other.k | |
522 | } | |
523 | } | |
524 | ||
525 | impl Eq for Dropable<'_> {} | |
526 | ||
527 | #[test] | |
528 | fn test_into_iter_drops() { | |
529 | let key = AtomicUsize::new(0); | |
530 | let value = AtomicUsize::new(0); | |
531 | ||
532 | let hm = { | |
533 | let mut hm = HashMap::new(); | |
534 | ||
535 | assert_eq!(key.load(Ordering::Relaxed), 0); | |
536 | assert_eq!(value.load(Ordering::Relaxed), 0); | |
537 | ||
538 | for i in 0..100 { | |
539 | let d1 = Dropable::new(i, &key); | |
540 | let d2 = Dropable::new(i + 100, &value); | |
541 | hm.insert(d1, d2); | |
542 | } | |
543 | ||
544 | assert_eq!(key.load(Ordering::Relaxed), 100); | |
545 | assert_eq!(value.load(Ordering::Relaxed), 100); | |
546 | ||
547 | hm | |
548 | }; | |
549 | ||
550 | // By the way, ensure that cloning doesn't screw up the dropping. | |
551 | drop(hm.clone()); | |
552 | ||
553 | assert_eq!(key.load(Ordering::Relaxed), 100); | |
554 | assert_eq!(value.load(Ordering::Relaxed), 100); | |
555 | ||
556 | // Ensure that dropping the iterator does not leak anything. | |
557 | drop(hm.clone().into_par_iter()); | |
558 | ||
559 | { | |
560 | assert_eq!(key.load(Ordering::Relaxed), 100); | |
561 | assert_eq!(value.load(Ordering::Relaxed), 100); | |
562 | ||
563 | // retain only half | |
564 | let _v: Vec<_> = hm | |
565 | .into_par_iter() | |
566 | .filter(|&(ref key, _)| key.k < 50) | |
567 | .collect(); | |
568 | ||
569 | assert_eq!(key.load(Ordering::Relaxed), 50); | |
570 | assert_eq!(value.load(Ordering::Relaxed), 50); | |
571 | }; | |
572 | ||
573 | assert_eq!(key.load(Ordering::Relaxed), 0); | |
574 | assert_eq!(value.load(Ordering::Relaxed), 0); | |
575 | } | |
576 | ||
577 | #[test] | |
578 | fn test_drain_drops() { | |
579 | let key = AtomicUsize::new(0); | |
580 | let value = AtomicUsize::new(0); | |
581 | ||
582 | let mut hm = { | |
583 | let mut hm = HashMap::new(); | |
584 | ||
585 | assert_eq!(key.load(Ordering::Relaxed), 0); | |
586 | assert_eq!(value.load(Ordering::Relaxed), 0); | |
587 | ||
588 | for i in 0..100 { | |
589 | let d1 = Dropable::new(i, &key); | |
590 | let d2 = Dropable::new(i + 100, &value); | |
591 | hm.insert(d1, d2); | |
592 | } | |
593 | ||
594 | assert_eq!(key.load(Ordering::Relaxed), 100); | |
595 | assert_eq!(value.load(Ordering::Relaxed), 100); | |
596 | ||
597 | hm | |
598 | }; | |
599 | ||
600 | // By the way, ensure that cloning doesn't screw up the dropping. | |
601 | drop(hm.clone()); | |
602 | ||
603 | assert_eq!(key.load(Ordering::Relaxed), 100); | |
604 | assert_eq!(value.load(Ordering::Relaxed), 100); | |
605 | ||
606 | // Ensure that dropping the drain iterator does not leak anything. | |
607 | drop(hm.clone().par_drain()); | |
608 | ||
609 | { | |
610 | assert_eq!(key.load(Ordering::Relaxed), 100); | |
611 | assert_eq!(value.load(Ordering::Relaxed), 100); | |
612 | ||
613 | // retain only half | |
614 | let _v: Vec<_> = hm.drain().filter(|&(ref key, _)| key.k < 50).collect(); | |
615 | assert!(hm.is_empty()); | |
616 | ||
617 | assert_eq!(key.load(Ordering::Relaxed), 50); | |
618 | assert_eq!(value.load(Ordering::Relaxed), 50); | |
619 | }; | |
620 | ||
621 | assert_eq!(key.load(Ordering::Relaxed), 0); | |
622 | assert_eq!(value.load(Ordering::Relaxed), 0); | |
623 | } | |
624 | ||
625 | #[test] | |
626 | fn test_empty_iter() { | |
627 | let mut m: HashMap<isize, bool> = HashMap::new(); | |
628 | assert_eq!(m.par_drain().count(), 0); | |
629 | assert_eq!(m.par_keys().count(), 0); | |
630 | assert_eq!(m.par_values().count(), 0); | |
631 | assert_eq!(m.par_values_mut().count(), 0); | |
632 | assert_eq!(m.par_iter().count(), 0); | |
633 | assert_eq!(m.par_iter_mut().count(), 0); | |
634 | assert_eq!(m.len(), 0); | |
635 | assert!(m.is_empty()); | |
636 | assert_eq!(m.into_par_iter().count(), 0); | |
637 | } | |
638 | ||
639 | #[test] | |
640 | fn test_iterate() { | |
641 | let mut m = HashMap::with_capacity(4); | |
642 | for i in 0..32 { | |
643 | assert!(m.insert(i, i * 2).is_none()); | |
644 | } | |
645 | assert_eq!(m.len(), 32); | |
646 | ||
647 | let observed = AtomicUsize::new(0); | |
648 | ||
649 | m.par_iter().for_each(|(k, v)| { | |
650 | assert_eq!(*v, *k * 2); | |
651 | observed.fetch_or(1 << *k, Ordering::Relaxed); | |
652 | }); | |
653 | assert_eq!(observed.into_inner(), 0xFFFF_FFFF); | |
654 | } | |
655 | ||
656 | #[test] | |
657 | fn test_keys() { | |
658 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
659 | let map: HashMap<_, _> = vec.into_par_iter().collect(); | |
660 | let keys: Vec<_> = map.par_keys().cloned().collect(); | |
661 | assert_eq!(keys.len(), 3); | |
662 | assert!(keys.contains(&1)); | |
663 | assert!(keys.contains(&2)); | |
664 | assert!(keys.contains(&3)); | |
665 | } | |
666 | ||
667 | #[test] | |
668 | fn test_values() { | |
669 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
670 | let map: HashMap<_, _> = vec.into_par_iter().collect(); | |
671 | let values: Vec<_> = map.par_values().cloned().collect(); | |
672 | assert_eq!(values.len(), 3); | |
673 | assert!(values.contains(&'a')); | |
674 | assert!(values.contains(&'b')); | |
675 | assert!(values.contains(&'c')); | |
676 | } | |
677 | ||
678 | #[test] | |
679 | fn test_values_mut() { | |
680 | let vec = vec![(1, 1), (2, 2), (3, 3)]; | |
681 | let mut map: HashMap<_, _> = vec.into_par_iter().collect(); | |
682 | map.par_values_mut().for_each(|value| *value = (*value) * 2); | |
683 | let values: Vec<_> = map.par_values().cloned().collect(); | |
684 | assert_eq!(values.len(), 3); | |
685 | assert!(values.contains(&2)); | |
686 | assert!(values.contains(&4)); | |
687 | assert!(values.contains(&6)); | |
688 | } | |
689 | ||
690 | #[test] | |
691 | fn test_eq() { | |
692 | let mut m1 = HashMap::new(); | |
693 | m1.insert(1, 2); | |
694 | m1.insert(2, 3); | |
695 | m1.insert(3, 4); | |
696 | ||
697 | let mut m2 = HashMap::new(); | |
698 | m2.insert(1, 2); | |
699 | m2.insert(2, 3); | |
700 | ||
701 | assert!(!m1.par_eq(&m2)); | |
702 | ||
703 | m2.insert(3, 4); | |
704 | ||
705 | assert!(m1.par_eq(&m2)); | |
706 | } | |
707 | ||
708 | #[test] | |
709 | fn test_from_iter() { | |
710 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
711 | ||
712 | let map: HashMap<_, _> = xs.par_iter().cloned().collect(); | |
713 | ||
714 | for &(k, v) in &xs { | |
715 | assert_eq!(map.get(&k), Some(&v)); | |
716 | } | |
717 | } | |
718 | ||
719 | #[test] | |
720 | fn test_extend_ref() { | |
721 | let mut a = HashMap::new(); | |
722 | a.insert(1, "one"); | |
723 | let mut b = HashMap::new(); | |
724 | b.insert(2, "two"); | |
725 | b.insert(3, "three"); | |
726 | ||
727 | a.par_extend(&b); | |
728 | ||
729 | assert_eq!(a.len(), 3); | |
730 | assert_eq!(a[&1], "one"); | |
731 | assert_eq!(a[&2], "two"); | |
732 | assert_eq!(a[&3], "three"); | |
733 | } | |
734 | } |