idcontain/

slab.rs

use super::id::{Id, IdIndex, IdTag, MAXIMUM_CAPACITY};
use rand::{self, Rng};
use std::marker::PhantomData;
use std::mem;
use std::ops::{Index, IndexMut};
use std::slice::{Iter as SliceIter, IterMut as SliceIterMut};

/// An `IdSlab` stores an unordered collection of elements with fast access by opaque `Id`-s.
///
/// Inserting an element returns an `Id` which may later be used for lookup and deletion. It
/// supports O(1) insertion, deletion and id-lookup. Ordering is unstable when elements are
/// added and removed.
///
/// The maximum number of elements which can be stored in an `IdSlab` is `MAXIMUM_CAPACITY`
/// (currently 2^32). This keeps `Id`-s at 64bits. A future version may support custom types for
/// the `Id`-s making the capacity-id-size trade-off customisable.
///
/// Example
/// ---
/// ```
/// use idcontain::{IdSlab, Id};
///
/// let mut id_slab: IdSlab<&'static str> = IdSlab::new();
///
/// // The `Id` type encodes the type of the value, to statically prevent errors caused by mixing
/// // id-s.
/// let hello_id: Id<&'static str> = id_slab.insert("hello");
/// let world_id = id_slab.insert("world");
///
/// assert_eq!(id_slab[hello_id], "hello");
/// assert_eq!(id_slab[world_id], "world");
///
/// assert_eq!(id_slab.remove(world_id), Some("world"));  // The value is returned on deletion.
/// assert!(!id_slab.contains(world_id));
///
/// // New id-s are different from previous ones, even though the memory is reused.
/// let new_world_id = id_slab.insert("new world");
/// assert!(new_world_id != world_id);
/// ```
///
/// Id Reuse
/// ---
/// Removing an `Id` will cause future lookups with that `Id` to fail (either returning `None` for
/// `get` and `remove`, or panicking for indexing), but this feature is 'best-effort' and should
/// not be relied on for memory safety or security.
///
/// In particular removing and adding an element 2^32 times will cause that `Id` to be reused. This
/// is, for most workloads unlikely and is made even less likely when operations are more mixed
/// (adding more elements and removing them in between).
///
///
/// Id Mixing
/// ---
/// Using an `Id` from a different `IdSlab` will fail at compile time, unless both `IdSlab`-s are of
/// the same type. You are encouraged to newtype liberally to make leverage this as much as
/// possible.
///
/// When using `Id`-s of the same type, lookups are still most likely going to fail at runtime:
///
/// ```
/// # use idcontain::IdSlab;
/// let mut id_slab_1 = IdSlab::new();
/// let id1 = id_slab_1.insert(1);
///
/// let mut id_slab_2 = IdSlab::new();
/// let id2 = id_slab_2.insert(1);
///
/// assert!(id1 != id2);
/// assert!(!id_slab_1.contains(id2));
/// assert!(!id_slab_2.contains(id1));
/// ```
///
/// The mechanism behind this is built on the same tagging mechanism used for preventing `Id` reuse
/// of the same `IdSlab`. As such, this feature is also best-effort and should not be used for
/// memory safety or security.
///
/// For all other situations, it's probably fine. The probability curve follows the birthday
/// paradox equation with `m=2^32 / avg_num_elements_per_id_slab` and `n=num_id_slabs`. So, for
/// instance, 10 `IdSlab`-s with 1000 elements each, gives a collision probability of about
/// `(n^2/2m) = 0.001%` or 1 in 100,000.
#[derive(Clone, Debug)]
pub struct IdSlab<T> {
    slots: Vec<TaggedSlot<T>>,
    first_free: IdIndex,
    seed_tag: IdTag,
    len: usize,
}

impl<T> IdSlab<T> {
    /// Creates a new `IdSlab` with zero capacity.
    ///
    /// The first insertion will cause an allocation.
    pub fn new() -> Self {
        Self::with_capacity(0)
    }

