generational_arena/lib.rs
1/*!
2[](https://docs.rs/generational-arena/)
3[](https://crates.io/crates/generational-arena)
4[](https://crates.io/crates/generational-arena)
5[](https://github.com/fitzgen/generational-arena/actions/workflows/rust.yml)
6
7A safe arena allocator that allows deletion without suffering from [the ABA
8problem](https://en.wikipedia.org/wiki/ABA_problem) by using generational
9indices.
10
11Inspired by [Catherine West's closing keynote at RustConf
122018](https://www.youtube.com/watch?v=aKLntZcp27M), where these ideas (and many
13more!) were presented in the context of an Entity-Component-System for games
14programming.
15
16## What? Why?
17
18Imagine you are working with a graph and you want to add and delete individual
19nodes at a time, or you are writing a game and its world consists of many
20inter-referencing objects with dynamic lifetimes that depend on user
21input. These are situations where matching Rust's ownership and lifetime rules
22can get tricky.
23
24It doesn't make sense to use shared ownership with interior mutability (i.e.
25`Rc<RefCell<T>>` or `Arc<Mutex<T>>`) nor borrowed references (ie `&'a T` or `&'a
26mut T`) for structures. The cycles rule out reference counted types, and the
27required shared mutability rules out borrows. Furthermore, lifetimes are dynamic
28and don't follow the borrowed-data-outlives-the-borrower discipline.
29
30In these situations, it is tempting to store objects in a `Vec<T>` and have them
31reference each other via their indices. No more borrow checker or ownership
32problems! Often, this solution is good enough.
33
34However, now we can't delete individual items from that `Vec<T>` when we no
35longer need them, because we end up either
36
37* messing up the indices of every element that follows the deleted one, or
38
39* suffering from the [ABA
40 problem](https://en.wikipedia.org/wiki/ABA_problem). To elaborate further, if
41 we tried to replace the `Vec<T>` with a `Vec<Option<T>>`, and delete an
42 element by setting it to `None`, then we create the possibility for this buggy
43 sequence:
44
45 * `obj1` references `obj2` at index `i`
46
47 * someone else deletes `obj2` from index `i`, setting that element to `None`
48
49 * a third thing allocates `obj3`, which ends up at index `i`, because the
50 element at that index is `None` and therefore available for allocation
51
52 * `obj1` attempts to get `obj2` at index `i`, but incorrectly is given
53 `obj3`, when instead the get should fail.
54
55By introducing a monotonically increasing generation counter to the collection,
56associating each element in the collection with the generation when it was
57inserted, and getting elements from the collection with the *pair* of index and
58the generation at the time when the element was inserted, then we can solve the
59aforementioned ABA problem. When indexing into the collection, if the index
60pair's generation does not match the generation of the element at that index,
61then the operation fails.
62
63## Features
64
65* Zero `unsafe`
66* Well tested, including quickchecks
67* `no_std` compatibility
68* All the trait implementations you expect: `IntoIterator`, `FromIterator`,
69 `Extend`, etc...
70
71## Usage
72
73First, add `generational-arena` to your `Cargo.toml`:
74
75```toml
76[dependencies]
77generational-arena = "0.2"
78```
79
80Then, import the crate and use the
81[`generational_arena::Arena`](./struct.Arena.html) type!
82
83```rust
84extern crate generational_arena;
85use generational_arena::Arena;
86
87let mut arena = Arena::new();
88
89// Insert some elements into the arena.
90let rza = arena.insert("Robert Fitzgerald Diggs");
91let gza = arena.insert("Gary Grice");
92let bill = arena.insert("Bill Gates");
93
94// Inserted elements can be accessed infallibly via indexing (and missing
95// entries will panic).
96assert_eq!(arena[rza], "Robert Fitzgerald Diggs");
97
98// Alternatively, the `get` and `get_mut` methods provide fallible lookup.
99if let Some(genius) = arena.get(gza) {
100 println!("The gza gza genius: {}", genius);
101}
102if let Some(val) = arena.get_mut(bill) {
103 *val = "Bill Gates doesn't belong in this set...";
104}
105
106// We can remove elements.
107arena.remove(bill);
108
109// Insert a new one.
110let murray = arena.insert("Bill Murray");
111
112// The arena does not contain `bill` anymore, but it does contain `murray`, even
113// though they are almost certainly at the same index within the arena in
114// practice. Ambiguities are resolved with an associated generation tag.
115assert!(!arena.contains(bill));
116assert!(arena.contains(murray));
117
118// Iterate over everything inside the arena.
119for (idx, value) in &arena {
120 println!("{:?} is at {:?}", value, idx);
121}
122```
123
124## `no_std`
125
126To enable `no_std` compatibility, disable the on-by-default "std" feature.
127
128```toml
129[dependencies]
130generational-arena = { version = "0.2", default-features = false }
131```
132
133### Serialization and Deserialization with [`serde`](https://crates.io/crates/serde)
134
135To enable serialization/deserialization support, enable the "serde" feature.
136
137```toml
138[dependencies]
139generational-arena = { version = "0.2", features = ["serde"] }
140```
141 */
142
143#![forbid(unsafe_code, missing_docs, missing_debug_implementations)]
144#![no_std]
145
146cfg_if::cfg_if! {
147 if #[cfg(feature = "std")] {
148 extern crate std;
149 use std::vec::{self, Vec};
150 } else {
151 extern crate alloc;
152 use alloc::vec::{self, Vec};
153 }
154}
155
156use core::cmp;
157use core::iter::{self, Extend, FromIterator, FusedIterator};
158use core::mem;
159use core::ops;
160use core::slice;
161
162#[cfg(feature = "serde")]
163mod serde_impl;
164
165/// The `Arena` allows inserting and removing elements that are referred to by
166/// `Index`.
167///
168/// [See the module-level documentation for example usage and motivation.](./index.html)
169#[derive(Clone, Debug)]
170pub struct Arena<T> {
171 items: Vec<Entry<T>>,
172 generation: u64,
173 free_list_head: Option<usize>,
174 len: usize,
175}
176
177#[derive(Clone, Debug)]
178enum Entry<T> {
179 Free { next_free: Option<usize> },
180 Occupied { generation: u64, value: T },
181}
182
183/// An index (and generation) into an `Arena`.
184///
185/// To get an `Index`, insert an element into an `Arena`, and the `Index` for
186/// that element will be returned.
187///
188/// # Examples
189///
190/// ```
191/// use generational_arena::Arena;
192///
193/// let mut arena = Arena::new();
194/// let idx = arena.insert(123);
195/// assert_eq!(arena[idx], 123);
196/// ```
197#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
198pub struct Index {
199 index: usize,
200 generation: u64,
201}
202
203impl Index {
204 /// Create a new `Index` from its raw parts.
205 ///
206 /// The parts must have been returned from an earlier call to
207 /// `into_raw_parts`.
208 ///
209 /// Providing arbitrary values will lead to malformed indices and ultimately
210 /// panics.
211 pub fn from_raw_parts(a: usize, b: u64) -> Index {
212 Index {
213 index: a,
214 generation: b,
215 }
216 }
217
218 /// Convert this `Index` into its raw parts.
219 ///
220 /// This niche method is useful for converting an `Index` into another
221 /// identifier type. Usually, you should prefer a newtype wrapper around
222 /// `Index` like `pub struct MyIdentifier(Index);`. However, for external
223 /// types whose definition you can't customize, but which you can construct
224 /// instances of, this method can be useful.
225 pub fn into_raw_parts(self) -> (usize, u64) {
226 (self.index, self.generation)
227 }
228}
229
230const DEFAULT_CAPACITY: usize = 4;
231
232impl<T> Default for Arena<T> {
233 fn default() -> Arena<T> {
234 Arena::new()
235 }
236}
237
238impl<T> Arena<T> {
239 /// Constructs a new, empty `Arena`.
240 ///
241 /// # Examples
242 ///
243 /// ```
244 /// use generational_arena::Arena;
245 ///
246 /// let mut arena = Arena::<usize>::new();
247 /// # let _ = arena;
248 /// ```
249 pub fn new() -> Arena<T> {
250 Arena::with_capacity(DEFAULT_CAPACITY)
251 }
252
253 /// Constructs a new, empty `Arena<T>` with the specified capacity.
254 ///
255 /// The `Arena<T>` will be able to hold `n` elements without further allocation.
256 ///
257 /// # Examples
258 ///
259 /// ```
260 /// use generational_arena::Arena;
261 ///
262 /// let mut arena = Arena::with_capacity(10);
263 ///
264 /// // These insertions will not require further allocation.
265 /// for i in 0..10 {
266 /// assert!(arena.try_insert(i).is_ok());
267 /// }
268 ///
269 /// // But now we are at capacity, and there is no more room.
270 /// assert!(arena.try_insert(99).is_err());
271 /// ```
272 pub fn with_capacity(n: usize) -> Arena<T> {
273 let n = cmp::max(n, 1);
274 let mut arena = Arena {
275 items: Vec::new(),
276 generation: 0,
277 free_list_head: None,
278 len: 0,
279 };
280 arena.reserve(n);
281 arena
282 }
283
284 /// Clear all the items inside the arena, but keep its allocation.
285 ///
286 /// # Examples
287 ///
288 /// ```
289 /// use generational_arena::Arena;
290 ///
291 /// let mut arena = Arena::with_capacity(1);
292 /// arena.insert(42);
293 /// arena.insert(43);
294 ///
295 /// arena.clear();
296 ///
297 /// assert_eq!(arena.capacity(), 2);
298 /// ```
299 pub fn clear(&mut self) {
300 self.items.clear();
301
302 let end = self.items.capacity();
303 self.items.extend((0..end).map(|i| {
304 if i == end - 1 {
305 Entry::Free { next_free: None }
306 } else {
307 Entry::Free {
308 next_free: Some(i + 1),
309 }
310 }
311 }));
312 if !self.is_empty() {
313 // Increment generation, but if there are no elements, do nothing to
314 // avoid unnecessary incrementing generation.
315 self.generation += 1;
316 }
317 self.free_list_head = Some(0);
318 self.len = 0;
319 }
320
321 /// Attempts to insert `value` into the arena using existing capacity.
322 ///
323 /// This method will never allocate new capacity in the arena.
324 ///
325 /// If insertion succeeds, then the `value`'s index is returned. If
326 /// insertion fails, then `Err(value)` is returned to give ownership of
327 /// `value` back to the caller.
328 ///
329 /// # Examples
330 ///
331 /// ```
332 /// use generational_arena::Arena;
333 ///
334 /// let mut arena = Arena::new();
335 ///
336 /// match arena.try_insert(42) {
337 /// Ok(idx) => {
338 /// // Insertion succeeded.
339 /// assert_eq!(arena[idx], 42);
340 /// }
341 /// Err(x) => {
342 /// // Insertion failed.
343 /// assert_eq!(x, 42);
344 /// }
345 /// };
346 /// ```
347 #[inline]
348 pub fn try_insert(&mut self, value: T) -> Result<Index, T> {
349 match self.try_alloc_next_index() {
350 None => Err(value),
351 Some(index) => {
352 self.items[index.index] = Entry::Occupied {
353 generation: self.generation,
354 value,
355 };
356 Ok(index)
357 },
358 }
359 }
360
361 /// Attempts to insert the value returned by `create` into the arena using existing capacity.
362 /// `create` is called with the new value's associated index, allowing values that know their own index.
363 ///
364 /// This method will never allocate new capacity in the arena.
365 ///
366 /// If insertion succeeds, then the new index is returned. If
367 /// insertion fails, then `Err(create)` is returned to give ownership of
368 /// `create` back to the caller.
369 ///
370 /// # Examples
371 ///
372 /// ```
373 /// use generational_arena::{Arena, Index};
374 ///
375 /// let mut arena = Arena::new();
376 ///
377 /// match arena.try_insert_with(|idx| (42, idx)) {
378 /// Ok(idx) => {
379 /// // Insertion succeeded.
380 /// assert_eq!(arena[idx].0, 42);
381 /// assert_eq!(arena[idx].1, idx);
382 /// }
383 /// Err(x) => {
384 /// // Insertion failed.
385 /// }
386 /// };
387 /// ```
388 #[inline]
389 pub fn try_insert_with<F: FnOnce(Index) -> T>(&mut self, create: F) -> Result<Index, F> {
390 match self.try_alloc_next_index() {
391 None => Err(create),
392 Some(index) => {
393 self.items[index.index] = Entry::Occupied {
394 generation: self.generation,
395 value: create(index),
396 };
397 Ok(index)
398 },
399 }
400 }
401
402 #[inline]
403 fn try_alloc_next_index(&mut self) -> Option<Index> {
404 match self.free_list_head {
405 None => None,
406 Some(i) => match self.items[i] {
407 Entry::Occupied { .. } => panic!("corrupt free list"),
408 Entry::Free { next_free } => {
409 self.free_list_head = next_free;
410 self.len += 1;
411 Some(Index {
412 index: i,
413 generation: self.generation,
414 })
415 }
416 }
417 }
418 }
419
420 /// Insert `value` into the arena, allocating more capacity if necessary.
421 ///
422 /// The `value`'s associated index in the arena is returned.
423 ///
424 /// # Examples
425 ///
426 /// ```
427 /// use generational_arena::Arena;
428 ///
429 /// let mut arena = Arena::new();
430 ///
431 /// let idx = arena.insert(42);
432 /// assert_eq!(arena[idx], 42);
433 /// ```
434 #[inline]
435 pub fn insert(&mut self, value: T) -> Index {
436 match self.try_insert(value) {
437 Ok(i) => i,
438 Err(value) => self.insert_slow_path(value),
439 }
440 }
441
442 /// Insert the value returned by `create` into the arena, allocating more capacity if necessary.
443 /// `create` is called with the new value's associated index, allowing values that know their own index.
444 ///
445 /// The new value's associated index in the arena is returned.
446 ///
447 /// # Examples
448 ///
449 /// ```
450 /// use generational_arena::{Arena, Index};
451 ///
452 /// let mut arena = Arena::new();
453 ///
454 /// let idx = arena.insert_with(|idx| (42, idx));
455 /// assert_eq!(arena[idx].0, 42);
456 /// assert_eq!(arena[idx].1, idx);
457 /// ```
458 #[inline]
459 pub fn insert_with(&mut self, create: impl FnOnce(Index) -> T) -> Index {
460 match self.try_insert_with(create) {
461 Ok(i) => i,
462 Err(create) => self.insert_with_slow_path(create),
463 }
464 }
465
466 #[inline(never)]
467 fn insert_slow_path(&mut self, value: T) -> Index {
468 let len = if self.capacity() == 0 {
469 // `drain()` sets the capacity to 0 and if the capacity is 0, the
470 // next `try_insert() `will refer to an out-of-range index because
471 // the next `reserve()` does not add element, resulting in a panic.
472 // So ensure that `self` have at least 1 capacity here.
473 //
474 // Ideally, this problem should be handled within `drain()`,but
475 // this problem cannot be handled within `drain()` because `drain()`
476 // returns an iterator that borrows `self` mutably.
477 1
478 } else {
479 self.items.len()
480 };
481 self.reserve(len);
482 self.try_insert(value)
483 .map_err(|_| ())
484 .expect("inserting will always succeed after reserving additional space")
485 }
486
487 #[inline(never)]
488 fn insert_with_slow_path(&mut self, create: impl FnOnce(Index) -> T) -> Index {
489 let len = self.items.len();
490 self.reserve(len);
491 self.try_insert_with(create)
492 .map_err(|_| ())
493 .expect("inserting will always succeed after reserving additional space")
494 }
495
496 /// Remove the element at index `i` from the arena.
497 ///
498 /// If the element at index `i` is still in the arena, then it is
499 /// returned. If it is not in the arena, then `None` is returned.
500 ///
501 /// # Examples
502 ///
503 /// ```
504 /// use generational_arena::Arena;
505 ///
506 /// let mut arena = Arena::new();
507 /// let idx = arena.insert(42);
508 ///
509 /// assert_eq!(arena.remove(idx), Some(42));
510 /// assert_eq!(arena.remove(idx), None);
511 /// ```
512 pub fn remove(&mut self, i: Index) -> Option<T> {
513 if i.index >= self.items.len() {
514 return None;
515 }
516
517 match self.items[i.index] {
518 Entry::Occupied { generation, .. } if i.generation == generation => {
519 let entry = mem::replace(
520 &mut self.items[i.index],
521 Entry::Free { next_free: self.free_list_head },
522 );
523 self.generation += 1;
524 self.free_list_head = Some(i.index);
525 self.len -= 1;
526
527 match entry {
528 Entry::Occupied { generation: _, value } => Some(value),
529 _ => unreachable!(),
530 }
531 }
532 _ => None,
533 }
534 }
535
536 /// Retains only the elements specified by the predicate.
537 ///
538 /// In other words, remove all indices such that `predicate(index, &value)` returns `false`.
539 ///
540 /// # Examples
541 ///
542 /// ```
543 /// use generational_arena::Arena;
544 ///
545 /// let mut crew = Arena::new();
546 /// crew.extend(&["Jim Hawkins", "John Silver", "Alexander Smollett", "Israel Hands"]);
547 /// let pirates = ["John Silver", "Israel Hands"]; // too dangerous to keep them around
548 /// crew.retain(|_index, member| !pirates.contains(member));
549 /// let mut crew_members = crew.iter().map(|(_, member)| **member);
550 /// assert_eq!(crew_members.next(), Some("Jim Hawkins"));
551 /// assert_eq!(crew_members.next(), Some("Alexander Smollett"));
552 /// assert!(crew_members.next().is_none());
553 /// ```
554 pub fn retain(&mut self, mut predicate: impl FnMut(Index, &mut T) -> bool) {
555 for i in 0..self.capacity() {
556 let remove = match &mut self.items[i] {
557 Entry::Occupied { generation, value } => {
558 let index = Index {
559 index: i,
560 generation: *generation,
561 };
562 if predicate(index, value) {
563 None
564 } else {
565 Some(index)
566 }
567 }
568
569 _ => None,
570 };
571 if let Some(index) = remove {
572 self.remove(index);
573 }
574 }
575 }
576
577 /// Is the element at index `i` in the arena?
578 ///
579 /// Returns `true` if the element at `i` is in the arena, `false` otherwise.
580 ///
581 /// # Examples
582 ///
583 /// ```
584 /// use generational_arena::Arena;
585 ///
586 /// let mut arena = Arena::new();
587 /// let idx = arena.insert(42);
588 ///
589 /// assert!(arena.contains(idx));
590 /// arena.remove(idx);
591 /// assert!(!arena.contains(idx));
592 /// ```
593 pub fn contains(&self, i: Index) -> bool {
594 self.get(i).is_some()
595 }
596
597 /// Get a shared reference to the element at index `i` if it is in the
598 /// arena.
599 ///
600 /// If the element at index `i` is not in the arena, then `None` is returned.
601 ///
602 /// # Examples
603 ///
604 /// ```
605 /// use generational_arena::Arena;
606 ///
607 /// let mut arena = Arena::new();
608 /// let idx = arena.insert(42);
609 ///
610 /// assert_eq!(arena.get(idx), Some(&42));
611 /// arena.remove(idx);
612 /// assert!(arena.get(idx).is_none());
613 /// ```
614 pub fn get(&self, i: Index) -> Option<&T> {
615 match self.items.get(i.index) {
616 Some(Entry::Occupied {
617 generation,
618 value,
619 }) if *generation == i.generation => Some(value),
620 _ => None,
621 }
622 }
623
624 /// Get an exclusive reference to the element at index `i` if it is in the
625 /// arena.
626 ///
627 /// If the element at index `i` is not in the arena, then `None` is returned.
628 ///
629 /// # Examples
630 ///
631 /// ```
632 /// use generational_arena::Arena;
633 ///
634 /// let mut arena = Arena::new();
635 /// let idx = arena.insert(42);
636 ///
637 /// *arena.get_mut(idx).unwrap() += 1;
638 /// assert_eq!(arena.remove(idx), Some(43));
639 /// assert!(arena.get_mut(idx).is_none());
640 /// ```
641 pub fn get_mut(&mut self, i: Index) -> Option<&mut T> {
642 match self.items.get_mut(i.index) {
643 Some(Entry::Occupied {
644 generation,
645 value,
646 }) if *generation == i.generation => Some(value),
647 _ => None,
648 }
649 }
650
651 /// Get a pair of exclusive references to the elements at index `i1` and `i2` if it is in the
652 /// arena.
653 ///
654 /// If the element at index `i1` or `i2` is not in the arena, then `None` is returned for this
655 /// element.
656 ///
657 /// # Panics
658 ///
659 /// Panics if `i1` and `i2` are pointing to the same item of the arena.
660 ///
661 /// # Examples
662 ///
663 /// ```
664 /// use generational_arena::Arena;
665 ///
666 /// let mut arena = Arena::new();
667 /// let idx1 = arena.insert(0);
668 /// let idx2 = arena.insert(1);
669 ///
670 /// {
671 /// let (item1, item2) = arena.get2_mut(idx1, idx2);
672 ///
673 /// *item1.unwrap() = 3;
674 /// *item2.unwrap() = 4;
675 /// }
676 ///
677 /// assert_eq!(arena[idx1], 3);
678 /// assert_eq!(arena[idx2], 4);
679 /// ```
680 pub fn get2_mut(&mut self, i1: Index, i2: Index) -> (Option<&mut T>, Option<&mut T>) {
681 let len = self.items.len();
682
683 if i1.index == i2.index {
684 assert!(i1.generation != i2.generation);
685
686 if i1.generation > i2.generation {
687 return (self.get_mut(i1), None);
688 }
689 return (None, self.get_mut(i2));
690 }
691
692 if i1.index >= len {
693 return (None, self.get_mut(i2));
694 } else if i2.index >= len {
695 return (self.get_mut(i1), None);
696 }
697
698 let (raw_item1, raw_item2) = {
699 let (xs, ys) = self.items.split_at_mut(cmp::max(i1.index, i2.index));
700 if i1.index < i2.index {
701 (&mut xs[i1.index], &mut ys[0])
702 } else {
703 (&mut ys[0], &mut xs[i2.index])
704 }
705 };
706
707 let item1 = match raw_item1 {
708 Entry::Occupied {
709 generation,
710 value,
711 } if *generation == i1.generation => Some(value),
712 _ => None,
713 };
714
715 let item2 = match raw_item2 {
716 Entry::Occupied {
717 generation,
718 value,
719 } if *generation == i2.generation => Some(value),
720 _ => None,
721 };
722
723 (item1, item2)
724 }
725
726 /// Get the length of this arena.
727 ///
728 /// The length is the number of elements the arena holds.
729 ///
730 /// # Examples
731 ///
732 /// ```
733 /// use generational_arena::Arena;
734 ///
735 /// let mut arena = Arena::new();
736 /// assert_eq!(arena.len(), 0);
737 ///
738 /// let idx = arena.insert(42);
739 /// assert_eq!(arena.len(), 1);
740 ///
741 /// let _ = arena.insert(0);
742 /// assert_eq!(arena.len(), 2);
743 ///
744 /// assert_eq!(arena.remove(idx), Some(42));
745 /// assert_eq!(arena.len(), 1);
746 /// ```
747 pub fn len(&self) -> usize {
748 self.len
749 }
750
751 /// Returns true if the arena contains no elements
752 ///
753 /// # Examples
754 ///
755 /// ```
756 /// use generational_arena::Arena;
757 ///
758 /// let mut arena = Arena::new();
759 /// assert!(arena.is_empty());
760 ///
761 /// let idx = arena.insert(42);
762 /// assert!(!arena.is_empty());
763 ///
764 /// assert_eq!(arena.remove(idx), Some(42));
765 /// assert!(arena.is_empty());
766 /// ```
767 pub fn is_empty(&self) -> bool {
768 self.len == 0
769 }
770
771 /// Get the capacity of this arena.
772 ///
773 /// The capacity is the maximum number of elements the arena can hold
774 /// without further allocation, including however many it currently
775 /// contains.
776 ///
777 /// # Examples
778 ///
779 /// ```
780 /// use generational_arena::Arena;
781 ///
782 /// let mut arena = Arena::with_capacity(10);
783 /// assert_eq!(arena.capacity(), 10);
784 ///
785 /// // `try_insert` does not allocate new capacity.
786 /// for i in 0..10 {
787 /// assert!(arena.try_insert(1).is_ok());
788 /// assert_eq!(arena.capacity(), 10);
789 /// }
790 ///
791 /// // But `insert` will if the arena is already at capacity.
792 /// arena.insert(0);
793 /// assert!(arena.capacity() > 10);
794 /// ```
795 pub fn capacity(&self) -> usize {
796 self.items.len()
797 }
798
799 /// Allocate space for `additional_capacity` more elements in the arena.
800 ///
801 /// # Panics
802 ///
803 /// Panics if this causes the capacity to overflow.
804 ///
805 /// # Examples
806 ///
807 /// ```
808 /// use generational_arena::Arena;
809 ///
810 /// let mut arena = Arena::with_capacity(10);
811 /// arena.reserve(5);
812 /// assert_eq!(arena.capacity(), 15);
813 /// # let _: Arena<usize> = arena;
814 /// ```
815 pub fn reserve(&mut self, additional_capacity: usize) {
816 let start = self.items.len();
817 let end = self.items.len() + additional_capacity;
818 let old_head = self.free_list_head;
819 self.items.reserve_exact(additional_capacity);
820 self.items.extend((start..end).map(|i| {
821 if i == end - 1 {
822 Entry::Free {
823 next_free: old_head,
824 }
825 } else {
826 Entry::Free {
827 next_free: Some(i + 1),
828 }
829 }
830 }));
831 self.free_list_head = Some(start);
832 }
833
834 /// Iterate over shared references to the elements in this arena.
835 ///
836 /// Yields pairs of `(Index, &T)` items.
837 ///
838 /// Order of iteration is not defined.
839 ///
840 /// # Examples
841 ///
842 /// ```
843 /// use generational_arena::Arena;
844 ///
845 /// let mut arena = Arena::new();
846 /// for i in 0..10 {
847 /// arena.insert(i * i);
848 /// }
849 ///
850 /// for (idx, value) in arena.iter() {
851 /// println!("{} is at index {:?}", value, idx);
852 /// }
853 /// ```
854 pub fn iter(&self) -> Iter<T> {
855 Iter {
856 len: self.len,
857 inner: self.items.iter().enumerate(),
858 }
859 }
860
861 /// Iterate over exclusive references to the elements in this arena.
862 ///
863 /// Yields pairs of `(Index, &mut T)` items.
864 ///
865 /// Order of iteration is not defined.
866 ///
867 /// # Examples
868 ///
869 /// ```
870 /// use generational_arena::Arena;
871 ///
872 /// let mut arena = Arena::new();
873 /// for i in 0..10 {
874 /// arena.insert(i * i);
875 /// }
876 ///
877 /// for (_idx, value) in arena.iter_mut() {
878 /// *value += 5;
879 /// }
880 /// ```
881 pub fn iter_mut(&mut self) -> IterMut<T> {
882 IterMut {
883 len: self.len,
884 inner: self.items.iter_mut().enumerate(),
885 }
886 }
887
888 /// Iterate over elements of the arena and remove them.
889 ///
890 /// Yields pairs of `(Index, T)` items.
891 ///
892 /// Order of iteration is not defined.
893 ///
894 /// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
895 ///
896 /// # Examples
897 ///
898 /// ```
899 /// use generational_arena::Arena;
900 ///
901 /// let mut arena = Arena::new();
902 /// let idx_1 = arena.insert("hello");
903 /// let idx_2 = arena.insert("world");
904 ///
905 /// assert!(arena.get(idx_1).is_some());
906 /// assert!(arena.get(idx_2).is_some());
907 /// for (idx, value) in arena.drain() {
908 /// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
909 /// }
910 /// assert!(arena.get(idx_1).is_none());
911 /// assert!(arena.get(idx_2).is_none());
912 /// ```
913 pub fn drain(&mut self) -> Drain<T> {
914 let old_len = self.len;
915 if !self.is_empty() {
916 // Increment generation, but if there are no elements, do nothing to
917 // avoid unnecessary incrementing generation.
918 self.generation += 1;
919 }
920 self.free_list_head = None;
921 self.len = 0;
922 Drain {
923 len: old_len,
924 inner: self.items.drain(..).enumerate(),
925 }
926 }
927
928 /// Given an i of `usize` without a generation, get a shared reference
929 /// to the element and the matching `Index` of the entry behind `i`.
930 ///
931 /// This method is useful when you know there might be an element at the
932 /// position i, but don't know its generation or precise Index.
933 ///
934 /// Use cases include using indexing such as Hierarchical BitMap Indexing or
935 /// other kinds of bit-efficient indexing.
936 ///
937 /// You should use the `get` method instead most of the time.
938 pub fn get_unknown_gen(&self, i: usize) -> Option<(&T, Index)> {
939 match self.items.get(i) {
940 Some(Entry::Occupied {
941 generation,
942 value,
943 }) => Some((value, Index { generation: *generation, index: i})),
944 _ => None,
945 }
946 }
947
948 /// Given an i of `usize` without a generation, get an exclusive reference
949 /// to the element and the matching `Index` of the entry behind `i`.
950 ///
951 /// This method is useful when you know there might be an element at the
952 /// position i, but don't know its generation or precise Index.
953 ///
954 /// Use cases include using indexing such as Hierarchical BitMap Indexing or
955 /// other kinds of bit-efficient indexing.
956 ///
957 /// You should use the `get_mut` method instead most of the time.
958 pub fn get_unknown_gen_mut(&mut self, i: usize) -> Option<(&mut T, Index)> {
959 match self.items.get_mut(i) {
960 Some(Entry::Occupied {
961 generation,
962 value,
963 }) => Some((value, Index { generation: *generation, index: i})),
964 _ => None,
965 }
966 }
967}
968
969impl<T> IntoIterator for Arena<T> {
970 type Item = T;
971 type IntoIter = IntoIter<T>;
972 fn into_iter(self) -> Self::IntoIter {
973 IntoIter {
974 len: self.len,
975 inner: self.items.into_iter(),
976 }
977 }
978}
979
980/// An iterator over the elements in an arena.
981///
982/// Yields `T` items.
983///
984/// Order of iteration is not defined.
985///
986/// # Examples
987///
988/// ```
989/// use generational_arena::Arena;
990///
991/// let mut arena = Arena::new();
992/// for i in 0..10 {
993/// arena.insert(i * i);
994/// }
995///
996/// for value in arena {
997/// assert!(value < 100);
998/// }
999/// ```
1000#[derive(Clone, Debug)]
1001pub struct IntoIter<T> {
1002 len: usize,
1003 inner: vec::IntoIter<Entry<T>>,
1004}
1005
1006impl<T> Iterator for IntoIter<T> {
1007 type Item = T;
1008
1009 fn next(&mut self) -> Option<Self::Item> {
1010 loop {
1011 match self.inner.next() {
1012 Some(Entry::Free { .. }) => continue,
1013 Some(Entry::Occupied { value, .. }) => {
1014 self.len -= 1;
1015 return Some(value);
1016 }
1017 None => {
1018 debug_assert_eq!(self.len, 0);
1019 return None;
1020 }
1021 }
1022 }
1023 }
1024
1025 fn size_hint(&self) -> (usize, Option<usize>) {
1026 (self.len, Some(self.len))
1027 }
1028}
1029
1030impl<T> DoubleEndedIterator for IntoIter<T> {
1031 fn next_back(&mut self) -> Option<Self::Item> {
1032 loop {
1033 match self.inner.next_back() {
1034 Some(Entry::Free { .. }) => continue,
1035 Some(Entry::Occupied { value, .. }) => {
1036 self.len -= 1;
1037 return Some(value);
1038 }
1039 None => {
1040 debug_assert_eq!(self.len, 0);
1041 return None;
1042 }
1043 }
1044 }
1045 }
1046}
1047
1048impl<T> ExactSizeIterator for IntoIter<T> {
1049 fn len(&self) -> usize {
1050 self.len
1051 }
1052}
1053
1054impl<T> FusedIterator for IntoIter<T> {}
1055
1056impl<'a, T> IntoIterator for &'a Arena<T> {
1057 type Item = (Index, &'a T);
1058 type IntoIter = Iter<'a, T>;
1059 fn into_iter(self) -> Self::IntoIter {
1060 self.iter()
1061 }
1062}
1063
1064/// An iterator over shared references to the elements in an arena.
1065///
1066/// Yields pairs of `(Index, &T)` items.
1067///
1068/// Order of iteration is not defined.
1069///
1070/// # Examples
1071///
1072/// ```
1073/// use generational_arena::Arena;
1074///
1075/// let mut arena = Arena::new();
1076/// for i in 0..10 {
1077/// arena.insert(i * i);
1078/// }
1079///
1080/// for (idx, value) in &arena {
1081/// println!("{} is at index {:?}", value, idx);
1082/// }
1083/// ```
1084#[derive(Clone, Debug)]
1085pub struct Iter<'a, T: 'a> {
1086 len: usize,
1087 inner: iter::Enumerate<slice::Iter<'a, Entry<T>>>,
1088}
1089
1090impl<'a, T> Iterator for Iter<'a, T> {
1091 type Item = (Index, &'a T);
1092
1093 fn next(&mut self) -> Option<Self::Item> {
1094 loop {
1095 match self.inner.next() {
1096 Some((_, &Entry::Free { .. })) => continue,
1097 Some((
1098 index,
1099 &Entry::Occupied {
1100 generation,
1101 ref value,
1102 },
1103 )) => {
1104 self.len -= 1;
1105 let idx = Index { index, generation };
1106 return Some((idx, value));
1107 }
1108 None => {
1109 debug_assert_eq!(self.len, 0);
1110 return None;
1111 }
1112 }
1113 }
1114 }
1115
1116 fn size_hint(&self) -> (usize, Option<usize>) {
1117 (self.len, Some(self.len))
1118 }
1119}
1120
1121impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1122 fn next_back(&mut self) -> Option<Self::Item> {
1123 loop {
1124 match self.inner.next_back() {
1125 Some((_, &Entry::Free { .. })) => continue,
1126 Some((
1127 index,
1128 &Entry::Occupied {
1129 generation,
1130 ref value,
1131 },
1132 )) => {
1133 self.len -= 1;
1134 let idx = Index { index, generation };
1135 return Some((idx, value));
1136 }
1137 None => {
1138 debug_assert_eq!(self.len, 0);
1139 return None;
1140 }
1141 }
1142 }
1143 }
1144}
1145
1146impl<'a, T> ExactSizeIterator for Iter<'a, T> {
1147 fn len(&self) -> usize {
1148 self.len
1149 }
1150}
1151
1152impl<'a, T> FusedIterator for Iter<'a, T> {}
1153
1154impl<'a, T> IntoIterator for &'a mut Arena<T> {
1155 type Item = (Index, &'a mut T);
1156 type IntoIter = IterMut<'a, T>;
1157 fn into_iter(self) -> Self::IntoIter {
1158 self.iter_mut()
1159 }
1160}
1161
1162/// An iterator over exclusive references to elements in this arena.
1163///
1164/// Yields pairs of `(Index, &mut T)` items.
1165///
1166/// Order of iteration is not defined.
1167///
1168/// # Examples
1169///
1170/// ```
1171/// use generational_arena::Arena;
1172///
1173/// let mut arena = Arena::new();
1174/// for i in 0..10 {
1175/// arena.insert(i * i);
1176/// }
1177///
1178/// for (_idx, value) in &mut arena {
1179/// *value += 5;
1180/// }
1181/// ```
1182#[derive(Debug)]
1183pub struct IterMut<'a, T: 'a> {
1184 len: usize,
1185 inner: iter::Enumerate<slice::IterMut<'a, Entry<T>>>,
1186}
1187
1188impl<'a, T> Iterator for IterMut<'a, T> {
1189 type Item = (Index, &'a mut T);
1190
1191 fn next(&mut self) -> Option<Self::Item> {
1192 loop {
1193 match self.inner.next() {
1194 Some((_, &mut Entry::Free { .. })) => continue,
1195 Some((
1196 index,
1197 &mut Entry::Occupied {
1198 generation,
1199 ref mut value,
1200 },
1201 )) => {
1202 self.len -= 1;
1203 let idx = Index { index, generation };
1204 return Some((idx, value));
1205 }
1206 None => {
1207 debug_assert_eq!(self.len, 0);
1208 return None;
1209 }
1210 }
1211 }
1212 }
1213
1214 fn size_hint(&self) -> (usize, Option<usize>) {
1215 (self.len, Some(self.len))
1216 }
1217}
1218
1219impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1220 fn next_back(&mut self) -> Option<Self::Item> {
1221 loop {
1222 match self.inner.next_back() {
1223 Some((_, &mut Entry::Free { .. })) => continue,
1224 Some((
1225 index,
1226 &mut Entry::Occupied {
1227 generation,
1228 ref mut value,
1229 },
1230 )) => {
1231 self.len -= 1;
1232 let idx = Index { index, generation };
1233 return Some((idx, value));
1234 }
1235 None => {
1236 debug_assert_eq!(self.len, 0);
1237 return None;
1238 }
1239 }
1240 }
1241 }
1242}
1243
1244impl<'a, T> ExactSizeIterator for IterMut<'a, T> {
1245 fn len(&self) -> usize {
1246 self.len
1247 }
1248}
1249
1250impl<'a, T> FusedIterator for IterMut<'a, T> {}
1251
1252/// An iterator that removes elements from the arena.
1253///
1254/// Yields pairs of `(Index, T)` items.
1255///
1256/// Order of iteration is not defined.
1257///
1258/// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
1259///
1260/// # Examples
1261///
1262/// ```
1263/// use generational_arena::Arena;
1264///
1265/// let mut arena = Arena::new();
1266/// let idx_1 = arena.insert("hello");
1267/// let idx_2 = arena.insert("world");
1268///
1269/// assert!(arena.get(idx_1).is_some());
1270/// assert!(arena.get(idx_2).is_some());
1271/// for (idx, value) in arena.drain() {
1272/// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
1273/// }
1274/// assert!(arena.get(idx_1).is_none());
1275/// assert!(arena.get(idx_2).is_none());
1276/// ```
1277#[derive(Debug)]
1278pub struct Drain<'a, T: 'a> {
1279 len: usize,
1280 inner: iter::Enumerate<vec::Drain<'a, Entry<T>>>,
1281}
1282
1283impl<'a, T> Iterator for Drain<'a, T> {
1284 type Item = (Index, T);
1285
1286 fn next(&mut self) -> Option<Self::Item> {
1287 loop {
1288 match self.inner.next() {
1289 Some((_, Entry::Free { .. })) => continue,
1290 Some((index, Entry::Occupied { generation, value })) => {
1291 let idx = Index { index, generation };
1292 self.len -= 1;
1293 return Some((idx, value));
1294 }
1295 None => {
1296 debug_assert_eq!(self.len, 0);
1297 return None;
1298 }
1299 }
1300 }
1301 }
1302
1303 fn size_hint(&self) -> (usize, Option<usize>) {
1304 (self.len, Some(self.len))
1305 }
1306}
1307
1308impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
1309 fn next_back(&mut self) -> Option<Self::Item> {
1310 loop {
1311 match self.inner.next_back() {
1312 Some((_, Entry::Free { .. })) => continue,
1313 Some((index, Entry::Occupied { generation, value })) => {
1314 let idx = Index { index, generation };
1315 self.len -= 1;
1316 return Some((idx, value));
1317 }
1318 None => {
1319 debug_assert_eq!(self.len, 0);
1320 return None;
1321 }
1322 }
1323 }
1324 }
1325}
1326
1327impl<'a, T> ExactSizeIterator for Drain<'a, T> {
1328 fn len(&self) -> usize {
1329 self.len
1330 }
1331}
1332
1333impl<'a, T> FusedIterator for Drain<'a, T> {}
1334
1335impl<T> Extend<T> for Arena<T> {
1336 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1337 for t in iter {
1338 self.insert(t);
1339 }
1340 }
1341}
1342
1343impl<T> FromIterator<T> for Arena<T> {
1344 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1345 let iter = iter.into_iter();
1346 let (lower, upper) = iter.size_hint();
1347 let cap = upper.unwrap_or(lower);
1348 let cap = cmp::max(cap, 1);
1349 let mut arena = Arena::with_capacity(cap);
1350 arena.extend(iter);
1351 arena
1352 }
1353}
1354
1355impl<T> ops::Index<Index> for Arena<T> {
1356 type Output = T;
1357
1358 fn index(&self, index: Index) -> &Self::Output {
1359 self.get(index).expect("No element at index")
1360 }
1361}
1362
1363impl<T> ops::IndexMut<Index> for Arena<T> {
1364 fn index_mut(&mut self, index: Index) -> &mut Self::Output {
1365 self.get_mut(index).expect("No element at index")
1366 }
1367}