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