1 | #![cfg_attr (not(feature = "std" ), no_std)] |
2 | #![warn ( |
3 | missing_debug_implementations, |
4 | missing_docs, |
5 | rust_2018_idioms, |
6 | unreachable_pub |
7 | )] |
8 | #![doc (test( |
9 | no_crate_inject, |
10 | attr(deny(warnings, rust_2018_idioms), allow(dead_code, unused_variables)) |
11 | ))] |
12 | |
13 | //! Pre-allocated storage for a uniform data type. |
14 | //! |
15 | //! `Slab` provides pre-allocated storage for a single data type. If many values |
16 | //! of a single type are being allocated, it can be more efficient to |
17 | //! pre-allocate the necessary storage. Since the size of the type is uniform, |
18 | //! memory fragmentation can be avoided. Storing, clearing, and lookup |
19 | //! operations become very cheap. |
20 | //! |
21 | //! While `Slab` may look like other Rust collections, it is not intended to be |
22 | //! used as a general purpose collection. The primary difference between `Slab` |
23 | //! and `Vec` is that `Slab` returns the key when storing the value. |
24 | //! |
25 | //! It is important to note that keys may be reused. In other words, once a |
26 | //! value associated with a given key is removed from a slab, that key may be |
27 | //! returned from future calls to `insert`. |
28 | //! |
29 | //! # Examples |
30 | //! |
31 | //! Basic storing and retrieval. |
32 | //! |
33 | //! ``` |
34 | //! # use slab::*; |
35 | //! let mut slab = Slab::new(); |
36 | //! |
37 | //! let hello = slab.insert("hello" ); |
38 | //! let world = slab.insert("world" ); |
39 | //! |
40 | //! assert_eq!(slab[hello], "hello" ); |
41 | //! assert_eq!(slab[world], "world" ); |
42 | //! |
43 | //! slab[world] = "earth" ; |
44 | //! assert_eq!(slab[world], "earth" ); |
45 | //! ``` |
46 | //! |
47 | //! Sometimes it is useful to be able to associate the key with the value being |
48 | //! inserted in the slab. This can be done with the `vacant_entry` API as such: |
49 | //! |
50 | //! ``` |
51 | //! # use slab::*; |
52 | //! let mut slab = Slab::new(); |
53 | //! |
54 | //! let hello = { |
55 | //! let entry = slab.vacant_entry(); |
56 | //! let key = entry.key(); |
57 | //! |
58 | //! entry.insert((key, "hello" )); |
59 | //! key |
60 | //! }; |
61 | //! |
62 | //! assert_eq!(hello, slab[hello].0); |
63 | //! assert_eq!("hello" , slab[hello].1); |
64 | //! ``` |
65 | //! |
66 | //! It is generally a good idea to specify the desired capacity of a slab at |
67 | //! creation time. Note that `Slab` will grow the internal capacity when |
68 | //! attempting to insert a new value once the existing capacity has been reached. |
69 | //! To avoid this, add a check. |
70 | //! |
71 | //! ``` |
72 | //! # use slab::*; |
73 | //! let mut slab = Slab::with_capacity(1024); |
74 | //! |
75 | //! // ... use the slab |
76 | //! |
77 | //! if slab.len() == slab.capacity() { |
78 | //! panic!("slab full" ); |
79 | //! } |
80 | //! |
81 | //! slab.insert("the slab is not at capacity yet" ); |
82 | //! ``` |
83 | //! |
84 | //! # Capacity and reallocation |
85 | //! |
86 | //! The capacity of a slab is the amount of space allocated for any future |
87 | //! values that will be inserted in the slab. This is not to be confused with |
88 | //! the *length* of the slab, which specifies the number of actual values |
89 | //! currently being inserted. If a slab's length is equal to its capacity, the |
90 | //! next value inserted into the slab will require growing the slab by |
91 | //! reallocating. |
92 | //! |
93 | //! For example, a slab with capacity 10 and length 0 would be an empty slab |
94 | //! with space for 10 more stored values. Storing 10 or fewer elements into the |
95 | //! slab will not change its capacity or cause reallocation to occur. However, |
96 | //! if the slab length is increased to 11 (due to another `insert`), it will |
97 | //! have to reallocate, which can be slow. For this reason, it is recommended to |
98 | //! use [`Slab::with_capacity`] whenever possible to specify how many values the |
99 | //! slab is expected to store. |
100 | //! |
101 | //! # Implementation |
102 | //! |
103 | //! `Slab` is backed by a `Vec` of slots. Each slot is either occupied or |
104 | //! vacant. `Slab` maintains a stack of vacant slots using a linked list. To |
105 | //! find a vacant slot, the stack is popped. When a slot is released, it is |
106 | //! pushed onto the stack. |
107 | //! |
108 | //! If there are no more available slots in the stack, then `Vec::reserve(1)` is |
109 | //! called and a new slot is created. |
110 | //! |
111 | //! [`Slab::with_capacity`]: struct.Slab.html#with_capacity |
112 | |
113 | #[cfg (not(feature = "std" ))] |
114 | extern crate alloc; |
115 | #[cfg (feature = "std" )] |
116 | extern crate std as alloc; |
117 | |
118 | #[cfg (feature = "serde" )] |
119 | mod serde; |
120 | |
121 | mod builder; |
122 | |
123 | use alloc::vec::{self, Vec}; |
124 | use core::iter::{self, FromIterator, FusedIterator}; |
125 | use 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)] |
133 | pub 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 | |
145 | impl<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)] |
174 | pub 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` |
180 | pub 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` |
186 | pub struct Iter<'a, T> { |
187 | entries: iter::Enumerate<slice::Iter<'a, Entry<T>>>, |
188 | len: usize, |
189 | } |
190 | |
191 | impl<'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` |
201 | pub struct IterMut<'a, T> { |
202 | entries: iter::Enumerate<slice::IterMut<'a, Entry<T>>>, |
203 | len: usize, |
204 | } |
205 | |
206 | /// A draining iterator for `Slab` |
207 | pub struct Drain<'a, T> { |
208 | inner: vec::Drain<'a, Entry<T>>, |
209 | len: usize, |
210 | } |
211 | |
212 | #[derive (Clone)] |
213 | enum Entry<T> { |
214 | Vacant(usize), |
215 | Occupied(T), |
216 | } |
217 | |
218 | impl<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 | |
1185 | impl<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 | |
1197 | impl<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 | |
1207 | impl<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 | |
1219 | impl<'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 | |
1228 | impl<'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 | /// ``` |
1267 | impl<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 | |
1282 | impl<T> fmt::Debug for Slab<T> |
1283 | where |
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 | |
1298 | impl<T> fmt::Debug for IntoIter<T> |
1299 | where |
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 | |
1309 | impl<T> fmt::Debug for Iter<'_, T> |
1310 | where |
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 | |
1320 | impl<T> fmt::Debug for IterMut<'_, T> |
1321 | where |
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 | |
1331 | impl<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 | |
1339 | impl<'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 | |
1399 | impl<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 | |
1419 | impl<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 | |
1433 | impl<T> ExactSizeIterator for IntoIter<T> { |
1434 | fn len(&self) -> usize { |
1435 | self.len |
1436 | } |
1437 | } |
1438 | |
1439 | impl<T> FusedIterator for IntoIter<T> {} |
1440 | |
1441 | // ===== Iter ===== |
1442 | |
1443 | impl<'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 | |
1463 | impl<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 | |
1477 | impl<T> ExactSizeIterator for Iter<'_, T> { |
1478 | fn len(&self) -> usize { |
1479 | self.len |
1480 | } |
1481 | } |
1482 | |
1483 | impl<T> FusedIterator for Iter<'_, T> {} |
1484 | |
1485 | // ===== IterMut ===== |
1486 | |
1487 | impl<'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 | |
1507 | impl<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 | |
1521 | impl<T> ExactSizeIterator for IterMut<'_, T> { |
1522 | fn len(&self) -> usize { |
1523 | self.len |
1524 | } |
1525 | } |
1526 | |
1527 | impl<T> FusedIterator for IterMut<'_, T> {} |
1528 | |
1529 | // ===== Drain ===== |
1530 | |
1531 | impl<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 | |
1551 | impl<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 | |
1565 | impl<T> ExactSizeIterator for Drain<'_, T> { |
1566 | fn len(&self) -> usize { |
1567 | self.len |
1568 | } |
1569 | } |
1570 | |
1571 | impl<T> FusedIterator for Drain<'_, T> {} |
1572 | |