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