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