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")))] 18 use alloc::collections::TryReserveError; 19 use alloc::vec::Vec; 20 use core::fmt; 21 use core::iter::FusedIterator; 22 use core::marker::PhantomData; 23 use core::mem::ManuallyDrop; 24 #[allow(unused_imports)] // MaybeUninit is only used on nightly at the moment. 25 use core::mem::MaybeUninit; 26 use core::ops::{Index, IndexMut}; 27 28 use crate::util::{Never, UnwrapUnchecked}; 29 use crate::{DefaultKey, Key, KeyData}; 30 31 // Metadata to maintain the freelist. 32 #[derive(Clone, Copy, Debug)] 33 struct 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. 40 union 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. 47 struct Slot<T> { 48 u: SlotUnion<T>, 49 version: u32, // Even = vacant, odd = occupied. 50 } 51 52 // Safe API to read a slot. 53 enum SlotContent<'a, T: 'a> { 54 Occupied(&'a T), 55 Vacant(&'a FreeListEntry), 56 } 57 58 enum SlotContentMut<'a, T: 'a> { 59 OccupiedMut(&'a mut T), 60 VacantMut(&'a mut FreeListEntry), 61 } 62 63 use self::SlotContent::{Occupied, Vacant}; 64 use self::SlotContentMut::{OccupiedMut, VacantMut}; 65 66 impl<T> Slot<T> { 67 // Is this slot occupied? 68 #[inline(always)] occupied(&self) -> bool69 pub fn occupied(&self) -> bool { 70 self.version % 2 == 1 71 } 72 get(&self) -> SlotContent<T>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 get_mut(&mut self) -> SlotContentMut<T>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 94 impl<T> Drop for Slot<T> { drop(&mut self)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 105 impl<T: Clone> Clone for Slot<T> { clone(&self) -> Self106 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 clone_from(&mut self, source: &Self)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 133 impl<T: fmt::Debug> fmt::Debug for Slot<T> { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result134 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 135 let mut builder = fmt.debug_struct("Slot"); 136 builder.field("version", &self.version); 137 match self.get() { 138 Occupied(value) => builder.field("value", value).finish(), 139 Vacant(free) => builder.field("free", 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)] 148 pub struct HopSlotMap<K: Key, V> { 149 slots: Vec<Slot<V>>, 150 num_elems: u32, 151 _k: PhantomData<fn(K) -> K>, 152 } 153 154 impl<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 /// ``` new() -> Self163 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 /// ``` with_capacity(capacity: usize) -> Self178 pub fn with_capacity(capacity: usize) -> Self { 179 Self::with_capacity_and_key(capacity) 180 } 181 } 182 183 impl<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 /// ``` with_key() -> Self195 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 /// ``` with_capacity_and_key(capacity: usize) -> Self217 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 /// ``` len(&self) -> usize250 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 /// ``` is_empty(&self) -> bool266 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 /// ``` capacity(&self) -> usize280 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 /// ``` reserve(&mut self, additional: usize)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")))] try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>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 /// ``` contains_key(&self, key: K) -> bool341 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)] insert(&mut self, value: V) -> K365 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. freelist(&mut self, idx: u32) -> &mut FreeListEntry372 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)] insert_with_key<F>(&mut self, f: F) -> K where F: FnOnce(K) -> V,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 /// ``` try_insert_with_key<F, E>(&mut self, f: F) -> Result<K, E> where F: FnOnce(K) -> Result<V, E>,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)] remove_from_slot(&mut self, idx: usize) -> V488 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 /// ``` remove(&mut self, key: K) -> Option<V>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 /// ``` retain<F>(&mut self, mut f: F) where F: FnMut(K, &mut V) -> bool,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 /// ``` clear(&mut self)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 /// ``` drain(&mut self) -> Drain<K, V>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 /// ``` get(&self, key: K) -> Option<&V>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 /// ``` get_unchecked(&self, key: K) -> &V712 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 /// ``` get_mut(&mut self, key: K) -> Option<&mut V>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 /// ``` get_unchecked_mut(&mut self, key: K) -> &mut V759 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)] get_disjoint_mut<const N: usize>(&mut self, keys: [K; N]) -> Option<[&mut V; N]>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)] get_disjoint_unchecked_mut<const N: usize>( &mut self, keys: [K; N], ) -> [&mut V; N]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 /// ``` iter(&self) -> Iter<K, V>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 /// ``` iter_mut(&mut self) -> IterMut<K, V>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 /// ``` keys(&self) -> Keys<K, V>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 /// ``` values(&self) -> Values<K, V>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 /// ``` values_mut(&mut self) -> ValuesMut<K, V>977 pub fn values_mut(&mut self) -> ValuesMut<K, V> { 978 ValuesMut { 979 inner: self.iter_mut(), 980 } 981 } 982 } 983 984 impl<K: Key, V> Clone for HopSlotMap<K, V> 985 where 986 V: Clone, 987 { clone(&self) -> Self988 fn clone(&self) -> Self { 989 Self { 990 slots: self.slots.clone(), 991 ..*self 992 } 993 } 994 clone_from(&mut self, source: &Self)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 1001 impl<K: Key, V> Default for HopSlotMap<K, V> { default() -> Self1002 fn default() -> Self { 1003 Self::with_key() 1004 } 1005 } 1006 1007 impl<K: Key, V> Index<K> for HopSlotMap<K, V> { 1008 type Output = V; 1009 index(&self, key: K) -> &V1010 fn index(&self, key: K) -> &V { 1011 match self.get(key) { 1012 Some(r) => r, 1013 None => panic!("invalid HopSlotMap key used"), 1014 } 1015 } 1016 } 1017 1018 impl<K: Key, V> IndexMut<K> for HopSlotMap<K, V> { index_mut(&mut self, key: K) -> &mut V1019 fn index_mut(&mut self, key: K) -> &mut V { 1020 match self.get_mut(key) { 1021 Some(r) => 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)] 1032 pub 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)] 1042 pub 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)] 1053 pub 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 1060 impl<'a, K: 'a + Key, V: 'a> Clone for Iter<'a, K, V> { clone(&self) -> Self1061 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)] 1075 pub 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)] 1086 pub struct Keys<'a, K: Key + 'a, V: 'a> { 1087 inner: Iter<'a, K, V>, 1088 } 1089 1090 impl<'a, K: 'a + Key, V: 'a> Clone for Keys<'a, K, V> { clone(&self) -> Self1091 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)] 1102 pub struct Values<'a, K: Key + 'a, V: 'a> { 1103 inner: Iter<'a, K, V>, 1104 } 1105 1106 impl<'a, K: 'a + Key, V: 'a> Clone for Values<'a, K, V> { clone(&self) -> Self1107 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)] 1118 pub struct ValuesMut<'a, K: Key + 'a, V: 'a> { 1119 inner: IterMut<'a, K, V>, 1120 } 1121 1122 impl<'a, K: Key, V> Iterator for Drain<'a, K, V> { 1123 type Item = (K, V); 1124 next(&mut self) -> Option<(K, V)>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 size_hint(&self) -> (usize, Option<usize>)1144 fn size_hint(&self) -> (usize, Option<usize>) { 1145 (self.sm.len(), Some(self.sm.len())) 1146 } 1147 } 1148 1149 impl<'a, K: Key, V> Drop for Drain<'a, K, V> { drop(&mut self)1150 fn drop(&mut self) { 1151 self.for_each(|_drop| {}); 1152 } 1153 } 1154 1155 impl<K: Key, V> Iterator for IntoIter<K, V> { 1156 type Item = (K, V); 1157 next(&mut self) -> Option<(K, V)>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 size_hint(&self) -> (usize, Option<usize>)1183 fn size_hint(&self) -> (usize, Option<usize>) { 1184 (self.num_left, Some(self.num_left)) 1185 } 1186 } 1187 1188 impl<'a, K: Key, V> Iterator for Iter<'a, K, V> { 1189 type Item = (K, &'a V); 1190 next(&mut self) -> Option<(K, &'a V)>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 size_hint(&self) -> (usize, Option<usize>)1210 fn size_hint(&self) -> (usize, Option<usize>) { 1211 (self.num_left, Some(self.num_left)) 1212 } 1213 } 1214 1215 impl<'a, K: Key, V> Iterator for IterMut<'a, K, V> { 1216 type Item = (K, &'a mut V); 1217 next(&mut self) -> Option<(K, &'a mut V)>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 size_hint(&self) -> (usize, Option<usize>)1249 fn size_hint(&self) -> (usize, Option<usize>) { 1250 (self.num_left, Some(self.num_left)) 1251 } 1252 } 1253 1254 impl<'a, K: Key, V> Iterator for Keys<'a, K, V> { 1255 type Item = K; 1256 next(&mut self) -> Option<K>1257 fn next(&mut self) -> Option<K> { 1258 self.inner.next().map(|(key, _)| key) 1259 } 1260 size_hint(&self) -> (usize, Option<usize>)1261 fn size_hint(&self) -> (usize, Option<usize>) { 1262 self.inner.size_hint() 1263 } 1264 } 1265 1266 impl<'a, K: Key, V> Iterator for Values<'a, K, V> { 1267 type Item = &'a V; 1268 next(&mut self) -> Option<&'a V>1269 fn next(&mut self) -> Option<&'a V> { 1270 self.inner.next().map(|(_, value)| value) 1271 } 1272 size_hint(&self) -> (usize, Option<usize>)1273 fn size_hint(&self) -> (usize, Option<usize>) { 1274 self.inner.size_hint() 1275 } 1276 } 1277 1278 impl<'a, K: Key, V> Iterator for ValuesMut<'a, K, V> { 1279 type Item = &'a mut V; 1280 next(&mut self) -> Option<&'a mut V>1281 fn next(&mut self) -> Option<&'a mut V> { 1282 self.inner.next().map(|(_, value)| value) 1283 } 1284 size_hint(&self) -> (usize, Option<usize>)1285 fn size_hint(&self) -> (usize, Option<usize>) { 1286 self.inner.size_hint() 1287 } 1288 } 1289 1290 impl<'a, K: Key, V> IntoIterator for &'a HopSlotMap<K, V> { 1291 type Item = (K, &'a V); 1292 type IntoIter = Iter<'a, K, V>; 1293 into_iter(self) -> Self::IntoIter1294 fn into_iter(self) -> Self::IntoIter { 1295 self.iter() 1296 } 1297 } 1298 1299 impl<'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 into_iter(self) -> Self::IntoIter1303 fn into_iter(self) -> Self::IntoIter { 1304 self.iter_mut() 1305 } 1306 } 1307 1308 impl<K: Key, V> IntoIterator for HopSlotMap<K, V> { 1309 type Item = (K, V); 1310 type IntoIter = IntoIter<K, V>; 1311 into_iter(self) -> Self::IntoIter1312 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 1322 impl<'a, K: Key, V> FusedIterator for Iter<'a, K, V> {} 1323 impl<'a, K: Key, V> FusedIterator for IterMut<'a, K, V> {} 1324 impl<'a, K: Key, V> FusedIterator for Keys<'a, K, V> {} 1325 impl<'a, K: Key, V> FusedIterator for Values<'a, K, V> {} 1326 impl<'a, K: Key, V> FusedIterator for ValuesMut<'a, K, V> {} 1327 impl<'a, K: Key, V> FusedIterator for Drain<'a, K, V> {} 1328 impl<K: Key, V> FusedIterator for IntoIter<K, V> {} 1329 1330 impl<'a, K: Key, V> ExactSizeIterator for Iter<'a, K, V> {} 1331 impl<'a, K: Key, V> ExactSizeIterator for IterMut<'a, K, V> {} 1332 impl<'a, K: Key, V> ExactSizeIterator for Keys<'a, K, V> {} 1333 impl<'a, K: Key, V> ExactSizeIterator for Values<'a, K, V> {} 1334 impl<'a, K: Key, V> ExactSizeIterator for ValuesMut<'a, K, V> {} 1335 impl<'a, K: Key, V> ExactSizeIterator for Drain<'a, K, V> {} 1336 impl<K: Key, V> ExactSizeIterator for IntoIter<K, V> {} 1337 1338 // Serialization with serde. 1339 #[cfg(feature = "serde")] 1340 mod 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> { serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer,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 { deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>,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> { serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer,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> { deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>,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)] 1471 mod 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> { drop(&mut self)1482 fn drop(&mut self) { 1483 *self.0.borrow_mut() += 1; 1484 } 1485 } 1486 1487 #[cfg(all(nightly, feature = "unstable"))] 1488 #[test] check_drops()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] disjoint()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] slotmap_serde()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] slotmap_serde_freelist()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