1 #![cfg_attr(not(feature = "std"), no_std)] 2 #![warn( 3 missing_debug_implementations, 4 missing_docs, 5 rust_2018_idioms, 6 unreachable_pub 7 )] 8 #![doc(test( 9 no_crate_inject, 10 attr(deny(warnings, rust_2018_idioms), allow(dead_code, unused_variables)) 11 ))] 12 13 //! Pre-allocated storage for a uniform data type. 14 //! 15 //! `Slab` provides pre-allocated storage for a single data type. If many values 16 //! of a single type are being allocated, it can be more efficient to 17 //! pre-allocate the necessary storage. Since the size of the type is uniform, 18 //! memory fragmentation can be avoided. Storing, clearing, and lookup 19 //! operations become very cheap. 20 //! 21 //! While `Slab` may look like other Rust collections, it is not intended to be 22 //! used as a general purpose collection. The primary difference between `Slab` 23 //! and `Vec` is that `Slab` returns the key when storing the value. 24 //! 25 //! It is important to note that keys may be reused. In other words, once a 26 //! value associated with a given key is removed from a slab, that key may be 27 //! returned from future calls to `insert`. 28 //! 29 //! # Examples 30 //! 31 //! Basic storing and retrieval. 32 //! 33 //! ``` 34 //! # use slab::*; 35 //! let mut slab = Slab::new(); 36 //! 37 //! let hello = slab.insert("hello"); 38 //! let world = slab.insert("world"); 39 //! 40 //! assert_eq!(slab[hello], "hello"); 41 //! assert_eq!(slab[world], "world"); 42 //! 43 //! slab[world] = "earth"; 44 //! assert_eq!(slab[world], "earth"); 45 //! ``` 46 //! 47 //! Sometimes it is useful to be able to associate the key with the value being 48 //! inserted in the slab. This can be done with the `vacant_entry` API as such: 49 //! 50 //! ``` 51 //! # use slab::*; 52 //! let mut slab = Slab::new(); 53 //! 54 //! let hello = { 55 //! let entry = slab.vacant_entry(); 56 //! let key = entry.key(); 57 //! 58 //! entry.insert((key, "hello")); 59 //! key 60 //! }; 61 //! 62 //! assert_eq!(hello, slab[hello].0); 63 //! assert_eq!("hello", slab[hello].1); 64 //! ``` 65 //! 66 //! It is generally a good idea to specify the desired capacity of a slab at 67 //! creation time. Note that `Slab` will grow the internal capacity when 68 //! attempting to insert a new value once the existing capacity has been reached. 69 //! To avoid this, add a check. 70 //! 71 //! ``` 72 //! # use slab::*; 73 //! let mut slab = Slab::with_capacity(1024); 74 //! 75 //! // ... use the slab 76 //! 77 //! if slab.len() == slab.capacity() { 78 //! panic!("slab full"); 79 //! } 80 //! 81 //! slab.insert("the slab is not at capacity yet"); 82 //! ``` 83 //! 84 //! # Capacity and reallocation 85 //! 86 //! The capacity of a slab is the amount of space allocated for any future 87 //! values that will be inserted in the slab. This is not to be confused with 88 //! the *length* of the slab, which specifies the number of actual values 89 //! currently being inserted. If a slab's length is equal to its capacity, the 90 //! next value inserted into the slab will require growing the slab by 91 //! reallocating. 92 //! 93 //! For example, a slab with capacity 10 and length 0 would be an empty slab 94 //! with space for 10 more stored values. Storing 10 or fewer elements into the 95 //! slab will not change its capacity or cause reallocation to occur. However, 96 //! if the slab length is increased to 11 (due to another `insert`), it will 97 //! have to reallocate, which can be slow. For this reason, it is recommended to 98 //! use [`Slab::with_capacity`] whenever possible to specify how many values the 99 //! slab is expected to store. 100 //! 101 //! # Implementation 102 //! 103 //! `Slab` is backed by a `Vec` of slots. Each slot is either occupied or 104 //! vacant. `Slab` maintains a stack of vacant slots using a linked list. To 105 //! find a vacant slot, the stack is popped. When a slot is released, it is 106 //! pushed onto the stack. 107 //! 108 //! If there are no more available slots in the stack, then `Vec::reserve(1)` is 109 //! called and a new slot is created. 110 //! 111 //! [`Slab::with_capacity`]: struct.Slab.html#with_capacity 112 113 #[cfg(not(feature = "std"))] 114 extern crate alloc; 115 #[cfg(feature = "std")] 116 extern crate std as alloc; 117 118 #[cfg(feature = "serde")] 119 mod serde; 120 121 use alloc::vec::{self, Vec}; 122 use core::iter::{self, FromIterator, FusedIterator}; 123 use core::{fmt, mem, ops, slice}; 124 125 /// Pre-allocated storage for a uniform data type 126 /// 127 /// See the [module documentation] for more details. 128 /// 129 /// [module documentation]: index.html 130 #[derive(Clone)] 131 pub struct Slab<T> { 132 // Chunk of memory 133 entries: Vec<Entry<T>>, 134 135 // Number of Filled elements currently in the slab 136 len: usize, 137 138 // Offset of the next available slot in the slab. Set to the slab's 139 // capacity when the slab is full. 140 next: usize, 141 } 142 143 impl<T> Default for Slab<T> { default() -> Self144 fn default() -> Self { 145 Slab::new() 146 } 147 } 148 149 /// A handle to a vacant entry in a `Slab`. 150 /// 151 /// `VacantEntry` allows constructing values with the key that they will be 152 /// assigned to. 153 /// 154 /// # Examples 155 /// 156 /// ``` 157 /// # use slab::*; 158 /// let mut slab = Slab::new(); 159 /// 160 /// let hello = { 161 /// let entry = slab.vacant_entry(); 162 /// let key = entry.key(); 163 /// 164 /// entry.insert((key, "hello")); 165 /// key 166 /// }; 167 /// 168 /// assert_eq!(hello, slab[hello].0); 169 /// assert_eq!("hello", slab[hello].1); 170 /// ``` 171 #[derive(Debug)] 172 pub struct VacantEntry<'a, T> { 173 slab: &'a mut Slab<T>, 174 key: usize, 175 } 176 177 /// A consuming iterator over the values stored in a `Slab` 178 pub struct IntoIter<T> { 179 entries: iter::Enumerate<vec::IntoIter<Entry<T>>>, 180 len: usize, 181 } 182 183 /// An iterator over the values stored in the `Slab` 184 pub struct Iter<'a, T> { 185 entries: iter::Enumerate<slice::Iter<'a, Entry<T>>>, 186 len: usize, 187 } 188 189 impl<'a, T> Clone for Iter<'a, T> { clone(&self) -> Self190 fn clone(&self) -> Self { 191 Self { 192 entries: self.entries.clone(), 193 len: self.len, 194 } 195 } 196 } 197 198 /// A mutable iterator over the values stored in the `Slab` 199 pub struct IterMut<'a, T> { 200 entries: iter::Enumerate<slice::IterMut<'a, Entry<T>>>, 201 len: usize, 202 } 203 204 /// A draining iterator for `Slab` 205 pub struct Drain<'a, T> { 206 inner: vec::Drain<'a, Entry<T>>, 207 len: usize, 208 } 209 210 #[derive(Clone)] 211 enum Entry<T> { 212 Vacant(usize), 213 Occupied(T), 214 } 215 216 impl<T> Slab<T> { 217 /// Construct a new, empty `Slab`. 218 /// 219 /// The function does not allocate and the returned slab will have no 220 /// capacity until `insert` is called or capacity is explicitly reserved. 221 /// 222 /// # Examples 223 /// 224 /// ``` 225 /// # use slab::*; 226 /// let slab: Slab<i32> = Slab::new(); 227 /// ``` new() -> Slab<T>228 pub fn new() -> Slab<T> { 229 Slab::with_capacity(0) 230 } 231 232 /// Construct a new, empty `Slab` with the specified capacity. 233 /// 234 /// The returned slab will be able to store exactly `capacity` without 235 /// reallocating. If `capacity` is 0, the slab will not allocate. 236 /// 237 /// It is important to note that this function does not specify the *length* 238 /// of the returned slab, but only the capacity. For an explanation of the 239 /// difference between length and capacity, see [Capacity and 240 /// reallocation](index.html#capacity-and-reallocation). 241 /// 242 /// # Examples 243 /// 244 /// ``` 245 /// # use slab::*; 246 /// let mut slab = Slab::with_capacity(10); 247 /// 248 /// // The slab contains no values, even though it has capacity for more 249 /// assert_eq!(slab.len(), 0); 250 /// 251 /// // These are all done without reallocating... 252 /// for i in 0..10 { 253 /// slab.insert(i); 254 /// } 255 /// 256 /// // ...but this may make the slab reallocate 257 /// slab.insert(11); 258 /// ``` with_capacity(capacity: usize) -> Slab<T>259 pub fn with_capacity(capacity: usize) -> Slab<T> { 260 Slab { 261 entries: Vec::with_capacity(capacity), 262 next: 0, 263 len: 0, 264 } 265 } 266 267 /// Return the number of values the slab can store without reallocating. 268 /// 269 /// # Examples 270 /// 271 /// ``` 272 /// # use slab::*; 273 /// let slab: Slab<i32> = Slab::with_capacity(10); 274 /// assert_eq!(slab.capacity(), 10); 275 /// ``` capacity(&self) -> usize276 pub fn capacity(&self) -> usize { 277 self.entries.capacity() 278 } 279 280 /// Reserve capacity for at least `additional` more values to be stored 281 /// without allocating. 282 /// 283 /// `reserve` does nothing if the slab already has sufficient capacity for 284 /// `additional` more values. If more capacity is required, a new segment of 285 /// memory will be allocated and all existing values will be copied into it. 286 /// As such, if the slab is already very large, a call to `reserve` can end 287 /// up being expensive. 288 /// 289 /// The slab may reserve more than `additional` extra space in order to 290 /// avoid frequent reallocations. Use `reserve_exact` instead to guarantee 291 /// that only the requested space is allocated. 292 /// 293 /// # Panics 294 /// 295 /// Panics if the new capacity overflows `usize`. 296 /// 297 /// # Examples 298 /// 299 /// ``` 300 /// # use slab::*; 301 /// let mut slab = Slab::new(); 302 /// slab.insert("hello"); 303 /// slab.reserve(10); 304 /// assert!(slab.capacity() >= 11); 305 /// ``` reserve(&mut self, additional: usize)306 pub fn reserve(&mut self, additional: usize) { 307 if self.capacity() - self.len >= additional { 308 return; 309 } 310 let need_add = additional - (self.entries.len() - self.len); 311 self.entries.reserve(need_add); 312 } 313 314 /// Reserve the minimum capacity required to store exactly `additional` 315 /// more values. 316 /// 317 /// `reserve_exact` does nothing if the slab already has sufficient capacity 318 /// for `additional` more values. If more capacity is required, a new segment 319 /// of memory will be allocated and all existing values will be copied into 320 /// it. As such, if the slab is already very large, a call to `reserve` can 321 /// end up being expensive. 322 /// 323 /// Note that the allocator may give the slab more space than it requests. 324 /// Therefore capacity can not be relied upon to be precisely minimal. 325 /// Prefer `reserve` if future insertions are expected. 326 /// 327 /// # Panics 328 /// 329 /// Panics if the new capacity overflows `usize`. 330 /// 331 /// # Examples 332 /// 333 /// ``` 334 /// # use slab::*; 335 /// let mut slab = Slab::new(); 336 /// slab.insert("hello"); 337 /// slab.reserve_exact(10); 338 /// assert!(slab.capacity() >= 11); 339 /// ``` reserve_exact(&mut self, additional: usize)340 pub fn reserve_exact(&mut self, additional: usize) { 341 if self.capacity() - self.len >= additional { 342 return; 343 } 344 let need_add = additional - (self.entries.len() - self.len); 345 self.entries.reserve_exact(need_add); 346 } 347 348 /// Shrink the capacity of the slab as much as possible without invalidating keys. 349 /// 350 /// Because values cannot be moved to a different index, the slab cannot 351 /// shrink past any stored values. 352 /// It will drop down as close as possible to the length but the allocator may 353 /// still inform the underlying vector that there is space for a few more elements. 354 /// 355 /// This function can take O(n) time even when the capacity cannot be reduced 356 /// or the allocation is shrunk in place. Repeated calls run in O(1) though. 357 /// 358 /// # Examples 359 /// 360 /// ``` 361 /// # use slab::*; 362 /// let mut slab = Slab::with_capacity(10); 363 /// 364 /// for i in 0..3 { 365 /// slab.insert(i); 366 /// } 367 /// 368 /// slab.shrink_to_fit(); 369 /// assert!(slab.capacity() >= 3 && slab.capacity() < 10); 370 /// ``` 371 /// 372 /// The slab cannot shrink past the last present value even if previous 373 /// values are removed: 374 /// 375 /// ``` 376 /// # use slab::*; 377 /// let mut slab = Slab::with_capacity(10); 378 /// 379 /// for i in 0..4 { 380 /// slab.insert(i); 381 /// } 382 /// 383 /// slab.remove(0); 384 /// slab.remove(3); 385 /// 386 /// slab.shrink_to_fit(); 387 /// assert!(slab.capacity() >= 3 && slab.capacity() < 10); 388 /// ``` shrink_to_fit(&mut self)389 pub fn shrink_to_fit(&mut self) { 390 // Remove all vacant entries after the last occupied one, so that 391 // the capacity can be reduced to what is actually needed. 392 // If the slab is empty the vector can simply be cleared, but that 393 // optimization would not affect time complexity when T: Drop. 394 let len_before = self.entries.len(); 395 while let Some(&Entry::Vacant(_)) = self.entries.last() { 396 self.entries.pop(); 397 } 398 399 // Removing entries breaks the list of vacant entries, 400 // so it must be repaired 401 if self.entries.len() != len_before { 402 // Some vacant entries were removed, so the list now likely¹ 403 // either contains references to the removed entries, or has an 404 // invalid end marker. Fix this by recreating the list. 405 self.recreate_vacant_list(); 406 // ¹: If the removed entries formed the tail of the list, with the 407 // most recently popped entry being the head of them, (so that its 408 // index is now the end marker) the list is still valid. 409 // Checking for that unlikely scenario of this infrequently called 410 // is not worth the code complexity. 411 } 412 413 self.entries.shrink_to_fit(); 414 } 415 416 /// Iterate through all entries to recreate and repair the vacant list. 417 /// self.len must be correct and is not modified. recreate_vacant_list(&mut self)418 fn recreate_vacant_list(&mut self) { 419 self.next = self.entries.len(); 420 // We can stop once we've found all vacant entries 421 let mut remaining_vacant = self.entries.len() - self.len; 422 // Iterate in reverse order so that lower keys are at the start of 423 // the vacant list. This way future shrinks are more likely to be 424 // able to remove vacant entries. 425 for (i, entry) in self.entries.iter_mut().enumerate().rev() { 426 if remaining_vacant == 0 { 427 break; 428 } 429 if let Entry::Vacant(ref mut next) = *entry { 430 *next = self.next; 431 self.next = i; 432 remaining_vacant -= 1; 433 } 434 } 435 } 436 437 /// Reduce the capacity as much as possible, changing the key for elements when necessary. 438 /// 439 /// To allow updating references to the elements which must be moved to a new key, 440 /// this function takes a closure which is called before moving each element. 441 /// The second and third parameters to the closure are the current key and 442 /// new key respectively. 443 /// In case changing the key for one element turns out not to be possible, 444 /// the move can be cancelled by returning `false` from the closure. 445 /// In that case no further attempts at relocating elements is made. 446 /// If the closure unwinds, the slab will be left in a consistent state, 447 /// but the value that the closure panicked on might be removed. 448 /// 449 /// # Examples 450 /// 451 /// ``` 452 /// # use slab::*; 453 /// 454 /// let mut slab = Slab::with_capacity(10); 455 /// let a = slab.insert('a'); 456 /// slab.insert('b'); 457 /// slab.insert('c'); 458 /// slab.remove(a); 459 /// slab.compact(|&mut value, from, to| { 460 /// assert_eq!((value, from, to), ('c', 2, 0)); 461 /// true 462 /// }); 463 /// assert!(slab.capacity() >= 2 && slab.capacity() < 10); 464 /// ``` 465 /// 466 /// The value is not moved when the closure returns `Err`: 467 /// 468 /// ``` 469 /// # use slab::*; 470 /// 471 /// let mut slab = Slab::with_capacity(100); 472 /// let a = slab.insert('a'); 473 /// let b = slab.insert('b'); 474 /// slab.remove(a); 475 /// slab.compact(|&mut value, from, to| false); 476 /// assert_eq!(slab.iter().next(), Some((b, &'b'))); 477 /// ``` compact<F>(&mut self, mut rekey: F) where F: FnMut(&mut T, usize, usize) -> bool,478 pub fn compact<F>(&mut self, mut rekey: F) 479 where 480 F: FnMut(&mut T, usize, usize) -> bool, 481 { 482 // If the closure unwinds, we need to restore a valid list of vacant entries 483 struct CleanupGuard<'a, T> { 484 slab: &'a mut Slab<T>, 485 decrement: bool, 486 } 487 impl<T> Drop for CleanupGuard<'_, T> { 488 fn drop(&mut self) { 489 if self.decrement { 490 // Value was popped and not pushed back on 491 self.slab.len -= 1; 492 } 493 self.slab.recreate_vacant_list(); 494 } 495 } 496 let mut guard = CleanupGuard { 497 slab: self, 498 decrement: true, 499 }; 500 501 let mut occupied_until = 0; 502 // While there are vacant entries 503 while guard.slab.entries.len() > guard.slab.len { 504 // Find a value that needs to be moved, 505 // by popping entries until we find an occupied one. 506 // (entries cannot be empty because 0 is not greater than anything) 507 if let Some(Entry::Occupied(mut value)) = guard.slab.entries.pop() { 508 // Found one, now find a vacant entry to move it to 509 while let Some(&Entry::Occupied(_)) = guard.slab.entries.get(occupied_until) { 510 occupied_until += 1; 511 } 512 // Let the caller try to update references to the key 513 if !rekey(&mut value, guard.slab.entries.len(), occupied_until) { 514 // Changing the key failed, so push the entry back on at its old index. 515 guard.slab.entries.push(Entry::Occupied(value)); 516 guard.decrement = false; 517 guard.slab.entries.shrink_to_fit(); 518 return; 519 // Guard drop handles cleanup 520 } 521 // Put the value in its new spot 522 guard.slab.entries[occupied_until] = Entry::Occupied(value); 523 // ... and mark it as occupied (this is optional) 524 occupied_until += 1; 525 } 526 } 527 guard.slab.next = guard.slab.len; 528 guard.slab.entries.shrink_to_fit(); 529 // Normal cleanup is not necessary 530 mem::forget(guard); 531 } 532 533 /// Clear the slab of all values. 534 /// 535 /// # Examples 536 /// 537 /// ``` 538 /// # use slab::*; 539 /// let mut slab = Slab::new(); 540 /// 541 /// for i in 0..3 { 542 /// slab.insert(i); 543 /// } 544 /// 545 /// slab.clear(); 546 /// assert!(slab.is_empty()); 547 /// ``` clear(&mut self)548 pub fn clear(&mut self) { 549 self.entries.clear(); 550 self.len = 0; 551 self.next = 0; 552 } 553 554 /// Return the number of stored values. 555 /// 556 /// # Examples 557 /// 558 /// ``` 559 /// # use slab::*; 560 /// let mut slab = Slab::new(); 561 /// 562 /// for i in 0..3 { 563 /// slab.insert(i); 564 /// } 565 /// 566 /// assert_eq!(3, slab.len()); 567 /// ``` len(&self) -> usize568 pub fn len(&self) -> usize { 569 self.len 570 } 571 572 /// Return `true` if there are no values stored in the slab. 573 /// 574 /// # Examples 575 /// 576 /// ``` 577 /// # use slab::*; 578 /// let mut slab = Slab::new(); 579 /// assert!(slab.is_empty()); 580 /// 581 /// slab.insert(1); 582 /// assert!(!slab.is_empty()); 583 /// ``` is_empty(&self) -> bool584 pub fn is_empty(&self) -> bool { 585 self.len == 0 586 } 587 588 /// Return an iterator over the slab. 589 /// 590 /// This function should generally be **avoided** as it is not efficient. 591 /// Iterators must iterate over every slot in the slab even if it is 592 /// vacant. As such, a slab with a capacity of 1 million but only one 593 /// stored value must still iterate the million slots. 594 /// 595 /// # Examples 596 /// 597 /// ``` 598 /// # use slab::*; 599 /// let mut slab = Slab::new(); 600 /// 601 /// for i in 0..3 { 602 /// slab.insert(i); 603 /// } 604 /// 605 /// let mut iterator = slab.iter(); 606 /// 607 /// assert_eq!(iterator.next(), Some((0, &0))); 608 /// assert_eq!(iterator.next(), Some((1, &1))); 609 /// assert_eq!(iterator.next(), Some((2, &2))); 610 /// assert_eq!(iterator.next(), None); 611 /// ``` iter(&self) -> Iter<'_, T>612 pub fn iter(&self) -> Iter<'_, T> { 613 Iter { 614 entries: self.entries.iter().enumerate(), 615 len: self.len, 616 } 617 } 618 619 /// Return an iterator that allows modifying each value. 620 /// 621 /// This function should generally be **avoided** as it is not efficient. 622 /// Iterators must iterate over every slot in the slab even if it is 623 /// vacant. As such, a slab with a capacity of 1 million but only one 624 /// stored value must still iterate the million slots. 625 /// 626 /// # Examples 627 /// 628 /// ``` 629 /// # use slab::*; 630 /// let mut slab = Slab::new(); 631 /// 632 /// let key1 = slab.insert(0); 633 /// let key2 = slab.insert(1); 634 /// 635 /// for (key, val) in slab.iter_mut() { 636 /// if key == key1 { 637 /// *val += 2; 638 /// } 639 /// } 640 /// 641 /// assert_eq!(slab[key1], 2); 642 /// assert_eq!(slab[key2], 1); 643 /// ``` iter_mut(&mut self) -> IterMut<'_, T>644 pub fn iter_mut(&mut self) -> IterMut<'_, T> { 645 IterMut { 646 entries: self.entries.iter_mut().enumerate(), 647 len: self.len, 648 } 649 } 650 651 /// Return a reference to the value associated with the given key. 652 /// 653 /// If the given key is not associated with a value, then `None` is 654 /// returned. 655 /// 656 /// # Examples 657 /// 658 /// ``` 659 /// # use slab::*; 660 /// let mut slab = Slab::new(); 661 /// let key = slab.insert("hello"); 662 /// 663 /// assert_eq!(slab.get(key), Some(&"hello")); 664 /// assert_eq!(slab.get(123), None); 665 /// ``` get(&self, key: usize) -> Option<&T>666 pub fn get(&self, key: usize) -> Option<&T> { 667 match self.entries.get(key) { 668 Some(&Entry::Occupied(ref val)) => Some(val), 669 _ => None, 670 } 671 } 672 673 /// Return a mutable reference to the value associated with the given key. 674 /// 675 /// If the given key is not associated with a value, then `None` is 676 /// returned. 677 /// 678 /// # Examples 679 /// 680 /// ``` 681 /// # use slab::*; 682 /// let mut slab = Slab::new(); 683 /// let key = slab.insert("hello"); 684 /// 685 /// *slab.get_mut(key).unwrap() = "world"; 686 /// 687 /// assert_eq!(slab[key], "world"); 688 /// assert_eq!(slab.get_mut(123), None); 689 /// ``` get_mut(&mut self, key: usize) -> Option<&mut T>690 pub fn get_mut(&mut self, key: usize) -> Option<&mut T> { 691 match self.entries.get_mut(key) { 692 Some(&mut Entry::Occupied(ref mut val)) => Some(val), 693 _ => None, 694 } 695 } 696 697 /// Return two mutable references to the values associated with the two 698 /// given keys simultaneously. 699 /// 700 /// If any one of the given keys is not associated with a value, then `None` 701 /// is returned. 702 /// 703 /// This function can be used to get two mutable references out of one slab, 704 /// so that you can manipulate both of them at the same time, eg. swap them. 705 /// 706 /// # Examples 707 /// 708 /// ``` 709 /// # use slab::*; 710 /// use std::mem; 711 /// 712 /// let mut slab = Slab::new(); 713 /// let key1 = slab.insert(1); 714 /// let key2 = slab.insert(2); 715 /// let (value1, value2) = slab.get2_mut(key1, key2).unwrap(); 716 /// mem::swap(value1, value2); 717 /// assert_eq!(slab[key1], 2); 718 /// assert_eq!(slab[key2], 1); 719 /// ``` get2_mut(&mut self, key1: usize, key2: usize) -> Option<(&mut T, &mut T)>720 pub fn get2_mut(&mut self, key1: usize, key2: usize) -> Option<(&mut T, &mut T)> { 721 assert!(key1 != key2); 722 723 let (entry1, entry2); 724 725 if key1 > key2 { 726 let (slice1, slice2) = self.entries.split_at_mut(key1); 727 entry1 = slice2.get_mut(0); 728 entry2 = slice1.get_mut(key2); 729 } else { 730 let (slice1, slice2) = self.entries.split_at_mut(key2); 731 entry1 = slice1.get_mut(key1); 732 entry2 = slice2.get_mut(0); 733 } 734 735 match (entry1, entry2) { 736 ( 737 Some(&mut Entry::Occupied(ref mut val1)), 738 Some(&mut Entry::Occupied(ref mut val2)), 739 ) => Some((val1, val2)), 740 _ => None, 741 } 742 } 743 744 /// Return a reference to the value associated with the given key without 745 /// performing bounds checking. 746 /// 747 /// For a safe alternative see [`get`](Slab::get). 748 /// 749 /// This function should be used with care. 750 /// 751 /// # Safety 752 /// 753 /// The key must be within bounds. 754 /// 755 /// # Examples 756 /// 757 /// ``` 758 /// # use slab::*; 759 /// let mut slab = Slab::new(); 760 /// let key = slab.insert(2); 761 /// 762 /// unsafe { 763 /// assert_eq!(slab.get_unchecked(key), &2); 764 /// } 765 /// ``` get_unchecked(&self, key: usize) -> &T766 pub unsafe fn get_unchecked(&self, key: usize) -> &T { 767 match *self.entries.get_unchecked(key) { 768 Entry::Occupied(ref val) => val, 769 _ => unreachable!(), 770 } 771 } 772 773 /// Return a mutable reference to the value associated with the given key 774 /// without performing bounds checking. 775 /// 776 /// For a safe alternative see [`get_mut`](Slab::get_mut). 777 /// 778 /// This function should be used with care. 779 /// 780 /// # Safety 781 /// 782 /// The key must be within bounds. 783 /// 784 /// # Examples 785 /// 786 /// ``` 787 /// # use slab::*; 788 /// let mut slab = Slab::new(); 789 /// let key = slab.insert(2); 790 /// 791 /// unsafe { 792 /// let val = slab.get_unchecked_mut(key); 793 /// *val = 13; 794 /// } 795 /// 796 /// assert_eq!(slab[key], 13); 797 /// ``` get_unchecked_mut(&mut self, key: usize) -> &mut T798 pub unsafe fn get_unchecked_mut(&mut self, key: usize) -> &mut T { 799 match *self.entries.get_unchecked_mut(key) { 800 Entry::Occupied(ref mut val) => val, 801 _ => unreachable!(), 802 } 803 } 804 805 /// Return two mutable references to the values associated with the two 806 /// given keys simultaneously without performing bounds checking and safety 807 /// condition checking. 808 /// 809 /// For a safe alternative see [`get2_mut`](Slab::get2_mut). 810 /// 811 /// This function should be used with care. 812 /// 813 /// # Safety 814 /// 815 /// - Both keys must be within bounds. 816 /// - The condition `key1 != key2` must hold. 817 /// 818 /// # Examples 819 /// 820 /// ``` 821 /// # use slab::*; 822 /// use std::mem; 823 /// 824 /// let mut slab = Slab::new(); 825 /// let key1 = slab.insert(1); 826 /// let key2 = slab.insert(2); 827 /// let (value1, value2) = unsafe { slab.get2_unchecked_mut(key1, key2) }; 828 /// mem::swap(value1, value2); 829 /// assert_eq!(slab[key1], 2); 830 /// assert_eq!(slab[key2], 1); 831 /// ``` get2_unchecked_mut(&mut self, key1: usize, key2: usize) -> (&mut T, &mut T)832 pub unsafe fn get2_unchecked_mut(&mut self, key1: usize, key2: usize) -> (&mut T, &mut T) { 833 let ptr1 = self.entries.get_unchecked_mut(key1) as *mut Entry<T>; 834 let ptr2 = self.entries.get_unchecked_mut(key2) as *mut Entry<T>; 835 match (&mut *ptr1, &mut *ptr2) { 836 (&mut Entry::Occupied(ref mut val1), &mut Entry::Occupied(ref mut val2)) => { 837 (val1, val2) 838 } 839 _ => unreachable!(), 840 } 841 } 842 843 /// Get the key for an element in the slab. 844 /// 845 /// The reference must point to an element owned by the slab. 846 /// Otherwise this function will panic. 847 /// This is a constant-time operation because the key can be calculated 848 /// from the reference with pointer arithmetic. 849 /// 850 /// # Panics 851 /// 852 /// This function will panic if the reference does not point to an element 853 /// of the slab. 854 /// 855 /// # Examples 856 /// 857 /// ``` 858 /// # use slab::*; 859 /// 860 /// let mut slab = Slab::new(); 861 /// let key = slab.insert(String::from("foo")); 862 /// let value = &slab[key]; 863 /// assert_eq!(slab.key_of(value), key); 864 /// ``` 865 /// 866 /// Values are not compared, so passing a reference to a different location 867 /// will result in a panic: 868 /// 869 /// ```should_panic 870 /// # use slab::*; 871 /// 872 /// let mut slab = Slab::new(); 873 /// let key = slab.insert(0); 874 /// let bad = &0; 875 /// slab.key_of(bad); // this will panic 876 /// unreachable!(); 877 /// ``` key_of(&self, present_element: &T) -> usize878 pub fn key_of(&self, present_element: &T) -> usize { 879 let element_ptr = present_element as *const T as usize; 880 let base_ptr = self.entries.as_ptr() as usize; 881 // Use wrapping subtraction in case the reference is bad 882 let byte_offset = element_ptr.wrapping_sub(base_ptr); 883 // The division rounds away any offset of T inside Entry 884 // The size of Entry<T> is never zero even if T is due to Vacant(usize) 885 let key = byte_offset / mem::size_of::<Entry<T>>(); 886 // Prevent returning unspecified (but out of bounds) values 887 if key >= self.entries.len() { 888 panic!("The reference points to a value outside this slab"); 889 } 890 // The reference cannot point to a vacant entry, because then it would not be valid 891 key 892 } 893 894 /// Insert a value in the slab, returning key assigned to the value. 895 /// 896 /// The returned key can later be used to retrieve or remove the value using indexed 897 /// lookup and `remove`. Additional capacity is allocated if needed. See 898 /// [Capacity and reallocation](index.html#capacity-and-reallocation). 899 /// 900 /// # Panics 901 /// 902 /// Panics if the number of elements in the vector overflows a `usize`. 903 /// 904 /// # Examples 905 /// 906 /// ``` 907 /// # use slab::*; 908 /// let mut slab = Slab::new(); 909 /// let key = slab.insert("hello"); 910 /// assert_eq!(slab[key], "hello"); 911 /// ``` insert(&mut self, val: T) -> usize912 pub fn insert(&mut self, val: T) -> usize { 913 let key = self.next; 914 915 self.insert_at(key, val); 916 917 key 918 } 919 920 /// Return a handle to a vacant entry allowing for further manipulation. 921 /// 922 /// This function is useful when creating values that must contain their 923 /// slab key. The returned `VacantEntry` reserves a slot in the slab and is 924 /// able to query the associated key. 925 /// 926 /// # Examples 927 /// 928 /// ``` 929 /// # use slab::*; 930 /// let mut slab = Slab::new(); 931 /// 932 /// let hello = { 933 /// let entry = slab.vacant_entry(); 934 /// let key = entry.key(); 935 /// 936 /// entry.insert((key, "hello")); 937 /// key 938 /// }; 939 /// 940 /// assert_eq!(hello, slab[hello].0); 941 /// assert_eq!("hello", slab[hello].1); 942 /// ``` vacant_entry(&mut self) -> VacantEntry<'_, T>943 pub fn vacant_entry(&mut self) -> VacantEntry<'_, T> { 944 VacantEntry { 945 key: self.next, 946 slab: self, 947 } 948 } 949 insert_at(&mut self, key: usize, val: T)950 fn insert_at(&mut self, key: usize, val: T) { 951 self.len += 1; 952 953 if key == self.entries.len() { 954 self.entries.push(Entry::Occupied(val)); 955 self.next = key + 1; 956 } else { 957 self.next = match self.entries.get(key) { 958 Some(&Entry::Vacant(next)) => next, 959 _ => unreachable!(), 960 }; 961 self.entries[key] = Entry::Occupied(val); 962 } 963 } 964 965 /// Tries to remove the value associated with the given key, 966 /// returning the value if the key existed. 967 /// 968 /// The key is then released and may be associated with future stored 969 /// values. 970 /// 971 /// # Examples 972 /// 973 /// ``` 974 /// # use slab::*; 975 /// let mut slab = Slab::new(); 976 /// 977 /// let hello = slab.insert("hello"); 978 /// 979 /// assert_eq!(slab.try_remove(hello), Some("hello")); 980 /// assert!(!slab.contains(hello)); 981 /// ``` try_remove(&mut self, key: usize) -> Option<T>982 pub fn try_remove(&mut self, key: usize) -> Option<T> { 983 if let Some(entry) = self.entries.get_mut(key) { 984 // Swap the entry at the provided value 985 let prev = mem::replace(entry, Entry::Vacant(self.next)); 986 987 match prev { 988 Entry::Occupied(val) => { 989 self.len -= 1; 990 self.next = key; 991 return val.into(); 992 } 993 _ => { 994 // Woops, the entry is actually vacant, restore the state 995 *entry = prev; 996 } 997 } 998 } 999 None 1000 } 1001 1002 /// Remove and return the value associated with the given key. 1003 /// 1004 /// The key is then released and may be associated with future stored 1005 /// values. 1006 /// 1007 /// # Panics 1008 /// 1009 /// Panics if `key` is not associated with a value. 1010 /// 1011 /// # Examples 1012 /// 1013 /// ``` 1014 /// # use slab::*; 1015 /// let mut slab = Slab::new(); 1016 /// 1017 /// let hello = slab.insert("hello"); 1018 /// 1019 /// assert_eq!(slab.remove(hello), "hello"); 1020 /// assert!(!slab.contains(hello)); 1021 /// ``` remove(&mut self, key: usize) -> T1022 pub fn remove(&mut self, key: usize) -> T { 1023 self.try_remove(key).expect("invalid key") 1024 } 1025 1026 /// Return `true` if a value is associated with the given key. 1027 /// 1028 /// # Examples 1029 /// 1030 /// ``` 1031 /// # use slab::*; 1032 /// let mut slab = Slab::new(); 1033 /// 1034 /// let hello = slab.insert("hello"); 1035 /// assert!(slab.contains(hello)); 1036 /// 1037 /// slab.remove(hello); 1038 /// 1039 /// assert!(!slab.contains(hello)); 1040 /// ``` contains(&self, key: usize) -> bool1041 pub fn contains(&self, key: usize) -> bool { 1042 match self.entries.get(key) { 1043 Some(&Entry::Occupied(_)) => true, 1044 _ => false, 1045 } 1046 } 1047 1048 /// Retain only the elements specified by the predicate. 1049 /// 1050 /// In other words, remove all elements `e` such that `f(usize, &mut e)` 1051 /// returns false. This method operates in place and preserves the key 1052 /// associated with the retained values. 1053 /// 1054 /// # Examples 1055 /// 1056 /// ``` 1057 /// # use slab::*; 1058 /// let mut slab = Slab::new(); 1059 /// 1060 /// let k1 = slab.insert(0); 1061 /// let k2 = slab.insert(1); 1062 /// let k3 = slab.insert(2); 1063 /// 1064 /// slab.retain(|key, val| key == k1 || *val == 1); 1065 /// 1066 /// assert!(slab.contains(k1)); 1067 /// assert!(slab.contains(k2)); 1068 /// assert!(!slab.contains(k3)); 1069 /// 1070 /// assert_eq!(2, slab.len()); 1071 /// ``` retain<F>(&mut self, mut f: F) where F: FnMut(usize, &mut T) -> bool,1072 pub fn retain<F>(&mut self, mut f: F) 1073 where 1074 F: FnMut(usize, &mut T) -> bool, 1075 { 1076 for i in 0..self.entries.len() { 1077 let keep = match self.entries[i] { 1078 Entry::Occupied(ref mut v) => f(i, v), 1079 _ => true, 1080 }; 1081 1082 if !keep { 1083 self.remove(i); 1084 } 1085 } 1086 } 1087 1088 /// Return a draining iterator that removes all elements from the slab and 1089 /// yields the removed items. 1090 /// 1091 /// Note: Elements are removed even if the iterator is only partially 1092 /// consumed or not consumed at all. 1093 /// 1094 /// # Examples 1095 /// 1096 /// ``` 1097 /// # use slab::*; 1098 /// let mut slab = Slab::new(); 1099 /// 1100 /// let _ = slab.insert(0); 1101 /// let _ = slab.insert(1); 1102 /// let _ = slab.insert(2); 1103 /// 1104 /// { 1105 /// let mut drain = slab.drain(); 1106 /// 1107 /// assert_eq!(Some(0), drain.next()); 1108 /// assert_eq!(Some(1), drain.next()); 1109 /// assert_eq!(Some(2), drain.next()); 1110 /// assert_eq!(None, drain.next()); 1111 /// } 1112 /// 1113 /// assert!(slab.is_empty()); 1114 /// ``` drain(&mut self) -> Drain<'_, T>1115 pub fn drain(&mut self) -> Drain<'_, T> { 1116 let old_len = self.len; 1117 self.len = 0; 1118 self.next = 0; 1119 Drain { 1120 inner: self.entries.drain(..), 1121 len: old_len, 1122 } 1123 } 1124 } 1125 1126 impl<T> ops::Index<usize> for Slab<T> { 1127 type Output = T; 1128 index(&self, key: usize) -> &T1129 fn index(&self, key: usize) -> &T { 1130 match self.entries.get(key) { 1131 Some(&Entry::Occupied(ref v)) => v, 1132 _ => panic!("invalid key"), 1133 } 1134 } 1135 } 1136 1137 impl<T> ops::IndexMut<usize> for Slab<T> { index_mut(&mut self, key: usize) -> &mut T1138 fn index_mut(&mut self, key: usize) -> &mut T { 1139 match self.entries.get_mut(key) { 1140 Some(&mut Entry::Occupied(ref mut v)) => v, 1141 _ => panic!("invalid key"), 1142 } 1143 } 1144 } 1145 1146 impl<T> IntoIterator for Slab<T> { 1147 type Item = (usize, T); 1148 type IntoIter = IntoIter<T>; 1149 into_iter(self) -> IntoIter<T>1150 fn into_iter(self) -> IntoIter<T> { 1151 IntoIter { 1152 entries: self.entries.into_iter().enumerate(), 1153 len: self.len, 1154 } 1155 } 1156 } 1157 1158 impl<'a, T> IntoIterator for &'a Slab<T> { 1159 type Item = (usize, &'a T); 1160 type IntoIter = Iter<'a, T>; 1161 into_iter(self) -> Iter<'a, T>1162 fn into_iter(self) -> Iter<'a, T> { 1163 self.iter() 1164 } 1165 } 1166 1167 impl<'a, T> IntoIterator for &'a mut Slab<T> { 1168 type Item = (usize, &'a mut T); 1169 type IntoIter = IterMut<'a, T>; 1170 into_iter(self) -> IterMut<'a, T>1171 fn into_iter(self) -> IterMut<'a, T> { 1172 self.iter_mut() 1173 } 1174 } 1175 1176 /// Create a slab from an iterator of key-value pairs. 1177 /// 1178 /// If the iterator produces duplicate keys, the previous value is replaced with the later one. 1179 /// The keys does not need to be sorted beforehand, and this function always 1180 /// takes O(n) time. 1181 /// Note that the returned slab will use space proportional to the largest key, 1182 /// so don't use `Slab` with untrusted keys. 1183 /// 1184 /// # Examples 1185 /// 1186 /// ``` 1187 /// # use slab::*; 1188 /// 1189 /// let vec = vec![(2,'a'), (6,'b'), (7,'c')]; 1190 /// let slab = vec.into_iter().collect::<Slab<char>>(); 1191 /// assert_eq!(slab.len(), 3); 1192 /// assert!(slab.capacity() >= 8); 1193 /// assert_eq!(slab[2], 'a'); 1194 /// ``` 1195 /// 1196 /// With duplicate and unsorted keys: 1197 /// 1198 /// ``` 1199 /// # use slab::*; 1200 /// 1201 /// let vec = vec![(20,'a'), (10,'b'), (11,'c'), (10,'d')]; 1202 /// let slab = vec.into_iter().collect::<Slab<char>>(); 1203 /// assert_eq!(slab.len(), 3); 1204 /// assert_eq!(slab[10], 'd'); 1205 /// ``` 1206 impl<T> FromIterator<(usize, T)> for Slab<T> { from_iter<I>(iterable: I) -> Self where I: IntoIterator<Item = (usize, T)>,1207 fn from_iter<I>(iterable: I) -> Self 1208 where 1209 I: IntoIterator<Item = (usize, T)>, 1210 { 1211 let iterator = iterable.into_iter(); 1212 let mut slab = Self::with_capacity(iterator.size_hint().0); 1213 1214 let mut vacant_list_broken = false; 1215 let mut first_vacant_index = None; 1216 for (key, value) in iterator { 1217 if key < slab.entries.len() { 1218 // iterator is not sorted, might need to recreate vacant list 1219 if let Entry::Vacant(_) = slab.entries[key] { 1220 vacant_list_broken = true; 1221 slab.len += 1; 1222 } 1223 // if an element with this key already exists, replace it. 1224 // This is consistent with HashMap and BtreeMap 1225 slab.entries[key] = Entry::Occupied(value); 1226 } else { 1227 if first_vacant_index.is_none() && slab.entries.len() < key { 1228 first_vacant_index = Some(slab.entries.len()); 1229 } 1230 // insert holes as necessary 1231 while slab.entries.len() < key { 1232 // add the entry to the start of the vacant list 1233 let next = slab.next; 1234 slab.next = slab.entries.len(); 1235 slab.entries.push(Entry::Vacant(next)); 1236 } 1237 slab.entries.push(Entry::Occupied(value)); 1238 slab.len += 1; 1239 } 1240 } 1241 if slab.len == slab.entries.len() { 1242 // no vacant entries, so next might not have been updated 1243 slab.next = slab.entries.len(); 1244 } else if vacant_list_broken { 1245 slab.recreate_vacant_list(); 1246 } else if let Some(first_vacant_index) = first_vacant_index { 1247 let next = slab.entries.len(); 1248 match &mut slab.entries[first_vacant_index] { 1249 Entry::Vacant(n) => *n = next, 1250 _ => unreachable!(), 1251 } 1252 } else { 1253 unreachable!() 1254 } 1255 1256 slab 1257 } 1258 } 1259 1260 impl<T> fmt::Debug for Slab<T> 1261 where 1262 T: fmt::Debug, 1263 { fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result1264 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { 1265 if fmt.alternate() { 1266 fmt.debug_map().entries(self.iter()).finish() 1267 } else { 1268 fmt.debug_struct("Slab") 1269 .field("len", &self.len) 1270 .field("cap", &self.capacity()) 1271 .finish() 1272 } 1273 } 1274 } 1275 1276 impl<T> fmt::Debug for IntoIter<T> 1277 where 1278 T: fmt::Debug, 1279 { fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result1280 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { 1281 fmt.debug_struct("IntoIter") 1282 .field("remaining", &self.len) 1283 .finish() 1284 } 1285 } 1286 1287 impl<T> fmt::Debug for Iter<'_, T> 1288 where 1289 T: fmt::Debug, 1290 { fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result1291 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { 1292 fmt.debug_struct("Iter") 1293 .field("remaining", &self.len) 1294 .finish() 1295 } 1296 } 1297 1298 impl<T> fmt::Debug for IterMut<'_, T> 1299 where 1300 T: fmt::Debug, 1301 { fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result1302 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { 1303 fmt.debug_struct("IterMut") 1304 .field("remaining", &self.len) 1305 .finish() 1306 } 1307 } 1308 1309 impl<T> fmt::Debug for Drain<'_, T> { fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result1310 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { 1311 fmt.debug_struct("Drain").finish() 1312 } 1313 } 1314 1315 // ===== VacantEntry ===== 1316 1317 impl<'a, T> VacantEntry<'a, T> { 1318 /// Insert a value in the entry, returning a mutable reference to the value. 1319 /// 1320 /// To get the key associated with the value, use `key` prior to calling 1321 /// `insert`. 1322 /// 1323 /// # Examples 1324 /// 1325 /// ``` 1326 /// # use slab::*; 1327 /// let mut slab = Slab::new(); 1328 /// 1329 /// let hello = { 1330 /// let entry = slab.vacant_entry(); 1331 /// let key = entry.key(); 1332 /// 1333 /// entry.insert((key, "hello")); 1334 /// key 1335 /// }; 1336 /// 1337 /// assert_eq!(hello, slab[hello].0); 1338 /// assert_eq!("hello", slab[hello].1); 1339 /// ``` insert(self, val: T) -> &'a mut T1340 pub fn insert(self, val: T) -> &'a mut T { 1341 self.slab.insert_at(self.key, val); 1342 1343 match self.slab.entries.get_mut(self.key) { 1344 Some(&mut Entry::Occupied(ref mut v)) => v, 1345 _ => unreachable!(), 1346 } 1347 } 1348 1349 /// Return the key associated with this entry. 1350 /// 1351 /// A value stored in this entry will be associated with this key. 1352 /// 1353 /// # Examples 1354 /// 1355 /// ``` 1356 /// # use slab::*; 1357 /// let mut slab = Slab::new(); 1358 /// 1359 /// let hello = { 1360 /// let entry = slab.vacant_entry(); 1361 /// let key = entry.key(); 1362 /// 1363 /// entry.insert((key, "hello")); 1364 /// key 1365 /// }; 1366 /// 1367 /// assert_eq!(hello, slab[hello].0); 1368 /// assert_eq!("hello", slab[hello].1); 1369 /// ``` key(&self) -> usize1370 pub fn key(&self) -> usize { 1371 self.key 1372 } 1373 } 1374 1375 // ===== IntoIter ===== 1376 1377 impl<T> Iterator for IntoIter<T> { 1378 type Item = (usize, T); 1379 next(&mut self) -> Option<Self::Item>1380 fn next(&mut self) -> Option<Self::Item> { 1381 for (key, entry) in &mut self.entries { 1382 if let Entry::Occupied(v) = entry { 1383 self.len -= 1; 1384 return Some((key, v)); 1385 } 1386 } 1387 1388 debug_assert_eq!(self.len, 0); 1389 None 1390 } 1391 size_hint(&self) -> (usize, Option<usize>)1392 fn size_hint(&self) -> (usize, Option<usize>) { 1393 (self.len, Some(self.len)) 1394 } 1395 } 1396 1397 impl<T> DoubleEndedIterator for IntoIter<T> { next_back(&mut self) -> Option<Self::Item>1398 fn next_back(&mut self) -> Option<Self::Item> { 1399 while let Some((key, entry)) = self.entries.next_back() { 1400 if let Entry::Occupied(v) = entry { 1401 self.len -= 1; 1402 return Some((key, v)); 1403 } 1404 } 1405 1406 debug_assert_eq!(self.len, 0); 1407 None 1408 } 1409 } 1410 1411 impl<T> ExactSizeIterator for IntoIter<T> { len(&self) -> usize1412 fn len(&self) -> usize { 1413 self.len 1414 } 1415 } 1416 1417 impl<T> FusedIterator for IntoIter<T> {} 1418 1419 // ===== Iter ===== 1420 1421 impl<'a, T> Iterator for Iter<'a, T> { 1422 type Item = (usize, &'a T); 1423 next(&mut self) -> Option<Self::Item>1424 fn next(&mut self) -> Option<Self::Item> { 1425 for (key, entry) in &mut self.entries { 1426 if let Entry::Occupied(ref v) = *entry { 1427 self.len -= 1; 1428 return Some((key, v)); 1429 } 1430 } 1431 1432 debug_assert_eq!(self.len, 0); 1433 None 1434 } 1435 size_hint(&self) -> (usize, Option<usize>)1436 fn size_hint(&self) -> (usize, Option<usize>) { 1437 (self.len, Some(self.len)) 1438 } 1439 } 1440 1441 impl<T> DoubleEndedIterator for Iter<'_, T> { next_back(&mut self) -> Option<Self::Item>1442 fn next_back(&mut self) -> Option<Self::Item> { 1443 while let Some((key, entry)) = self.entries.next_back() { 1444 if let Entry::Occupied(ref v) = *entry { 1445 self.len -= 1; 1446 return Some((key, v)); 1447 } 1448 } 1449 1450 debug_assert_eq!(self.len, 0); 1451 None 1452 } 1453 } 1454 1455 impl<T> ExactSizeIterator for Iter<'_, T> { len(&self) -> usize1456 fn len(&self) -> usize { 1457 self.len 1458 } 1459 } 1460 1461 impl<T> FusedIterator for Iter<'_, T> {} 1462 1463 // ===== IterMut ===== 1464 1465 impl<'a, T> Iterator for IterMut<'a, T> { 1466 type Item = (usize, &'a mut T); 1467 next(&mut self) -> Option<Self::Item>1468 fn next(&mut self) -> Option<Self::Item> { 1469 for (key, entry) in &mut self.entries { 1470 if let Entry::Occupied(ref mut v) = *entry { 1471 self.len -= 1; 1472 return Some((key, v)); 1473 } 1474 } 1475 1476 debug_assert_eq!(self.len, 0); 1477 None 1478 } 1479 size_hint(&self) -> (usize, Option<usize>)1480 fn size_hint(&self) -> (usize, Option<usize>) { 1481 (self.len, Some(self.len)) 1482 } 1483 } 1484 1485 impl<T> DoubleEndedIterator for IterMut<'_, T> { next_back(&mut self) -> Option<Self::Item>1486 fn next_back(&mut self) -> Option<Self::Item> { 1487 while let Some((key, entry)) = self.entries.next_back() { 1488 if let Entry::Occupied(ref mut v) = *entry { 1489 self.len -= 1; 1490 return Some((key, v)); 1491 } 1492 } 1493 1494 debug_assert_eq!(self.len, 0); 1495 None 1496 } 1497 } 1498 1499 impl<T> ExactSizeIterator for IterMut<'_, T> { len(&self) -> usize1500 fn len(&self) -> usize { 1501 self.len 1502 } 1503 } 1504 1505 impl<T> FusedIterator for IterMut<'_, T> {} 1506 1507 // ===== Drain ===== 1508 1509 impl<T> Iterator for Drain<'_, T> { 1510 type Item = T; 1511 next(&mut self) -> Option<Self::Item>1512 fn next(&mut self) -> Option<Self::Item> { 1513 for entry in &mut self.inner { 1514 if let Entry::Occupied(v) = entry { 1515 self.len -= 1; 1516 return Some(v); 1517 } 1518 } 1519 1520 debug_assert_eq!(self.len, 0); 1521 None 1522 } 1523 size_hint(&self) -> (usize, Option<usize>)1524 fn size_hint(&self) -> (usize, Option<usize>) { 1525 (self.len, Some(self.len)) 1526 } 1527 } 1528 1529 impl<T> DoubleEndedIterator for Drain<'_, T> { next_back(&mut self) -> Option<Self::Item>1530 fn next_back(&mut self) -> Option<Self::Item> { 1531 while let Some(entry) = self.inner.next_back() { 1532 if let Entry::Occupied(v) = entry { 1533 self.len -= 1; 1534 return Some(v); 1535 } 1536 } 1537 1538 debug_assert_eq!(self.len, 0); 1539 None 1540 } 1541 } 1542 1543 impl<T> ExactSizeIterator for Drain<'_, T> { len(&self) -> usize1544 fn len(&self) -> usize { 1545 self.len 1546 } 1547 } 1548 1549 impl<T> FusedIterator for Drain<'_, T> {} 1550