    /// Creates a new `IdSlab` with a given capacity.
    ///
    /// As long as number of elements stays under this capacity, no re-allocation will be
    /// triggered.
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_and_seed_tag(capacity, default_seed_tag())
    }

    /// Creates a new `IdSlab` with a given capacity and seed tag.
    ///
    /// This is an advanced feature which may cause more `Id` collisions between your `IdSlab`-s if
    /// used incorrectly.
    ///
    /// The `seed_tag` of an `IdSlab` is the tag assigned to new slots. Removing elements increments
    /// this tag and wraps around, providing the mechanism for `Id` reuse prevention and `Id`
    /// mixing detection.
    ///
    /// The `new` and `with_capacity` constructors set the seed tag to a random number, but better
    /// strategies exist for preventing collisions if you know your workload.
    pub fn with_capacity_and_seed_tag(capacity: usize, seed_tag: IdTag) -> Self {
        assert!(capacity <= MAXIMUM_CAPACITY);

        IdSlab {
            slots: if capacity == 0 {
                Vec::new()
            } else {
                Vec::with_capacity(capacity)
            },
            first_free: 0,
            seed_tag: seed_tag,
            len: 0,
        }
    }

    /// Returns the number of elements in the `IdSlab`.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// assert_eq!(id_slab.len(), 0);
    ///
    /// let id = id_slab.insert(1);
    /// assert_eq!(id_slab.len(), 1);
    ///
    /// id_slab.remove(id);
    /// assert_eq!(id_slab.len(), 0);
    /// ```
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns true if the slab is empty.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// assert!(id_slab.is_empty());
    ///
    /// let id = id_slab.insert(1);
    /// assert!(!id_slab.is_empty());
    ///
    /// id_slab.remove(id);
    /// assert!(id_slab.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns `true` if there exists an element with the given `Id`.
    ///
    /// See struct-level docs for caveats about `Id` reuse and mixing (almost always fine, but
    /// `contains` may give you false positives in pathological cases so don't rely on it for
    /// memory safety or security).
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// assert_eq!(id_slab.len(), 0);
    ///
    /// let id = id_slab.insert(1);
    /// assert!(id_slab.contains(id));
    ///
    /// id_slab.remove(id);
    /// assert!(!id_slab.contains(id));
    /// ```
    pub fn contains(&self, id: Id<T>) -> bool {
        match self.slots.get(id.index as usize) {
            Some(&TaggedSlot {
                slot: Slot::Occupied { .. },
                tag,
            }) if tag == id.tag => true,
            _ => false,
        }
    }

    /// Returns a reference to an element by `Id` or `None` if it doesn't exist.
    ///
    /// Use indexing for a panicking version of this operation.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// let id = id_slab.insert(1);
    ///
    /// assert_eq!(id_slab.get(id), Some(&1));
    ///
    /// id_slab.remove(id);
    /// assert_eq!(id_slab.get(id), None);
    /// ```
    pub fn get(&self, id: Id<T>) -> Option<&T> {
        self.get_or_tagged_slot(id).ok()
    }

    /// Returns a mutable reference to an element by `Id` or `None` if it doesn't exist.
    ///
    /// Use indexing for a panicking version of this operation.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// let id = id_slab.insert(1);
    ///
    /// *id_slab.get_mut(id).unwrap() = 10;
    /// assert_eq!(id_slab[id], 10);
    ///
    /// id_slab.remove(id);
    /// assert_eq!(id_slab.get_mut(id), None);
    /// ```
    pub fn get_mut(&mut self, id: Id<T>) -> Option<&mut T> {
        self.get_mut_or_tagged_slot(id).ok()
    }

    /// Inserts a new element into the `IdSlab`, returning its `Id<T>`.
    ///
    /// In general the `Id`-s do not get reused and should not collide with other `IdSlab`-s, but
    /// caveats apply, see the struct-level doc for more details.
    ///
    /// Panics
    /// ---
    /// If `self.len() == MAXIMUM_CAPACITY`.
    ///
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// let id1 = id_slab.insert(1);
    /// let id2 = id_slab.insert(2);
    ///
    /// assert_eq!(id_slab[id1], 1);
    /// assert_eq!(id_slab[id2], 2);
    ///
    /// // Id-s are not (caveats apply) shared between `IdSlab`-s.
    /// let mut new_id_slab = IdSlab::new();
    /// let new_id1 = new_id_slab.insert(1);
    /// assert!(new_id1 != id1);
    ///
    /// // Id-s are not (caveats apply) reused.
    /// id_slab.remove(id1);
    /// let id3 = id_slab.insert(3);
    /// assert!(id3 != id1);
    /// ```
    pub fn insert(&mut self, value: T) -> Id<T> {
        assert!(self.len() < MAXIMUM_CAPACITY);

        self.len += 1;
        if self.first_free < self.slots.len() as IdIndex {
            let index = self.first_free;
            let tagged_slot = &mut self.slots[self.first_free as usize];
            match mem::replace(&mut tagged_slot.slot, Slot::Occupied { value: value }) {
                Slot::Free { next_free } => self.first_free = next_free,
                Slot::Occupied { .. } => panic!("Occupied slot in free list."),
            }
            Id {
                tag: tagged_slot.tag,
                index: index,
                _data: PhantomData,
            }
        } else {
            self.slots.push(TaggedSlot {
                tag: self.seed_tag,
                slot: Slot::Occupied { value: value },
            });
            self.first_free = self.slots.len() as IdIndex;
            Id {
                index: self.first_free - 1,
                tag: self.seed_tag,
                _data: PhantomData,
            }
        }
    }

    /// Removes an element by `Id` returning its value.
    ///
    /// Returns `None` if no element with the given `Id` exists. See the struct level docs for the
    /// pathological cases where this may not be the case.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// let id1 = id_slab.insert(1);
    ///
    /// assert_eq!(id_slab[id1], 1);
    /// assert_eq!(id_slab.remove(id1), Some(1));
    ///
    /// assert!(!id_slab.contains(id1));
    /// assert_eq!(id_slab.remove(id1), None);
    /// ```
    pub fn remove(&mut self, id: Id<T>) -> Option<T> {
        let IdSlab {
            ref mut slots,
            ref mut len,
            ref mut first_free,
            ..
        } = *self;
        slots.get_mut(id.index as usize).and_then(|tagged_slot| {
            if tagged_slot.tag == id.tag {
                match mem::replace(
                    &mut tagged_slot.slot,
                    Slot::Free {
                        next_free: *first_free,
                    },
                ) {
                    Slot::Occupied { value } => {
                        *len = len.checked_sub(1).expect("invalid len in remove()");
                        tagged_slot.tag = tagged_slot.tag.wrapping_add(1);
                        *first_free = id.index;
                        Some(value)
                    }
                    rollback @ Slot::Free { .. } => {
                        tagged_slot.slot = rollback;
                        None
                    }
                }
            } else {
                None
            }
        })
    }

    /// Iterates over references to the elements in the `IdSlab`.
    ///
    /// While this operation has good cache locality, its worst-case complexity is
    /// `O(max_number_of_elements_ever)`. I.e.  there are pathological cases where adding and
    /// removing 1 million elements, then adding one element back will cause iteration to be `O(1
    /// million)`.
    ///
    /// The iteration order is unspecified, but it doesn't change unless the `IdSlab` is mutated.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// id_slab.insert(1);
    /// id_slab.insert(2);
    /// id_slab.insert(3);
    ///
    /// for i in id_slab.iter() {
    ///     println!("{}", i);  // Prints 1, 2, 3.
    /// }
    ///
    /// // Can use `&id_slab` instead:
    /// for i in &id_slab {
    ///     println!("{}", i);  // Prints 1, 2, 3.
    /// }
    /// ```
    pub fn iter(&self) -> Iter<T> {
        Iter {
            num_left: self.len(),
            iter: self.slots.iter(),
        }
    }

    /// Iterates over mutable references to the elements in the `IdSlab`.
    ///
    /// See `iter` for notes on complexity and iteration order.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// id_slab.insert(1);
    /// id_slab.insert(2);
    /// id_slab.insert(3);
    ///
    /// for value in id_slab.iter_mut() {  // Or `&mut id_slab`.
    ///     *value += 1;
    /// }
    ///
    /// for i in &id_slab {
    ///     println!("{}", i);  // Prints 2, 3, 4.
    /// }
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            num_left: self.len(),
            iter: self.slots.iter_mut(),
        }
    }

    fn get_or_tagged_slot(&self, id: Id<T>) -> Result<&T, Option<&TaggedSlot<T>>> {
        match self.slots.get(id.index as usize) {
            Some(&TaggedSlot {
                slot: Slot::Occupied { ref value },
                tag,
            }) if tag == id.tag => Ok(value),
            tagged_slot => Err(tagged_slot),
        }
    }

    fn get_mut_or_tagged_slot(&mut self, id: Id<T>) -> Result<&mut T, Option<&mut TaggedSlot<T>>> {
        match self.slots.get_mut(id.index as usize) {
            Some(tagged_slot) => {
                if id.tag == tagged_slot.tag {
                    match tagged_slot.slot {
                        Slot::Occupied { ref mut value } => Ok(value),
                        _ => Err(Some(tagged_slot)),
                    }
                } else {
                    Err(Some(tagged_slot))
                }
            }
            _ => Err(None),
        }
    }

    /// Returns a reference to an element by index or `None` if it doesn't exist.
    ///
    /// This is a low-level operation that bypasses the tag check. Useful for building other
    /// containers on top.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// let id = id_slab.insert(1);
    ///
    /// assert_eq!(id_slab.by_index(0), Some(&1));
    /// ```
    pub fn by_index(&self, index: IdIndex) -> Option<&T> {
        match self.slots.get(index as usize) {
            Some(&TaggedSlot {
                slot: Slot::Occupied { ref value },
                ..
            }) => Some(value),
            _ => None,
        }
    }

    /// Returns a mutable reference to an element by index or `None` if it doesn't exist.
    ///
    /// This is a low-level operation that bypasses the tag check. Useful for building other
    /// containers on top.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// let id = id_slab.insert(1);
    ///
    /// *id_slab.by_index_mut(0).unwrap() = 10;
    /// assert_eq!(id_slab[id], 10);
    /// ```
    pub fn by_index_mut(&mut self, index: IdIndex) -> Option<&mut T> {
        match self.slots.get_mut(index as usize) {
            Some(&mut TaggedSlot {
                slot: Slot::Occupied { ref mut value },
                ..
            }) => Some(value),
            _ => None,
        }
    }

    /// Returns the `Id` for a given occupied index.
    ///
    /// Returns `None` if the index is invalid.
    ///
    /// This is a low-level operation that bypasses the tag check. Useful for building other
    /// containers on top.
    ///
    /// Panics
    /// ---
    /// None.
    ///
    /// Example
    /// ---
    /// ```
    /// # use idcontain::IdSlab;
    /// let mut id_slab = IdSlab::new();
    /// let id = id_slab.insert(1);
    ///
    /// assert_eq!(id_slab.index_to_id(0), Some(id));
    /// ```
    pub fn index_to_id(&self, index: IdIndex) -> Option<Id<T>> {
        match self.slots.get(index as usize) {
            Some(&TaggedSlot {
                slot: Slot::Occupied { .. },
                tag,
            }) => Some(Id {
                index: index,
                tag: tag,
                _data: PhantomData,
            }),
            _ => None,
        }
    }
}

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

