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