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