#[cold]
#[inline(never)]
fn panic_for_bad_id<T>(
    num_slots: usize,
    seed_tag: IdTag,
    len: usize,
    tagged_slot: Option<&TaggedSlot<T>>,
    id: Id<T>,
) -> ! {
    let reason = if id.index as usize > num_slots {
        format!(
            "index `{}` larger than number of slots `{}` (wrong `IdSlab`?)",
            id.index, num_slots
        )
    } else if let Some(&TaggedSlot { tag, ref slot }) = tagged_slot {
        if tag > id.tag {
            if (tag - id.tag) < 100 {
                format!("tag `{}` older than slot tag `{}`, deleted?", id.tag, tag)
            } else {
                format!(
                    "tag `{}` much older than slot tag `{}`, wrong `IdSlab` or deleted?",
                    id.tag, tag
                )
            }
        } else if tag < id.tag {
            format!(
                "tag `{}` newer than slot tag `{}`, wrong `IdSlab`?",
                id.tag, tag
            )
        } else {
            match *slot {
                Slot::Free { .. } => format!(
                    "tag `{}` matches, but the slot is free, wrong `IdSlab` with same \
                     seed_tag `{}`?",
                    id.tag, seed_tag
                ),
                Slot::Occupied { .. } => "<IdSlab bug [occupied], please report!>".to_owned(),
            }
        }
    } else {
        "<IdSlab bug [no TaggedSlot], please report!>".to_owned()
    };
    panic!(
        "Invalid id: {} (id={{ index=`{}`, tag=`{}` }}, id_slab={{ num_slots=`{}`, \
         seed_tag=`{}`, len=`{}` }})",
        reason, id.index, id.tag, num_slots, seed_tag, len
    )
}

