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