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