obj_pool/lib.rs
1//! A simple object pool.
2//!
3//! `ObjPool<T>` is basically just a `Vec<Option<T>>`, which allows you to:
4//!
5//! * Insert an object (reuse an existing `None` element, or append to the end) and get an `ObjId`
6//! in return.
7//! * Remove object with a specified `ObjId`.
8//! * Access object with a specified `ObjId`.
9//! * Convert `ObjId` to index and back for specified `ObjPool`.
10//!
11//! # Limitations:
12//!
13//! * `ObjId` is always 32-bit long.
14//!
15//! # Examples
16//!
17//! Some data structures built using `ObjPool<T>`:
18//!
19//! * [Doubly linked list](https://github.com/artemshein/obj-pool/blob/master/examples/linked_list.rs)
20//! * [Splay tree](https://github.com/artemshein/obj-pool/blob/master/examples/splay_tree.rs)
21use std::{
22 fmt, iter, mem,
23 num::{NonZeroU32, ParseIntError},
24 ops::{Index, IndexMut},
25 ptr,
26 str::FromStr,
27 vec,
28};
29
30use std::ops::Deref;
31use std::slice;
32use unreachable::unreachable;
33
34#[cfg(feature = "serde_support")]
35use serde::{Deserialize, Serialize};
36
37mod par;
38pub use par::*;
39
40/// A slot, which is either vacant or occupied.
41///
42/// Vacant slots in object pool are linked together into a singly linked list. This allows the object pool to
43/// efficiently find a vacant slot before inserting a new object, or reclaiming a slot after
44/// removing an object.
45#[derive(Clone)]
46enum Slot<T> {
47 /// Vacant slot, containing index to the next slot in the linked list.
48 Vacant(u32),
49
50 /// Occupied slot, containing a value.
51 Occupied(T),
52}
53
54/// An id of the object in an `ObjPool`.
55///
56/// In release it is basically just an index in the underlying vector, but in debug it's an `index` +
57/// `ObjPool`-specific `offset`. This is made to be able to check `ObjId` if it's from the same
58/// `ObjPool` we are trying to get an object from.
59#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
60#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
61pub struct ObjId(pub NonZeroU32);
62
63impl ObjId {
64 pub fn from_index(index: u32) -> Self {
65 Self(NonZeroU32::new(index + 1).expect("invalid index"))
66 }
67
68 pub const fn into_index(self) -> u32 {
69 self.0.get() - 1
70 }
71}
72
73impl std::fmt::Display for ObjId {
74 fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
75 self.0.fmt(f)
76 }
77}
78
79impl FromStr for ObjId {
80 type Err = ParseIntError;
81
82 fn from_str(s: &str) -> Result<Self, Self::Err> {
83 Ok(ObjId(s.parse::<NonZeroU32>()?))
84 }
85}
86
87impl Deref for ObjId {
88 type Target = NonZeroU32;
89
90 fn deref(&self) -> &Self::Target {
91 &self.0
92 }
93}
94
95impl From<NonZeroU32> for ObjId {
96 fn from(v: NonZeroU32) -> ObjId {
97 ObjId(v)
98 }
99}
100
101/// An object pool.
102///
103/// `ObjPool<T>` holds an array of slots for storing objects.
104/// Every slot is always in one of two states: occupied or vacant.
105///
106/// Essentially, this is equivalent to `Vec<Option<T>>`.
107///
108/// # Insert and remove
109///
110/// When inserting a new object into object pool, a vacant slot is found and then the object is placed
111/// into the slot. If there are no vacant slots, the array is reallocated with bigger capacity.
112/// The cost of insertion is amortized `O(1)`.
113///
114/// When removing an object, the slot containing it is marked as vacant and the object is returned.
115/// The cost of removal is `O(1)`.
116///
117/// ```
118/// use obj_pool::ObjPool;
119///
120/// let mut obj_pool = ObjPool::new();
121/// let a = obj_pool.insert(10);
122/// assert_eq!(a.into_index(), 0);
123/// let b = obj_pool.insert(20);
124/// assert_eq!(b.into_index(), 1);
125///
126/// assert_ne!(a, b); // ids are not the same
127///
128/// assert_eq!(obj_pool.remove(a), Some(10));
129/// assert_eq!(obj_pool.get(a), None); // there is no object with this `ObjId` anymore
130///
131/// assert_eq!(obj_pool.insert(30), a); // slot is reused, got the same `ObjId`
132/// ```
133///
134/// # Indexing
135///
136/// You can also access objects in an object pool by `ObjId`.
137/// However, accessing an object with invalid `ObjId` will result in panic.
138///
139/// ```
140/// use obj_pool::ObjPool;
141///
142/// let mut obj_pool = ObjPool::new();
143/// let a = obj_pool.insert(10);
144/// let b = obj_pool.insert(20);
145///
146/// assert_eq!(obj_pool[a], 10);
147/// assert_eq!(obj_pool[b], 20);
148///
149/// obj_pool[a] += obj_pool[b];
150/// assert_eq!(obj_pool[a], 30);
151/// ```
152///
153/// To access slots without fear of panicking, use `get` and `get_mut`, which return `Option`s.
154pub struct ObjPool<T> {
155 /// Slots in which objects are stored.
156 slots: Vec<Slot<T>>,
157
158 /// Number of occupied slots in the object pool.
159 len: u32,
160
161 /// Index of the first vacant slot in the linked list.
162 head: u32,
163}
164
165impl<T> AsRef<ObjPool<T>> for ObjPool<T> {
166 fn as_ref(&self) -> &ObjPool<T> {
167 self
168 }
169}
170
171impl<T> AsMut<ObjPool<T>> for ObjPool<T> {
172 fn as_mut(&mut self) -> &mut ObjPool<T> {
173 self
174 }
175}
176
177impl<T> ObjPool<T> {
178 /// Constructs a new, empty object pool.
179 ///
180 /// The object pool will not allocate until objects are inserted into it.
181 ///
182 /// # Examples
183 ///
184 /// ```
185 /// use obj_pool::ObjPool;
186 ///
187 /// let mut obj_pool: ObjPool<i32> = ObjPool::new();
188 /// ```
189 #[inline]
190 pub const fn new() -> Self {
191 ObjPool {
192 slots: Vec::new(),
193 len: 0,
194 head: u32::MAX,
195 }
196 }
197
198 /// Get an index in the `ObjPool` for the given `ObjId`.
199 #[inline]
200 pub const fn obj_id_to_index(obj_id: ObjId) -> u32 {
201 obj_id.into_index()
202 }
203
204 /// Make an `ObjId` from an index in this `ObjPool`.
205 #[inline]
206 pub fn index_to_obj_id(index: u32) -> ObjId {
207 ObjId::from_index(index)
208 }
209
210 /// Constructs a new, empty object pool with the specified capacity (number of slots).
211 ///
212 /// The object pool will be able to hold exactly `capacity` objects without reallocating.
213 /// If `capacity` is 0, the object pool will not allocate.
214 ///
215 /// # Examples
216 ///
217 /// ```
218 /// use obj_pool::ObjPool;
219 ///
220 /// let mut obj_pool = ObjPool::with_capacity(10);
221 ///
222 /// assert_eq!(obj_pool.len(), 0);
223 /// assert_eq!(obj_pool.capacity(), 10);
224 ///
225 /// // These inserts are done without reallocating...
226 /// for i in 0..10 {
227 /// obj_pool.insert(i);
228 /// }
229 /// assert_eq!(obj_pool.capacity(), 10);
230 ///
231 /// // ... but this one will reallocate.
232 /// obj_pool.insert(11);
233 /// assert!(obj_pool.capacity() > 10);
234 /// ```
235 #[inline]
236 pub fn with_capacity(cap: usize) -> Self {
237 ObjPool {
238 slots: Vec::with_capacity(cap),
239 len: 0,
240 head: u32::MAX,
241 }
242 }
243
244 /// Returns the number of slots in the object pool.
245 ///
246 /// # Examples
247 ///
248 /// ```
249 /// use obj_pool::ObjPool;
250 ///
251 /// let obj_pool: ObjPool<i32> = ObjPool::with_capacity(10);
252 /// assert_eq!(obj_pool.capacity(), 10);
253 /// ```
254 #[inline]
255 pub fn capacity(&self) -> usize {
256 self.slots.capacity()
257 }
258
259 /// Returns the number of occupied slots in the object pool.
260 ///
261 /// # Examples
262 ///
263 /// ```
264 /// use obj_pool::ObjPool;
265 ///
266 /// let mut obj_pool = ObjPool::new();
267 /// assert_eq!(obj_pool.len(), 0);
268 ///
269 /// for i in 0..10 {
270 /// obj_pool.insert(());
271 /// assert_eq!(obj_pool.len(), i + 1);
272 /// }
273 /// ```
274 #[inline]
275 pub fn len(&self) -> u32 {
276 self.len
277 }
278
279 /// Returns `true` if all slots are vacant.
280 ///
281 /// # Examples
282 ///
283 /// ```
284 /// use obj_pool::ObjPool;
285 ///
286 /// let mut obj_pool = ObjPool::new();
287 /// assert!(obj_pool.is_empty());
288 ///
289 /// obj_pool.insert(1);
290 /// assert!(!obj_pool.is_empty());
291 /// ```
292 #[inline]
293 pub fn is_empty(&self) -> bool {
294 self.len == 0
295 }
296
297 /// Returns the `ObjId` of the next inserted object if no other
298 /// mutating calls take place in between.
299 ///
300 /// # Examples
301 ///
302 /// ```
303 /// use obj_pool::ObjPool;
304 ///
305 /// let mut obj_pool = ObjPool::new();
306 ///
307 /// let a = obj_pool.next_vacant();
308 /// let b = obj_pool.insert(1);
309 /// assert_eq!(a, b);
310 /// let c = obj_pool.next_vacant();
311 /// let d = obj_pool.insert(2);
312 /// assert_eq!(c, d);
313 /// ```
314 #[inline]
315 pub fn next_vacant(&mut self) -> ObjId {
316 Self::index_to_obj_id(if self.head == u32::MAX {
317 self.len
318 } else {
319 self.head
320 })
321 }
322
323 /// Inserts an object into the object pool and returns the `ObjId` of this object.
324 /// The object pool will reallocate if it's full.
325 ///
326 /// # Examples
327 ///
328 /// ```
329 /// use obj_pool::ObjPool;
330 ///
331 /// let mut obj_pool = ObjPool::new();
332 ///
333 /// let a = obj_pool.insert(1);
334 /// let b = obj_pool.insert(2);
335 /// assert!(a != b);
336 /// ```
337 pub fn insert(&mut self, object: T) -> ObjId {
338 self.len += 1;
339
340 if self.head == u32::MAX {
341 self.slots.push(Slot::Occupied(object));
342 Self::index_to_obj_id(self.len - 1)
343 } else {
344 let index = self.head;
345 match self.slots[index as usize] {
346 Slot::Vacant(next) => {
347 self.head = next;
348 self.slots[index as usize] = Slot::Occupied(object);
349 }
350 Slot::Occupied(_) => unreachable!(),
351 }
352 Self::index_to_obj_id(index)
353 }
354 }
355
356 /// Removes the object stored by `ObjId` from the object pool and returns it.
357 ///
358 /// `None` is returned in case the there is no object with such an `ObjId`.
359 ///
360 /// # Examples
361 ///
362 /// ```
363 /// use obj_pool::ObjPool;
364 ///
365 /// let mut obj_pool = ObjPool::new();
366 /// let a = obj_pool.insert("hello");
367 ///
368 /// assert_eq!(obj_pool.len(), 1);
369 /// assert_eq!(obj_pool.remove(a), Some("hello"));
370 ///
371 /// assert_eq!(obj_pool.len(), 0);
372 /// assert_eq!(obj_pool.remove(a), None);
373 /// ```
374 pub fn remove(&mut self, obj_id: ObjId) -> Option<T> {
375 let index = Self::obj_id_to_index(obj_id);
376 match self.slots.get_mut(index as usize) {
377 None => None,
378 Some(&mut Slot::Vacant(_)) => None,
379 Some(slot @ &mut Slot::Occupied(_)) => {
380 if let Slot::Occupied(object) = mem::replace(slot, Slot::Vacant(self.head)) {
381 self.head = index;
382 self.len -= 1;
383 Some(object)
384 } else {
385 unreachable!();
386 }
387 }
388 }
389 }
390
391 /// Clears the object pool, removing and dropping all objects it holds. Keeps the allocated memory
392 /// for reuse.
393 ///
394 /// # Examples
395 ///
396 /// ```
397 /// use obj_pool::ObjPool;
398 ///
399 /// let mut obj_pool = ObjPool::new();
400 /// for i in 0..10 {
401 /// obj_pool.insert(i);
402 /// }
403 ///
404 /// assert_eq!(obj_pool.len(), 10);
405 /// obj_pool.clear();
406 /// assert_eq!(obj_pool.len(), 0);
407 /// ```
408 #[inline]
409 pub fn clear(&mut self) {
410 self.slots.clear();
411 self.len = 0;
412 self.head = u32::MAX;
413 }
414
415 /// Returns a reference to the object by its `ObjId`.
416 ///
417 /// If object is not found with given `obj_id`, `None` is returned.
418 ///
419 /// # Examples
420 ///
421 /// ```
422 /// use obj_pool::ObjPool;
423 ///
424 /// let mut obj_pool = ObjPool::new();
425 /// let obj_id = obj_pool.insert("hello");
426 ///
427 /// assert_eq!(obj_pool.get(obj_id), Some(&"hello"));
428 /// obj_pool.remove(obj_id);
429 /// assert_eq!(obj_pool.get(obj_id), None);
430 /// ```
431 pub fn get(&self, obj_id: ObjId) -> Option<&T> {
432 let index = Self::obj_id_to_index(obj_id) as usize;
433 match self.slots.get(index) {
434 None => None,
435 Some(&Slot::Vacant(_)) => None,
436 Some(&Slot::Occupied(ref object)) => Some(object),
437 }
438 }
439
440 /// Returns a mutable reference to the object by its `ObjId`.
441 ///
442 /// If object can't be found, `None` is returned.
443 ///
444 /// # Examples
445 ///
446 /// ```
447 /// use obj_pool::ObjPool;
448 ///
449 /// let mut obj_pool = ObjPool::new();
450 /// let obj_id = obj_pool.insert(7);
451 ///
452 /// assert_eq!(obj_pool.get_mut(obj_id), Some(&mut 7));
453 /// *obj_pool.get_mut(obj_id).unwrap() *= 10;
454 /// assert_eq!(obj_pool.get_mut(obj_id), Some(&mut 70));
455 /// ```
456 #[inline]
457 pub fn get_mut(&mut self, obj_id: ObjId) -> Option<&mut T> {
458 let index = Self::obj_id_to_index(obj_id) as usize;
459 match self.slots.get_mut(index) {
460 None => None,
461 Some(&mut Slot::Vacant(_)) => None,
462 Some(&mut Slot::Occupied(ref mut object)) => Some(object),
463 }
464 }
465
466 /// Returns a reference to the object by its `ObjId`.
467 ///
468 /// # Safety
469 ///
470 /// Behavior is undefined if object can't be found.
471 ///
472 /// # Examples
473 ///
474 /// ```
475 /// use obj_pool::ObjPool;
476 ///
477 /// let mut obj_pool = ObjPool::new();
478 /// let obj_id = obj_pool.insert("hello");
479 ///
480 /// unsafe { assert_eq!(&*obj_pool.get_unchecked(obj_id), &"hello") }
481 /// ```
482 pub unsafe fn get_unchecked(&self, obj_id: ObjId) -> &T {
483 match self.slots.get(Self::obj_id_to_index(obj_id) as usize) {
484 None => unreachable(),
485 Some(&Slot::Vacant(_)) => unreachable(),
486 Some(&Slot::Occupied(ref object)) => object,
487 }
488 }
489
490 /// Returns a mutable reference to the object by its `ObjId`.
491 ///
492 /// # Safety
493 ///
494 /// Behavior is undefined if object can't be found.
495 ///
496 /// # Examples
497 ///
498 /// ```
499 /// use obj_pool::ObjPool;
500 ///
501 /// let mut obj_pool = ObjPool::new();
502 /// let obj_id = obj_pool.insert("hello");
503 ///
504 /// unsafe { assert_eq!(&*obj_pool.get_unchecked_mut(obj_id), &"hello") }
505 /// ```
506 pub unsafe fn get_unchecked_mut(&mut self, obj_id: ObjId) -> &mut T {
507 let index = Self::obj_id_to_index(obj_id) as usize;
508 match self.slots.get_mut(index) {
509 Some(&mut Slot::Vacant(_)) => unreachable(),
510 Some(&mut Slot::Occupied(ref mut object)) => object,
511 _ => unreachable(),
512 }
513 }
514
515 /// Swaps two objects in the object pool.
516 ///
517 /// The two `ObjId`s are `a` and `b`.
518 ///
519 /// # Panics
520 ///
521 /// Panics if any of the `ObjId`s is invalid.
522 ///
523 /// # Examples
524 ///
525 /// ```
526 /// use obj_pool::ObjPool;
527 ///
528 /// let mut obj_pool = ObjPool::new();
529 /// let a = obj_pool.insert(7);
530 /// let b = obj_pool.insert(8);
531 ///
532 /// obj_pool.swap(a, b);
533 /// assert_eq!(obj_pool.get(a), Some(&8));
534 /// assert_eq!(obj_pool.get(b), Some(&7));
535 /// ```
536 #[inline]
537 pub fn swap(&mut self, a: ObjId, b: ObjId) {
538 unsafe {
539 let fst = self.get_mut(a).unwrap() as *mut _;
540 let snd = self.get_mut(b).unwrap() as *mut _;
541 if a != b {
542 ptr::swap(fst, snd);
543 }
544 }
545 }
546
547 /// Reserves capacity for at least `additional` more objects to be inserted. The object pool may
548 /// reserve more space to avoid frequent reallocations.
549 ///
550 /// # Panics
551 ///
552 /// Panics if the new capacity overflows `u32`.
553 ///
554 /// # Examples
555 ///
556 /// ```
557 /// use obj_pool::ObjPool;
558 ///
559 /// let mut obj_pool = ObjPool::new();
560 /// obj_pool.insert("hello");
561 ///
562 /// obj_pool.reserve(10);
563 /// assert!(obj_pool.capacity() >= 11);
564 /// ```
565 pub fn reserve(&mut self, additional: u32) {
566 let vacant = self.slots.len() as u32 - self.len;
567 if additional > vacant {
568 self.slots.reserve((additional - vacant) as usize);
569 }
570 }
571
572 /// Reserves the minimum capacity for exactly `additional` more objects to be inserted.
573 ///
574 /// Note that the allocator may give the object pool more space than it requests.
575 ///
576 /// # Panics
577 ///
578 /// Panics if the new capacity overflows `u32`.
579 ///
580 /// # Examples
581 ///
582 /// ```
583 /// use obj_pool::ObjPool;
584 ///
585 /// let mut obj_pool = ObjPool::new();
586 /// obj_pool.insert("hello");
587 ///
588 /// obj_pool.reserve_exact(10);
589 /// assert!(obj_pool.capacity() >= 11);
590 /// ```
591 pub fn reserve_exact(&mut self, additional: u32) {
592 let vacant = self.slots.len() as u32 - self.len;
593 if additional > vacant {
594 self.slots.reserve_exact((additional - vacant) as usize);
595 }
596 }
597
598 /// Returns an iterator over occupied slots.
599 ///
600 /// # Examples
601 ///
602 /// ```
603 /// use obj_pool::ObjPool;
604 ///
605 /// let mut obj_pool = ObjPool::new();
606 /// obj_pool.insert(1);
607 /// obj_pool.insert(2);
608 /// obj_pool.insert(4);
609 ///
610 /// let mut iterator = obj_pool.iter();
611 /// assert_eq!(iterator.next(), Some((ObjPool::<usize>::index_to_obj_id(0), &1)));
612 /// assert_eq!(iterator.next(), Some((ObjPool::<usize>::index_to_obj_id(1), &2)));
613 /// assert_eq!(iterator.next(), Some((ObjPool::<usize>::index_to_obj_id(2), &4)));
614 /// ```
615 #[inline]
616 pub fn iter(&self) -> Iter<T> {
617 Iter {
618 slots: self.slots.iter().enumerate(),
619 }
620 }
621
622 /// Returns an iterator that returns mutable references to objects.
623 ///
624 /// # Examples
625 ///
626 /// ```
627 /// use obj_pool::ObjPool;
628 ///
629 /// let mut obj_pool = ObjPool::new();
630 /// obj_pool.insert("zero".to_string());
631 /// obj_pool.insert("one".to_string());
632 /// obj_pool.insert("two".to_string());
633 ///
634 /// for (obj_id, object) in obj_pool.iter_mut() {
635 /// *object = obj_id.into_index().to_string() + " " + object;
636 /// }
637 ///
638 /// let mut iterator = obj_pool.iter();
639 /// assert_eq!(iterator.next(), Some((ObjPool::<String>::index_to_obj_id(0), &"0 zero".to_string())));
640 /// assert_eq!(iterator.next(), Some((ObjPool::<String>::index_to_obj_id(1), &"1 one".to_string())));
641 /// assert_eq!(iterator.next(), Some((ObjPool::<String>::index_to_obj_id(2), &"2 two".to_string())));
642 /// ```
643 #[inline]
644 pub fn iter_mut(&mut self) -> IterMut<T> {
645 IterMut {
646 slots: self.slots.iter_mut().enumerate(),
647 }
648 }
649
650 /// Shrinks the capacity of the object pool as much as possible.
651 ///
652 /// It will drop down as close as possible to the length but the allocator may still inform
653 /// the object pool that there is space for a few more elements.
654 ///
655 /// # Examples
656 ///
657 /// ```
658 /// use obj_pool::ObjPool;
659 ///
660 /// let mut obj_pool = ObjPool::with_capacity(10);
661 /// obj_pool.insert("first".to_string());
662 /// obj_pool.insert("second".to_string());
663 /// obj_pool.insert("third".to_string());
664 /// assert_eq!(obj_pool.capacity(), 10);
665 /// obj_pool.shrink_to_fit();
666 /// assert!(obj_pool.capacity() >= 3);
667 /// ```
668 pub fn shrink_to_fit(&mut self) {
669 self.slots.shrink_to_fit();
670 }
671}
672
673impl<T> fmt::Debug for ObjPool<T> {
674 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
675 write!(f, "ObjPool {{ ... }}")
676 }
677}
678
679impl<T> Index<ObjId> for ObjPool<T> {
680 type Output = T;
681
682 #[inline]
683 fn index(&self, obj_id: ObjId) -> &T {
684 self.get(obj_id).expect("object not found")
685 }
686}
687
688impl<T> IndexMut<ObjId> for ObjPool<T> {
689 #[inline]
690 fn index_mut(&mut self, obj_id: ObjId) -> &mut T {
691 self.get_mut(obj_id).expect("object not found")
692 }
693}
694
695impl<T> Default for ObjPool<T> {
696 fn default() -> Self {
697 ObjPool::new()
698 }
699}
700
701impl<T: Clone> Clone for ObjPool<T> {
702 fn clone(&self) -> Self {
703 ObjPool {
704 slots: self.slots.clone(),
705 len: self.len,
706 head: self.head,
707 }
708 }
709}
710
711/// An iterator over the occupied slots in a `ObjPool`.
712pub struct IntoIter<T> {
713 slots: iter::Enumerate<vec::IntoIter<Slot<T>>>,
714}
715
716impl<T> IntoIter<T> {
717 #[inline]
718 pub const fn obj_id_to_index(obj_id: ObjId) -> u32 {
719 obj_id.into_index()
720 }
721
722 #[inline]
723 pub fn index_to_obj_id(index: u32) -> ObjId {
724 ObjId::from_index(index)
725 }
726}
727
728impl<T> Iterator for IntoIter<T> {
729 type Item = (ObjId, T);
730
731 #[inline]
732 fn next(&mut self) -> Option<Self::Item> {
733 while let Some((index, slot)) = self.slots.next() {
734 if let Slot::Occupied(object) = slot {
735 return Some((Self::index_to_obj_id(index as u32), object));
736 }
737 }
738 None
739 }
740}
741
742impl<T> IntoIterator for ObjPool<T> {
743 type Item = (ObjId, T);
744 type IntoIter = IntoIter<T>;
745
746 #[inline]
747 fn into_iter(self) -> Self::IntoIter {
748 IntoIter {
749 slots: self.slots.into_iter().enumerate(),
750 }
751 }
752}
753
754impl<T> iter::FromIterator<T> for ObjPool<T> {
755 fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> ObjPool<T> {
756 let iter = iter.into_iter();
757 let mut obj_pool = ObjPool::with_capacity(iter.size_hint().0);
758 for i in iter {
759 obj_pool.insert(i);
760 }
761 obj_pool
762 }
763}
764
765impl<T> fmt::Debug for IntoIter<T> {
766 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
767 write!(f, "IntoIter {{ ... }}")
768 }
769}
770
771/// An iterator over references to the occupied slots in a `ObjPool`.
772pub struct Iter<'a, T: 'a> {
773 slots: iter::Enumerate<slice::Iter<'a, Slot<T>>>,
774}
775
776impl<'a, T: 'a> Iter<'a, T> {
777 #[inline]
778 pub fn index_to_obj_id(index: u32) -> ObjId {
779 ObjId::from_index(index)
780 }
781}
782
783impl<'a, T> Iterator for Iter<'a, T> {
784 type Item = (ObjId, &'a T);
785
786 #[inline]
787 fn next(&mut self) -> Option<Self::Item> {
788 while let Some((index, slot)) = self.slots.next() {
789 if let Slot::Occupied(ref object) = *slot {
790 return Some((Self::index_to_obj_id(index as u32), object));
791 }
792 }
793 None
794 }
795}
796
797impl<'a, T> IntoIterator for &'a ObjPool<T> {
798 type Item = (ObjId, &'a T);
799 type IntoIter = Iter<'a, T>;
800
801 #[inline]
802 fn into_iter(self) -> Self::IntoIter {
803 self.iter()
804 }
805}
806
807impl<'a, T> fmt::Debug for Iter<'a, T> {
808 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
809 write!(f, "Iter {{ ... }}")
810 }
811}
812
813/// An iterator over mutable references to the occupied slots in a `Arena`.
814pub struct IterMut<'a, T: 'a> {
815 slots: iter::Enumerate<slice::IterMut<'a, Slot<T>>>,
816}
817
818impl<'a, T: 'a> IterMut<'a, T> {
819 #[inline]
820 pub const fn obj_id_to_index(obj_id: ObjId) -> u32 {
821 obj_id.into_index()
822 }
823
824 #[inline]
825 pub fn index_to_obj_id(index: u32) -> ObjId {
826 ObjId::from_index(index)
827 }
828}
829
830impl<'a, T> Iterator for IterMut<'a, T> {
831 type Item = (ObjId, &'a mut T);
832
833 #[inline]
834 fn next(&mut self) -> Option<Self::Item> {
835 while let Some((index, slot)) = self.slots.next() {
836 if let Slot::Occupied(ref mut object) = *slot {
837 return Some((Self::index_to_obj_id(index as u32), object));
838 }
839 }
840 None
841 }
842}
843
844impl<'a, T> IntoIterator for &'a mut ObjPool<T> {
845 type Item = (ObjId, &'a mut T);
846 type IntoIter = IterMut<'a, T>;
847
848 #[inline]
849 fn into_iter(self) -> Self::IntoIter {
850 self.iter_mut()
851 }
852}
853
854impl<'a, T> fmt::Debug for IterMut<'a, T> {
855 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
856 write!(f, "IterMut {{ ... }}")
857 }
858}
859
860#[cfg(test)]
861mod tests {
862 use super::*;
863
864 #[test]
865 fn new() {
866 let obj_pool = ObjPool::<i32>::new();
867 assert!(obj_pool.is_empty());
868 assert_eq!(obj_pool.len(), 0);
869 assert_eq!(obj_pool.capacity(), 0);
870 }
871
872 #[test]
873 fn insert() {
874 let mut obj_pool = ObjPool::new();
875
876 for i in 0..10 {
877 let a = obj_pool.insert(i * 10);
878 assert_eq!(obj_pool[a], i * 10);
879 }
880 assert!(!obj_pool.is_empty());
881 assert_eq!(obj_pool.len(), 10);
882 }
883
884 #[test]
885 fn with_capacity() {
886 let mut obj_pool = ObjPool::with_capacity(10);
887 assert_eq!(obj_pool.capacity(), 10);
888
889 for _ in 0..10 {
890 obj_pool.insert(());
891 }
892 assert_eq!(obj_pool.len(), 10);
893 assert_eq!(obj_pool.capacity(), 10);
894
895 obj_pool.insert(());
896 assert_eq!(obj_pool.len(), 11);
897 assert!(obj_pool.capacity() > 10);
898 }
899
900 #[test]
901 fn remove() {
902 let mut obj_pool = ObjPool::new();
903
904 let a = obj_pool.insert(0);
905 let b = obj_pool.insert(10);
906 let c = obj_pool.insert(20);
907 obj_pool.insert(30);
908 assert_eq!(obj_pool.len(), 4);
909
910 assert_eq!(obj_pool.remove(b), Some(10));
911 assert_eq!(obj_pool.remove(c), Some(20));
912 assert_eq!(obj_pool.len(), 2);
913
914 obj_pool.insert(-1);
915 obj_pool.insert(-1);
916 assert_eq!(obj_pool.len(), 4);
917
918 assert_eq!(obj_pool.remove(a), Some(0));
919 obj_pool.insert(-1);
920 assert_eq!(obj_pool.len(), 4);
921
922 obj_pool.insert(400);
923 assert_eq!(obj_pool.len(), 5);
924 }
925
926 #[test]
927 fn clear() {
928 let mut obj_pool = ObjPool::new();
929 obj_pool.insert(10);
930 obj_pool.insert(20);
931
932 assert!(!obj_pool.is_empty());
933 assert_eq!(obj_pool.len(), 2);
934
935 let cap = obj_pool.capacity();
936 obj_pool.clear();
937
938 assert!(obj_pool.is_empty());
939 assert_eq!(obj_pool.len(), 0);
940 assert_eq!(obj_pool.capacity(), cap);
941 }
942
943 #[test]
944 fn indexing() {
945 let mut obj_pool = ObjPool::new();
946
947 let a = obj_pool.insert(10);
948 let b = obj_pool.insert(20);
949 let c = obj_pool.insert(30);
950
951 obj_pool[b] += obj_pool[c];
952 assert_eq!(obj_pool[a], 10);
953 assert_eq!(obj_pool[b], 50);
954 assert_eq!(obj_pool[c], 30);
955 }
956
957 #[test]
958 #[should_panic]
959 fn indexing_vacant() {
960 let mut obj_pool = ObjPool::new();
961
962 let _ = obj_pool.insert(10);
963 let b = obj_pool.insert(20);
964 let _ = obj_pool.insert(30);
965
966 obj_pool.remove(b);
967 obj_pool[b];
968 }
969
970 #[test]
971 #[should_panic]
972 fn invalid_indexing() {
973 let mut obj_pool = ObjPool::new();
974
975 obj_pool.insert(10);
976 obj_pool.insert(20);
977 let a = obj_pool.insert(30);
978 obj_pool.remove(a);
979
980 obj_pool[a];
981 }
982
983 #[test]
984 fn get() {
985 let mut obj_pool = ObjPool::new();
986
987 let a = obj_pool.insert(10);
988 let b = obj_pool.insert(20);
989 let c = obj_pool.insert(30);
990
991 *obj_pool.get_mut(b).unwrap() += *obj_pool.get(c).unwrap();
992 assert_eq!(obj_pool.get(a), Some(&10));
993 assert_eq!(obj_pool.get(b), Some(&50));
994 assert_eq!(obj_pool.get(c), Some(&30));
995
996 obj_pool.remove(b);
997 assert_eq!(obj_pool.get(b), None);
998 assert_eq!(obj_pool.get_mut(b), None);
999 }
1000
1001 #[test]
1002 fn reserve() {
1003 let mut obj_pool = ObjPool::new();
1004 obj_pool.insert(1);
1005 obj_pool.insert(2);
1006
1007 obj_pool.reserve(10);
1008 assert!(obj_pool.capacity() >= 11);
1009 }
1010
1011 #[test]
1012 fn reserve_exact() {
1013 let mut obj_pool = ObjPool::new();
1014 obj_pool.insert(1);
1015 obj_pool.insert(2);
1016 obj_pool.reserve(10);
1017 assert!(obj_pool.capacity() >= 11);
1018 }
1019
1020 #[test]
1021 fn iter() {
1022 let mut arena = ObjPool::new();
1023 let a = arena.insert(10);
1024 let b = arena.insert(20);
1025 let c = arena.insert(30);
1026 let d = arena.insert(40);
1027
1028 arena.remove(b);
1029
1030 let mut it = arena.iter();
1031 assert_eq!(it.next(), Some((a, &10)));
1032 assert_eq!(it.next(), Some((c, &30)));
1033 assert_eq!(it.next(), Some((d, &40)));
1034 assert_eq!(it.next(), None);
1035 }
1036
1037 #[test]
1038 fn iter_mut() {
1039 let mut obj_pool = ObjPool::new();
1040 let a = obj_pool.insert(10);
1041 let b = obj_pool.insert(20);
1042 let c = obj_pool.insert(30);
1043 let d = obj_pool.insert(40);
1044
1045 obj_pool.remove(b);
1046
1047 {
1048 let mut it = obj_pool.iter_mut();
1049 assert_eq!(it.next(), Some((a, &mut 10)));
1050 assert_eq!(it.next(), Some((c, &mut 30)));
1051 assert_eq!(it.next(), Some((d, &mut 40)));
1052 assert_eq!(it.next(), None);
1053 }
1054
1055 for (obj_id, value) in &mut obj_pool {
1056 *value += obj_id.get();
1057 }
1058
1059 let mut it = obj_pool.iter_mut();
1060 assert_eq!(*it.next().unwrap().1, 10 + a.get());
1061 assert_eq!(*it.next().unwrap().1, 30 + c.get());
1062 assert_eq!(*it.next().unwrap().1, 40 + d.get());
1063 assert_eq!(it.next(), None);
1064 }
1065
1066 #[test]
1067 fn from_iter() {
1068 let obj_pool: ObjPool<usize> = [10, 20, 30, 40].iter().cloned().collect();
1069
1070 let mut it = obj_pool.iter();
1071 assert_eq!(it.next(), Some((ObjPool::<usize>::index_to_obj_id(0), &10)));
1072 assert_eq!(it.next(), Some((ObjPool::<usize>::index_to_obj_id(1), &20)));
1073 assert_eq!(it.next(), Some((ObjPool::<usize>::index_to_obj_id(2), &30)));
1074 assert_eq!(it.next(), Some((ObjPool::<usize>::index_to_obj_id(3), &40)));
1075 assert_eq!(it.next(), None);
1076 }
1077}