obj_pool/

lib.rs

//! A simple object pool.
//!
//! `ObjPool<T>` is basically just a `Vec<Option<T>>`, which allows you to:
//!
//! * Insert an object (reuse an existing `None` element, or append to the end) and get an `ObjId`
//!   in return.
//! * Remove object with a specified `ObjId`.
//! * Access object with a specified `ObjId`.
//! * Convert `ObjId` to index and back for specified `ObjPool`.
//!
//! # Limitations:
//!
//! * `ObjId` is always 32-bit long.
//!
//! # Debug-only misuse detection
//!
//! In debug builds every pool mixes a random pool-specific offset into the `ObjId`s it issues.
//! An `ObjId` used with a different pool than the one that created it then decodes to a vacant
//! or out-of-bounds slot with overwhelming probability, so the lookup returns `None` (or panics
//! when indexing) instead of silently returning an unrelated object. Release builds skip the
//! masking entirely: an `ObjId` is just the slot index plus one.
//!
//! # Examples
//!
//! Some data structures built using `ObjPool<T>`:
//!
//! * [Doubly linked list](https://github.com/artemshein/obj-pool/blob/master/examples/linked_list.rs)
//! * [Splay tree](https://github.com/artemshein/obj-pool/blob/master/examples/splay_tree.rs)
use std::{
    fmt,
    hint::unreachable_unchecked,
    iter, mem,
    num::{NonZeroU32, ParseIntError},
    ops::{Index, IndexMut},
    ptr,
    str::FromStr,
    vec,
};

use std::ops::Deref;
use std::slice;

#[cfg(feature = "serde_support")]
use serde::{Deserialize, Serialize};

mod par;
pub use par::*;

/// A slot, which is either vacant or occupied.
///
/// Vacant slots in object pool are linked together into a singly linked list. This allows the object pool to
/// efficiently find a vacant slot before inserting a new object, or reclaiming a slot after
/// removing an object.
#[derive(Clone)]
enum Slot<T> {
    /// Vacant slot, containing index to the next slot in the linked list.
    Vacant(u32),

    /// Occupied slot, containing a value.
    Occupied(T),
}

/// An id of the object in an `ObjPool`.
///
/// In release builds it is basically just an index in the underlying vector (plus one). In debug
/// builds every pool additionally mixes a random pool-specific offset into each `ObjId` it
/// issues, so an `ObjId` created by one pool is (with overwhelming probability) rejected when
/// used with another pool instead of silently aliasing an unrelated object.
#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
pub struct ObjId(pub NonZeroU32);

impl ObjId {
    /// Creates an `ObjId` from a raw index, without any pool-specific masking.
    ///
    /// Note: in debug builds every pool mixes a random pool-specific offset into the ids it
    /// issues, so to create an id valid for a particular pool use
    /// [`ObjPool::index_to_obj_id`] instead.
    pub fn from_index(index: u32) -> Self {
        debug_assert!(index < u32::MAX, "index out of range");
        // SAFETY: index + 1 is non-zero for any index < u32::MAX, which the
        // debug assertion above guarantees. Using unchecked here makes the
        // function side-effect-free in release builds so the compiler can
        // eliminate ObjId construction when the result is unused (e.g. in
        // iterator benchmarks that discard the key with `_`).
        Self(unsafe { NonZeroU32::new_unchecked(index + 1) })
    }

    /// Converts the `ObjId` into a raw index, without any pool-specific unmasking.
    ///
    /// Note: in debug builds every pool mixes a random pool-specific offset into the ids it
    /// issues, so to get the slot index of an id use [`ObjPool::obj_id_to_index`] instead.
    pub const fn into_index(self) -> u32 {
        self.0.get() - 1
    }
}

impl std::fmt::Display for ObjId {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        self.0.fmt(f)
    }
}

impl FromStr for ObjId {
    type Err = ParseIntError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Ok(ObjId(s.parse::<NonZeroU32>()?))
    }
}

impl Deref for ObjId {
    type Target = NonZeroU32;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl From<NonZeroU32> for ObjId {
    fn from(v: NonZeroU32) -> ObjId {
        ObjId(v)
    }
}

/// Debug-only random per-pool offset which is mixed into every `ObjId` a pool issues.
///
/// An `ObjId` is rotated by the offset within the `NonZeroU32` value domain `[1, u32::MAX]`,
/// so an id of one pool decodes to an (almost certainly out-of-bounds or vacant) garbage index
/// in any other pool instead of silently aliasing an unrelated object. In release builds this
/// is a zero-sized no-op.
#[derive(Clone, Copy)]
pub(crate) struct PoolTag {
    #[cfg(debug_assertions)]
    offset: u32,
}

impl PoolTag {
    /// A tag with no offset assigned yet; ids pass through unchanged.
    pub(crate) const fn empty() -> Self {
        PoolTag {
            #[cfg(debug_assertions)]
            offset: 0,
        }
    }

    /// A tag with a random offset already assigned (in debug builds).
    pub(crate) fn random() -> Self {
        let mut tag = Self::empty();
        tag.randomize();
        tag
    }

    /// Assigns a random offset if none is assigned yet (in debug builds).
    #[inline]
    pub(crate) fn randomize(&mut self) {
        #[cfg(debug_assertions)]
        if self.offset == 0 {
            self.offset = random_offset();
        }
    }