impl<T> Index<Id<T>> for IdSlab<T> {
    type Output = T;

    fn index(&self, id: Id<T>) -> &Self::Output {
        self.get_or_tagged_slot(id).unwrap_or_else(|tagged_slot| {
            panic_for_bad_id(self.slots.len(), self.seed_tag, self.len, tagged_slot, id)
        })
    }
}

impl<T> IndexMut<Id<T>> for IdSlab<T> {
    fn index_mut(&mut self, id: Id<T>) -> &mut Self::Output {
        let num_slots = self.slots.len();
        let &mut IdSlab { seed_tag, len, .. } = self;
        self.get_mut_or_tagged_slot(id)
            .unwrap_or_else(|tagged_slot| {
                panic_for_bad_id(
                    num_slots,
                    seed_tag,
                    len,
                    tagged_slot.map(|tagged_slot| &*tagged_slot),
                    id,
                )
            })
    }
}

/// The type returned by `IdSlab.iter()`.
#[derive(Clone, Debug)]
pub struct Iter<'a, T: 'a> {
    num_left: usize,
    iter: SliceIter<'a, TaggedSlot<T>>,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        while self.num_left > 0 {
            let tagged_slot = self.iter.next().expect("Too few elements in Iter");
            if let TaggedSlot {
                slot: Slot::Occupied { ref value },
                ..
            } = *tagged_slot
            {
                self.num_left -= 1;
                return Some(value);
            }
        }
        None
    }

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

