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