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