    /// Mixes the pool offset into a raw `ObjId`.
    #[inline]
    pub(crate) fn mask_id(self, obj_id: ObjId) -> ObjId {
        #[cfg(debug_assertions)]
        return ObjId(rotate_id(obj_id.0, self.offset as u64));
        #[cfg(not(debug_assertions))]
        obj_id
    }

    /// Removes the pool offset from an external `ObjId`.
    #[inline]
    pub(crate) fn unmask_id(self, obj_id: ObjId) -> ObjId {
        #[cfg(debug_assertions)]
        return ObjId(rotate_id(obj_id.0, ID_DOMAIN - self.offset as u64));
        #[cfg(not(debug_assertions))]
        obj_id
    }
}

/// Size of the `NonZeroU32` value domain `[1, u32::MAX]` an `ObjId` lives in.
#[cfg(debug_assertions)]
const ID_DOMAIN: u64 = u32::MAX as u64;

/// Rotates `value` by `offset` positions within the `NonZeroU32` value domain. This is a
/// bijection on `[1, u32::MAX]` for any fixed `offset <= ID_DOMAIN`, and rotating back is
/// rotating by `ID_DOMAIN - offset`.
#[cfg(debug_assertions)]
fn rotate_id(value: NonZeroU32, offset: u64) -> NonZeroU32 {
    let rotated = ((value.get() as u64 - 1) + offset) % ID_DOMAIN;
    NonZeroU32::new(rotated as u32 + 1).expect("rotation preserves non-zero")
}

/// Returns a random per-pool offset in `[1, u32::MAX - 1]`, so that it is never zero (the
/// "not assigned yet" sentinel) and never a multiple of `ID_DOMAIN` (an identity rotation).
#[cfg(debug_assertions)]
fn random_offset() -> u32 {
    use std::collections::hash_map::RandomState;
    use std::hash::{BuildHasher, Hasher};
    let random = RandomState::new().build_hasher().finish() as u32;
    1 + random % (u32::MAX - 1)
}

/// An object pool.
///
/// `ObjPool<T>` holds an array of slots for storing objects.
/// Every slot is always in one of two states: occupied or vacant.
///
/// Essentially, this is equivalent to `Vec<Option<T>>`.
///
/// # Insert and remove
///
/// When inserting a new object into object pool, a vacant slot is found and then the object is placed
/// into the slot. If there are no vacant slots, the array is reallocated with bigger capacity.
/// The cost of insertion is amortized `O(1)`.
///
/// When removing an object, the slot containing it is marked as vacant and the object is returned.
/// The cost of removal is `O(1)`.
///
/// ```
/// use obj_pool::ObjPool;
///
/// let mut obj_pool = ObjPool::new();
/// let a = obj_pool.insert(10);
/// assert_eq!(obj_pool.obj_id_to_index(a), 0);
/// let b = obj_pool.insert(20);
/// assert_eq!(obj_pool.obj_id_to_index(b), 1);
///
/// assert_ne!(a, b); // ids are not the same
///
/// assert_eq!(obj_pool.remove(a), Some(10));
/// assert_eq!(obj_pool.get(a), None); // there is no object with this `ObjId` anymore
///
/// assert_eq!(obj_pool.insert(30), a); // slot is reused, got the same `ObjId`
/// ```
///
/// # Indexing
///
/// You can also access objects in an object pool by `ObjId`.
/// However, accessing an object with invalid `ObjId` will result in panic.
///
/// ```
/// use obj_pool::ObjPool;
///
/// let mut obj_pool = ObjPool::new();
/// let a = obj_pool.insert(10);
/// let b = obj_pool.insert(20);
///
/// assert_eq!(obj_pool[a], 10);
/// assert_eq!(obj_pool[b], 20);
///
/// obj_pool[a] += obj_pool[b];
/// assert_eq!(obj_pool[a], 30);
/// ```
///
/// To access slots without fear of panicking, use `get` and `get_mut`, which return `Option`s.
pub struct ObjPool<T> {
    /// Slots in which objects are stored.
    slots: Vec<Slot<T>>,

    /// Number of occupied slots in the object pool.
    len: u32,

    /// Index of the first vacant slot in the linked list.
    head: u32,

    /// Debug-only random tag mixed into every `ObjId` of this pool.
    tag: PoolTag,
}

impl<T> AsRef<ObjPool<T>> for ObjPool<T> {
    fn as_ref(&self) -> &ObjPool<T> {
        self
    }
}

impl<T> AsMut<ObjPool<T>> for ObjPool<T> {
    fn as_mut(&mut self) -> &mut ObjPool<T> {
        self
    }
}

impl<T> ObjPool<T> {
    /// Constructs a new, empty object pool.
    ///
    /// The object pool will not allocate until objects are inserted into it.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool: ObjPool<i32> = ObjPool::new();
    /// ```
    #[inline]
    pub const fn new() -> Self {
        ObjPool {
            slots: Vec::new(),
            len: 0,
            head: u32::MAX,
            // `new` is const, so the random tag is assigned lazily on the first insertion.
            tag: PoolTag::empty(),
        }
    }