impl<'a, T: 'a> DoubleEndedIterator for Iter<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        while self.num_left > 0 {
            let tagged_slot = self.iter.next_back().expect("Too few elements in Iter");
            if let TaggedSlot {
                slot: Slot::Occupied { ref value },
                ..
            } = *tagged_slot
            {
                self.num_left -= 1;
                return Some(value);
            }
        }
        None
    }
}

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

fn default_seed_tag() -> IdTag {
    rand::thread_rng().gen()
}

/// The type returned by `IdSlab.iter_mut()`.
#[derive(Debug)]
pub struct IterMut<'a, T: 'a> {
    iter: SliceIterMut<'a, TaggedSlot<T>>,
    num_left: usize,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        while self.num_left > 0 {
            let tagged_slot = self.iter.next().expect("Too few elements in IterMut");
            if let TaggedSlot {
                slot: Slot::Occupied { ref mut value },
                ..
            } = *tagged_slot
            {
                self.num_left -= 1;
                return Some(value);
            }
        }
        None
    }

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

impl<'a, T: 'a> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        while self.num_left > 0 {
            let tagged_slot = self.iter.next_back().expect("Too few elements in IterMut");
            if let TaggedSlot {
                slot: Slot::Occupied { ref mut value },
                ..
            } = *tagged_slot
            {
                self.num_left -= 1;
                return Some(value);
            }
        }
        None
    }
}

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

