1 #![doc(html_root_url = "https://docs.rs/slab/0.4.2")] 2 #![deny(warnings, missing_docs, missing_debug_implementations)] 3 #![cfg_attr(test, deny(warnings, unreachable_pub))] 4 5 //! Pre-allocated storage for a uniform data type. 6 //! 7 //! `Slab` provides pre-allocated storage for a single data type. If many values 8 //! of a single type are being allocated, it can be more efficient to 9 //! pre-allocate the necessary storage. Since the size of the type is uniform, 10 //! memory fragmentation can be avoided. Storing, clearing, and lookup 11 //! operations become very cheap. 12 //! 13 //! While `Slab` may look like other Rust collections, it is not intended to be 14 //! used as a general purpose collection. The primary difference between `Slab` 15 //! and `Vec` is that `Slab` returns the key when storing the value. 16 //! 17 //! It is important to note that keys may be reused. In other words, once a 18 //! value associated with a given key is removed from a slab, that key may be 19 //! returned from future calls to `insert`. 20 //! 21 //! # Examples 22 //! 23 //! Basic storing and retrieval. 24 //! 25 //! ``` 26 //! # use slab::*; 27 //! let mut slab = Slab::new(); 28 //! 29 //! let hello = slab.insert("hello"); 30 //! let world = slab.insert("world"); 31 //! 32 //! assert_eq!(slab[hello], "hello"); 33 //! assert_eq!(slab[world], "world"); 34 //! 35 //! slab[world] = "earth"; 36 //! assert_eq!(slab[world], "earth"); 37 //! ``` 38 //! 39 //! Sometimes it is useful to be able to associate the key with the value being 40 //! inserted in the slab. This can be done with the `vacant_entry` API as such: 41 //! 42 //! ``` 43 //! # use slab::*; 44 //! let mut slab = Slab::new(); 45 //! 46 //! let hello = { 47 //! let entry = slab.vacant_entry(); 48 //! let key = entry.key(); 49 //! 50 //! entry.insert((key, "hello")); 51 //! key 52 //! }; 53 //! 54 //! assert_eq!(hello, slab[hello].0); 55 //! assert_eq!("hello", slab[hello].1); 56 //! ``` 57 //! 58 //! It is generally a good idea to specify the desired capacity of a slab at 59 //! creation time. Note that `Slab` will grow the internal capacity when 60 //! attempting to insert a new value once the existing capacity has been reached. 61 //! To avoid this, add a check. 62 //! 63 //! ``` 64 //! # use slab::*; 65 //! let mut slab = Slab::with_capacity(1024); 66 //! 67 //! // ... use the slab 68 //! 69 //! if slab.len() == slab.capacity() { 70 //! panic!("slab full"); 71 //! } 72 //! 73 //! slab.insert("the slab is not at capacity yet"); 74 //! ``` 75 //! 76 //! # Capacity and reallocation 77 //! 78 //! The capacity of a slab is the amount of space allocated for any future 79 //! values that will be inserted in the slab. This is not to be confused with 80 //! the *length* of the slab, which specifies the number of actual values 81 //! currently being inserted. If a slab's length is equal to its capacity, the 82 //! next value inserted into the slab will require growing the slab by 83 //! reallocating. 84 //! 85 //! For example, a slab with capacity 10 and length 0 would be an empty slab 86 //! with space for 10 more stored values. Storing 10 or fewer elements into the 87 //! slab will not change its capacity or cause reallocation to occur. However, 88 //! if the slab length is increased to 11 (due to another `insert`), it will 89 //! have to reallocate, which can be slow. For this reason, it is recommended to 90 //! use [`Slab::with_capacity`] whenever possible to specify how many values the 91 //! slab is expected to store. 92 //! 93 //! # Implementation 94 //! 95 //! `Slab` is backed by a `Vec` of slots. Each slot is either occupied or 96 //! vacant. `Slab` maintains a stack of vacant slots using a linked list. To 97 //! find a vacant slot, the stack is popped. When a slot is released, it is 98 //! pushed onto the stack. 99 //! 100 //! If there are no more available slots in the stack, then `Vec::reserve(1)` is 101 //! called and a new slot is created. 102 //! 103 //! [`Slab::with_capacity`]: struct.Slab.html#with_capacity 104 105 use std::iter::IntoIterator; 106 use std::ops; 107 use std::vec; 108 use std::{fmt, mem}; 109 110 /// Pre-allocated storage for a uniform data type 111 /// 112 /// See the [module documentation] for more details. 113 /// 114 /// [module documentation]: index.html 115 #[derive(Clone)] 116 pub struct Slab<T> { 117 // Chunk of memory 118 entries: Vec<Entry<T>>, 119 120 // Number of Filled elements currently in the slab 121 len: usize, 122 123 // Offset of the next available slot in the slab. Set to the slab's 124 // capacity when the slab is full. 125 next: usize, 126 } 127 128 impl<T> Default for Slab<T> { default() -> Self129 fn default() -> Self { 130 Slab::new() 131 } 132 } 133 134 /// A handle to a vacant entry in a `Slab`. 135 /// 136 /// `VacantEntry` allows constructing values with the key that they will be 137 /// assigned to. 138 /// 139 /// # Examples 140 /// 141 /// ``` 142 /// # use slab::*; 143 /// let mut slab = Slab::new(); 144 /// 145 /// let hello = { 146 /// let entry = slab.vacant_entry(); 147 /// let key = entry.key(); 148 /// 149 /// entry.insert((key, "hello")); 150 /// key 151 /// }; 152 /// 153 /// assert_eq!(hello, slab[hello].0); 154 /// assert_eq!("hello", slab[hello].1); 155 /// ``` 156 #[derive(Debug)] 157 pub struct VacantEntry<'a, T: 'a> { 158 slab: &'a mut Slab<T>, 159 key: usize, 160 } 161 162 /// An iterator over the values stored in the `Slab` 163 pub struct Iter<'a, T: 'a> { 164 entries: std::slice::Iter<'a, Entry<T>>, 165 curr: usize, 166 } 167 168 /// A mutable iterator over the values stored in the `Slab` 169 pub struct IterMut<'a, T: 'a> { 170 entries: std::slice::IterMut<'a, Entry<T>>, 171 curr: usize, 172 } 173 174 /// A draining iterator for `Slab` 175 pub struct Drain<'a, T: 'a>(vec::Drain<'a, Entry<T>>); 176 177 #[derive(Clone)] 178 enum Entry<T> { 179 Vacant(usize), 180 Occupied(T), 181 } 182 183 impl<T> Slab<T> { 184 /// Construct a new, empty `Slab`. 185 /// 186 /// The function does not allocate and the returned slab will have no 187 /// capacity until `insert` is called or capacity is explicitly reserved. 188 /// 189 /// # Examples 190 /// 191 /// ``` 192 /// # use slab::*; 193 /// let slab: Slab<i32> = Slab::new(); 194 /// ``` new() -> Slab<T>195 pub fn new() -> Slab<T> { 196 Slab::with_capacity(0) 197 } 198 199 /// Construct a new, empty `Slab` with the specified capacity. 200 /// 201 /// The returned slab will be able to store exactly `capacity` without 202 /// reallocating. If `capacity` is 0, the slab will not allocate. 203 /// 204 /// It is important to note that this function does not specify the *length* 205 /// of the returned slab, but only the capacity. For an explanation of the 206 /// difference between length and capacity, see [Capacity and 207 /// reallocation](index.html#capacity-and-reallocation). 208 /// 209 /// # Examples 210 /// 211 /// ``` 212 /// # use slab::*; 213 /// let mut slab = Slab::with_capacity(10); 214 /// 215 /// // The slab contains no values, even though it has capacity for more 216 /// assert_eq!(slab.len(), 0); 217 /// 218 /// // These are all done without reallocating... 219 /// for i in 0..10 { 220 /// slab.insert(i); 221 /// } 222 /// 223 /// // ...but this may make the slab reallocate 224 /// slab.insert(11); 225 /// ``` with_capacity(capacity: usize) -> Slab<T>226 pub fn with_capacity(capacity: usize) -> Slab<T> { 227 Slab { 228 entries: Vec::with_capacity(capacity), 229 next: 0, 230 len: 0, 231 } 232 } 233 234 /// Return the number of values the slab can store without reallocating. 235 /// 236 /// # Examples 237 /// 238 /// ``` 239 /// # use slab::*; 240 /// let slab: Slab<i32> = Slab::with_capacity(10); 241 /// assert_eq!(slab.capacity(), 10); 242 /// ``` capacity(&self) -> usize243 pub fn capacity(&self) -> usize { 244 self.entries.capacity() 245 } 246 247 /// Reserve capacity for at least `additional` more values to be stored 248 /// without allocating. 249 /// 250 /// `reserve` does nothing if the slab already has sufficient capacity for 251 /// `additional` more values. If more capacity is required, a new segment of 252 /// memory will be allocated and all existing values will be copied into it. 253 /// As such, if the slab is already very large, a call to `reserve` can end 254 /// up being expensive. 255 /// 256 /// The slab may reserve more than `additional` extra space in order to 257 /// avoid frequent reallocations. Use `reserve_exact` instead to guarantee 258 /// that only the requested space is allocated. 259 /// 260 /// # Panics 261 /// 262 /// Panics if the new capacity overflows `usize`. 263 /// 264 /// # Examples 265 /// 266 /// ``` 267 /// # use slab::*; 268 /// let mut slab = Slab::new(); 269 /// slab.insert("hello"); 270 /// slab.reserve(10); 271 /// assert!(slab.capacity() >= 11); 272 /// ``` reserve(&mut self, additional: usize)273 pub fn reserve(&mut self, additional: usize) { 274 if self.capacity() - self.len >= additional { 275 return; 276 } 277 let need_add = self.len + additional - self.entries.len(); 278 self.entries.reserve(need_add); 279 } 280 281 /// Reserve the minimum capacity required to store exactly `additional` 282 /// more values. 283 /// 284 /// `reserve_exact` does nothing if the slab already has sufficient capacity 285 /// for `additional` more valus. If more capacity is required, a new segment 286 /// of memory will be allocated and all existing values will be copied into 287 /// it. As such, if the slab is already very large, a call to `reserve` can 288 /// end up being expensive. 289 /// 290 /// Note that the allocator may give the slab more space than it requests. 291 /// Therefore capacity can not be relied upon to be precisely minimal. 292 /// Prefer `reserve` if future insertions are expected. 293 /// 294 /// # Panics 295 /// 296 /// Panics if the new capacity overflows `usize`. 297 /// 298 /// # Examples 299 /// 300 /// ``` 301 /// # use slab::*; 302 /// let mut slab = Slab::new(); 303 /// slab.insert("hello"); 304 /// slab.reserve_exact(10); 305 /// assert!(slab.capacity() >= 11); 306 /// ``` reserve_exact(&mut self, additional: usize)307 pub fn reserve_exact(&mut self, additional: usize) { 308 if self.capacity() - self.len >= additional { 309 return; 310 } 311 let need_add = self.len + additional - self.entries.len(); 312 self.entries.reserve_exact(need_add); 313 } 314 315 /// Shrink the capacity of the slab as much as possible. 316 /// 317 /// It will drop down as close as possible to the length but the allocator 318 /// may still inform the vector that there is space for a few more elements. 319 /// Also, since values are not moved, the slab cannot shrink past any stored 320 /// values. 321 /// 322 /// # Examples 323 /// 324 /// ``` 325 /// # use slab::*; 326 /// let mut slab = Slab::with_capacity(10); 327 /// 328 /// for i in 0..3 { 329 /// slab.insert(i); 330 /// } 331 /// 332 /// assert_eq!(slab.capacity(), 10); 333 /// slab.shrink_to_fit(); 334 /// assert!(slab.capacity() >= 3); 335 /// ``` 336 /// 337 /// In this case, even though two values are removed, the slab cannot shrink 338 /// past the last value. 339 /// 340 /// ``` 341 /// # use slab::*; 342 /// let mut slab = Slab::with_capacity(10); 343 /// 344 /// for i in 0..3 { 345 /// slab.insert(i); 346 /// } 347 /// 348 /// slab.remove(0); 349 /// slab.remove(1); 350 /// 351 /// assert_eq!(slab.capacity(), 10); 352 /// slab.shrink_to_fit(); 353 /// assert!(slab.capacity() >= 3); 354 /// ``` shrink_to_fit(&mut self)355 pub fn shrink_to_fit(&mut self) { 356 self.entries.shrink_to_fit(); 357 } 358 359 /// Clear the slab of all values. 360 /// 361 /// # Examples 362 /// 363 /// ``` 364 /// # use slab::*; 365 /// let mut slab = Slab::new(); 366 /// 367 /// for i in 0..3 { 368 /// slab.insert(i); 369 /// } 370 /// 371 /// slab.clear(); 372 /// assert!(slab.is_empty()); 373 /// ``` clear(&mut self)374 pub fn clear(&mut self) { 375 self.entries.clear(); 376 self.len = 0; 377 self.next = 0; 378 } 379 380 /// Return the number of stored values. 381 /// 382 /// # Examples 383 /// 384 /// ``` 385 /// # use slab::*; 386 /// let mut slab = Slab::new(); 387 /// 388 /// for i in 0..3 { 389 /// slab.insert(i); 390 /// } 391 /// 392 /// assert_eq!(3, slab.len()); 393 /// ``` len(&self) -> usize394 pub fn len(&self) -> usize { 395 self.len 396 } 397 398 /// Return `true` if there are no values stored in the slab. 399 /// 400 /// # Examples 401 /// 402 /// ``` 403 /// # use slab::*; 404 /// let mut slab = Slab::new(); 405 /// assert!(slab.is_empty()); 406 /// 407 /// slab.insert(1); 408 /// assert!(!slab.is_empty()); 409 /// ``` is_empty(&self) -> bool410 pub fn is_empty(&self) -> bool { 411 self.len == 0 412 } 413 414 /// Return an iterator over the slab. 415 /// 416 /// This function should generally be **avoided** as it is not efficient. 417 /// Iterators must iterate over every slot in the slab even if it is 418 /// vacant. As such, a slab with a capacity of 1 million but only one 419 /// stored value must still iterate the million slots. 420 /// 421 /// # Examples 422 /// 423 /// ``` 424 /// # use slab::*; 425 /// let mut slab = Slab::new(); 426 /// 427 /// for i in 0..3 { 428 /// slab.insert(i); 429 /// } 430 /// 431 /// let mut iterator = slab.iter(); 432 /// 433 /// assert_eq!(iterator.next(), Some((0, &0))); 434 /// assert_eq!(iterator.next(), Some((1, &1))); 435 /// assert_eq!(iterator.next(), Some((2, &2))); 436 /// assert_eq!(iterator.next(), None); 437 /// ``` iter(&self) -> Iter<T>438 pub fn iter(&self) -> Iter<T> { 439 Iter { 440 entries: self.entries.iter(), 441 curr: 0, 442 } 443 } 444 445 /// Return an iterator that allows modifying each value. 446 /// 447 /// This function should generally be **avoided** as it is not efficient. 448 /// Iterators must iterate over every slot in the slab even if it is 449 /// vacant. As such, a slab with a capacity of 1 million but only one 450 /// stored value must still iterate the million slots. 451 /// 452 /// # Examples 453 /// 454 /// ``` 455 /// # use slab::*; 456 /// let mut slab = Slab::new(); 457 /// 458 /// let key1 = slab.insert(0); 459 /// let key2 = slab.insert(1); 460 /// 461 /// for (key, val) in slab.iter_mut() { 462 /// if key == key1 { 463 /// *val += 2; 464 /// } 465 /// } 466 /// 467 /// assert_eq!(slab[key1], 2); 468 /// assert_eq!(slab[key2], 1); 469 /// ``` iter_mut(&mut self) -> IterMut<T>470 pub fn iter_mut(&mut self) -> IterMut<T> { 471 IterMut { 472 entries: self.entries.iter_mut(), 473 curr: 0, 474 } 475 } 476 477 /// Return a reference to the value associated with the given key. 478 /// 479 /// If the given key is not associated with a value, then `None` is 480 /// returned. 481 /// 482 /// # Examples 483 /// 484 /// ``` 485 /// # use slab::*; 486 /// let mut slab = Slab::new(); 487 /// let key = slab.insert("hello"); 488 /// 489 /// assert_eq!(slab.get(key), Some(&"hello")); 490 /// assert_eq!(slab.get(123), None); 491 /// ``` get(&self, key: usize) -> Option<&T>492 pub fn get(&self, key: usize) -> Option<&T> { 493 match self.entries.get(key) { 494 Some(&Entry::Occupied(ref val)) => Some(val), 495 _ => None, 496 } 497 } 498 499 /// Return a mutable reference to the value associated with the given key. 500 /// 501 /// If the given key is not associated with a value, then `None` is 502 /// returned. 503 /// 504 /// # Examples 505 /// 506 /// ``` 507 /// # use slab::*; 508 /// let mut slab = Slab::new(); 509 /// let key = slab.insert("hello"); 510 /// 511 /// *slab.get_mut(key).unwrap() = "world"; 512 /// 513 /// assert_eq!(slab[key], "world"); 514 /// assert_eq!(slab.get_mut(123), None); 515 /// ``` get_mut(&mut self, key: usize) -> Option<&mut T>516 pub fn get_mut(&mut self, key: usize) -> Option<&mut T> { 517 match self.entries.get_mut(key) { 518 Some(&mut Entry::Occupied(ref mut val)) => Some(val), 519 _ => None, 520 } 521 } 522 523 /// Return a reference to the value associated with the given key without 524 /// performing bounds checking. 525 /// 526 /// This function should be used with care. 527 /// 528 /// # Examples 529 /// 530 /// ``` 531 /// # use slab::*; 532 /// let mut slab = Slab::new(); 533 /// let key = slab.insert(2); 534 /// 535 /// unsafe { 536 /// assert_eq!(slab.get_unchecked(key), &2); 537 /// } 538 /// ``` get_unchecked(&self, key: usize) -> &T539 pub unsafe fn get_unchecked(&self, key: usize) -> &T { 540 match *self.entries.get_unchecked(key) { 541 Entry::Occupied(ref val) => val, 542 _ => unreachable!(), 543 } 544 } 545 546 /// Return a mutable reference to the value associated with the given key 547 /// without performing bounds checking. 548 /// 549 /// This function should be used with care. 550 /// 551 /// # Examples 552 /// 553 /// ``` 554 /// # use slab::*; 555 /// let mut slab = Slab::new(); 556 /// let key = slab.insert(2); 557 /// 558 /// unsafe { 559 /// let val = slab.get_unchecked_mut(key); 560 /// *val = 13; 561 /// } 562 /// 563 /// assert_eq!(slab[key], 13); 564 /// ``` get_unchecked_mut(&mut self, key: usize) -> &mut T565 pub unsafe fn get_unchecked_mut(&mut self, key: usize) -> &mut T { 566 match *self.entries.get_unchecked_mut(key) { 567 Entry::Occupied(ref mut val) => val, 568 _ => unreachable!(), 569 } 570 } 571 572 /// Insert a value in the slab, returning key assigned to the value. 573 /// 574 /// The returned key can later be used to retrieve or remove the value using indexed 575 /// lookup and `remove`. Additional capacity is allocated if needed. See 576 /// [Capacity and reallocation](index.html#capacity-and-reallocation). 577 /// 578 /// # Panics 579 /// 580 /// Panics if the number of elements in the vector overflows a `usize`. 581 /// 582 /// # Examples 583 /// 584 /// ``` 585 /// # use slab::*; 586 /// let mut slab = Slab::new(); 587 /// let key = slab.insert("hello"); 588 /// assert_eq!(slab[key], "hello"); 589 /// ``` insert(&mut self, val: T) -> usize590 pub fn insert(&mut self, val: T) -> usize { 591 let key = self.next; 592 593 self.insert_at(key, val); 594 595 key 596 } 597 598 /// Return a handle to a vacant entry allowing for further manipulation. 599 /// 600 /// This function is useful when creating values that must contain their 601 /// slab key. The returned `VacantEntry` reserves a slot in the slab and is 602 /// able to query the associated key. 603 /// 604 /// # Examples 605 /// 606 /// ``` 607 /// # use slab::*; 608 /// let mut slab = Slab::new(); 609 /// 610 /// let hello = { 611 /// let entry = slab.vacant_entry(); 612 /// let key = entry.key(); 613 /// 614 /// entry.insert((key, "hello")); 615 /// key 616 /// }; 617 /// 618 /// assert_eq!(hello, slab[hello].0); 619 /// assert_eq!("hello", slab[hello].1); 620 /// ``` vacant_entry(&mut self) -> VacantEntry<T>621 pub fn vacant_entry(&mut self) -> VacantEntry<T> { 622 VacantEntry { 623 key: self.next, 624 slab: self, 625 } 626 } 627 insert_at(&mut self, key: usize, val: T)628 fn insert_at(&mut self, key: usize, val: T) { 629 self.len += 1; 630 631 if key == self.entries.len() { 632 self.entries.push(Entry::Occupied(val)); 633 self.next = key + 1; 634 } else { 635 let prev = mem::replace(&mut self.entries[key], Entry::Occupied(val)); 636 637 match prev { 638 Entry::Vacant(next) => { 639 self.next = next; 640 } 641 _ => unreachable!(), 642 } 643 } 644 } 645 646 /// Remove and return the value associated with the given key. 647 /// 648 /// The key is then released and may be associated with future stored 649 /// values. 650 /// 651 /// # Panics 652 /// 653 /// Panics if `key` is not associated with a value. 654 /// 655 /// # Examples 656 /// 657 /// ``` 658 /// # use slab::*; 659 /// let mut slab = Slab::new(); 660 /// 661 /// let hello = slab.insert("hello"); 662 /// 663 /// assert_eq!(slab.remove(hello), "hello"); 664 /// assert!(!slab.contains(hello)); 665 /// ``` remove(&mut self, key: usize) -> T666 pub fn remove(&mut self, key: usize) -> T { 667 // Swap the entry at the provided value 668 let prev = mem::replace(&mut self.entries[key], Entry::Vacant(self.next)); 669 670 match prev { 671 Entry::Occupied(val) => { 672 self.len -= 1; 673 self.next = key; 674 val 675 } 676 _ => { 677 // Woops, the entry is actually vacant, restore the state 678 self.entries[key] = prev; 679 panic!("invalid key"); 680 } 681 } 682 } 683 684 /// Return `true` if a value is associated with the given key. 685 /// 686 /// # Examples 687 /// 688 /// ``` 689 /// # use slab::*; 690 /// let mut slab = Slab::new(); 691 /// 692 /// let hello = slab.insert("hello"); 693 /// assert!(slab.contains(hello)); 694 /// 695 /// slab.remove(hello); 696 /// 697 /// assert!(!slab.contains(hello)); 698 /// ``` contains(&self, key: usize) -> bool699 pub fn contains(&self, key: usize) -> bool { 700 self.entries 701 .get(key) 702 .map(|e| match *e { 703 Entry::Occupied(_) => true, 704 _ => false, 705 }) 706 .unwrap_or(false) 707 } 708 709 /// Retain only the elements specified by the predicate. 710 /// 711 /// In other words, remove all elements `e` such that `f(usize, &mut e)` 712 /// returns false. This method operates in place and preserves the key 713 /// associated with the retained values. 714 /// 715 /// # Examples 716 /// 717 /// ``` 718 /// # use slab::*; 719 /// let mut slab = Slab::new(); 720 /// 721 /// let k1 = slab.insert(0); 722 /// let k2 = slab.insert(1); 723 /// let k3 = slab.insert(2); 724 /// 725 /// slab.retain(|key, val| key == k1 || *val == 1); 726 /// 727 /// assert!(slab.contains(k1)); 728 /// assert!(slab.contains(k2)); 729 /// assert!(!slab.contains(k3)); 730 /// 731 /// assert_eq!(2, slab.len()); 732 /// ``` retain<F>(&mut self, mut f: F) where F: FnMut(usize, &mut T) -> bool,733 pub fn retain<F>(&mut self, mut f: F) 734 where 735 F: FnMut(usize, &mut T) -> bool, 736 { 737 for i in 0..self.entries.len() { 738 let keep = match self.entries[i] { 739 Entry::Occupied(ref mut v) => f(i, v), 740 _ => true, 741 }; 742 743 if !keep { 744 self.remove(i); 745 } 746 } 747 } 748 749 /// Return a draining iterator that removes all elements from the slab and 750 /// yields the removed items. 751 /// 752 /// Note: Elements are removed even if the iterator is only partially 753 /// consumed or not consumed at all. 754 /// 755 /// # Examples 756 /// 757 /// ``` 758 /// # use slab::*; 759 /// let mut slab = Slab::new(); 760 /// 761 /// let _ = slab.insert(0); 762 /// let _ = slab.insert(1); 763 /// let _ = slab.insert(2); 764 /// 765 /// { 766 /// let mut drain = slab.drain(); 767 /// 768 /// assert_eq!(Some(0), drain.next()); 769 /// assert_eq!(Some(1), drain.next()); 770 /// assert_eq!(Some(2), drain.next()); 771 /// assert_eq!(None, drain.next()); 772 /// } 773 /// 774 /// assert!(slab.is_empty()); 775 /// ``` drain(&mut self) -> Drain<T>776 pub fn drain(&mut self) -> Drain<T> { 777 self.len = 0; 778 self.next = 0; 779 Drain(self.entries.drain(..)) 780 } 781 } 782 783 impl<T> ops::Index<usize> for Slab<T> { 784 type Output = T; 785 index(&self, key: usize) -> &T786 fn index(&self, key: usize) -> &T { 787 match self.entries[key] { 788 Entry::Occupied(ref v) => v, 789 _ => panic!("invalid key"), 790 } 791 } 792 } 793 794 impl<T> ops::IndexMut<usize> for Slab<T> { index_mut(&mut self, key: usize) -> &mut T795 fn index_mut(&mut self, key: usize) -> &mut T { 796 match self.entries[key] { 797 Entry::Occupied(ref mut v) => v, 798 _ => panic!("invalid key"), 799 } 800 } 801 } 802 803 impl<'a, T> IntoIterator for &'a Slab<T> { 804 type Item = (usize, &'a T); 805 type IntoIter = Iter<'a, T>; 806 into_iter(self) -> Iter<'a, T>807 fn into_iter(self) -> Iter<'a, T> { 808 self.iter() 809 } 810 } 811 812 impl<'a, T> IntoIterator for &'a mut Slab<T> { 813 type Item = (usize, &'a mut T); 814 type IntoIter = IterMut<'a, T>; 815 into_iter(self) -> IterMut<'a, T>816 fn into_iter(self) -> IterMut<'a, T> { 817 self.iter_mut() 818 } 819 } 820 821 impl<T> fmt::Debug for Slab<T> 822 where 823 T: fmt::Debug, 824 { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result825 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 826 write!( 827 fmt, 828 "Slab {{ len: {}, cap: {} }}", 829 self.len, 830 self.capacity() 831 ) 832 } 833 } 834 835 impl<'a, T: 'a> fmt::Debug for Iter<'a, T> 836 where 837 T: fmt::Debug, 838 { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result839 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 840 fmt.debug_struct("Iter") 841 .field("curr", &self.curr) 842 .field("remaining", &self.entries.len()) 843 .finish() 844 } 845 } 846 847 impl<'a, T: 'a> fmt::Debug for IterMut<'a, T> 848 where 849 T: fmt::Debug, 850 { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result851 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 852 fmt.debug_struct("IterMut") 853 .field("curr", &self.curr) 854 .field("remaining", &self.entries.len()) 855 .finish() 856 } 857 } 858 859 impl<'a, T: 'a> fmt::Debug for Drain<'a, T> { fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result860 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 861 fmt.debug_struct("Drain").finish() 862 } 863 } 864 865 // ===== VacantEntry ===== 866 867 impl<'a, T> VacantEntry<'a, T> { 868 /// Insert a value in the entry, returning a mutable reference to the value. 869 /// 870 /// To get the key associated with the value, use `key` prior to calling 871 /// `insert`. 872 /// 873 /// # Examples 874 /// 875 /// ``` 876 /// # use slab::*; 877 /// let mut slab = Slab::new(); 878 /// 879 /// let hello = { 880 /// let entry = slab.vacant_entry(); 881 /// let key = entry.key(); 882 /// 883 /// entry.insert((key, "hello")); 884 /// key 885 /// }; 886 /// 887 /// assert_eq!(hello, slab[hello].0); 888 /// assert_eq!("hello", slab[hello].1); 889 /// ``` insert(self, val: T) -> &'a mut T890 pub fn insert(self, val: T) -> &'a mut T { 891 self.slab.insert_at(self.key, val); 892 893 match self.slab.entries[self.key] { 894 Entry::Occupied(ref mut v) => v, 895 _ => unreachable!(), 896 } 897 } 898 899 /// Return the key associated with this entry. 900 /// 901 /// A value stored in this entry will be associated with this key. 902 /// 903 /// # Examples 904 /// 905 /// ``` 906 /// # use slab::*; 907 /// let mut slab = Slab::new(); 908 /// 909 /// let hello = { 910 /// let entry = slab.vacant_entry(); 911 /// let key = entry.key(); 912 /// 913 /// entry.insert((key, "hello")); 914 /// key 915 /// }; 916 /// 917 /// assert_eq!(hello, slab[hello].0); 918 /// assert_eq!("hello", slab[hello].1); 919 /// ``` key(&self) -> usize920 pub fn key(&self) -> usize { 921 self.key 922 } 923 } 924 925 // ===== Iter ===== 926 927 impl<'a, T> Iterator for Iter<'a, T> { 928 type Item = (usize, &'a T); 929 next(&mut self) -> Option<(usize, &'a T)>930 fn next(&mut self) -> Option<(usize, &'a T)> { 931 while let Some(entry) = self.entries.next() { 932 let curr = self.curr; 933 self.curr += 1; 934 935 if let Entry::Occupied(ref v) = *entry { 936 return Some((curr, v)); 937 } 938 } 939 940 None 941 } 942 } 943 944 // ===== IterMut ===== 945 946 impl<'a, T> Iterator for IterMut<'a, T> { 947 type Item = (usize, &'a mut T); 948 next(&mut self) -> Option<(usize, &'a mut T)>949 fn next(&mut self) -> Option<(usize, &'a mut T)> { 950 while let Some(entry) = self.entries.next() { 951 let curr = self.curr; 952 self.curr += 1; 953 954 if let Entry::Occupied(ref mut v) = *entry { 955 return Some((curr, v)); 956 } 957 } 958 959 None 960 } 961 } 962 963 // ===== Drain ===== 964 965 impl<'a, T> Iterator for Drain<'a, T> { 966 type Item = T; 967 next(&mut self) -> Option<T>968 fn next(&mut self) -> Option<T> { 969 while let Some(entry) = self.0.next() { 970 if let Entry::Occupied(v) = entry { 971 return Some(v); 972 } 973 } 974 975 None 976 } 977 } 978