    /// Get an index in the `ObjPool` for the given `ObjId`.
    ///
    /// In debug builds this removes the pool-specific random offset from the id, so the result
    /// is only meaningful for ids issued by this pool.
    #[inline]
    pub fn obj_id_to_index(&self, obj_id: ObjId) -> u32 {
        self.tag.unmask_id(obj_id).into_index()
    }

    /// Make an `ObjId` from an index in this `ObjPool`.
    ///
    /// In debug builds the id is masked with the pool-specific random offset. For a pool created
    /// with `ObjPool::new` the offset is assigned on the first insertion, so ids created before
    /// that are not valid afterwards.
    #[inline]
    pub fn index_to_obj_id(&self, index: u32) -> ObjId {
        self.tag.mask_id(ObjId::from_index(index))
    }

    /// Constructs a new, empty object pool with the specified capacity (number of slots).
    ///
    /// The object pool will be able to hold exactly `capacity` objects without reallocating.
    /// If `capacity` is 0, the object pool will not allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::with_capacity(10);
    ///
    /// assert_eq!(obj_pool.len(), 0);
    /// assert_eq!(obj_pool.capacity(), 10);
    ///
    /// // These inserts are done without reallocating...
    /// for i in 0..10 {
    ///     obj_pool.insert(i);
    /// }
    /// assert_eq!(obj_pool.capacity(), 10);
    ///
    /// // ... but this one will reallocate.
    /// obj_pool.insert(11);
    /// assert!(obj_pool.capacity() > 10);
    /// ```
    #[inline]
    pub fn with_capacity(cap: usize) -> Self {
        ObjPool {
            slots: Vec::with_capacity(cap),
            len: 0,
            head: u32::MAX,
            tag: PoolTag::random(),
        }
    }

    /// Returns the number of slots in the object pool.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let obj_pool: ObjPool<i32> = ObjPool::with_capacity(10);
    /// assert_eq!(obj_pool.capacity(), 10);
    /// ```
    #[inline]
    pub fn capacity(&self) -> usize {
        self.slots.capacity()
    }

    /// Returns the number of occupied slots in the object pool.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// assert_eq!(obj_pool.len(), 0);
    ///
    /// for i in 0..10 {
    ///     obj_pool.insert(());
    ///     assert_eq!(obj_pool.len(), i + 1);
    /// }
    /// ```
    #[inline]
    pub fn len(&self) -> u32 {
        self.len
    }

    /// Returns `true` if all slots are vacant.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// assert!(obj_pool.is_empty());
    ///
    /// obj_pool.insert(1);
    /// assert!(!obj_pool.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns the `ObjId` of the next inserted object if no other
    /// mutating calls take place in between.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    ///
    /// let a = obj_pool.next_vacant();
    /// let b = obj_pool.insert(1);
    /// assert_eq!(a, b);
    /// let c = obj_pool.next_vacant();
    /// let d = obj_pool.insert(2);
    /// assert_eq!(c, d);
    /// ```
    #[inline]
    pub fn next_vacant(&mut self) -> ObjId {
        self.tag.randomize();
        self.index_to_obj_id(if self.head == u32::MAX {
            self.len
        } else {
            self.head
        })
    }

    /// Inserts an object into the object pool and returns the `ObjId` of this object.
    /// The object pool will reallocate if it's full.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    ///
    /// let a = obj_pool.insert(1);
    /// let b = obj_pool.insert(2);
    /// assert!(a != b);
    /// ```
    pub fn insert(&mut self, object: T) -> ObjId {
        self.tag.randomize();
        self.len += 1;

        if self.head == u32::MAX {
            self.slots.push(Slot::Occupied(object));
            self.index_to_obj_id(self.len - 1)
        } else {
            let index = self.head;
            match self.slots[index as usize] {
                Slot::Vacant(next) => {
                    self.head = next;
                    self.slots[index as usize] = Slot::Occupied(object);
                }
                Slot::Occupied(_) => unreachable!(),
            }
            self.index_to_obj_id(index)
        }
    }

    /// Removes the object stored by `ObjId` from the object pool and returns it.
    ///
    /// `None` is returned in case the there is no object with such an `ObjId`.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// let a = obj_pool.insert("hello");
    ///
    /// assert_eq!(obj_pool.len(), 1);
    /// assert_eq!(obj_pool.remove(a), Some("hello"));
    ///
    /// assert_eq!(obj_pool.len(), 0);
    /// assert_eq!(obj_pool.remove(a), None);
    /// ```
    pub fn remove(&mut self, obj_id: ObjId) -> Option<T> {
        let index = self.obj_id_to_index(obj_id);
        match self.slots.get_mut(index as usize) {
            None => None,
            Some(&mut Slot::Vacant(_)) => None,
            Some(slot @ &mut Slot::Occupied(_)) => {
                if let Slot::Occupied(object) = mem::replace(slot, Slot::Vacant(self.head)) {
                    self.head = index;
                    self.len -= 1;
                    Some(object)
                } else {
                    unreachable!();
                }
            }
        }
    }

    /// Clears the object pool, removing and dropping all objects it holds, and releases the
    /// allocated memory.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// for i in 0..10 {
    ///     obj_pool.insert(i);
    /// }
    ///
    /// assert_eq!(obj_pool.len(), 10);
    /// obj_pool.clear();
    /// assert_eq!(obj_pool.len(), 0);
    /// assert_eq!(obj_pool.capacity(), 0);
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        self.slots.clear();
        self.slots.shrink_to_fit();
        self.len = 0;
        self.head = u32::MAX;
    }