impl<'a, T: 'a> IntoIterator for &'a IdSlab<T> {
    type IntoIter = Iter<'a, T>;
    type Item = <Self::IntoIter as Iterator>::Item;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T: 'a> IntoIterator for &'a mut IdSlab<T> {
    type IntoIter = IterMut<'a, T>;
    type Item = <Self::IntoIter as Iterator>::Item;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

#[derive(Debug, Clone)]
enum Slot<T> {
    Free { next_free: IdIndex },
    Occupied { value: T },
}

#[derive(Debug, Clone)]
struct TaggedSlot<T> {
    tag: IdTag,
    slot: Slot<T>,
}

#[cfg(test)]
mod tests {
    use super::super::id::Id;
    use super::IdSlab;
    use std::marker::PhantomData;

    #[test]
    fn len_iter_contains_on_empty() {
        let id_slab = IdSlab::<i32>::new();
        assert_eq!(id_slab.len(), 0);
        assert_eq!(id_slab.iter().next(), None);
        assert!(!id_slab.contains(Id {
            index: 0,
            tag: 0,
            _data: PhantomData,
        }));
    }

    #[test]
    fn iter_mut_on_empty() {
        let mut id_slab = IdSlab::<String>::new();
        assert_eq!(id_slab.iter_mut().next(), None);
    }

    #[test]
    fn id_slab_insert_then_get_and_index() {
        let mut id_slab = IdSlab::new();

        let id_a = id_slab.insert(1);
        let id_b = id_slab.insert(2);
        let id_c = id_slab.insert(3);

        // Id-s all differ from each other.
        assert!(id_a != id_b);
        assert!(id_b != id_c);
        assert!(id_c != id_a);

        // `get` returns the correct values.
        assert_eq!(id_slab.get(id_a).map(|&x| x), Some(1));
        assert_eq!(id_slab.get(id_b).map(|&x| x), Some(2));
        assert_eq!(id_slab.get(id_c).map(|&x| x), Some(3));

        // `get_mut` returns the correct values.
        assert_eq!(id_slab.get_mut(id_a).map(|&mut x| x), Some(1));
        assert_eq!(id_slab.get_mut(id_b).map(|&mut x| x), Some(2));
        assert_eq!(id_slab.get_mut(id_c).map(|&mut x| x), Some(3));

        // `index` returns the correct values.
        assert_eq!(*(&id_slab[id_a]), 1);
        assert_eq!(*(&id_slab[id_b]), 2);
        assert_eq!(*(&id_slab[id_c]), 3);

        // `index` returns the correct values.
        assert_eq!(*(&mut id_slab[id_a]), 1);
        assert_eq!(*(&mut id_slab[id_b]), 2);
        assert_eq!(*(&mut id_slab[id_c]), 3);

        // Mutating through id_b then `get`-ing again works.
        id_slab[id_b] = 10;
        assert_eq!(id_slab[id_b], 10);
    }

    #[test]
    #[should_panic]
    fn id_slab_insert_then_remove_index_panics() {
        let mut id_slab = IdSlab::new();
        let id = id_slab.insert(1);
        id_slab.remove(id);
        id_slab[id];
    }

    #[test]
    #[should_panic]
    fn id_slab_insert_then_remove_index_mut_panics() {
        let mut id_slab = IdSlab::new();
        let id = id_slab.insert(1);
        id_slab.remove(id);
        id_slab[id] = 10;
    }

    #[test]
    fn id_slab_insert_then_remove_get() {
        let mut id_slab = IdSlab::with_capacity(3);

        let id_a = id_slab.insert(1);
        let id_b = id_slab.insert(2);
        let id_c = id_slab.insert(3);

        assert_eq!(id_slab.remove(id_b), Some(2));
        assert_eq!(id_slab.get(id_b), None);
        assert!(!id_slab.contains(id_b));

        assert_eq!(id_slab[id_a], 1);
        assert_eq!(id_slab[id_c], 3);

        let id_d = id_slab.insert(5);

        assert_eq!(id_slab.remove(id_a), Some(1));
        assert_eq!(id_slab.remove(id_a), None);
        assert_eq!(id_slab.remove(id_c), Some(3));
        assert_eq!(id_slab.get(id_a), None);
        assert_eq!(id_slab.get(id_c), None);
        assert!(!id_slab.contains(id_a));
        assert!(!id_slab.contains(id_b));
        assert!(!id_slab.contains(id_c));
        assert!(id_slab.contains(id_d));

        let id_e = id_slab.insert(6);
        let id_f = id_slab.insert(7);

        assert!(id_d.tag == id_b.tag.wrapping_add(1));
        assert!(id_d.index == id_b.index);

        assert!(id_e.tag == id_c.tag.wrapping_add(1));
        assert!(id_e.index == id_c.index);

        assert!(id_f.tag == id_a.tag.wrapping_add(1));
        assert!(id_f.index == id_a.index);
    }

    #[test]
    fn id_slab_insert_then_remove_iter() {
        let mut id_slab = IdSlab::with_capacity(3);

        let id_a = id_slab.insert(1);
        let id_b = id_slab.insert(2);
        id_slab.insert(3);
        id_slab.remove(id_b);
        id_slab.insert(4);
        let id_e = id_slab.insert(5);
        id_slab.remove(id_e);
        id_slab.remove(id_a);

        assert_eq!(&id_slab.iter().cloned().collect::<Vec<_>>()[..], &[4, 3]);
        assert_eq!(
            &id_slab.iter_mut().map(|&mut x| x).collect::<Vec<_>>()[..],
            &[4, 3]
        );

        assert_eq!(
            &(&id_slab).into_iter().cloned().collect::<Vec<_>>()[..],
            &[4, 3]
        );
        assert_eq!(
            &(&mut id_slab)
                .into_iter()
                .map(|&mut x| x)
                .collect::<Vec<_>>()[..],
            &[4, 3]
        );
    }

    #[test]
    fn id_slab_ids_from_different_id_slabs() {
        let mut id_slab_1 = IdSlab::with_capacity(3);
        let mut id_slab_2 = IdSlab::with_capacity(4);

        let id_a_1 = id_slab_1.insert(1);
        let id_b_1 = id_slab_1.insert(2);
        let id_c_1 = id_slab_1.insert(3);

        let id_a_2 = id_slab_2.insert(1);
        let id_b_2 = id_slab_2.insert(2);
        let id_c_2 = id_slab_2.insert(3);
        let id_d_2 = id_slab_2.insert(4);

        assert_eq!(id_slab_1.get(id_a_2), None);
        assert_eq!(id_slab_1.get(id_b_2), None);
        assert_eq!(id_slab_1.get(id_c_2), None);
        assert_eq!(id_slab_1.get(id_d_2), None);
        assert_eq!(id_slab_1.get_mut(id_a_2), None);
        assert_eq!(id_slab_1.get_mut(id_b_2), None);
        assert_eq!(id_slab_1.get_mut(id_c_2), None);
        assert_eq!(id_slab_1.get_mut(id_d_2), None);
        assert!(!id_slab_1.contains(id_a_2));
        assert!(!id_slab_1.contains(id_b_2));
        assert!(!id_slab_1.contains(id_c_2));
        assert!(!id_slab_1.contains(id_d_2));
        assert_eq!(id_slab_1.remove(id_a_2), None);
        assert_eq!(id_slab_1.remove(id_b_2), None);
        assert_eq!(id_slab_1.remove(id_c_2), None);
        assert_eq!(id_slab_1.remove(id_d_2), None);
        assert_eq!(&id_slab_1.iter().cloned().collect::<Vec<_>>(), &[1, 2, 3]);

        assert_eq!(id_slab_2.get(id_a_1), None);
        assert_eq!(id_slab_2.get(id_b_1), None);
        assert_eq!(id_slab_2.get(id_c_1), None);
        assert_eq!(id_slab_2.get_mut(id_a_1), None);
        assert_eq!(id_slab_2.get_mut(id_b_1), None);
        assert_eq!(id_slab_2.get_mut(id_c_1), None);
        assert!(!id_slab_2.contains(id_a_1));
        assert!(!id_slab_2.contains(id_b_1));
        assert!(!id_slab_2.contains(id_c_1));
        assert_eq!(id_slab_2.remove(id_a_1), None);
        assert_eq!(id_slab_2.remove(id_b_1), None);
        assert_eq!(id_slab_2.remove(id_c_1), None);
        assert_eq!(
            &id_slab_2.iter().cloned().collect::<Vec<_>>(),
            &[1, 2, 3, 4]
        );
    }
}