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