    /// Returns a reference to the object by its `ObjId`.
    ///
    /// If object is not found with given `obj_id`, `None` is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// let obj_id = obj_pool.insert("hello");
    ///
    /// assert_eq!(obj_pool.get(obj_id), Some(&"hello"));
    /// obj_pool.remove(obj_id);
    /// assert_eq!(obj_pool.get(obj_id), None);
    /// ```
    pub fn get(&self, obj_id: ObjId) -> Option<&T> {
        let index = self.obj_id_to_index(obj_id) as usize;
        match self.slots.get(index) {
            None => None,
            Some(&Slot::Vacant(_)) => None,
            Some(Slot::Occupied(object)) => Some(object),
        }
    }

    /// Returns a mutable reference to the object by its `ObjId`.
    ///
    /// If object can't be found, `None` is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// let obj_id = obj_pool.insert(7);
    ///
    /// assert_eq!(obj_pool.get_mut(obj_id), Some(&mut 7));
    /// *obj_pool.get_mut(obj_id).unwrap() *= 10;
    /// assert_eq!(obj_pool.get_mut(obj_id), Some(&mut 70));
    /// ```
    #[inline]
    pub fn get_mut(&mut self, obj_id: ObjId) -> Option<&mut T> {
        let index = self.obj_id_to_index(obj_id) as usize;
        match self.slots.get_mut(index) {
            None => None,
            Some(&mut Slot::Vacant(_)) => None,
            Some(&mut Slot::Occupied(ref mut object)) => Some(object),
        }
    }

    /// Returns a reference to the object by its `ObjId`.
    ///
    /// # Safety
    ///
    /// Behavior is undefined if object can't be found.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// let obj_id = obj_pool.insert("hello");
    ///
    /// unsafe { assert_eq!(&*obj_pool.get_unchecked(obj_id), &"hello") }
    /// ```
    pub unsafe fn get_unchecked(&self, obj_id: ObjId) -> &T {
        match self.slots.get(self.obj_id_to_index(obj_id) as usize) {
            None => unsafe { unreachable_unchecked() },
            Some(Slot::Vacant(_)) => unsafe { unreachable_unchecked() },
            Some(Slot::Occupied(object)) => object,
        }
    }

    /// Returns a mutable reference to the object by its `ObjId`.
    ///
    /// # Safety
    ///
    /// Behavior is undefined if object can't be found.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// let obj_id = obj_pool.insert("hello");
    ///
    /// unsafe { assert_eq!(&*obj_pool.get_unchecked_mut(obj_id), &"hello") }
    /// ```
    pub unsafe fn get_unchecked_mut(&mut self, obj_id: ObjId) -> &mut T {
        let index = self.obj_id_to_index(obj_id) as usize;
        match self.slots.get_mut(index) {
            Some(&mut Slot::Vacant(_)) => unsafe { unreachable_unchecked() },
            Some(&mut Slot::Occupied(ref mut object)) => object,
            _ => unsafe { unreachable_unchecked() },
        }
    }

    /// Swaps two objects in the object pool.
    ///
    /// The two `ObjId`s are `a` and `b`.
    ///
    /// # Panics
    ///
    /// Panics if any of the `ObjId`s is invalid.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// let a = obj_pool.insert(7);
    /// let b = obj_pool.insert(8);
    ///
    /// obj_pool.swap(a, b);
    /// assert_eq!(obj_pool.get(a), Some(&8));
    /// assert_eq!(obj_pool.get(b), Some(&7));
    /// ```
    #[inline]
    pub fn swap(&mut self, a: ObjId, b: ObjId) {
        unsafe {
            let fst = self.get_mut(a).unwrap() as *mut _;
            let snd = self.get_mut(b).unwrap() as *mut _;
            if a != b {
                ptr::swap(fst, snd);
            }
        }
    }

    /// Reserves capacity for at least `additional` more objects to be inserted. The object pool may
    /// reserve more space to avoid frequent reallocations.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity overflows `u32`.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// obj_pool.insert("hello");
    ///
    /// obj_pool.reserve(10);
    /// assert!(obj_pool.capacity() >= 11);
    /// ```
    pub fn reserve(&mut self, additional: u32) {
        let vacant = self.slots.len() as u32 - self.len;
        if additional > vacant {
            self.slots.reserve((additional - vacant) as usize);
        }
    }

    /// Reserves the minimum capacity for exactly `additional` more objects to be inserted.
    ///
    /// Note that the allocator may give the object pool more space than it requests.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity overflows `u32`.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// obj_pool.insert("hello");
    ///
    /// obj_pool.reserve_exact(10);
    /// assert!(obj_pool.capacity() >= 11);
    /// ```
    pub fn reserve_exact(&mut self, additional: u32) {
        let vacant = self.slots.len() as u32 - self.len;
        if additional > vacant {
            self.slots.reserve_exact((additional - vacant) as usize);
        }
    }

