1//! Contains the sparse secondary map implementation.
2
3#[cfg(all(nightly, any(doc, feature = "unstable")))]
4use alloc::collections::TryReserveError;
5#[allow(unused_imports)] // MaybeUninit is only used on nightly at the moment.
6use core::mem::MaybeUninit;
7use std::collections::hash_map::{self, HashMap};
8use std::hash;
9use std::iter::{Extend, FromIterator, FusedIterator};
10use std::marker::PhantomData;
11use std::ops::{Index, IndexMut};
12
13use super::{Key, KeyData};
14use crate::util::{is_older_version, UnwrapUnchecked};
15
16#[derive(Debug, Clone)]
17struct Slot<T> {
18 version: u32,
19 value: T,
20}
21
22/// Sparse secondary map, associate data with previously stored elements in a
23/// slot map.
24///
25/// A [`SparseSecondaryMap`] allows you to efficiently store additional
26/// information for each element in a slot map. You can have multiple secondary
27/// maps per slot map, but not multiple slot maps per secondary map. It is safe
28/// but unspecified behavior if you use keys from multiple different slot maps
29/// in the same [`SparseSecondaryMap`].
30///
31/// A [`SparseSecondaryMap`] does not leak memory even if you never remove
32/// elements. In return, when you remove a key from the primary slot map, after
33/// any insert the space associated with the removed element may be reclaimed.
34/// Don't expect the values associated with a removed key to stick around after
35/// an insertion has happened!
36///
37/// Unlike [`SecondaryMap`], the [`SparseSecondaryMap`] is backed by a
38/// [`HashMap`]. This means its access times are higher, but it uses less memory
39/// and iterates faster if there are only a few elements of the slot map in the
40/// secondary map. If most or all of the elements in a slot map are also found
41/// in the secondary map, use a [`SecondaryMap`] instead.
42///
43/// The current implementation of [`SparseSecondaryMap`] requires [`std`] and is
44/// thus not available in `no_std` environments.
45///
46/// [`SecondaryMap`]: crate::SecondaryMap
47/// [`HashMap`]: std::collections::HashMap
48///
49/// Example usage:
50///
51/// ```
52/// # use slotmap::*;
53/// let mut players = SlotMap::new();
54/// let mut health = SparseSecondaryMap::new();
55/// let mut ammo = SparseSecondaryMap::new();
56///
57/// let alice = players.insert("alice");
58/// let bob = players.insert("bob");
59///
60/// for p in players.keys() {
61/// health.insert(p, 100);
62/// ammo.insert(p, 30);
63/// }
64///
65/// // Alice attacks Bob with all her ammo!
66/// health[bob] -= ammo[alice] * 3;
67/// ammo[alice] = 0;
68/// ```
69
70#[derive(Debug, Clone)]
71pub struct SparseSecondaryMap<K: Key, V, S: hash::BuildHasher = hash_map::RandomState> {
72 slots: HashMap<u32, Slot<V>, S>,
73 _k: PhantomData<fn(K) -> K>,
74}
75
76impl<K: Key, V> SparseSecondaryMap<K, V, hash_map::RandomState> {
77 /// Constructs a new, empty [`SparseSecondaryMap`].
78 ///
79 /// # Examples
80 ///
81 /// ```
82 /// # use slotmap::*;
83 /// let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::new();
84 /// ```
85 pub fn new() -> Self {
86 Self::with_capacity(0)
87 }
88
89 /// Creates an empty [`SparseSecondaryMap`] with the given capacity of slots.
90 ///
91 /// The secondary map will not reallocate until it holds at least `capacity`
92 /// slots.
93 ///
94 /// # Examples
95 ///
96 /// ```
97 /// # use slotmap::*;
98 /// let mut sm: SlotMap<_, i32> = SlotMap::with_capacity(10);
99 /// let mut sec: SparseSecondaryMap<DefaultKey, i32> =
100 /// SparseSecondaryMap::with_capacity(sm.capacity());
101 /// ```
102 pub fn with_capacity(capacity: usize) -> Self {
103 Self {
104 slots: HashMap::with_capacity(capacity),
105 _k: PhantomData,
106 }
107 }
108}
109
110impl<K: Key, V, S: hash::BuildHasher> SparseSecondaryMap<K, V, S> {
111 /// Creates an empty [`SparseSecondaryMap`] which will use the given hash
112 /// builder to hash keys.
113 ///
114 /// The secondary map will not reallocate until it holds at least `capacity`
115 /// slots.
116 ///
117 /// # Examples
118 ///
119 /// ```
120 /// # use std::collections::hash_map::RandomState;
121 /// # use slotmap::*;
122 /// let mut sm: SlotMap<_, i32> = SlotMap::with_capacity(10);
123 /// let mut sec: SparseSecondaryMap<DefaultKey, i32, _> =
124 /// SparseSecondaryMap::with_hasher(RandomState::new());
125 /// ```
126 pub fn with_hasher(hash_builder: S) -> Self {
127 Self {
128 slots: HashMap::with_hasher(hash_builder),
129 _k: PhantomData,
130 }
131 }
132
133 /// Creates an empty [`SparseSecondaryMap`] with the given capacity of slots,
134 /// using `hash_builder` to hash the keys.
135 ///
136 /// The secondary map will not reallocate until it holds at least `capacity`
137 /// slots.
138 ///
139 /// # Examples
140 ///
141 /// ```
142 /// # use std::collections::hash_map::RandomState;
143 /// # use slotmap::*;
144 /// let mut sm: SlotMap<_, i32> = SlotMap::with_capacity(10);
145 /// let mut sec: SparseSecondaryMap<DefaultKey, i32, _> =
146 /// SparseSecondaryMap::with_capacity_and_hasher(10, RandomState::new());
147 /// ```
148 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
149 Self {
150 slots: HashMap::with_capacity_and_hasher(capacity, hash_builder),
151 _k: PhantomData,
152 }
153 }
154
155 /// Returns the number of elements in the secondary map.
156 ///
157 /// # Examples
158 ///
159 /// ```
160 /// # use slotmap::*;
161 /// let mut sm = SlotMap::new();
162 /// let k = sm.insert(4);
163 /// let mut squared = SparseSecondaryMap::new();
164 /// assert_eq!(squared.len(), 0);
165 /// squared.insert(k, 16);
166 /// assert_eq!(squared.len(), 1);
167 /// ```
168 pub fn len(&self) -> usize {
169 self.slots.len()
170 }
171
172 /// Returns if the secondary map is empty.
173 ///
174 /// # Examples
175 ///
176 /// ```
177 /// # use slotmap::*;
178 /// let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::new();
179 /// assert!(sec.is_empty());
180 /// ```
181 pub fn is_empty(&self) -> bool {
182 self.slots.is_empty()
183 }
184
185 /// Returns the number of elements the [`SparseSecondaryMap`] can hold without
186 /// reallocating.
187 ///
188 /// # Examples
189 ///
190 /// ```
191 /// # use slotmap::*;
192 /// let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::with_capacity(10);
193 /// assert!(sec.capacity() >= 10);
194 /// ```
195 pub fn capacity(&self) -> usize {
196 self.slots.capacity()
197 }
198
199 /// Reserves capacity for at least `additional` more slots in the
200 /// [`SparseSecondaryMap`]. The collection may reserve more space to avoid
201 /// frequent reallocations.
202 ///
203 /// # Panics
204 ///
205 /// Panics if the new allocation size overflows [`usize`].
206 ///
207 /// # Examples
208 ///
209 /// ```
210 /// # use slotmap::*;
211 /// let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::new();
212 /// sec.reserve(10);
213 /// assert!(sec.capacity() >= 10);
214 /// ```
215 pub fn reserve(&mut self, additional: usize) {
216 self.slots.reserve(additional);
217 }
218
219 /// Tries to reserve capacity for at least `additional` more slots in the
220 /// [`SparseSecondaryMap`]. The collection may reserve more space to avoid
221 /// frequent reallocations.
222 ///
223 /// # Examples
224 ///
225 /// ```
226 /// # use slotmap::*;
227 /// let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::new();
228 /// sec.try_reserve(10).unwrap();
229 /// assert!(sec.capacity() >= 10);
230 /// ```
231 #[cfg(all(nightly, any(doc, feature = "unstable")))]
232 #[cfg_attr(all(nightly, doc), doc(cfg(feature = "unstable")))]
233 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
234 self.slots.try_reserve(additional)
235 }
236
237 /// Returns [`true`] if the secondary map contains `key`.
238 ///
239 /// # Examples
240 ///
241 /// ```
242 /// # use slotmap::*;
243 /// let mut sm = SlotMap::new();
244 /// let k = sm.insert(4);
245 /// let mut squared = SparseSecondaryMap::new();
246 /// assert!(!squared.contains_key(k));
247 /// squared.insert(k, 16);
248 /// assert!(squared.contains_key(k));
249 /// ```
250 pub fn contains_key(&self, key: K) -> bool {
251 let kd = key.data();
252 self.slots.get(&kd.idx).map_or(false, |slot| slot.version == kd.version.get())
253 }
254
255 /// Inserts a value into the secondary map at the given `key`. Can silently
256 /// fail if `key` was removed from the originating slot map.
257 ///
258 /// Returns [`None`] if this key was not present in the map, the old value
259 /// otherwise.
260 ///
261 /// # Examples
262 ///
263 /// ```
264 /// # use slotmap::*;
265 /// let mut sm = SlotMap::new();
266 /// let k = sm.insert(4);
267 /// let mut squared = SparseSecondaryMap::new();
268 /// assert_eq!(squared.insert(k, 0), None);
269 /// assert_eq!(squared.insert(k, 4), Some(0));
270 /// // You don't have to use insert if the key is already in the secondary map.
271 /// squared[k] *= squared[k];
272 /// assert_eq!(squared[k], 16);
273 /// ```
274 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
275 if key.is_null() {
276 return None;
277 }
278
279 let kd = key.data();
280
281 if let Some(slot) = self.slots.get_mut(&kd.idx) {
282 if slot.version == kd.version.get() {
283 return Some(std::mem::replace(&mut slot.value, value));
284 }
285
286 // Don't replace existing newer values.
287 if is_older_version(kd.version.get(), slot.version) {
288 return None;
289 }
290
291 *slot = Slot {
292 version: kd.version.get(),
293 value,
294 };
295
296 return None;
297 }
298
299 self.slots.insert(kd.idx, Slot {
300 version: kd.version.get(),
301 value,
302 });
303
304 None
305 }
306
307 /// Removes a key from the secondary map, returning the value at the key if
308 /// the key was not previously removed. If `key` was removed from the
309 /// originating slot map, its corresponding entry in the secondary map may
310 /// or may not already be removed.
311 ///
312 /// # Examples
313 ///
314 /// ```
315 /// # use slotmap::*;
316 /// let mut sm = SlotMap::new();
317 /// let mut squared = SparseSecondaryMap::new();
318 /// let k = sm.insert(4);
319 /// squared.insert(k, 16);
320 /// squared.remove(k);
321 /// assert!(!squared.contains_key(k));
322 ///
323 /// // It's not necessary to remove keys deleted from the primary slot map, they
324 /// // get deleted automatically when their slots are reused on a subsequent insert.
325 /// squared.insert(k, 16);
326 /// sm.remove(k); // Remove k from the slot map, making an empty slot.
327 /// let new_k = sm.insert(2); // Since sm only has one empty slot, this reuses it.
328 /// assert!(!squared.contains_key(new_k)); // Space reuse does not mean equal keys.
329 /// assert!(squared.contains_key(k)); // Slot has not been reused in squared yet.
330 /// squared.insert(new_k, 4);
331 /// assert!(!squared.contains_key(k)); // Old key is no longer available.
332 /// ```
333 pub fn remove(&mut self, key: K) -> Option<V> {
334 let kd = key.data();
335
336 if let hash_map::Entry::Occupied(entry) = self.slots.entry(kd.idx) {
337 if entry.get().version == kd.version.get() {
338 return Some(entry.remove_entry().1.value);
339 }
340 }
341
342 None
343 }
344
345 /// Retains only the elements specified by the predicate.
346 ///
347 /// In other words, remove all key-value pairs `(k, v)` such that
348 /// `f(k, &mut v)` returns false. This method invalidates any removed keys.
349 ///
350 /// # Examples
351 ///
352 /// ```
353 /// # use slotmap::*;
354 /// let mut sm = SlotMap::new();
355 /// let mut sec = SparseSecondaryMap::new();
356 ///
357 /// let k1 = sm.insert(0); sec.insert(k1, 10);
358 /// let k2 = sm.insert(1); sec.insert(k2, 11);
359 /// let k3 = sm.insert(2); sec.insert(k3, 12);
360 ///
361 /// sec.retain(|key, val| key == k1 || *val == 11);
362 ///
363 /// assert!(sec.contains_key(k1));
364 /// assert!(sec.contains_key(k2));
365 /// assert!(!sec.contains_key(k3));
366 ///
367 /// assert_eq!(2, sec.len());
368 /// ```
369 pub fn retain<F>(&mut self, mut f: F)
370 where
371 F: FnMut(K, &mut V) -> bool,
372 {
373 self.slots.retain(|&idx, slot| {
374 let key = KeyData::new(idx, slot.version).into();
375 f(key, &mut slot.value)
376 })
377 }
378
379 /// Clears the secondary map. Keeps the allocated memory for reuse.
380 ///
381 /// # Examples
382 ///
383 /// ```
384 /// # use slotmap::*;
385 /// let mut sm = SlotMap::new();
386 /// let mut sec = SparseSecondaryMap::new();
387 /// for i in 0..10 {
388 /// sec.insert(sm.insert(i), i);
389 /// }
390 /// assert_eq!(sec.len(), 10);
391 /// sec.clear();
392 /// assert_eq!(sec.len(), 0);
393 /// ```
394 pub fn clear(&mut self) {
395 self.slots.clear();
396 }
397
398 /// Clears the slot map, returning all key-value pairs in arbitrary order as
399 /// an iterator. Keeps the allocated memory for reuse.
400 ///
401 /// When the iterator is dropped all elements in the slot map are removed,
402 /// even if the iterator was not fully consumed. If the iterator is not
403 /// dropped (using e.g. [`std::mem::forget`]), only the elements that were
404 /// iterated over are removed.
405 ///
406 /// # Examples
407 ///
408 /// ```
409 /// # use slotmap::*;
410 /// # use std::iter::FromIterator;
411 /// let mut sm = SlotMap::new();
412 /// let k = sm.insert(0);
413 /// let mut sec = SparseSecondaryMap::new();
414 /// sec.insert(k, 1);
415 /// let v: Vec<_> = sec.drain().collect();
416 /// assert_eq!(sec.len(), 0);
417 /// assert_eq!(v, vec![(k, 1)]);
418 /// ```
419 pub fn drain(&mut self) -> Drain<K, V> {
420 Drain {
421 inner: self.slots.drain(),
422 _k: PhantomData,
423 }
424 }
425
426 /// Returns a reference to the value corresponding to the key.
427 ///
428 /// # Examples
429 ///
430 /// ```
431 /// # use slotmap::*;
432 /// let mut sm = SlotMap::new();
433 /// let key = sm.insert("foo");
434 /// let mut sec = SparseSecondaryMap::new();
435 /// sec.insert(key, "bar");
436 /// assert_eq!(sec.get(key), Some(&"bar"));
437 /// sec.remove(key);
438 /// assert_eq!(sec.get(key), None);
439 /// ```
440 pub fn get(&self, key: K) -> Option<&V> {
441 let kd = key.data();
442 self.slots
443 .get(&kd.idx)
444 .filter(|slot| slot.version == kd.version.get())
445 .map(|slot| &slot.value)
446 }
447
448 /// Returns a reference to the value corresponding to the key without
449 /// version or bounds checking.
450 ///
451 /// # Safety
452 ///
453 /// This should only be used if `contains_key(key)` is true. Otherwise it is
454 /// potentially unsafe.
455 ///
456 /// # Examples
457 ///
458 /// ```
459 /// # use slotmap::*;
460 /// let mut sm = SlotMap::new();
461 /// let key = sm.insert("foo");
462 /// let mut sec = SparseSecondaryMap::new();
463 /// sec.insert(key, "bar");
464 /// assert_eq!(unsafe { sec.get_unchecked(key) }, &"bar");
465 /// sec.remove(key);
466 /// // sec.get_unchecked(key) is now dangerous!
467 /// ```
468 pub unsafe fn get_unchecked(&self, key: K) -> &V {
469 debug_assert!(self.contains_key(key));
470 self.get(key).unwrap_unchecked_()
471 }
472
473 /// Returns a mutable reference to the value corresponding to the key.
474 ///
475 /// # Examples
476 ///
477 /// ```
478 /// # use slotmap::*;
479 /// let mut sm = SlotMap::new();
480 /// let key = sm.insert("test");
481 /// let mut sec = SparseSecondaryMap::new();
482 /// sec.insert(key, 3.5);
483 /// if let Some(x) = sec.get_mut(key) {
484 /// *x += 3.0;
485 /// }
486 /// assert_eq!(sec[key], 6.5);
487 /// ```
488 pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
489 let kd = key.data();
490 self.slots
491 .get_mut(&kd.idx)
492 .filter(|slot| slot.version == kd.version.get())
493 .map(|slot| &mut slot.value)
494 }
495
496 /// Returns a mutable reference to the value corresponding to the key
497 /// without version or bounds checking.
498 ///
499 /// # Safety
500 ///
501 /// This should only be used if `contains_key(key)` is true. Otherwise it is
502 /// potentially unsafe.
503 ///
504 /// # Examples
505 ///
506 /// ```
507 /// # use slotmap::*;
508 /// let mut sm = SlotMap::new();
509 /// let key = sm.insert("foo");
510 /// let mut sec = SparseSecondaryMap::new();
511 /// sec.insert(key, "bar");
512 /// unsafe { *sec.get_unchecked_mut(key) = "baz" };
513 /// assert_eq!(sec[key], "baz");
514 /// sec.remove(key);
515 /// // sec.get_unchecked_mut(key) is now dangerous!
516 /// ```
517 pub unsafe fn get_unchecked_mut(&mut self, key: K) -> &mut V {
518 debug_assert!(self.contains_key(key));
519 self.get_mut(key).unwrap_unchecked_()
520 }
521
522 /// Returns mutable references to the values corresponding to the given
523 /// keys. All keys must be valid and disjoint, otherwise None is returned.
524 ///
525 /// Requires at least stable Rust version 1.51.
526 ///
527 /// # Examples
528 ///
529 /// ```
530 /// # use slotmap::*;
531 /// let mut sm = SlotMap::new();
532 /// let mut sec = SparseSecondaryMap::new();
533 /// let ka = sm.insert(()); sec.insert(ka, "butter");
534 /// let kb = sm.insert(()); sec.insert(kb, "apples");
535 /// let kc = sm.insert(()); sec.insert(kc, "charlie");
536 /// sec.remove(kc); // Make key c invalid.
537 /// assert_eq!(sec.get_disjoint_mut([ka, kb, kc]), None); // Has invalid key.
538 /// assert_eq!(sec.get_disjoint_mut([ka, ka]), None); // Not disjoint.
539 /// let [a, b] = sec.get_disjoint_mut([ka, kb]).unwrap();
540 /// std::mem::swap(a, b);
541 /// assert_eq!(sec[ka], "apples");
542 /// assert_eq!(sec[kb], "butter");
543 /// ```
544 #[cfg(has_min_const_generics)]
545 pub fn get_disjoint_mut<const N: usize>(&mut self, keys: [K; N]) -> Option<[&mut V; N]> {
546 // Create an uninitialized array of `MaybeUninit`. The `assume_init` is
547 // safe because the type we are claiming to have initialized here is a
548 // bunch of `MaybeUninit`s, which do not require initialization.
549 let mut ptrs: [MaybeUninit<*mut V>; N] = unsafe { MaybeUninit::uninit().assume_init() };
550
551 let mut i = 0;
552 while i < N {
553 let kd = keys[i].data();
554
555 match self.slots.get_mut(&kd.idx) {
556 Some(Slot { version, value }) if *version == kd.version.get() => {
557 // This key is valid, and the slot is occupied. Temporarily
558 // make the version even so duplicate keys would show up as
559 // invalid, since keys always have an odd version. This
560 // gives us a linear time disjointness check.
561 ptrs[i] = MaybeUninit::new(&mut *value);
562 *version ^= 1;
563 },
564
565 _ => break,
566 }
567
568 i += 1;
569 }
570
571 // Undo temporary even versions.
572 for k in &keys[0..i] {
573 match self.slots.get_mut(&k.data().idx) {
574 Some(Slot { version, .. }) => {
575 *version ^= 1;
576 },
577 _ => unsafe { core::hint::unreachable_unchecked() },
578 }
579 }
580
581 if i == N {
582 // All were valid and disjoint.
583 Some(unsafe { core::mem::transmute_copy::<_, [&mut V; N]>(&ptrs) })
584 } else {
585 None
586 }
587 }
588
589 /// Returns mutable references to the values corresponding to the given
590 /// keys. All keys must be valid and disjoint.
591 ///
592 /// Requires at least stable Rust version 1.51.
593 ///
594 /// # Safety
595 ///
596 /// This should only be used if `contains_key(key)` is true for every given
597 /// key and no two keys are equal. Otherwise it is potentially unsafe.
598 ///
599 /// # Examples
600 ///
601 /// ```
602 /// # use slotmap::*;
603 /// let mut sm = SlotMap::new();
604 /// let mut sec = SparseSecondaryMap::new();
605 /// let ka = sm.insert(()); sec.insert(ka, "butter");
606 /// let kb = sm.insert(()); sec.insert(kb, "apples");
607 /// let [a, b] = unsafe { sec.get_disjoint_unchecked_mut([ka, kb]) };
608 /// std::mem::swap(a, b);
609 /// assert_eq!(sec[ka], "apples");
610 /// assert_eq!(sec[kb], "butter");
611 /// ```
612 #[cfg(has_min_const_generics)]
613 pub unsafe fn get_disjoint_unchecked_mut<const N: usize>(
614 &mut self,
615 keys: [K; N],
616 ) -> [&mut V; N] {
617 // Safe, see get_disjoint_mut.
618 let mut ptrs: [MaybeUninit<*mut V>; N] = MaybeUninit::uninit().assume_init();
619 for i in 0..N {
620 ptrs[i] = MaybeUninit::new(self.get_unchecked_mut(keys[i]));
621 }
622 core::mem::transmute_copy::<_, [&mut V; N]>(&ptrs)
623 }
624
625 /// An iterator visiting all key-value pairs in arbitrary order. The
626 /// iterator element type is `(K, &'a V)`.
627 ///
628 /// This function must iterate over all slots, empty or not. In the face of
629 /// many deleted elements it can be inefficient.
630 ///
631 /// # Examples
632 ///
633 /// ```
634 /// # use slotmap::*;
635 /// let mut sm = SlotMap::new();
636 /// let mut sec = SparseSecondaryMap::new();
637 /// let k0 = sm.insert(0); sec.insert(k0, 10);
638 /// let k1 = sm.insert(1); sec.insert(k1, 11);
639 /// let k2 = sm.insert(2); sec.insert(k2, 12);
640 ///
641 /// for (k, v) in sec.iter() {
642 /// println!("key: {:?}, val: {}", k, v);
643 /// }
644 /// ```
645 pub fn iter(&self) -> Iter<K, V> {
646 Iter {
647 inner: self.slots.iter(),
648 _k: PhantomData,
649 }
650 }
651
652 /// An iterator visiting all key-value pairs in arbitrary order, with
653 /// mutable references to the values. The iterator element type is
654 /// `(K, &'a mut V)`.
655 ///
656 /// This function must iterate over all slots, empty or not. In the face of
657 /// many deleted elements it can be inefficient.
658 ///
659 /// # Examples
660 ///
661 /// ```
662 /// # use slotmap::*;
663 /// let mut sm = SlotMap::new();
664 /// let mut sec = SparseSecondaryMap::new();
665 /// let k0 = sm.insert(1); sec.insert(k0, 10);
666 /// let k1 = sm.insert(2); sec.insert(k1, 20);
667 /// let k2 = sm.insert(3); sec.insert(k2, 30);
668 ///
669 /// for (k, v) in sec.iter_mut() {
670 /// if k != k1 {
671 /// *v *= -1;
672 /// }
673 /// }
674 ///
675 /// assert_eq!(sec[k0], -10);
676 /// assert_eq!(sec[k1], 20);
677 /// assert_eq!(sec[k2], -30);
678 /// ```
679 pub fn iter_mut(&mut self) -> IterMut<K, V> {
680 IterMut {
681 inner: self.slots.iter_mut(),
682 _k: PhantomData,
683 }
684 }
685
686 /// An iterator visiting all keys in arbitrary order. The iterator element
687 /// type is `K`.
688 ///
689 /// This function must iterate over all slots, empty or not. In the face of
690 /// many deleted elements it can be inefficient.
691 ///
692 /// # Examples
693 ///
694 /// ```
695 /// # use slotmap::*;
696 /// # use std::collections::HashSet;
697 /// let mut sm = SlotMap::new();
698 /// let mut sec = SparseSecondaryMap::new();
699 /// let k0 = sm.insert(1); sec.insert(k0, 10);
700 /// let k1 = sm.insert(2); sec.insert(k1, 20);
701 /// let k2 = sm.insert(3); sec.insert(k2, 30);
702 /// let keys: HashSet<_> = sec.keys().collect();
703 /// let check: HashSet<_> = vec![k0, k1, k2].into_iter().collect();
704 /// assert_eq!(keys, check);
705 /// ```
706 pub fn keys(&self) -> Keys<K, V> {
707 Keys { inner: self.iter() }
708 }
709
710 /// An iterator visiting all values in arbitrary order. The iterator element
711 /// type is `&'a V`.
712 ///
713 /// This function must iterate over all slots, empty or not. In the face of
714 /// many deleted elements it can be inefficient.
715 ///
716 /// # Examples
717 ///
718 /// ```
719 /// # use slotmap::*;
720 /// # use std::collections::HashSet;
721 /// let mut sm = SlotMap::new();
722 /// let mut sec = SparseSecondaryMap::new();
723 /// let k0 = sm.insert(1); sec.insert(k0, 10);
724 /// let k1 = sm.insert(2); sec.insert(k1, 20);
725 /// let k2 = sm.insert(3); sec.insert(k2, 30);
726 /// let values: HashSet<_> = sec.values().collect();
727 /// let check: HashSet<_> = vec![&10, &20, &30].into_iter().collect();
728 /// assert_eq!(values, check);
729 /// ```
730 pub fn values(&self) -> Values<K, V> {
731 Values { inner: self.iter() }
732 }
733
734 /// An iterator visiting all values mutably in arbitrary order. The iterator
735 /// element type is `&'a mut V`.
736 ///
737 /// This function must iterate over all slots, empty or not. In the face of
738 /// many deleted elements it can be inefficient.
739 ///
740 /// # Examples
741 ///
742 /// ```
743 /// # use slotmap::*;
744 /// # use std::collections::HashSet;
745 /// let mut sm = SlotMap::new();
746 /// let mut sec = SparseSecondaryMap::new();
747 /// sec.insert(sm.insert(1), 10);
748 /// sec.insert(sm.insert(2), 20);
749 /// sec.insert(sm.insert(3), 30);
750 /// sec.values_mut().for_each(|n| { *n *= 3 });
751 /// let values: HashSet<_> = sec.into_iter().map(|(_k, v)| v).collect();
752 /// let check: HashSet<_> = vec![30, 60, 90].into_iter().collect();
753 /// assert_eq!(values, check);
754 /// ```
755 pub fn values_mut(&mut self) -> ValuesMut<K, V> {
756 ValuesMut {
757 inner: self.iter_mut(),
758 }
759 }
760
761 /// Gets the given key's corresponding [`Entry`] in the map for in-place
762 /// manipulation. May return [`None`] if the key was removed from the
763 /// originating slot map.
764 ///
765 /// # Examples
766 ///
767 /// ```
768 /// # use slotmap::*;
769 /// let mut sm = SlotMap::new();
770 /// let mut sec = SparseSecondaryMap::new();
771 /// let k = sm.insert(1);
772 /// let v = sec.entry(k).unwrap().or_insert(10);
773 /// assert_eq!(*v, 10);
774 /// ```
775 pub fn entry(&mut self, key: K) -> Option<Entry<K, V>> {
776 if key.is_null() {
777 return None;
778 }
779
780 let kd = key.data();
781
782 // Until we can map an OccupiedEntry to a VacantEntry I don't think
783 // there is a way to avoid this extra lookup.
784 if let hash_map::Entry::Occupied(o) = self.slots.entry(kd.idx) {
785 if o.get().version != kd.version.get() {
786 // Which is outdated, our key or the slot?
787 if is_older_version(o.get().version, kd.version.get()) {
788 o.remove();
789 } else {
790 return None;
791 }
792 }
793 }
794
795 Some(match self.slots.entry(kd.idx) {
796 hash_map::Entry::Occupied(inner) => {
797 // We know for certain that this entry's key matches ours due
798 // to the previous if block.
799 Entry::Occupied(OccupiedEntry {
800 inner,
801 kd,
802 _k: PhantomData,
803 })
804 },
805 hash_map::Entry::Vacant(inner) => Entry::Vacant(VacantEntry {
806 inner,
807 kd,
808 _k: PhantomData,
809 }),
810 })
811 }
812}
813
814impl<K, V, S> Default for SparseSecondaryMap<K, V, S>
815where
816 K: Key,
817 S: hash::BuildHasher + Default,
818{
819 fn default() -> Self {
820 Self::with_hasher(hash_builder:Default::default())
821 }
822}
823
824impl<K, V, S> Index<K> for SparseSecondaryMap<K, V, S>
825where
826 K: Key,
827 S: hash::BuildHasher,
828{
829 type Output = V;
830
831 fn index(&self, key: K) -> &V {
832 match self.get(key) {
833 Some(r: &V) => r,
834 None => panic!("invalid SparseSecondaryMap key used"),
835 }
836 }
837}
838
839impl<K, V, S> IndexMut<K> for SparseSecondaryMap<K, V, S>
840where
841 K: Key,
842 S: hash::BuildHasher,
843{
844 fn index_mut(&mut self, key: K) -> &mut V {
845 match self.get_mut(key) {
846 Some(r: &mut V) => r,
847 None => panic!("invalid SparseSecondaryMap key used"),
848 }
849 }
850}
851
852impl<K, V, S> PartialEq for SparseSecondaryMap<K, V, S>
853where
854 K: Key,
855 V: PartialEq,
856 S: hash::BuildHasher,
857{
858 fn eq(&self, other: &Self) -> bool {
859 if self.len() != other.len() {
860 return false;
861 }
862
863 self.iter()
864 .all(|(key: K, value: &V)| other.get(key).map_or(default:false, |other_value: &V| *value == *other_value))
865 }
866}
867
868impl<K, V, S> Eq for SparseSecondaryMap<K, V, S>
869where
870 K: Key,
871 V: Eq,
872 S: hash::BuildHasher,
873{
874}
875
876impl<K, V, S> FromIterator<(K, V)> for SparseSecondaryMap<K, V, S>
877where
878 K: Key,
879 S: hash::BuildHasher + Default,
880{
881 fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
882 let mut sec: SparseSecondaryMap = Self::default();
883 sec.extend(iter);
884 sec
885 }
886}
887
888impl<K, V, S> Extend<(K, V)> for SparseSecondaryMap<K, V, S>
889where
890 K: Key,
891 S: hash::BuildHasher,
892{
893 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
894 let iter: ::IntoIter = iter.into_iter();
895 for (k: K, v: V) in iter {
896 self.insert(key:k, value:v);
897 }
898 }
899}
900
901impl<'a, K, V, S> Extend<(K, &'a V)> for SparseSecondaryMap<K, V, S>
902where
903 K: Key,
904 V: 'a + Copy,
905 S: hash::BuildHasher,
906{
907 fn extend<I: IntoIterator<Item = (K, &'a V)>>(&mut self, iter: I) {
908 let iter: ::IntoIter = iter.into_iter();
909 for (k: K, v: &'a V) in iter {
910 self.insert(key:k, *v);
911 }
912 }
913}
914
915/// A view into a occupied entry in a [`SparseSecondaryMap`]. It is part of the
916/// [`Entry`] enum.
917#[derive(Debug)]
918pub struct OccupiedEntry<'a, K: Key, V> {
919 inner: hash_map::OccupiedEntry<'a, u32, Slot<V>>,
920 kd: KeyData,
921 _k: PhantomData<fn(K) -> K>,
922}
923
924/// A view into a vacant entry in a [`SparseSecondaryMap`]. It is part of the
925/// [`Entry`] enum.
926#[derive(Debug)]
927pub struct VacantEntry<'a, K: Key, V> {
928 inner: hash_map::VacantEntry<'a, u32, Slot<V>>,
929 kd: KeyData,
930 _k: PhantomData<fn(K) -> K>,
931}
932
933/// A view into a single entry in a [`SparseSecondaryMap`], which may either be
934/// vacant or occupied.
935///
936/// This `enum` is constructed using [`SparseSecondaryMap::entry`].
937#[derive(Debug)]
938pub enum Entry<'a, K: Key, V> {
939 /// An occupied entry.
940 Occupied(OccupiedEntry<'a, K, V>),
941
942 /// A vacant entry.
943 Vacant(VacantEntry<'a, K, V>),
944}
945
946impl<'a, K: Key, V> Entry<'a, K, V> {
947 /// Ensures a value is in the entry by inserting the default if empty, and
948 /// returns a mutable reference to the value in the entry.
949 ///
950 /// # Examples
951 ///
952 /// ```
953 /// # use slotmap::*;
954 /// let mut sm = SlotMap::new();
955 /// let mut sec = SparseSecondaryMap::new();
956 ///
957 /// let k = sm.insert("poneyland");
958 /// let v = sec.entry(k).unwrap().or_insert(10);
959 /// assert_eq!(*v, 10);
960 /// *sec.entry(k).unwrap().or_insert(1) *= 2;
961 /// assert_eq!(sec[k], 20);
962 /// ```
963 pub fn or_insert(self, default: V) -> &'a mut V {
964 self.or_insert_with(|| default)
965 }
966
967 /// Ensures a value is in the entry by inserting the result of the default
968 /// function if empty, and returns a mutable reference to the value in the
969 /// entry.
970 ///
971 /// # Examples
972 ///
973 /// ```
974 /// # use slotmap::*;
975 /// let mut sm = SlotMap::new();
976 /// let mut sec = SparseSecondaryMap::new();
977 ///
978 /// let k = sm.insert(1);
979 /// let v = sec.entry(k).unwrap().or_insert_with(|| "foobar".to_string());
980 /// assert_eq!(v, &"foobar");
981 /// ```
982 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
983 match self {
984 Entry::Occupied(x) => x.into_mut(),
985 Entry::Vacant(x) => x.insert(default()),
986 }
987 }
988
989 /// Returns this entry's key.
990 ///
991 /// # Examples
992 ///
993 /// ```
994 /// # use slotmap::*;
995 /// let mut sm = SlotMap::new();
996 /// let mut sec: SparseSecondaryMap<_, ()> = SparseSecondaryMap::new();
997 ///
998 /// let k = sm.insert(1);
999 /// let entry = sec.entry(k).unwrap();
1000 /// assert_eq!(entry.key(), k);
1001 /// ```
1002 pub fn key(&self) -> K {
1003 match self {
1004 Entry::Occupied(entry) => entry.kd.into(),
1005 Entry::Vacant(entry) => entry.kd.into(),
1006 }
1007 }
1008
1009 /// Provides in-place mutable access to an occupied entry before any
1010 /// potential inserts into the map.
1011 ///
1012 /// # Examples
1013 ///
1014 /// ```
1015 /// # use slotmap::*;
1016 /// let mut sm = SlotMap::new();
1017 /// let mut sec = SparseSecondaryMap::new();
1018 ///
1019 /// let k = sm.insert(1);
1020 /// sec.insert(k, 0);
1021 /// sec.entry(k).unwrap().and_modify(|x| *x = 1);
1022 ///
1023 /// assert_eq!(sec[k], 1)
1024 /// ```
1025 pub fn and_modify<F>(self, f: F) -> Self
1026 where
1027 F: FnOnce(&mut V),
1028 {
1029 match self {
1030 Entry::Occupied(mut entry) => {
1031 f(entry.get_mut());
1032 Entry::Occupied(entry)
1033 },
1034 Entry::Vacant(entry) => Entry::Vacant(entry),
1035 }
1036 }
1037}
1038
1039impl<'a, K: Key, V: Default> Entry<'a, K, V> {
1040 /// Ensures a value is in the entry by inserting the default value if empty,
1041 /// and returns a mutable reference to the value in the entry.
1042 ///
1043 /// # Examples
1044 ///
1045 /// ```
1046 /// # use slotmap::*;
1047 /// let mut sm = SlotMap::new();
1048 /// let mut sec: SparseSecondaryMap<_, Option<i32>> = SparseSecondaryMap::new();
1049 ///
1050 /// let k = sm.insert(1);
1051 /// sec.entry(k).unwrap().or_default();
1052 /// assert_eq!(sec[k], None)
1053 /// ```
1054 pub fn or_default(self) -> &'a mut V {
1055 self.or_insert_with(Default::default)
1056 }
1057}
1058
1059impl<'a, K: Key, V> OccupiedEntry<'a, K, V> {
1060 /// Returns this entry's key.
1061 ///
1062 /// # Examples
1063 ///
1064 /// ```
1065 /// # use slotmap::*;
1066 /// let mut sm = SlotMap::new();
1067 /// let mut sec = SparseSecondaryMap::new();
1068 ///
1069 /// let k = sm.insert(1);
1070 /// sec.insert(k, 10);
1071 /// assert_eq!(sec.entry(k).unwrap().key(), k);
1072 /// ```
1073 pub fn key(&self) -> K {
1074 self.kd.into()
1075 }
1076
1077 /// Removes the entry from the slot map and returns the key and value.
1078 ///
1079 /// # Examples
1080 ///
1081 /// ```
1082 /// # use slotmap::*;
1083 /// # use slotmap::sparse_secondary::Entry;
1084 /// let mut sm = SlotMap::new();
1085 /// let mut sec = SparseSecondaryMap::new();
1086 ///
1087 /// let foo = sm.insert("foo");
1088 /// sec.entry(foo).unwrap().or_insert("bar");
1089 ///
1090 /// if let Some(Entry::Occupied(o)) = sec.entry(foo) {
1091 /// assert_eq!(o.remove_entry(), (foo, "bar"));
1092 /// }
1093 /// assert_eq!(sec.contains_key(foo), false);
1094 /// ```
1095 pub fn remove_entry(self) -> (K, V) {
1096 (self.kd.into(), self.remove())
1097 }
1098
1099 /// Gets a reference to the value in the entry.
1100 ///
1101 /// # Examples
1102 ///
1103 /// ```
1104 /// # use slotmap::*;
1105 /// # use slotmap::sparse_secondary::Entry;
1106 /// let mut sm = SlotMap::new();
1107 /// let mut sec = SparseSecondaryMap::new();
1108 ///
1109 /// let k = sm.insert(1);
1110 /// sec.insert(k, 10);
1111 ///
1112 /// if let Entry::Occupied(o) = sec.entry(k).unwrap() {
1113 /// assert_eq!(*o.get(), 10);
1114 /// }
1115 /// ```
1116 pub fn get(&self) -> &V {
1117 &self.inner.get().value
1118 }
1119
1120 /// Gets a mutable reference to the value in the entry.
1121 ///
1122 /// If you need a reference to the [`OccupiedEntry`] which may outlive the
1123 /// destruction of the [`Entry`] value, see [`into_mut`].
1124 ///
1125 /// # Examples
1126 ///
1127 /// ```
1128 /// # use slotmap::*;
1129 /// # use slotmap::sparse_secondary::Entry;
1130 /// let mut sm = SlotMap::new();
1131 /// let mut sec = SparseSecondaryMap::new();
1132 ///
1133 /// let k = sm.insert(1);
1134 /// sec.insert(k, 10);
1135 /// if let Entry::Occupied(mut o) = sec.entry(k).unwrap() {
1136 /// *o.get_mut() = 20;
1137 /// }
1138 /// assert_eq!(sec[k], 20);
1139 /// ```
1140 ///
1141 /// [`into_mut`]: Self::into_mut
1142 pub fn get_mut(&mut self) -> &mut V {
1143 &mut self.inner.get_mut().value
1144 }
1145
1146 /// Converts the [`OccupiedEntry`] into a mutable reference to the value in
1147 /// the entry with a lifetime bound to the map itself.
1148 ///
1149 /// If you need multiple references to the [`OccupiedEntry`], see
1150 /// [`get_mut`].
1151 ///
1152 /// # Examples
1153 ///
1154 /// ```
1155 /// # use slotmap::*;
1156 /// # use slotmap::sparse_secondary::Entry;
1157 /// let mut sm = SlotMap::new();
1158 /// let mut sec = SparseSecondaryMap::new();
1159 ///
1160 /// let k = sm.insert(0);
1161 /// sec.insert(k, 0);
1162 ///
1163 /// let r;
1164 /// if let Entry::Occupied(o) = sec.entry(k).unwrap() {
1165 /// r = o.into_mut(); // v outlives the entry.
1166 /// } else {
1167 /// r = sm.get_mut(k).unwrap();
1168 /// }
1169 /// *r = 1;
1170 /// assert_eq!((sm[k], sec[k]), (0, 1));
1171 /// ```
1172 ///
1173 /// [`get_mut`]: Self::get_mut
1174 pub fn into_mut(self) -> &'a mut V {
1175 &mut self.inner.into_mut().value
1176 }
1177
1178 /// Sets the value of the entry, and returns the entry's old value.
1179 ///
1180 /// # Examples
1181 ///
1182 /// ```
1183 /// # use slotmap::*;
1184 /// # use slotmap::sparse_secondary::Entry;
1185 /// let mut sm = SlotMap::new();
1186 /// let mut sec = SparseSecondaryMap::new();
1187 ///
1188 /// let k = sm.insert(1);
1189 /// sec.insert(k, 10);
1190 ///
1191 /// if let Entry::Occupied(mut o) = sec.entry(k).unwrap() {
1192 /// let v = o.insert(20);
1193 /// assert_eq!(v, 10);
1194 /// assert_eq!(*o.get(), 20);
1195 /// }
1196 /// ```
1197 pub fn insert(&mut self, value: V) -> V {
1198 std::mem::replace(self.get_mut(), value)
1199 }
1200
1201 /// Takes the value out of the entry, and returns it.
1202 ///
1203 /// # Examples
1204 ///
1205 /// ```
1206 /// # use slotmap::*;
1207 /// # use slotmap::sparse_secondary::Entry;
1208 ///
1209 /// let mut sm = SlotMap::new();
1210 /// let mut sec = SparseSecondaryMap::new();
1211 ///
1212 /// let k = sm.insert(1);
1213 /// sec.insert(k, 10);
1214 ///
1215 /// if let Entry::Occupied(mut o) = sec.entry(k).unwrap() {
1216 /// assert_eq!(o.remove(), 10);
1217 /// assert_eq!(sec.contains_key(k), false);
1218 /// }
1219 /// ```
1220 pub fn remove(self) -> V {
1221 self.inner.remove().value
1222 }
1223}
1224
1225impl<'a, K: Key, V> VacantEntry<'a, K, V> {
1226 /// Gets the key that would be used when inserting a value through the
1227 /// [`VacantEntry`].
1228 ///
1229 /// # Examples
1230 ///
1231 /// ```
1232 /// # use slotmap::*;
1233 /// # use slotmap::sparse_secondary::Entry;
1234 ///
1235 /// let mut sm = SlotMap::new();
1236 /// let mut sec: SparseSecondaryMap<_, ()> = SparseSecondaryMap::new();
1237 ///
1238 /// let k = sm.insert(1);
1239 ///
1240 /// if let Entry::Vacant(v) = sec.entry(k).unwrap() {
1241 /// assert_eq!(v.key(), k);
1242 /// }
1243 /// ```
1244 pub fn key(&self) -> K {
1245 self.kd.into()
1246 }
1247
1248 /// Sets the value of the entry with the [`VacantEntry`]'s key, and returns
1249 /// a mutable reference to it.
1250 ///
1251 /// # Examples
1252 ///
1253 /// ```
1254 /// # use slotmap::*;
1255 /// # use slotmap::sparse_secondary::Entry;
1256 ///
1257 /// let mut sm = SlotMap::new();
1258 /// let mut sec = SparseSecondaryMap::new();
1259 ///
1260 /// let k = sm.insert(1);
1261 ///
1262 /// if let Entry::Vacant(v) = sec.entry(k).unwrap() {
1263 /// let new_val = v.insert(3);
1264 /// assert_eq!(new_val, &mut 3);
1265 /// }
1266 /// ```
1267 pub fn insert(self, value: V) -> &'a mut V {
1268 &mut self
1269 .inner
1270 .insert(Slot {
1271 version: self.kd.version.get(),
1272 value,
1273 })
1274 .value
1275 }
1276}
1277
1278// Iterators.
1279/// A draining iterator for [`SparseSecondaryMap`].
1280///
1281/// This iterator is created by [`SparseSecondaryMap::drain`].
1282#[derive(Debug)]
1283pub struct Drain<'a, K: Key + 'a, V: 'a> {
1284 inner: hash_map::Drain<'a, u32, Slot<V>>,
1285 _k: PhantomData<fn(K) -> K>,
1286}
1287
1288/// An iterator that moves key-value pairs out of a [`SparseSecondaryMap`].
1289///
1290/// This iterator is created by calling the `into_iter` method on [`SparseSecondaryMap`],
1291/// provided by the [`IntoIterator`] trait.
1292#[derive(Debug)]
1293pub struct IntoIter<K: Key, V> {
1294 inner: hash_map::IntoIter<u32, Slot<V>>,
1295 _k: PhantomData<fn(K) -> K>,
1296}
1297
1298/// An iterator over the key-value pairs in a [`SparseSecondaryMap`].
1299///
1300/// This iterator is created by [`SparseSecondaryMap::iter`].
1301#[derive(Debug)]
1302pub struct Iter<'a, K: Key + 'a, V: 'a> {
1303 inner: hash_map::Iter<'a, u32, Slot<V>>,
1304 _k: PhantomData<fn(K) -> K>,
1305}
1306
1307impl<'a, K: 'a + Key, V: 'a> Clone for Iter<'a, K, V> {
1308 fn clone(&self) -> Self {
1309 Iter {
1310 inner: self.inner.clone(),
1311 _k: self._k,
1312 }
1313 }
1314}
1315
1316/// A mutable iterator over the key-value pairs in a [`SparseSecondaryMap`].
1317///
1318/// This iterator is created by [`SparseSecondaryMap::iter_mut`].
1319#[derive(Debug)]
1320pub struct IterMut<'a, K: Key + 'a, V: 'a> {
1321 inner: hash_map::IterMut<'a, u32, Slot<V>>,
1322 _k: PhantomData<fn(K) -> K>,
1323}
1324
1325/// An iterator over the keys in a [`SparseSecondaryMap`].
1326///
1327/// This iterator is created by [`SparseSecondaryMap::keys`].
1328#[derive(Debug)]
1329pub struct Keys<'a, K: Key + 'a, V: 'a> {
1330 inner: Iter<'a, K, V>,
1331}
1332
1333impl<'a, K: 'a + Key, V: 'a> Clone for Keys<'a, K, V> {
1334 fn clone(&self) -> Self {
1335 Keys {
1336 inner: self.inner.clone(),
1337 }
1338 }
1339}
1340
1341/// An iterator over the values in a [`SparseSecondaryMap`].
1342///
1343/// This iterator is created by [`SparseSecondaryMap::values`].
1344#[derive(Debug)]
1345pub struct Values<'a, K: Key + 'a, V: 'a> {
1346 inner: Iter<'a, K, V>,
1347}
1348
1349impl<'a, K: 'a + Key, V: 'a> Clone for Values<'a, K, V> {
1350 fn clone(&self) -> Self {
1351 Values {
1352 inner: self.inner.clone(),
1353 }
1354 }
1355}
1356
1357/// A mutable iterator over the values in a [`SparseSecondaryMap`].
1358///
1359/// This iterator is created by [`SparseSecondaryMap::values_mut`].
1360#[derive(Debug)]
1361pub struct ValuesMut<'a, K: Key + 'a, V: 'a> {
1362 inner: IterMut<'a, K, V>,
1363}
1364
1365impl<'a, K: Key, V> Iterator for Drain<'a, K, V> {
1366 type Item = (K, V);
1367
1368 fn next(&mut self) -> Option<(K, V)> {
1369 self.inner.next().map(|(idx: u32, slot: Slot)| {
1370 let key: K = KeyData::new(idx, slot.version).into();
1371 (key, slot.value)
1372 })
1373 }
1374
1375 fn size_hint(&self) -> (usize, Option<usize>) {
1376 self.inner.size_hint()
1377 }
1378}
1379
1380impl<'a, K: Key, V> Drop for Drain<'a, K, V> {
1381 fn drop(&mut self) {
1382 self.for_each(|_drop: (K, V)| {});
1383 }
1384}
1385
1386impl<K: Key, V> Iterator for IntoIter<K, V> {
1387 type Item = (K, V);
1388
1389 fn next(&mut self) -> Option<(K, V)> {
1390 self.inner.next().map(|(idx: u32, slot: Slot)| {
1391 let key: K = KeyData::new(idx, slot.version).into();
1392 (key, slot.value)
1393 })
1394 }
1395
1396 fn size_hint(&self) -> (usize, Option<usize>) {
1397 self.inner.size_hint()
1398 }
1399}
1400
1401impl<'a, K: Key, V> Iterator for Iter<'a, K, V> {
1402 type Item = (K, &'a V);
1403
1404 fn next(&mut self) -> Option<(K, &'a V)> {
1405 self.inner.next().map(|(&idx: u32, slot: &'a Slot)| {
1406 let key: K = KeyData::new(idx, slot.version).into();
1407 (key, &slot.value)
1408 })
1409 }
1410
1411 fn size_hint(&self) -> (usize, Option<usize>) {
1412 self.inner.size_hint()
1413 }
1414}
1415
1416impl<'a, K: Key, V> Iterator for IterMut<'a, K, V> {
1417 type Item = (K, &'a mut V);
1418
1419 fn next(&mut self) -> Option<(K, &'a mut V)> {
1420 self.inner.next().map(|(&idx: u32, slot: &'a mut Slot)| {
1421 let key: K = KeyData::new(idx, slot.version).into();
1422 (key, &mut slot.value)
1423 })
1424 }
1425
1426 fn size_hint(&self) -> (usize, Option<usize>) {
1427 self.inner.size_hint()
1428 }
1429}
1430
1431impl<'a, K: Key, V> Iterator for Keys<'a, K, V> {
1432 type Item = K;
1433
1434 fn next(&mut self) -> Option<K> {
1435 self.inner.next().map(|(key: K, _)| key)
1436 }
1437
1438 fn size_hint(&self) -> (usize, Option<usize>) {
1439 self.inner.size_hint()
1440 }
1441}
1442
1443impl<'a, K: Key, V> Iterator for Values<'a, K, V> {
1444 type Item = &'a V;
1445
1446 fn next(&mut self) -> Option<&'a V> {
1447 self.inner.next().map(|(_, value: &'a V)| value)
1448 }
1449
1450 fn size_hint(&self) -> (usize, Option<usize>) {
1451 self.inner.size_hint()
1452 }
1453}
1454
1455impl<'a, K: Key, V> Iterator for ValuesMut<'a, K, V> {
1456 type Item = &'a mut V;
1457
1458 fn next(&mut self) -> Option<&'a mut V> {
1459 self.inner.next().map(|(_, value: &'a mut V)| value)
1460 }
1461
1462 fn size_hint(&self) -> (usize, Option<usize>) {
1463 self.inner.size_hint()
1464 }
1465}
1466
1467impl<'a, K, V, S> IntoIterator for &'a SparseSecondaryMap<K, V, S>
1468where
1469 K: Key,
1470 S: hash::BuildHasher,
1471{
1472 type Item = (K, &'a V);
1473 type IntoIter = Iter<'a, K, V>;
1474
1475 fn into_iter(self) -> Self::IntoIter {
1476 self.iter()
1477 }
1478}
1479
1480impl<'a, K, V, S> IntoIterator for &'a mut SparseSecondaryMap<K, V, S>
1481where
1482 K: Key,
1483 S: hash::BuildHasher,
1484{
1485 type Item = (K, &'a mut V);
1486 type IntoIter = IterMut<'a, K, V>;
1487
1488 fn into_iter(self) -> Self::IntoIter {
1489 self.iter_mut()
1490 }
1491}
1492
1493impl<K, V, S> IntoIterator for SparseSecondaryMap<K, V, S>
1494where
1495 K: Key,
1496 S: hash::BuildHasher,
1497{
1498 type Item = (K, V);
1499 type IntoIter = IntoIter<K, V>;
1500
1501 fn into_iter(self) -> Self::IntoIter {
1502 IntoIter {
1503 inner: self.slots.into_iter(),
1504 _k: PhantomData,
1505 }
1506 }
1507}
1508
1509impl<'a, K: Key, V> FusedIterator for Iter<'a, K, V> {}
1510impl<'a, K: Key, V> FusedIterator for IterMut<'a, K, V> {}
1511impl<'a, K: Key, V> FusedIterator for Keys<'a, K, V> {}
1512impl<'a, K: Key, V> FusedIterator for Values<'a, K, V> {}
1513impl<'a, K: Key, V> FusedIterator for ValuesMut<'a, K, V> {}
1514impl<'a, K: Key, V> FusedIterator for Drain<'a, K, V> {}
1515impl<K: Key, V> FusedIterator for IntoIter<K, V> {}
1516
1517impl<'a, K: Key, V> ExactSizeIterator for Iter<'a, K, V> {}
1518impl<'a, K: Key, V> ExactSizeIterator for IterMut<'a, K, V> {}
1519impl<'a, K: Key, V> ExactSizeIterator for Keys<'a, K, V> {}
1520impl<'a, K: Key, V> ExactSizeIterator for Values<'a, K, V> {}
1521impl<'a, K: Key, V> ExactSizeIterator for ValuesMut<'a, K, V> {}
1522impl<'a, K: Key, V> ExactSizeIterator for Drain<'a, K, V> {}
1523impl<K: Key, V> ExactSizeIterator for IntoIter<K, V> {}
1524
1525// Serialization with serde.
1526#[cfg(feature = "serde")]
1527mod serialize {
1528 use serde::{Deserialize, Deserializer, Serialize, Serializer};
1529
1530 use super::*;
1531 use crate::SecondaryMap;
1532
1533 impl<K, V, H> Serialize for SparseSecondaryMap<K, V, H>
1534 where
1535 K: Key,
1536 V: Serialize,
1537 H: hash::BuildHasher,
1538 {
1539 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1540 where
1541 S: Serializer,
1542 {
1543 let mut serde_sec = SecondaryMap::new();
1544 for (k, v) in self {
1545 serde_sec.insert(k, v);
1546 }
1547
1548 serde_sec.serialize(serializer)
1549 }
1550 }
1551
1552 impl<'de, K, V, S> Deserialize<'de> for SparseSecondaryMap<K, V, S>
1553 where
1554 K: Key,
1555 V: Deserialize<'de>,
1556 S: hash::BuildHasher + Default,
1557 {
1558 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1559 where
1560 D: Deserializer<'de>,
1561 {
1562 let serde_sec: SecondaryMap<K, V> = Deserialize::deserialize(deserializer)?;
1563 let mut sec = Self::default();
1564
1565 for (k, v) in serde_sec {
1566 sec.insert(k, v);
1567 }
1568
1569 Ok(sec)
1570 }
1571 }
1572}
1573
1574#[cfg(test)]
1575mod tests {
1576 use std::collections::HashMap;
1577
1578 use quickcheck::quickcheck;
1579
1580 use crate::*;
1581
1582 #[test]
1583 fn custom_hasher() {
1584 type FastSparseSecondaryMap<K, V> = SparseSecondaryMap<K, V, fxhash::FxBuildHasher>;
1585 let mut sm = SlotMap::new();
1586 let mut sec = FastSparseSecondaryMap::default();
1587 let key1 = sm.insert(42);
1588 sec.insert(key1, 1234);
1589 assert_eq!(sec[key1], 1234);
1590 assert_eq!(sec.len(), 1);
1591 let sec2 = sec.iter().map(|(k, &v)| (k, v)).collect::<FastSparseSecondaryMap<_, _>>();
1592 assert_eq!(sec, sec2);
1593 }
1594
1595 #[cfg(all(nightly, feature = "unstable"))]
1596 #[test]
1597 fn disjoint() {
1598 // Intended to be run with miri to find any potential UB.
1599 let mut sm = SlotMap::new();
1600 let mut sec = SparseSecondaryMap::new();
1601
1602 // Some churn.
1603 for i in 0..20usize {
1604 sm.insert(i);
1605 }
1606 sm.retain(|_, i| *i % 2 == 0);
1607
1608 for (i, k) in sm.keys().enumerate() {
1609 sec.insert(k, i);
1610 }
1611
1612 let keys: Vec<_> = sm.keys().collect();
1613 for i in 0..keys.len() {
1614 for j in 0..keys.len() {
1615 if let Some([r0, r1]) = sec.get_disjoint_mut([keys[i], keys[j]]) {
1616 *r0 ^= *r1;
1617 *r1 = r1.wrapping_add(*r0);
1618 } else {
1619 assert!(i == j);
1620 }
1621 }
1622 }
1623
1624 for i in 0..keys.len() {
1625 for j in 0..keys.len() {
1626 for k in 0..keys.len() {
1627 if let Some([r0, r1, r2]) = sec.get_disjoint_mut([keys[i], keys[j], keys[k]]) {
1628 *r0 ^= *r1;
1629 *r0 = r0.wrapping_add(*r2);
1630 *r1 ^= *r0;
1631 *r1 = r1.wrapping_add(*r2);
1632 *r2 ^= *r0;
1633 *r2 = r2.wrapping_add(*r1);
1634 } else {
1635 assert!(i == j || j == k || i == k);
1636 }
1637 }
1638 }
1639 }
1640 }
1641
1642 quickcheck! {
1643 fn qc_secmap_equiv_hashmap(operations: Vec<(u8, u32)>) -> bool {
1644 let mut hm = HashMap::new();
1645 let mut hm_keys = Vec::new();
1646 let mut unique_key = 0u32;
1647 let mut sm = SlotMap::new();
1648 let mut sec = SparseSecondaryMap::new();
1649 let mut sm_keys = Vec::new();
1650
1651 #[cfg(not(feature = "serde"))]
1652 let num_ops = 4;
1653 #[cfg(feature = "serde")]
1654 let num_ops = 5;
1655
1656 for (op, val) in operations {
1657 match op % num_ops {
1658 // Insert.
1659 0 => {
1660 hm.insert(unique_key, val);
1661 hm_keys.push(unique_key);
1662 unique_key += 1;
1663
1664 let k = sm.insert(val);
1665 sec.insert(k, val);
1666 sm_keys.push(k);
1667 }
1668
1669 // Delete.
1670 1 => {
1671 if hm_keys.is_empty() { continue; }
1672
1673 let idx = val as usize % hm_keys.len();
1674 sm.remove(sm_keys[idx]);
1675 if hm.remove(&hm_keys[idx]) != sec.remove(sm_keys[idx]) {
1676 return false;
1677 }
1678 }
1679
1680 // Access.
1681 2 => {
1682 if hm_keys.is_empty() { continue; }
1683 let idx = val as usize % hm_keys.len();
1684 let (hm_key, sm_key) = (&hm_keys[idx], sm_keys[idx]);
1685
1686 if hm.contains_key(hm_key) != sec.contains_key(sm_key) ||
1687 hm.get(hm_key) != sec.get(sm_key) {
1688 return false;
1689 }
1690 }
1691
1692 // Clone.
1693 3 => {
1694 sec = sec.clone();
1695 }
1696
1697 // Serde round-trip.
1698 #[cfg(feature = "serde")]
1699 4 => {
1700 let ser = serde_json::to_string(&sec).unwrap();
1701 sec = serde_json::from_str(&ser).unwrap();
1702 }
1703
1704 _ => unreachable!(),
1705 }
1706 }
1707
1708 let mut secv: Vec<_> = sec.values().collect();
1709 let mut hmv: Vec<_> = hm.values().collect();
1710 secv.sort();
1711 hmv.sort();
1712 secv == hmv
1713 }
1714 }
1715}
1716