    /// Returns an iterator over occupied slots.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// obj_pool.insert(1);
    /// obj_pool.insert(2);
    /// obj_pool.insert(4);
    ///
    /// let mut iterator = obj_pool.iter();
    /// assert_eq!(iterator.next(), Some((obj_pool.index_to_obj_id(0), &1)));
    /// assert_eq!(iterator.next(), Some((obj_pool.index_to_obj_id(1), &2)));
    /// assert_eq!(iterator.next(), Some((obj_pool.index_to_obj_id(2), &4)));
    /// ```
    #[inline]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            len: self.len as usize,
            slots: self.slots.iter().enumerate(),
            tag: self.tag,
        }
    }

    /// Returns an iterator that returns mutable references to objects.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::new();
    /// let a = obj_pool.insert("zero".to_string());
    /// obj_pool.insert("one".to_string());
    /// obj_pool.insert("two".to_string());
    ///
    /// for (obj_id, object) in obj_pool.iter_mut() {
    ///     if obj_id == a {
    ///         *object += "!";
    ///     } else {
    ///         *object += "?";
    ///     }
    /// }
    ///
    /// let mut iterator = obj_pool.iter();
    /// assert_eq!(iterator.next(), Some((obj_pool.index_to_obj_id(0), &"zero!".to_string())));
    /// assert_eq!(iterator.next(), Some((obj_pool.index_to_obj_id(1), &"one?".to_string())));
    /// assert_eq!(iterator.next(), Some((obj_pool.index_to_obj_id(2), &"two?".to_string())));
    /// ```
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            len: self.len as usize,
            slots: self.slots.iter_mut().enumerate(),
            tag: self.tag,
        }
    }

    /// Shrinks the capacity of the object pool as much as possible.
    ///
    /// It will drop down as close as possible to the length but the allocator may still inform
    /// the object pool that there is space for a few more elements.
    ///
    /// # Examples
    ///
    /// ```
    /// use obj_pool::ObjPool;
    ///
    /// let mut obj_pool = ObjPool::with_capacity(10);
    /// obj_pool.insert("first".to_string());
    /// obj_pool.insert("second".to_string());
    /// obj_pool.insert("third".to_string());
    /// assert_eq!(obj_pool.capacity(), 10);
    /// obj_pool.shrink_to_fit();
    /// assert!(obj_pool.capacity() >= 3);
    /// ```
    pub fn shrink_to_fit(&mut self) {
        self.slots.shrink_to_fit();
    }
}

impl<T> fmt::Debug for ObjPool<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "ObjPool {{ ... }}")
    }
}

impl<T> Index<ObjId> for ObjPool<T> {
    type Output = T;

    #[inline]
    fn index(&self, obj_id: ObjId) -> &T {
        self.get(obj_id).expect("object not found")
    }
}

impl<T> IndexMut<ObjId> for ObjPool<T> {
    #[inline]
    fn index_mut(&mut self, obj_id: ObjId) -> &mut T {
        self.get_mut(obj_id).expect("object not found")
    }
}

impl<T> Default for ObjPool<T> {
    fn default() -> Self {
        ObjPool::new()
    }
}

impl<T: Clone> Clone for ObjPool<T> {
    fn clone(&self) -> Self {
        ObjPool {
            slots: self.slots.clone(),
            len: self.len,
            head: self.head,
            // The clone keeps the tag, so ids issued by the original pool stay valid for it.
            tag: self.tag,
        }
    }
}

/// An iterator over the occupied slots in a `ObjPool`.
pub struct IntoIter<T> {
    slots: iter::Enumerate<vec::IntoIter<Slot<T>>>,
    len: usize,
    tag: PoolTag,
}

impl<T> Iterator for IntoIter<T> {
    type Item = (ObjId, T);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        for (index, slot) in self.slots.by_ref() {
            if let Slot::Occupied(object) = slot {
                self.len -= 1;
                return Some((self.tag.mask_id(ObjId::from_index(index as u32)), object));
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<T> ExactSizeIterator for IntoIter<T> {
    fn len(&self) -> usize {
        self.len
    }
}

impl<T> iter::FusedIterator for IntoIter<T> {}

impl<T> IntoIterator for ObjPool<T> {
    type Item = (ObjId, T);
    type IntoIter = IntoIter<T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            len: self.len as usize,
            tag: self.tag,
            slots: self.slots.into_iter().enumerate(),
        }
    }
}

impl<T> iter::FromIterator<T> for ObjPool<T> {
    fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> ObjPool<T> {
        let iter = iter.into_iter();
        let mut obj_pool = ObjPool::with_capacity(iter.size_hint().0);
        for i in iter {
            obj_pool.insert(i);
        }
        obj_pool
    }
}

impl<T> fmt::Debug for IntoIter<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "IntoIter {{ ... }}")
    }
}

/// An iterator over references to the occupied slots in a `ObjPool`.
pub struct Iter<'a, T: 'a> {
    slots: iter::Enumerate<slice::Iter<'a, Slot<T>>>,
    len: usize,
    tag: PoolTag,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = (ObjId, &'a T);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        for (index, slot) in self.slots.by_ref() {
            if let Slot::Occupied(ref object) = *slot {
                self.len -= 1;
                return Some((self.tag.mask_id(ObjId::from_index(index as u32)), object));
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<T> ExactSizeIterator for Iter<'_, T> {
    fn len(&self) -> usize {
        self.len
    }
}

impl<T> iter::FusedIterator for Iter<'_, T> {}

impl<'a, T> IntoIterator for &'a ObjPool<T> {
    type Item = (ObjId, &'a T);
    type IntoIter = Iter<'a, T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T> fmt::Debug for Iter<'a, T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Iter {{ ... }}")
    }
}

/// An iterator over mutable references to the occupied slots in a `Arena`.
pub struct IterMut<'a, T: 'a> {
    slots: iter::Enumerate<slice::IterMut<'a, Slot<T>>>,
    len: usize,
    tag: PoolTag,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = (ObjId, &'a mut T);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        for (index, slot) in self.slots.by_ref() {
            if let Slot::Occupied(ref mut object) = *slot {
                self.len -= 1;
                return Some((self.tag.mask_id(ObjId::from_index(index as u32)), object));
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }
}

impl<T> ExactSizeIterator for IterMut<'_, T> {
    fn len(&self) -> usize {
        self.len
    }
}

impl<T> iter::FusedIterator for IterMut<'_, T> {}

impl<'a, T> IntoIterator for &'a mut ObjPool<T> {
    type Item = (ObjId, &'a mut T);
    type IntoIter = IterMut<'a, T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<'a, T> fmt::Debug for IterMut<'a, T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "IterMut {{ ... }}")
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn new() {
        let obj_pool = ObjPool::<i32>::new();
        assert!(obj_pool.is_empty());
        assert_eq!(obj_pool.len(), 0);
        assert_eq!(obj_pool.capacity(), 0);
    }

    #[test]
    fn insert() {
        let mut obj_pool = ObjPool::new();

        for i in 0..10 {
            let a = obj_pool.insert(i * 10);
            assert_eq!(obj_pool[a], i * 10);
        }
        assert!(!obj_pool.is_empty());
        assert_eq!(obj_pool.len(), 10);
    }

    #[test]
    fn with_capacity() {
        let mut obj_pool = ObjPool::with_capacity(10);
        assert_eq!(obj_pool.capacity(), 10);

        for _ in 0..10 {
            obj_pool.insert(());
        }
        assert_eq!(obj_pool.len(), 10);
        assert_eq!(obj_pool.capacity(), 10);

        obj_pool.insert(());
        assert_eq!(obj_pool.len(), 11);
        assert!(obj_pool.capacity() > 10);
    }

    #[test]
    fn remove() {
        let mut obj_pool = ObjPool::new();

        let a = obj_pool.insert(0);
        let b = obj_pool.insert(10);
        let c = obj_pool.insert(20);
        obj_pool.insert(30);
        assert_eq!(obj_pool.len(), 4);

        assert_eq!(obj_pool.remove(b), Some(10));
        assert_eq!(obj_pool.remove(c), Some(20));
        assert_eq!(obj_pool.len(), 2);

        obj_pool.insert(-1);
        obj_pool.insert(-1);
        assert_eq!(obj_pool.len(), 4);

        assert_eq!(obj_pool.remove(a), Some(0));
        obj_pool.insert(-1);
        assert_eq!(obj_pool.len(), 4);

        obj_pool.insert(400);
        assert_eq!(obj_pool.len(), 5);
    }

    #[test]
    fn clear() {
        let mut obj_pool = ObjPool::new();
        obj_pool.insert(10);
        obj_pool.insert(20);

        assert!(!obj_pool.is_empty());
        assert_eq!(obj_pool.len(), 2);

        obj_pool.clear();

        assert!(obj_pool.is_empty());
        assert_eq!(obj_pool.len(), 0);
        assert_eq!(obj_pool.capacity(), 0);
    }

    #[test]
    fn indexing() {
        let mut obj_pool = ObjPool::new();

        let a = obj_pool.insert(10);
        let b = obj_pool.insert(20);
        let c = obj_pool.insert(30);

        obj_pool[b] += obj_pool[c];
        assert_eq!(obj_pool[a], 10);
        assert_eq!(obj_pool[b], 50);
        assert_eq!(obj_pool[c], 30);
    }

    #[test]
    #[should_panic]
    fn indexing_vacant() {
        let mut obj_pool = ObjPool::new();

        let _ = obj_pool.insert(10);
        let b = obj_pool.insert(20);
        let _ = obj_pool.insert(30);

        obj_pool.remove(b);
        obj_pool[b];
    }

    #[test]
    #[should_panic]
    fn invalid_indexing() {
        let mut obj_pool = ObjPool::new();

        obj_pool.insert(10);
        obj_pool.insert(20);
        let a = obj_pool.insert(30);
        obj_pool.remove(a);

        obj_pool[a];
    }

    #[test]
    fn get() {
        let mut obj_pool = ObjPool::new();

        let a = obj_pool.insert(10);
        let b = obj_pool.insert(20);
        let c = obj_pool.insert(30);

        *obj_pool.get_mut(b).unwrap() += *obj_pool.get(c).unwrap();
        assert_eq!(obj_pool.get(a), Some(&10));
        assert_eq!(obj_pool.get(b), Some(&50));
        assert_eq!(obj_pool.get(c), Some(&30));

        obj_pool.remove(b);
        assert_eq!(obj_pool.get(b), None);
        assert_eq!(obj_pool.get_mut(b), None);
    }

    #[test]
    fn reserve() {
        let mut obj_pool = ObjPool::new();
        obj_pool.insert(1);
        obj_pool.insert(2);

        obj_pool.reserve(10);
        assert!(obj_pool.capacity() >= 11);
    }

    #[test]
    fn reserve_exact() {
        let mut obj_pool = ObjPool::new();
        obj_pool.insert(1);
        obj_pool.insert(2);
        obj_pool.reserve(10);
        assert!(obj_pool.capacity() >= 11);
    }

    #[test]
    fn iter() {
        let mut arena = ObjPool::new();
        let a = arena.insert(10);
        let b = arena.insert(20);
        let c = arena.insert(30);
        let d = arena.insert(40);

        arena.remove(b);

        let mut it = arena.iter();
        assert_eq!(it.next(), Some((a, &10)));
        assert_eq!(it.next(), Some((c, &30)));
        assert_eq!(it.next(), Some((d, &40)));
        assert_eq!(it.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(10);
        let b = obj_pool.insert(20);
        let c = obj_pool.insert(30);
        let d = obj_pool.insert(40);

        obj_pool.remove(b);

        {
            let mut it = obj_pool.iter_mut();
            assert_eq!(it.next(), Some((a, &mut 10)));
            assert_eq!(it.next(), Some((c, &mut 30)));
            assert_eq!(it.next(), Some((d, &mut 40)));
            assert_eq!(it.next(), None);
        }

        for (obj_id, value) in &mut obj_pool {
            *value += obj_id.get();
        }

        let mut it = obj_pool.iter_mut();
        assert_eq!(*it.next().unwrap().1, 10 + a.get());
        assert_eq!(*it.next().unwrap().1, 30 + c.get());
        assert_eq!(*it.next().unwrap().1, 40 + d.get());
        assert_eq!(it.next(), None);
    }

    #[test]
    fn from_iter() {
        let obj_pool: ObjPool<usize> = [10, 20, 30, 40].iter().cloned().collect();

        let mut it = obj_pool.iter();
        assert_eq!(it.next(), Some((obj_pool.index_to_obj_id(0), &10)));
        assert_eq!(it.next(), Some((obj_pool.index_to_obj_id(1), &20)));
        assert_eq!(it.next(), Some((obj_pool.index_to_obj_id(2), &30)));
        assert_eq!(it.next(), Some((obj_pool.index_to_obj_id(3), &40)));
        assert_eq!(it.next(), None);
    }

    #[test]
    fn obj_id_index_round_trip() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(10);
        let b = obj_pool.insert(20);

        assert_eq!(obj_pool.obj_id_to_index(a), 0);
        assert_eq!(obj_pool.obj_id_to_index(b), 1);
        assert_eq!(obj_pool.index_to_obj_id(0), a);
        assert_eq!(obj_pool.index_to_obj_id(1), b);
    }

    #[cfg(debug_assertions)]
    #[test]
    fn foreign_obj_id_is_rejected() {
        let mut a = ObjPool::new();
        let id = a.insert(10);

        let mut b = ObjPool::new();
        b.insert(20);
        // Make sure the pools did not roll the same random offset, so the check
        // below is deterministic: `id` unmasks in `b` to a non-zero index, which
        // is out of bounds for a pool with a single slot.
        while b.tag.offset == a.tag.offset {
            b = ObjPool::new();
            b.insert(20);
        }

        assert_eq!(b.get(id), None);
        assert_eq!(b.get_mut(id), None);
        assert_eq!(b.remove(id), None);
        assert_eq!(b.get(b.index_to_obj_id(0)), Some(&20));
    }

    #[test]
    fn free_list_is_lifo() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(1);
        let b = obj_pool.insert(2);
        let c = obj_pool.insert(3);

        obj_pool.remove(a);
        obj_pool.remove(c);

        // Vacant slots are reused most-recently-removed first.
        assert_eq!(obj_pool.next_vacant(), c);
        assert_eq!(obj_pool.insert(30), c);
        assert_eq!(obj_pool.next_vacant(), a);
        assert_eq!(obj_pool.insert(10), a);

        // No vacant slots left: the next insert appends.
        let next = obj_pool.next_vacant();
        assert_eq!(obj_pool.obj_id_to_index(next), 3);
        assert_eq!(obj_pool.insert(4), next);
        assert_eq!(obj_pool.len(), 4);
        assert_eq!(obj_pool.get(b), Some(&2));
    }

    #[test]
    fn unknown_id_is_not_found() {
        let mut obj_pool = ObjPool::new();
        obj_pool.insert(1);

        let unknown = obj_pool.index_to_obj_id(100);
        assert_eq!(obj_pool.get(unknown), None);
        assert_eq!(obj_pool.get_mut(unknown), None);
        assert_eq!(obj_pool.remove(unknown), None);
        assert_eq!(obj_pool.len(), 1);
    }

    #[test]
    fn clear_then_insert_reuses_ids() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(1);
        obj_pool.insert(2);
        obj_pool.clear();

        // Stale ids decode out of bounds after a clear.
        assert_eq!(obj_pool.get(a), None);
        assert_eq!(obj_pool.remove(a), None);

        // The pool keeps its tag, so freshly inserted objects get the same ids again.
        let b = obj_pool.insert(3);
        assert_eq!(b, a);
        assert_eq!(obj_pool.get(b), Some(&3));
        assert_eq!(obj_pool.len(), 1);
    }

    #[test]
    fn into_iter_skips_vacant() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(10);
        let b = obj_pool.insert(20);
        let c = obj_pool.insert(30);
        obj_pool.remove(b);

        let items: Vec<_> = obj_pool.into_iter().collect();
        assert_eq!(items, [(a, 10), (c, 30)]);
    }

    #[test]
    fn iterate_with_vacant_ends() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(10);
        let b = obj_pool.insert(20);
        let c = obj_pool.insert(30);
        obj_pool.remove(a);
        obj_pool.remove(c);

        let items: Vec<_> = obj_pool.iter().map(|(k, &v)| (k, v)).collect();
        assert_eq!(items, [(b, 20)]);
    }

    #[test]
    fn iterate_empty_and_fully_vacant() {
        let mut obj_pool: ObjPool<i32> = ObjPool::new();
        assert_eq!(obj_pool.iter().next(), None);
        assert_eq!(obj_pool.iter().size_hint(), (0, Some(0)));

        let keys: Vec<_> = (0..4).map(|v| obj_pool.insert(v)).collect();
        for k in keys {
            obj_pool.remove(k);
        }
        assert!(obj_pool.is_empty());
        assert_eq!(obj_pool.iter().size_hint(), (0, Some(0)));
        assert_eq!(obj_pool.iter().next(), None);
        assert_eq!(obj_pool.iter_mut().next(), None);
        assert_eq!(obj_pool.into_iter().next(), None);
    }

    #[test]
    fn iterator_len_and_fuse() {
        let mut obj_pool = ObjPool::new();
        obj_pool.insert(10);
        let b = obj_pool.insert(20);
        obj_pool.insert(30);
        obj_pool.remove(b);

        let mut it = obj_pool.iter();
        assert_eq!(it.len(), 2);
        assert_eq!(it.size_hint(), (2, Some(2)));
        it.next();
        assert_eq!(it.len(), 1);
        it.next();
        assert_eq!(it.len(), 0);
        assert_eq!(it.next(), None);
        // Fused: keeps returning `None` after the end.
        assert_eq!(it.next(), None);

        let mut it = obj_pool.iter_mut();
        assert_eq!(it.len(), 2);
        it.next();
        assert_eq!(it.size_hint(), (1, Some(1)));

        let mut it = obj_pool.into_iter();
        assert_eq!(it.len(), 2);
        it.next();
        assert_eq!(it.len(), 1);
    }

    #[test]
    fn clone_preserves_ids_and_free_list() {
        let mut original = ObjPool::new();
        let a = original.insert(1);
        let b = original.insert(2);
        let c = original.insert(3);
        original.remove(b);

        let mut clone = original.clone();
        // Ids issued by the original resolve to the same objects in the clone.
        assert_eq!(clone.get(a), Some(&1));
        assert_eq!(clone.get(b), None);
        assert_eq!(clone.get(c), Some(&3));
        assert_eq!(clone.len(), original.len());

        // The free list is cloned too: both pools reuse the same vacant slot,
        // then append, issuing equal ids.
        assert_eq!(clone.insert(20), original.insert(20));
        assert_eq!(clone.insert(4), original.insert(4));
    }

    #[test]
    fn swap_with_itself() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(7);
        obj_pool.swap(a, a);
        assert_eq!(obj_pool.get(a), Some(&7));
    }

    #[test]
    #[should_panic]
    fn swap_removed_id_panics() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(1);
        let b = obj_pool.insert(2);
        obj_pool.remove(b);
        obj_pool.swap(a, b);
    }

    #[test]
    fn reserve_accounts_for_vacant_slots() {
        let mut obj_pool = ObjPool::with_capacity(2);
        let a = obj_pool.insert(1);
        obj_pool.insert(2);
        obj_pool.remove(a);

        // One slot is vacant, so reserving room for one object needs no new memory.
        obj_pool.reserve(1);
        assert_eq!(obj_pool.capacity(), 2);
        obj_pool.reserve_exact(1);
        assert_eq!(obj_pool.capacity(), 2);
    }

    #[test]
    fn obj_id_display_from_str_round_trip() {
        let mut obj_pool = ObjPool::new();
        let a = obj_pool.insert(7);

        let parsed: ObjId = a.to_string().parse().unwrap();
        assert_eq!(parsed, a);
        assert_eq!(obj_pool.get(parsed), Some(&7));

        assert!("0".parse::<ObjId>().is_err());
        assert!("".parse::<ObjId>().is_err());
        assert!("abc".parse::<ObjId>().is_err());
        assert!("4294967296".parse::<ObjId>().is_err()); // u32::MAX + 1
    }

    #[test]
    fn obj_id_raw_round_trip() {
        for index in [0, 1, 42, u32::MAX - 1] {
            assert_eq!(ObjId::from_index(index).into_index(), index);
        }
    }

    #[cfg(debug_assertions)]
    #[test]
    #[should_panic(expected = "index out of range")]
    fn from_index_max_panics_in_debug() {
        let _ = ObjId::from_index(u32::MAX);
    }
}