concurrent_slotmap/

lib.rs

extern crate alloc;

use core::{
    cell::Cell,
    cmp, fmt,
    hash::{Hash, Hasher},
    hint,
    iter::{self, FusedIterator},
    marker::PhantomData,
    mem::{self, MaybeUninit},
    num::NonZeroU32,
    slice,
    sync::atomic::{
        self, AtomicI32, AtomicU32, AtomicUsize,
        Ordering::{Acquire, Relaxed, Release},
    },
};
pub use slot::Slot;
use slot::{header_ptr_from_slots, Vec};
use std::{hash::DefaultHasher, thread};

pub mod hyaline;
mod slot;

/// The slot index used to signify the lack thereof.
const NIL: u32 = u32::MAX;

/// The number of low bits that can be used for user-tagged generations.
const TAG_BITS: u32 = 8;

/// The mask for user-tagged generations.
const TAG_MASK: u32 = (1 << TAG_BITS) - 1;

/// The number of bits following the user-tag bits that are used for the state of a slot.
const STATE_BITS: u32 = 2;

/// The mask for the state of a slot.
const STATE_MASK: u32 = 0b11 << TAG_BITS;

/// The state tag used to signify that the slot is vacant.
const VACANT_TAG: u32 = 0b00 << TAG_BITS;

/// The state tag used to signify that the slot is occupied.
const OCCUPIED_TAG: u32 = 0b01 << TAG_BITS;

/// The state tag used to signify that the slot has been invalidated.
const INVALIDATED_TAG: u32 = 0b10 << TAG_BITS;

/// The state tag used to signify that the invalidated slot has been reclaimed.
const RECLAIMED_TAG: u32 = 0b11 << TAG_BITS;

/// The mask for the generation.
const GENERATION_MASK: u32 = u32::MAX << (TAG_BITS + STATE_BITS);

/// A single generation.
const ONE_GENERATION: u32 = 1 << (TAG_BITS + STATE_BITS);

/// The number of shards to use.
static SHARD_COUNT: AtomicUsize = AtomicUsize::new(0);

thread_local! {
    /// The thread-local shard index.
    static SHARD_INDEX: Cell<usize> = const { Cell::new(0) };
}

pub struct SlotMap<K, V> {
    inner: SlotMapInner<V>,
    marker: PhantomData<fn(K) -> K>,
}

struct SlotMapInner<V> {
    /// ```compile_fail,E0597
    /// let map = concurrent_slotmap::SlotMap::<_, &'static str>::new(1);
    /// let guard = &map.pin();
    /// let id = {
    ///     let s = "oh no".to_owned();
    ///     map.insert(&s, guard)
    /// };
    /// dbg!(map.get(id, guard));
    /// ```
    slots: Vec<V>,
    collector: hyaline::CollectorHandle,
}

#[repr(transparent)]
struct Header {
    shards: [HeaderShard],
}

#[repr(align(128))]
struct HeaderShard {
    /// The list of slots which have already been dropped and are ready to be claimed by insert
    /// operations.
    free_list: AtomicU32,
    /// The number of occupied slots.
    len: AtomicI32,
}

// SAFETY: `SlotMap` is an owned collection, which makes it safe to send to another thread as long
// as the value is safe to send to another thread. The key is a phantom parameter.
unsafe impl<K, V: Send> Send for SlotMap<K, V> {}

// SAFETY: `SlotMap` allows pushing through a shared reference, which allows a shared `SlotMap` to
// be used to send values to another thread. Additionally, `SlotMap` allows getting a reference to
// any value from any thread. Therefore, it is safe to share `SlotMap` between threads as long as
// the value is both sendable and shareable. The key is a phantom parameter.
unsafe impl<K, V: Send + Sync> Sync for SlotMap<K, V> {}

impl<V> SlotMap<SlotId, V> {
    #[must_use]
    #[track_caller]
    pub fn new(max_capacity: u32) -> Self {
        Self::with_key(max_capacity)
    }

    /// # Safety
    ///
    /// Please see the safety documentation of [`with_collector_and_key`].
    ///
    /// [`with_collector_and_key`]: Self::with_collector_and_key
    #[must_use]
    #[track_caller]
    pub unsafe fn with_collector(max_capacity: u32, collector: hyaline::CollectorHandle) -> Self {
        // SAFETY: Enforced by the caller.
        unsafe { Self::with_collector_and_key(max_capacity, collector) }
    }
}

impl<K, V> SlotMap<K, V> {
    #[must_use]
    #[track_caller]
    pub fn with_key(max_capacity: u32) -> Self {
        // SAFETY: It's not possible to obtain a `hyaline::Guard` that isn't bound to the collection
        // without using either the unsafe `hyaline::CollectorHandle::pin` or the unsafe
        // `SlotMap::with_collector[_and_key]` followed by `SlotMap::pin`.
        unsafe { Self::with_collector_and_key(max_capacity, hyaline::CollectorHandle::new()) }
    }

    /// # Safety
    ///
    /// The given `collector` must not be used to create any `Guard` that outlives the collection.
    /// It would result in the `Guard`'s drop implementation attempting to free slots from the
    /// already freed collection, resulting in a Use-After-Free. You must ensure that the `Guard`
    /// has its lifetime bound to the collections it protects.
    ///
    /// Note that it is not enough for [`CollectorHandle::pin`] to be unsafe because
    /// [`SlotMap::pin`] is safe:
    ///
    /// ```no_run
    /// # use concurrent_slotmap::{hyaline::CollectorHandle, SlotMap};
    /// #
    /// let collector = CollectorHandle::new();
    /// let map1 = unsafe { SlotMap::<_, i32>::with_collector(1, collector.clone()) };
    /// let guard = &map1.pin();
    /// let map2 = unsafe { SlotMap::<_, i32>::with_collector(1, collector) };
    ///
    /// map2.remove(map2.insert(69, guard), guard);
    ///
    /// // undefined behavior! ⚠️
    /// ```
    ///
    /// [`CollectorHandle::pin`]: hyaline::CollectorHandle::pin
    #[must_use]
    #[track_caller]
    pub unsafe fn with_collector_and_key(
        max_capacity: u32,
        collector: hyaline::CollectorHandle,
    ) -> Self {
        SlotMap {
            inner: SlotMapInner {
                slots: Vec::new(max_capacity),
                collector,
            },
            marker: PhantomData,
        }
    }

    #[inline]
    #[must_use]
    pub fn capacity(&self) -> u32 {
        self.inner.slots.capacity()
    }

    #[inline]
    #[must_use]
    pub fn len(&self) -> u32 {
        self.inner.header().len()
    }

    #[inline]
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    #[inline]
    #[must_use]
    pub fn collector(&self) -> &hyaline::CollectorHandle {
        &self.inner.collector
    }

    #[inline]
    #[must_use]
    pub fn pin(&self) -> hyaline::Guard<'_> {
        self.inner.pin()
    }

    /// # Panics
    ///
    /// Panics if `guard.collector()` does not equal `self.collector()`.
    #[inline]
    #[track_caller]
    pub fn slots<'a>(&'a self, guard: &'a hyaline::Guard<'a>) -> Slots<'a, V> {
        self.inner.check_guard(guard);

        Slots {
            slots: self.inner.slots.iter(),
        }
    }
}

impl<K: Key, V> SlotMap<K, V> {
    /// # Panics
    ///
    /// Panics if `guard.collector()` does not equal `self.collector()`.
    #[inline]
    #[track_caller]
    pub fn insert<'a>(&'a self, value: V, guard: &'a hyaline::Guard<'a>) -> K {
        self.insert_with_tag(value, 0, guard)
    }

    /// # Panics
    ///
    /// - Panics if `guard.collector()` does not equal `self.collector()`.
    /// - Panics if `tag` has more than the low 8 bits set.
    #[inline]
    #[track_caller]
    pub fn insert_with_tag<'a>(&'a self, value: V, tag: u32, guard: &'a hyaline::Guard<'a>) -> K {
        K::from_id(self.inner.insert_with_tag_with(tag, guard, |_| value))
    }

    /// # Panics
    ///
    /// Panics if `guard.global()` is `Some` and does not equal `self.global()`.
    #[inline]
    #[track_caller]
    pub fn insert_with<'a>(&'a self, guard: &'a hyaline::Guard<'a>, f: impl FnOnce(K) -> V) -> K {
        self.insert_with_tag_with(0, guard, f)
    }

    /// # Panics
    ///
    /// - Panics if `guard.collector()` does not equal `self.collector()`.
    /// - Panics if `tag` has more than the low 8 bits set.
    #[inline]
    #[track_caller]
    pub fn insert_with_tag_with<'a>(
        &'a self,
        tag: u32,
        guard: &'a hyaline::Guard<'a>,
        f: impl FnOnce(K) -> V,
    ) -> K {
        let f = |id| f(K::from_id(id));

        K::from_id(self.inner.insert_with_tag_with(tag, guard, f))
    }

    #[inline]
    pub fn insert_mut(&mut self, value: V) -> K {
        self.insert_with_tag_mut(value, 0)
    }

    /// # Panics
    ///
    /// Panics if `tag` has more than the low 8 bits set.
    #[inline]
    #[track_caller]
    pub fn insert_with_tag_mut(&mut self, value: V, tag: u32) -> K {
        K::from_id(self.inner.insert_with_tag_with_mut(tag, |_| value))
    }

    #[inline]
    pub fn insert_with_mut(&mut self, f: impl FnOnce(K) -> V) -> K {
        self.insert_with_tag_with_mut(0, f)
    }

    /// # Panics
    ///
    /// Panics if `tag` has more than the low 8 bits set.
    #[inline]
    #[track_caller]
    pub fn insert_with_tag_with_mut(&mut self, tag: u32, f: impl FnOnce(K) -> V) -> K {
        let f = |id| f(K::from_id(id));

        K::from_id(self.inner.insert_with_tag_with_mut(tag, f))
    }

    /// # Panics
    ///
    /// Panics if `guard.collector()` does not equal `self.collector()`.
    #[inline]
    #[track_caller]
    pub fn remove<'a>(&'a self, key: K, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.inner.remove(key.as_id(), guard)
    }

    #[inline]
    pub fn remove_mut(&mut self, key: K) -> Option<V> {
        self.inner.remove_mut(key.as_id())
    }

    /// # Safety
    ///
    /// `key` must refer to a currently occupied slot. That also excludes a race condition when
    /// calling this method.
    #[inline]
    #[track_caller]
    pub unsafe fn remove_unchecked<'a>(&'a self, key: K, guard: &'a hyaline::Guard<'a>) -> &'a V {
        // SAFETY: Enforced by the caller.
        unsafe { self.inner.remove_unchecked(key.as_id(), guard) }
    }

    #[cfg(test)]
    fn remove_index<'a>(&'a self, index: u32, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.inner.remove_index(index, guard)
    }

    #[inline]
    #[track_caller]
    pub fn invalidate<'a>(&'a self, key: K, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.inner.invalidate(key.as_id(), guard)
    }

    #[inline]
    pub fn remove_invalidated(&self, key: K) -> Option<()> {
        self.inner.remove_invalidated(key.as_id())
    }

    /// # Safety
    ///
    /// `key` must refer to a currently invalidated slot. That also excludes a race condition when
    /// calling this method.
    #[inline]
    pub unsafe fn remove_invalidated_unchecked(&self, key: K) {
        // SAFETY: Enforced by the caller.
        unsafe { self.inner.remove_invalidated_unchecked(key.as_id()) };
    }

    /// # Panics
    ///
    /// Panics if `guard.collector()` does not equal `self.collector()`.
    #[inline(always)]
    #[must_use]
    #[track_caller]
    pub fn get<'a>(&'a self, key: K, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.inner.get(key.as_id(), guard)
    }

    #[inline(always)]
    #[must_use]
    pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
        self.inner.get_mut(key.as_id())
    }

    #[inline]
    #[must_use]
    pub fn get_disjoint_mut<const N: usize>(&mut self, keys: [K; N]) -> Option<[&mut V; N]> {
        self.inner.get_disjoint_mut(keys.map(Key::as_id))
    }

    #[cfg(test)]
    fn index<'a>(&'a self, index: u32, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.inner.index(index, guard)
    }

    /// # Safety
    ///
    /// The slot must be currently occupied.
    ///
    /// # Panics
    ///
    /// Panics if `guard.collector()` does not equal `self.collector()`.
    #[inline(always)]
    #[must_use]
    #[track_caller]
    pub unsafe fn get_unchecked<'a>(&'a self, key: K, guard: &'a hyaline::Guard<'a>) -> &'a V {
        // SAFETY: Enforced by the caller.
        unsafe { self.inner.get_unchecked(key.as_id(), guard) }
    }

    /// # Safety
    ///
    /// The slot must be currently occupied.
    #[inline(always)]
    #[must_use]
    pub unsafe fn get_unchecked_mut(&mut self, key: K) -> &mut V {
        // SAFETY: Enforced by the caller.
        unsafe { self.inner.get_unchecked_mut(key.as_id()) }
    }

    /// # Panics
    ///
    /// Panics if `guard.collector()` does not equal `self.collector()`.
    #[inline]
    #[must_use]
    #[track_caller]
    pub fn iter<'a>(&'a self, guard: &'a hyaline::Guard<'a>) -> Iter<'a, K, V> {
        self.inner.check_guard(guard);

        Iter {
            slots: self.inner.slots.iter().enumerate(),
            marker: PhantomData,
        }
    }

    #[inline]
    #[must_use]
    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        IterMut {
            slots: self.inner.slots.iter_mut().enumerate(),
            marker: PhantomData,
        }
    }
}

impl<K: Key, V> SlotMap<K, MaybeUninit<V>> {
    /// # Panics
    ///
    /// Panics if `guard.collector()` does not equal `self.collector()`.
    #[inline]
    #[track_caller]
    pub fn revive_or_insert_with<'a>(
        &'a self,
        guard: &'a hyaline::Guard<'a>,
        f: impl FnOnce(K) -> MaybeUninit<V>,
    ) -> (K, &'a MaybeUninit<V>) {
        let f = |id| f(K::from_id(id));

        let (id, value) = self.inner.revive_or_insert_with(guard, f);

        (K::from_id(id), value)
    }
}

impl<V> SlotMapInner<V> {
    fn pin(&self) -> hyaline::Guard<'_> {
        // SAFETY: The guard's lifetime is bound to the collection.
        unsafe { self.collector.pin() }
    }

    #[track_caller]
    fn insert_with_tag_with<'a>(
        &'a self,
        tag: u32,
        guard: &'a hyaline::Guard<'a>,
        f: impl FnOnce(SlotId) -> V,
    ) -> SlotId {
        assert_eq!(tag & !TAG_MASK, 0);

        let id = if let Some((id, slot)) = self.allocate_slot(tag, guard) {
            // SAFETY: The free-list always contains slots that are no longer read by any threads
            // and we have removed the slot from the free-list such that no other threads can be
            // writing the same slot.
            unsafe { slot.value.get().cast::<V>().write(f(id)) };

            slot.generation.store(id.generation(), Release);

            id
        } else {
            self.slots.push_with_tag_with(tag, f).0
        };

        self.header().shard().len.fetch_add(1, Relaxed);

        id
    }

    #[track_caller]
    fn allocate_slot<'a>(
        &'a self,
        tag: u32,
        guard: &'a hyaline::Guard<'a>,
    ) -> Option<(SlotId, &'a Slot<V>)> {
        self.check_guard(guard);

        'outer: for shard in self.header().shards() {
            let mut free_list_head = shard.free_list.load(Acquire);
            let mut backoff = Backoff::new();

            loop {
                if free_list_head == NIL {
                    continue 'outer;
                }

                // SAFETY: We always push indices of existing slots into the free-lists and the
                // slots vector never shrinks, therefore the index must have staid in bounds.
                let slot = unsafe { self.slots.get_unchecked(free_list_head) };

                let next_free = slot.next_free.load(Relaxed);

                match shard.free_list.compare_exchange_weak(
                    free_list_head,
                    next_free,
                    Release,
                    Acquire,
                ) {
                    Ok(_) => {
                        let generation = slot.generation.load(Relaxed);

                        debug_assert!(generation & STATE_MASK == VACANT_TAG);

                        let new_generation = generation | OCCUPIED_TAG | tag;

                        // SAFETY: We always push slots with their state tag set to `VACANT_TAG`
                        // into the free-list and we replaced the tag with `OCCUPIED_TAG` above.
                        let id = unsafe { SlotId::new_unchecked(free_list_head, new_generation) };

                        return Some((id, slot));
                    }
                    Err(new_head) => {
                        free_list_head = new_head;
                        backoff.spin();
                    }
                }
            }
        }

        None
    }

    #[track_caller]
    fn insert_with_tag_with_mut(&mut self, tag: u32, f: impl FnOnce(SlotId) -> V) -> SlotId {
        assert_eq!(tag & !TAG_MASK, 0);

        // SAFETY: We unbind the lifetime to convince the borrow checker that we don't borrow
        // `self.slots` mutably more than once. We don't because the header and slots are occupying
        // disjoint memory ranges.
        let header = unsafe { mem::transmute::<&mut Header, &mut Header>(self.slots.header_mut()) };

        for shard in header.shards_mut() {
            let free_list_head = *shard.free_list.get_mut();

            if free_list_head != NIL {
                // SAFETY: We always push indices of existing slots into the free-lists and the
                // slots vector never shrinks, therefore the index must have staid in bounds.
                let slot = unsafe { self.slots.get_unchecked_mut(free_list_head) };

                *shard.free_list.get_mut() = *slot.next_free.get_mut();

                let generation = *slot.generation.get_mut();

                debug_assert!(generation & STATE_MASK == VACANT_TAG);

                let new_generation = generation | OCCUPIED_TAG | tag;

                // SAFETY: We always push slots with their state tag set to `VACANT_TAG` into the
                // free-list and we replaced the tag with `OCCUPIED_TAG` above.
                let id = unsafe { SlotId::new_unchecked(free_list_head, new_generation) };

                *slot.value.get_mut() = MaybeUninit::new(f(id));

                *slot.generation.get_mut() = new_generation;

                let len = header.shard_mut().len.get_mut();
                *len = len.wrapping_add(1);

                return id;
            }
        }

        let id = self.slots.push_with_tag_with_mut(tag, f);

        let len = header.shard_mut().len.get_mut();
        *len = len.wrapping_add(1);

        id
    }

    #[track_caller]
    fn remove<'a>(&'a self, id: SlotId, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.check_guard(guard);

        let slot = self.slots.get(id.index)?;
        let new_generation = (id.generation() & GENERATION_MASK).wrapping_add(ONE_GENERATION);

        if slot
            .generation
            .compare_exchange(id.generation(), new_generation, Acquire, Relaxed)
            .is_err()
        {
            return None;
        }

        self.header().shard().len.fetch_sub(1, Relaxed);

        // SAFETY: We set the slot's state tag to `VACANT_TAG` such that no other threads can access
        // the slot going forward.
        unsafe { guard.defer_reclaim(id.index, &self.slots) };

        // SAFETY:
        // * The `Acquire` ordering when loading the slot's generation synchronizes with the
        //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value is
        //   visible here.
        // * The `compare_exchange` above succeeded, which means that the previous state tag of the
        //   slot must have been `OCCUPIED_TAG`, which means it must have been initialized in
        //   `SlotMap::insert[_mut]`.
        Some(unsafe { slot.value_unchecked() })
    }

    fn remove_mut(&mut self, id: SlotId) -> Option<V> {
        // SAFETY: We unbind the lifetime to convince the borrow checker that we don't borrow
        // `self.slots` mutably more than once. We don't because the header and slots are occupying
        // disjoint memory ranges.
        let header = unsafe { mem::transmute::<&mut Header, &mut Header>(self.slots.header_mut()) };

        let slot = self.slots.get_mut(id.index)?;
        let generation = *slot.generation.get_mut();

        if generation == id.generation() {
            let new_generation = (generation & GENERATION_MASK).wrapping_add(ONE_GENERATION);
            *slot.generation.get_mut() = new_generation;

            *slot.next_free.get_mut() = *header.shard_mut().free_list.get_mut();
            *header.shard_mut().free_list.get_mut() = id.index;

            let len = header.shard_mut().len.get_mut();
            *len = len.wrapping_sub(1);

            // SAFETY:
            // * The mutable reference makes sure that access to the slot is synchronized.
            // * We checked that `id.generation` matches the slot's generation, which means that the
            //   previous state tag of the slot must have been `OCCUPIED_TAG`, which means it must
            //   have been initialized in `SlotMap::insert[_mut]`.
            // * We set the slot's state tag to `VACANT_TAG` such that future attempts to access the
            //   slot will fail.
            Some(unsafe { slot.value.get().cast::<V>().read() })
        } else {
            None
        }
    }

    #[track_caller]
    unsafe fn remove_unchecked<'a>(&'a self, id: SlotId, guard: &'a hyaline::Guard<'a>) -> &'a V {
        self.check_guard(guard);

        // SAFETY: The caller must ensure that the index is in bounds.
        let slot = unsafe { self.slots.get_unchecked(id.index) };

        let new_generation = (id.generation() & GENERATION_MASK).wrapping_add(ONE_GENERATION);

        let generation = slot.generation.swap(new_generation, Acquire);

        assert_unsafe_precondition!(
            is_occupied(generation),
            "`id` must refer to a currently occupied slot",
        );

        self.header().shard().len.fetch_sub(1, Relaxed);

        // SAFETY: We set the slot's state tag to `VACANT_TAG` such that no other threads can access
        // the slot going forward. The caller must ensure that a race condition doesn't occur.
        unsafe { guard.defer_reclaim(id.index, &self.slots) };

        // SAFETY:
        // * The `Acquire` ordering when loading the slot's generation synchronizes with the
        //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value is
        //   visible here.
        // * The caller must ensure that the slot is occupied, which means it must have been
        //   initialized in `SlotMap::insert[_mut]`.
        unsafe { slot.value_unchecked() }
    }

    #[cfg(test)]
    fn remove_index<'a>(&'a self, index: u32, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.check_guard(guard);

        let slot = self.slots.get(index)?;
        let mut generation = slot.generation.load(Relaxed);

        loop {
            if !is_occupied(generation) {
                return None;
            }

            let new_generation = (generation & GENERATION_MASK).wrapping_add(ONE_GENERATION);

            match slot.generation.compare_exchange_weak(
                generation,
                new_generation,
                Acquire,
                Relaxed,
            ) {
                Ok(_) => break,
                Err(new_generation) => generation = new_generation,
            }
        }

        self.header().shard().len.fetch_sub(1, Relaxed);

        // SAFETY: We set the slot's state tag to `VACANT_TAG` such that no other threads can access
        // the slot going forward.
        unsafe { guard.defer_reclaim(index, &self.slots) };

        // SAFETY:
        // * The `Acquire` ordering when loading the slot's generation synchronizes with the
        //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value is
        //   visible here.
        // * The `compare_exchange_weak` above succeeded, which means that the previous state tag of
        //   the slot must have been `OCCUPIED_TAG`, which means it must have been initialized in
        //   `SlotMap::insert[_mut]`.
        Some(unsafe { slot.value_unchecked() })
    }

    #[track_caller]
    fn invalidate<'a>(&'a self, id: SlotId, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.check_guard(guard);

        let slot = self.slots.get(id.index)?;
        let new_generation = (id.generation() & !STATE_MASK) | INVALIDATED_TAG;

        if slot
            .generation
            .compare_exchange(id.generation(), new_generation, Acquire, Relaxed)
            .is_err()
        {
            return None;
        }

        self.header().shard().len.fetch_sub(1, Relaxed);

        // SAFETY: We set the slot's state tag to `INVALIDATED_TAG` such that no other threads can
        // access the slot going forward.
        unsafe { guard.defer_reclaim_invalidated(id.index, &self.slots) };

        // SAFETY:
        // * The `Acquire` ordering when loading the slot's generation synchronizes with the
        //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value is
        //   visible here.
        // * The `compare_exchange` above succeeded, which means that the previous state tag of the
        //   slot must have been `OCCUPIED_TAG`, which means it must have been initialized in
        //   `SlotMap::insert[_mut]`.
        Some(unsafe { slot.value_unchecked() })
    }

    fn remove_invalidated(&self, id: SlotId) -> Option<()> {
        let slot = self.slots.get(id.index)?;
        let mut generation = slot.generation.load(Relaxed);
        let new_generation = (id.generation() & GENERATION_MASK).wrapping_add(ONE_GENERATION);

        loop {
            if generation & !STATE_MASK != id.generation() & !STATE_MASK {
                break None;
            }

            if generation & STATE_MASK == RECLAIMED_TAG {
                match slot.generation.compare_exchange_weak(
                    generation,
                    new_generation,
                    Acquire,
                    Relaxed,
                ) {
                    Ok(_) => {
                        // SAFETY:
                        // * The `Acquire` ordering when loading the slot's generation synchronizes
                        //   with the `Release` ordering in `SlotMap::insert`, making sure that the
                        //   newly written value is visible here.
                        // * The `compare_exchange_weak` above succeeded, which means that the
                        //   previous state tag of the slot must have been `RECLAIMED_TAG`, which
                        //   means it must have been reclaimed in `reclaim_invalidated`, which means
                        //   it must have been invalidated in `SlotMap::invalidate`, which means it
                        //   must have been initialized in `SlotMap::insert[_mut]`.
                        // * We set the slot's state tag to `VACANT_TAG` such that future attempts
                        //   to access the slot will fail.
                        unsafe { reclaim(id.index, self.slots.as_ptr()) };

                        break Some(());
                    }
                    Err(new_generation) => generation = new_generation,
                }
            } else if generation & STATE_MASK == INVALIDATED_TAG {
                match slot.generation.compare_exchange_weak(
                    generation,
                    new_generation,
                    Relaxed,
                    Relaxed,
                ) {
                    Ok(_) => break Some(()),
                    Err(new_generation) => generation = new_generation,
                }
            } else {
                break None;
            }
        }
    }

    unsafe fn remove_invalidated_unchecked(&self, id: SlotId) {
        // SAFETY: The caller must ensure that the index is in bounds.
        let slot = unsafe { self.slots.get_unchecked(id.index) };

        let new_generation = (id.generation() & GENERATION_MASK).wrapping_add(ONE_GENERATION);

        let generation = slot.generation.swap(new_generation, Relaxed);

        assert_unsafe_precondition!(
            generation & STATE_MASK == RECLAIMED_TAG || generation & STATE_MASK == INVALIDATED_TAG,
            "`id` must refer to a currently invalidated slot",
        );

        if generation & STATE_MASK == RECLAIMED_TAG {
            atomic::fence(Acquire);

            // SAFETY:
            // * The `Acquire` fence after loading the slot's generation synchronizes with the
            //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value
            //   is visible here.
            // * The previous state tag of the slot was `RECLAIMED_TAG`, which means it must have
            //   been reclaimed in `reclaim_invalidated`, which means it must have been invalidated
            //   in `SlotMap::invalidate`, which means it must have been initialized in
            //   `SlotMap::insert[_mut]`.
            // * We set the slot's state tag to `VACANT_TAG` such that future attempts to access the
            //   slot will fail.
            // * The caller must ensure that a race condition doesn't occur.
            unsafe { reclaim(id.index, self.slots.as_ptr()) };
        }
    }

    #[inline(always)]
    #[track_caller]
    fn get<'a>(&'a self, id: SlotId, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.check_guard(guard);

        let slot = self.slots.get(id.index)?;
        let generation = slot.generation.load(Acquire);

        if generation == id.generation() {
            // SAFETY:
            // * The `Acquire` ordering when loading the slot's generation synchronizes with the
            //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value
            //   is visible here.
            // * We checked that `id.generation` matches the slot's generation, which means that the
            //   state tag of the slot must have been `OCCUPIED_TAG`, which means it must have been
            //   initialized in `SlotMap::insert[_mut]`.
            Some(unsafe { slot.value_unchecked() })
        } else {
            None
        }
    }

    #[inline(always)]
    fn get_mut(&mut self, id: SlotId) -> Option<&mut V> {
        let slot = self.slots.get_mut(id.index)?;
        let generation = *slot.generation.get_mut();

        if generation == id.generation() {
            // SAFETY:
            // * The mutable reference makes sure that access to the slot is synchronized.
            // * We checked that `id.generation` matches the slot's generation, which means that the
            //   state tag of the slot must have been `OCCUPIED_TAG`, which means it must have been
            //   initialized in `SlotMap::insert[_mut]`.
            Some(unsafe { slot.value_unchecked_mut() })
        } else {
            None
        }
    }

    #[inline]
    fn get_disjoint_mut<const N: usize>(&mut self, ids: [SlotId; N]) -> Option<[&mut V; N]> {
        fn get_disjoint_check_valid<const N: usize>(ids: &[SlotId; N], len: u32) -> bool {
            let mut valid = true;

            for (i, id) in ids.iter().enumerate() {
                valid &= id.index < len;

                for id2 in &ids[..i] {
                    valid &= id.index != id2.index;
                }
            }

            valid
        }

        let len = self.slots.capacity_mut();

        if get_disjoint_check_valid(&ids, len) {
            // SAFETY: We checked that all indices are disjunct and in bounds of the slots vector.
            unsafe { self.get_disjoint_unchecked_mut(ids) }
        } else {
            None
        }
    }

    #[inline]
    unsafe fn get_disjoint_unchecked_mut<const N: usize>(
        &mut self,
        ids: [SlotId; N],
    ) -> Option<[&mut V; N]> {
        let mut refs = MaybeUninit::<[&mut V; N]>::uninit();
        let refs_ptr = refs.as_mut_ptr().cast::<&mut V>();

        for i in 0..N {
            // SAFETY: `i` is in bounds of the array.
            let id = unsafe { ids.get_unchecked(i) };

            // SAFETY:
            // * The caller must ensure that `ids` contains only IDs whose indices are in bounds of
            //   the slots vector.
            // * The caller must ensure that `ids` contains only IDs with disjunct indices.
            let slot = unsafe { self.slots.get_unchecked_mut(id.index) };

            // SAFETY: We unbind the lifetime to convince the borrow checker that we don't
            // repeatedly borrow from `self.slots`. We don't for the same reasons as above.
            // `Vec::get_unchecked_mut` also only borrows the one element and not the whole `Vec`.
            let slot = unsafe { mem::transmute::<&mut Slot<V>, &mut Slot<V>>(slot) };

            let generation = *slot.generation.get_mut();

            if generation != id.generation() {
                return None;
            }

            // SAFETY:
            // * The mutable reference makes sure that access to the slot is synchronized.
            // * We checked that `id.generation` matches the slot's generation, which means that the
            //   state tag of the slot must have been `OCCUPIED_TAG`, which means it must have been
            //   initialized in `SlotMap::insert[_mut]`.
            let value = unsafe { slot.value_unchecked_mut() };

            // SAFETY: `i` is in bounds of the array.
            unsafe { *refs_ptr.add(i) = value };
        }

        // SAFETY: We initialized all the elements.
        Some(unsafe { refs.assume_init() })
    }

    #[cfg(test)]
    fn index<'a>(&'a self, index: u32, guard: &'a hyaline::Guard<'a>) -> Option<&'a V> {
        self.check_guard(guard);

        let slot = self.slots.get(index)?;
        let generation = slot.generation.load(Acquire);

        if is_occupied(generation) {
            // SAFETY:
            // * The `Acquire` ordering when loading the slot's generation synchronizes with the
            //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value
            //   is visible here.
            // * We checked that the slot is occupied, which means that it must have been
            //   initialized in `SlotMap::insert[_mut]`.
            Some(unsafe { slot.value_unchecked() })
        } else {
            None
        }
    }

    #[inline(always)]
    #[track_caller]
    unsafe fn get_unchecked<'a>(&'a self, id: SlotId, guard: &'a hyaline::Guard<'a>) -> &'a V {
        self.check_guard(guard);

        // SAFETY: The caller must ensure that the index is in bounds.
        let slot = unsafe { self.slots.get_unchecked(id.index) };

        let _generation = slot.generation.load(Acquire);

        // SAFETY:
        // * The `Acquire` ordering when loading the slot's generation synchronizes with the
        //   `Release` ordering in `SlotMap::insert`, making sure that the newly written value is
        //   visible here.
        // * The caller must ensure that the slot is initialized.
        unsafe { slot.value_unchecked() }
    }

    #[inline(always)]
    unsafe fn get_unchecked_mut(&mut self, id: SlotId) -> &mut V {
        // SAFETY: The caller must ensure that the index is in bounds.
        let slot = unsafe { self.slots.get_unchecked_mut(id.index) };

        // SAFETY:
        // * The mutable reference makes sure that access to the slot is synchronized.
        // * The caller must ensure that the slot is initialized.
        unsafe { slot.value_unchecked_mut() }
    }

    #[inline]
    fn collector(&self) -> &hyaline::CollectorHandle {
        &self.collector
    }

    #[inline]
    fn header(&self) -> &Header {
        self.slots.header()
    }

    #[inline(always)]
    #[track_caller]
    fn check_guard(&self, guard: &hyaline::Guard<'_>) {
        #[inline(never)]
        #[track_caller]
        fn collector_mismatch() -> ! {
            panic!("the given guard does not belong to this collection");
        }

        if guard.collector() != self.collector() {
            collector_mismatch();
        }
    }
}

impl<V> SlotMapInner<MaybeUninit<V>> {
    #[track_caller]
    fn revive_or_insert_with<'a>(
        &'a self,
        guard: &'a hyaline::Guard<'a>,
        f: impl FnOnce(SlotId) -> MaybeUninit<V>,
    ) -> (SlotId, &'a MaybeUninit<V>) {
        let (id, slot) = if let Some((id, slot)) = self.allocate_slot(0, guard) {
            slot.generation.store(id.generation(), Release);

            (id, slot)
        } else {
            self.slots.push_with_tag_with(0, f)
        };

        self.header().shard().len.fetch_add(1, Relaxed);

        // SAFETY: The value is wrapped in `MaybeUninit`.
        (id, unsafe { slot.value_unchecked() })
    }
}

unsafe fn reclaim<V>(index: u32, slots: *const Slot<V>) {
    // SAFETY: The caller must ensure that `index` is in bounds of `slots` and that `slots` is a
    // valid pointer to the allocation of `Slot<V>`s.
    let slot = unsafe { &*slots.add(index as usize) };

    // SAFETY: The caller must ensure that we have exclusive access to the slot.
    unsafe { slot.value.get().cast::<V>().drop_in_place() };

    // SAFETY: The caller must ensure that `slots` is a valid pointer to the allocation of
    // `Slot<V>`s, and that allocation has the `Header` right before the start of the slots.
    let header = unsafe { &*header_ptr_from_slots(slots.cast()) };

    let shard = header.shard();

    let mut free_list_head = shard.free_list.load(Acquire);
    let mut backoff = Backoff::new();

    loop {
        slot.next_free.store(free_list_head, Relaxed);

        match shard
            .free_list
            .compare_exchange_weak(free_list_head, index, Release, Acquire)
        {
            Ok(_) => break,
            Err(new_head) => {
                free_list_head = new_head;
                backoff.spin();
            }
        }
    }
}

unsafe fn reclaim_invalidated<V>(index: u32, slots: *const Slot<V>) {
    // SAFETY: The caller must ensure that `index` is in bounds of `slots` and that `slots` is a
    // valid pointer to the allocation of `Slot<V>`s.
    let slot = unsafe { &*slots.add(index as usize) };

    let mut generation = slot.generation.load(Relaxed);

    while generation & STATE_MASK == INVALIDATED_TAG {
        let new_generation = (generation & !STATE_MASK) | RECLAIMED_TAG;

        match slot
            .generation
            .compare_exchange_weak(generation, new_generation, Relaxed, Relaxed)
        {
            Ok(_) => return,
            Err(new_generation) => generation = new_generation,
        }
    }

    debug_assert!(generation & STATE_MASK == VACANT_TAG);

    atomic::fence(Acquire);

    // SAFETY:
    // * The `Acquire` fence after loading the slot's generation synchronizes with the `Release`
    //   ordering in `SlotMap::insert`, making sure that the newly written value is visible here.
    // * The previous state tag of the slot must have been `VACANT_TAG`, which means it must have
    //   been removed in `SlotMap::remove_invalidated`, which means it must have been invalidated in
    //   `SlotMap::invalidate`, which means it must have been initialized in
    //   `SlotMap::insert[_mut]`.
    unsafe { reclaim(index, slots) };
}

impl<K: fmt::Debug + Key, V: fmt::Debug> fmt::Debug for SlotMap<K, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SlotMap").finish_non_exhaustive()
    }
}

impl<V> Drop for SlotMapInner<V> {
    fn drop(&mut self) {
        if !core::mem::needs_drop::<V>() {
            return;
        }

        for slot in self.slots.iter_mut() {
            if *slot.generation.get_mut() & STATE_MASK != VACANT_TAG {
                let ptr = slot.value.get_mut().as_mut_ptr();

                // SAFETY:
                // * The mutable reference makes sure that access to the slot is synchronized.
                // * We checked that the slot is not vacant, which means that it must have been
                //   initialized in `SlotMap::insert[_mut]`.
                unsafe { ptr.drop_in_place() };
            }
        }
    }
}

impl<'a, K: Key, V> IntoIterator for &'a mut SlotMap<K, V> {
    type Item = (K, &'a mut V);

    type IntoIter = IterMut<'a, K, V>;

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

impl Header {
    #[inline]
    fn shard(&self) -> &HeaderShard {
        let shard_index = SHARD_INDEX.with(Cell::get);

        // SAFETY: `set_shard_index` ensures that `SHARD_INDEX` is in bounds of the shards.
        unsafe { self.shards.get_unchecked(shard_index) }
    }

    #[inline]
    fn shard_mut(&mut self) -> &mut HeaderShard {
        // SAFETY: There is always a non-zero number of shards.
        unsafe { self.shards.get_unchecked_mut(0) }
    }

    #[inline]
    fn shards(&self) -> HeaderShards<'_> {
        let shard_index = SHARD_INDEX.with(Cell::get);

        HeaderShards {
            shards: &self.shards,
            shard_index,
            yielded: 0,
        }
    }

    #[inline]
    fn shards_mut(&mut self) -> slice::IterMut<'_, HeaderShard> {
        self.shards.iter_mut()
    }

    #[inline]
    fn len(&self) -> u32 {
        self.shards()
            .map(|shard| shard.len.load(Relaxed))
            .sum::<i32>()
            .try_into()
            .unwrap_or(0)
    }
}

struct HeaderShards<'a> {
    shards: &'a [HeaderShard],
    shard_index: usize,
    yielded: usize,
}

impl<'a> Iterator for HeaderShards<'a> {
    type Item = &'a HeaderShard;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.yielded < self.shards.len() {
            let current_index = (self.shard_index + self.yielded) & (self.shards.len() - 1);
            self.yielded += 1;

            // SAFETY: `Header::shards` ensures that `current_index` starts out in bounds of the
            // shards and we made sure that the next iteration has an index that's in bounds too.
            Some(unsafe { self.shards.get_unchecked(current_index) })
        } else {
            None
        }
    }
}

#[inline(never)]
fn set_shard_index() {
    let mut state = DefaultHasher::new();
    thread::current().id().hash(&mut state);
    let thread_id_hash = state.finish();

    let shard_count = SHARD_COUNT.load(Relaxed);
    let shard_index = (thread_id_hash & (shard_count as u64 - 1)) as usize;
    SHARD_INDEX.with(|cell| cell.set(shard_index));
}

pub trait Key: Sized {
    fn from_id(id: SlotId) -> Self;

    #[allow(clippy::wrong_self_convention)]
    fn as_id(self) -> SlotId;
}

impl Key for SlotId {
    #[inline(always)]
    fn from_id(id: SlotId) -> Self {
        id
    }

    #[inline(always)]
    fn as_id(self) -> SlotId {
        self
    }
}

#[derive(Clone, Copy)]
#[repr(C, align(8))]
pub struct SlotId {
    #[cfg(target_endian = "little")]
    index: u32,
    generation: NonZeroU32,
    #[cfg(target_endian = "big")]
    index: u32,
}

impl Default for SlotId {
    #[inline]
    fn default() -> Self {
        Self::INVALID
    }
}

impl SlotId {
    pub const INVALID: Self = SlotId {
        index: u32::MAX,
        generation: NonZeroU32::MAX,
    };

    pub const TAG_BITS: u32 = TAG_BITS;

    pub const TAG_MASK: u32 = TAG_MASK;

    pub const STATE_BITS: u32 = STATE_BITS;

    pub const STATE_MASK: u32 = STATE_MASK;

    pub const OCCUPIED_TAG: u32 = OCCUPIED_TAG;

    #[inline(always)]
    #[must_use]
    #[track_caller]
    pub const fn new(index: u32, generation: u32) -> Self {
        assert!(is_occupied(generation));

        // SAFETY: We checked that the state tag of `generation` is `OCCUPIED_TAG`.
        unsafe { SlotId::new_unchecked(index, generation) }
    }

    /// # Safety
    ///
    /// `generation`, when masked out with [`STATE_MASK`], must equal [`OCCUPIED_TAG`].
    ///
    /// [`STATE_MASK`]: Self::STATE_MASK
    /// [`OCCUPIED_TAG`]: Self::OCCUPIED_TAG
    #[inline(always)]
    #[must_use]
    pub const unsafe fn new_unchecked(index: u32, generation: u32) -> Self {
        // TODO: Replace with `assert_unsafe_precondition` when it can be made const.
        debug_assert!(is_occupied(generation));

        // SAFETY: The caller must ensure that the state tag of `generation` is `OCCUPIED_TAG`.
        let generation = unsafe { NonZeroU32::new_unchecked(generation) };

        SlotId { index, generation }
    }

    #[inline(always)]
    #[must_use]
    pub const fn index(self) -> u32 {
        self.index
    }

    #[inline(always)]
    #[must_use]
    pub const fn generation(self) -> u32 {
        self.generation.get()
    }

    #[inline(always)]
    #[must_use]
    pub const fn tag(self) -> u32 {
        self.generation.get() & TAG_MASK
    }

    #[inline]
    fn as_u64(self) -> u64 {
        u64::from(self.index) | (u64::from(self.generation.get()) << 32)
    }
}

impl fmt::Debug for SlotId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if *self == Self::INVALID {
            return f.write_str("INVALID");
        }

        let generation = self.generation() >> (TAG_BITS + STATE_BITS);
        write!(f, "{}v{}", self.index, generation)?;

        if self.generation() & TAG_MASK != 0 {
            write!(f, "t{}", self.generation() & TAG_MASK)?;
        }

        Ok(())
    }
}

impl PartialEq for SlotId {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        self.as_u64() == other.as_u64()
    }
}

impl Eq for SlotId {}

impl Hash for SlotId {
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.as_u64().hash(state);
    }
}

impl PartialOrd for SlotId {
    #[inline]
    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for SlotId {
    #[inline]
    fn cmp(&self, other: &Self) -> cmp::Ordering {
        self.as_u64().cmp(&other.as_u64())
    }
}

#[macro_export]
macro_rules! declare_key {
    (
        $(#[$meta:meta])*
        $vis:vis struct $name:ident $(;)?
    ) => {
        $(#[$meta])*
        #[repr(transparent)]
        $vis struct $name($crate::SlotId);

        impl $crate::Key for $name {
            #[inline(always)]
            fn from_id(id: $crate::SlotId) -> Self {
                $name(id)
            }

            #[inline(always)]
            fn as_id(self) -> $crate::SlotId {
                self.0
            }
        }
    };
}

pub struct Iter<'a, K, V> {
    slots: iter::Enumerate<slice::Iter<'a, Slot<V>>>,
    marker: PhantomData<fn(K) -> K>,
}

impl<K, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Iter").finish_non_exhaustive()
    }
}

impl<'a, K: Key, V> Iterator for Iter<'a, K, V> {
    type Item = (K, &'a V);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let (index, slot) = self.slots.next()?;
            let generation = slot.generation.load(Acquire);

            if is_occupied(generation) {
                // Our capacity can never exceed `u32::MAX`.
                #[allow(clippy::cast_possible_truncation)]
                let index = index as u32;

                // SAFETY: We checked that the occupied bit is set.
                let id = unsafe { SlotId::new_unchecked(index, generation) };

                // SAFETY:
                // * The `Acquire` ordering when loading the slot's generation synchronizes with the
                //   `Release` ordering in `SlotMap::insert`, making sure that the newly written
                //   value is visible here.
                // * We checked that the slot is occupied, which means that it must have been
                //   initialized in `SlotMap::insert[_mut]`.
                let r = unsafe { slot.value_unchecked() };

                break Some((K::from_id(id), r));
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.slots.len()))
    }
}

impl<K: Key, V> DoubleEndedIterator for Iter<'_, K, V> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        loop {
            let (index, slot) = self.slots.next_back()?;
            let generation = slot.generation.load(Acquire);

            if is_occupied(generation) {
                // Our capacity can never exceed `u32::MAX`.
                #[allow(clippy::cast_possible_truncation)]
                let index = index as u32;

                // SAFETY: We checked that the occupied bit is set.
                let id = unsafe { SlotId::new_unchecked(index, generation) };

                // SAFETY:
                // * The `Acquire` ordering when loading the slot's generation synchronizes with the
                //   `Release` ordering in `SlotMap::insert`, making sure that the newly written
                //   value is visible here.
                // * We checked that the slot is occupied, which means that it must have been
                //   initialized in `SlotMap::insert[_mut]`.
                let r = unsafe { slot.value_unchecked() };

                break Some((K::from_id(id), r));
            }
        }
    }
}

impl<K: Key, V> FusedIterator for Iter<'_, K, V> {}

pub struct IterMut<'a, K, V> {
    slots: iter::Enumerate<slice::IterMut<'a, Slot<V>>>,
    marker: PhantomData<fn(K) -> K>,
}

impl<K, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("IterMut").finish_non_exhaustive()
    }
}

impl<'a, K: Key, V> Iterator for IterMut<'a, K, V> {
    type Item = (K, &'a mut V);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let (index, slot) = self.slots.next()?;
            let generation = *slot.generation.get_mut();

            if is_occupied(generation) {
                // Our capacity can never exceed `u32::MAX`.
                #[allow(clippy::cast_possible_truncation)]
                let index = index as u32;

                // SAFETY: We checked that the `OCCUPIED_BIT` is set.
                let id = unsafe { SlotId::new_unchecked(index, generation) };

                // SAFETY: We checked that the slot is occupied, which means that it must have been
                // initialized in `SlotMap::insert[_mut]`.
                let r = unsafe { slot.value_unchecked_mut() };

                break Some((K::from_id(id), r));
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.slots.len()))
    }
}

impl<K: Key, V> DoubleEndedIterator for IterMut<'_, K, V> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        loop {
            let (index, slot) = self.slots.next_back()?;
            let generation = *slot.generation.get_mut();

            if is_occupied(generation) {
                // Our capacity can never exceed `u32::MAX`.
                #[allow(clippy::cast_possible_truncation)]
                let index = index as u32;

                // SAFETY: We checked that the `OCCUPIED_BIT` is set.
                let id = unsafe { SlotId::new_unchecked(index, generation) };

                // SAFETY: We checked that the slot is occupied, which means that it must have been
                // initialized in `SlotMap::insert[_mut]`.
                let r = unsafe { slot.value_unchecked_mut() };

                break Some((K::from_id(id), r));
            }
        }
    }
}

impl<K: Key, V> FusedIterator for IterMut<'_, K, V> {}

pub struct Slots<'a, V> {
    slots: slice::Iter<'a, Slot<V>>,
}

impl<V: fmt::Debug> fmt::Debug for Slots<'_, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Slots").finish_non_exhaustive()
    }
}

impl<'a, V> Iterator for Slots<'a, V> {
    type Item = &'a Slot<V>;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.slots.next()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.slots.size_hint()
    }
}

impl<V> DoubleEndedIterator for Slots<'_, V> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.slots.next_back()
    }
}

impl<V> FusedIterator for Slots<'_, V> {}

const fn is_occupied(generation: u32) -> bool {
    generation & STATE_MASK == OCCUPIED_TAG
}

const SPIN_LIMIT: u32 = 6;

struct Backoff {
    step: u32,
}

impl Backoff {
    fn new() -> Self {
        Backoff { step: 0 }
    }

    fn spin(&mut self) {
        for _ in 0..1 << self.step {
            hint::spin_loop();
        }

        if self.step <= SPIN_LIMIT {
            self.step += 1;
        }
    }
}

macro_rules! assert_unsafe_precondition {
    ($condition:expr, $message:expr $(,)?) => {
        // The nesting is intentional. There is a special path in the compiler for `if false`
        // facilitating conditional compilation without `#[cfg]` and the problems that come with it.
        if cfg!(debug_assertions) {
            if !$condition {
                crate::panic_nounwind(concat!("unsafe precondition(s) validated: ", $message));
            }
        }
    };
}
use assert_unsafe_precondition;

/// Polyfill for `core::panicking::panic_nounwind`.
#[cold]
#[inline(never)]
fn panic_nounwind(message: &'static str) -> ! {
    struct UnwindGuard;

    impl Drop for UnwindGuard {
        fn drop(&mut self) {
            panic!();
        }
    }

    let _guard = UnwindGuard;
    std::panic::panic_any(message);
}

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

    #[test]
    fn basic_usage1() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(69, guard);
        let y = map.insert(42, guard);

        assert_eq!(map.get(x, guard), Some(&69));
        assert_eq!(map.get(y, guard), Some(&42));

        map.remove(x, guard);

        let x2 = map.insert(12, guard);

        assert_eq!(map.get(x2, guard), Some(&12));
        assert_eq!(map.get(x, guard), None);

        map.remove(y, guard);
        map.remove(x2, guard);

        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.get(x2, guard), None);
    }

    #[test]
    fn basic_usage2() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(1, guard);
        let y = map.insert(2, guard);
        let z = map.insert(3, guard);

        assert_eq!(map.get(x, guard), Some(&1));
        assert_eq!(map.get(y, guard), Some(&2));
        assert_eq!(map.get(z, guard), Some(&3));

        map.remove(y, guard);

        let y2 = map.insert(20, guard);

        assert_eq!(map.get(y2, guard), Some(&20));
        assert_eq!(map.get(y, guard), None);

        map.remove(x, guard);
        map.remove(z, guard);

        let x2 = map.insert(10, guard);

        assert_eq!(map.get(x2, guard), Some(&10));
        assert_eq!(map.get(x, guard), None);

        let z2 = map.insert(30, guard);

        assert_eq!(map.get(z2, guard), Some(&30));
        assert_eq!(map.get(x, guard), None);

        map.remove(x2, guard);

        assert_eq!(map.get(x2, guard), None);

        map.remove(y2, guard);
        map.remove(z2, guard);

        assert_eq!(map.get(y2, guard), None);
        assert_eq!(map.get(z2, guard), None);
    }

    #[test]
    fn basic_usage3() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(1, guard);
        let y = map.insert(2, guard);

        assert_eq!(map.get(x, guard), Some(&1));
        assert_eq!(map.get(y, guard), Some(&2));

        let z = map.insert(3, guard);

        assert_eq!(map.get(z, guard), Some(&3));

        map.remove(x, guard);
        map.remove(z, guard);

        let z2 = map.insert(30, guard);
        let x2 = map.insert(10, guard);

        assert_eq!(map.get(x2, guard), Some(&10));
        assert_eq!(map.get(z2, guard), Some(&30));
        assert_eq!(map.get(x, guard), None);
        assert_eq!(map.get(z, guard), None);

        map.remove(x2, guard);
        map.remove(y, guard);
        map.remove(z2, guard);

        assert_eq!(map.get(x2, guard), None);
        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.get(z2, guard), None);
    }

    #[test]
    fn basic_usage_invalidated1() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(69, guard);
        let y = map.insert(42, guard);

        assert_eq!(map.get(x, guard), Some(&69));
        assert_eq!(map.get(y, guard), Some(&42));

        map.invalidate(x, guard);
        map.remove_invalidated(x);

        let x2 = map.insert(12, guard);

        assert_eq!(map.get(x2, guard), Some(&12));
        assert_eq!(map.get(x, guard), None);

        map.invalidate(y, guard);
        map.invalidate(x2, guard);

        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.get(x2, guard), None);

        map.remove_invalidated(y);
        map.remove_invalidated(x2);

        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.get(x2, guard), None);
    }

    #[test]
    fn basic_usage_invalidated2() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(1, guard);
        let y = map.insert(2, guard);
        let z = map.insert(3, guard);

        assert_eq!(map.get(x, guard), Some(&1));
        assert_eq!(map.get(y, guard), Some(&2));
        assert_eq!(map.get(z, guard), Some(&3));

        map.invalidate(y, guard);
        map.remove_invalidated(y);

        let y2 = map.insert(20, guard);

        assert_eq!(map.get(y2, guard), Some(&20));
        assert_eq!(map.get(y, guard), None);

        map.invalidate(x, guard);
        map.invalidate(z, guard);
        map.remove_invalidated(x);
        map.remove_invalidated(z);

        let x2 = map.insert(10, guard);

        assert_eq!(map.get(x2, guard), Some(&10));
        assert_eq!(map.get(x, guard), None);

        let z2 = map.insert(30, guard);

        assert_eq!(map.get(z2, guard), Some(&30));
        assert_eq!(map.get(x, guard), None);

        map.invalidate(x2, guard);

        assert_eq!(map.get(x2, guard), None);

        map.remove_invalidated(x2);

        assert_eq!(map.get(x2, guard), None);

        map.invalidate(y2, guard);
        map.invalidate(z2, guard);

        assert_eq!(map.get(y2, guard), None);
        assert_eq!(map.get(z2, guard), None);

        map.remove_invalidated(y2);
        map.remove_invalidated(z2);

        assert_eq!(map.get(y2, guard), None);
        assert_eq!(map.get(z2, guard), None);
    }

    #[test]
    fn basic_usage_invalidated3() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(1, guard);
        let y = map.insert(2, guard);

        assert_eq!(map.get(x, guard), Some(&1));
        assert_eq!(map.get(y, guard), Some(&2));

        let z = map.insert(3, guard);

        assert_eq!(map.get(z, guard), Some(&3));

        map.invalidate(x, guard);
        map.invalidate(z, guard);
        map.remove_invalidated(x);
        map.remove_invalidated(z);

        let z2 = map.insert(30, guard);
        let x2 = map.insert(10, guard);

        assert_eq!(map.get(x2, guard), Some(&10));
        assert_eq!(map.get(z2, guard), Some(&30));
        assert_eq!(map.get(x, guard), None);
        assert_eq!(map.get(z, guard), None);

        map.invalidate(x2, guard);
        map.invalidate(y, guard);
        map.invalidate(z2, guard);

        assert_eq!(map.get(x2, guard), None);
        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.get(z2, guard), None);

        map.remove_invalidated(x2);
        map.remove_invalidated(y);
        map.remove_invalidated(z2);

        assert_eq!(map.get(x2, guard), None);
        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.get(z2, guard), None);
    }

    #[test]
    fn basic_usage_mut1() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(69);
        let y = map.insert_mut(42);

        assert_eq!(map.get_mut(x), Some(&mut 69));
        assert_eq!(map.get_mut(y), Some(&mut 42));

        map.remove_mut(x);

        let x2 = map.insert_mut(12);

        assert_eq!(map.get_mut(x2), Some(&mut 12));
        assert_eq!(map.get_mut(x), None);

        map.remove_mut(y);
        map.remove_mut(x2);

        assert_eq!(map.get_mut(y), None);
        assert_eq!(map.get_mut(x2), None);
    }

    #[test]
    fn basic_usage_mut2() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(1);
        let y = map.insert_mut(2);
        let z = map.insert_mut(3);

        assert_eq!(map.get_mut(x), Some(&mut 1));
        assert_eq!(map.get_mut(y), Some(&mut 2));
        assert_eq!(map.get_mut(z), Some(&mut 3));

        map.remove_mut(y);

        let y2 = map.insert_mut(20);

        assert_eq!(map.get_mut(y2), Some(&mut 20));
        assert_eq!(map.get_mut(y), None);

        map.remove_mut(x);
        map.remove_mut(z);

        let x2 = map.insert_mut(10);

        assert_eq!(map.get_mut(x2), Some(&mut 10));
        assert_eq!(map.get_mut(x), None);

        let z2 = map.insert_mut(30);

        assert_eq!(map.get_mut(z2), Some(&mut 30));
        assert_eq!(map.get_mut(x), None);

        map.remove_mut(x2);

        assert_eq!(map.get_mut(x2), None);

        map.remove_mut(y2);
        map.remove_mut(z2);

        assert_eq!(map.get_mut(y2), None);
        assert_eq!(map.get_mut(z2), None);
    }

    #[test]
    fn basic_usage_mut3() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(1);
        let y = map.insert_mut(2);

        assert_eq!(map.get_mut(x), Some(&mut 1));
        assert_eq!(map.get_mut(y), Some(&mut 2));

        let z = map.insert_mut(3);

        assert_eq!(map.get_mut(z), Some(&mut 3));

        map.remove_mut(x);
        map.remove_mut(z);

        let z2 = map.insert_mut(30);
        let x2 = map.insert_mut(10);

        assert_eq!(map.get_mut(x2), Some(&mut 10));
        assert_eq!(map.get_mut(z2), Some(&mut 30));
        assert_eq!(map.get_mut(x), None);
        assert_eq!(map.get_mut(z), None);

        map.remove_mut(x2);
        map.remove_mut(y);
        map.remove_mut(z2);

        assert_eq!(map.get_mut(x2), None);
        assert_eq!(map.get_mut(y), None);
        assert_eq!(map.get_mut(z2), None);
    }

    #[test]
    fn iter1() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(1, guard);
        let _ = map.insert(2, guard);
        let y = map.insert(3, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove(x, guard);
        map.remove(y, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 2);
        assert!(iter.next().is_none());

        map.insert(3, guard);
        map.insert(1, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert_eq!(*iter.next().unwrap().1, 1);
        assert!(iter.next().is_none());
    }

    #[test]
    fn iter2() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let x = map.insert(1, guard);
        let y = map.insert(2, guard);
        let z = map.insert(3, guard);

        map.remove(x, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove(y, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove(z, guard);

        let mut iter = map.iter(guard);

        assert!(iter.next().is_none());
    }

    #[test]
    fn iter3() {
        let map = SlotMap::new(10);
        let guard = &map.pin();

        let _ = map.insert(1, guard);
        let x = map.insert(2, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 2);
        assert!(iter.next().is_none());

        map.remove(x, guard);

        let x = map.insert(2, guard);
        let _ = map.insert(3, guard);
        let y = map.insert(4, guard);

        map.remove(y, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove(x, guard);

        let mut iter = map.iter(guard);

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());
    }

    #[test]
    fn iter_mut1() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(1);
        let _ = map.insert_mut(2);
        let y = map.insert_mut(3);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove_mut(x);
        map.remove_mut(y);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 2);
        assert!(iter.next().is_none());

        map.insert_mut(3);
        map.insert_mut(1);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());
    }

    #[test]
    fn iter_mut2() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(1);
        let y = map.insert_mut(2);
        let z = map.insert_mut(3);

        map.remove_mut(x);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove_mut(y);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove_mut(z);

        let mut iter = map.iter_mut();

        assert!(iter.next().is_none());
    }

    #[test]
    fn iter_mut3() {
        let mut map = SlotMap::new(10);

        let _ = map.insert_mut(1);
        let x = map.insert_mut(2);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 2);
        assert!(iter.next().is_none());

        map.remove_mut(x);

        let x = map.insert_mut(2);
        let _ = map.insert_mut(3);
        let y = map.insert_mut(4);

        map.remove_mut(y);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 2);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());

        map.remove_mut(x);

        let mut iter = map.iter_mut();

        assert_eq!(*iter.next().unwrap().1, 1);
        assert_eq!(*iter.next().unwrap().1, 3);
        assert!(iter.next().is_none());
    }

    #[test]
    fn reusing_slots1() {
        let map = SlotMap::new(10);

        let x = map.insert(0, &map.pin());
        let y = map.insert(0, &map.pin());

        map.remove(y, &map.pin());
        map.pin().flush();

        let y2 = map.insert(0, &map.pin());
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.remove(x, &map.pin());
        map.pin().flush();

        let x2 = map.insert(0, &map.pin());
        assert_eq!(x2.index, x.index);
        assert_ne!(x2.generation, x.generation);

        map.remove(y2, &map.pin());
        map.remove(x2, &map.pin());
    }

    #[test]
    fn reusing_slots2() {
        let map = SlotMap::new(10);

        let x = map.insert(0, &map.pin());

        map.remove(x, &map.pin());
        map.pin().flush();

        let x2 = map.insert(0, &map.pin());
        assert_eq!(x.index, x2.index);
        assert_ne!(x.generation, x2.generation);

        let y = map.insert(0, &map.pin());
        let z = map.insert(0, &map.pin());

        map.remove(y, &map.pin());
        map.remove(x2, &map.pin());
        map.pin().flush();

        let x3 = map.insert(0, &map.pin());
        let y2 = map.insert(0, &map.pin());
        assert_eq!(x3.index, x2.index);
        assert_ne!(x3.generation, x2.generation);
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.remove(x3, &map.pin());
        map.remove(y2, &map.pin());
        map.remove(z, &map.pin());
    }

    #[test]
    fn reusing_slots3() {
        let map = SlotMap::new(10);

        let x = map.insert(0, &map.pin());
        let y = map.insert(0, &map.pin());

        map.remove(x, &map.pin());
        map.remove(y, &map.pin());
        map.pin().flush();

        let y2 = map.insert(0, &map.pin());
        let x2 = map.insert(0, &map.pin());
        let z = map.insert(0, &map.pin());
        assert_eq!(x2.index, x.index);
        assert_ne!(x2.generation, x.generation);
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.remove(x2, &map.pin());
        map.remove(z, &map.pin());
        map.remove(y2, &map.pin());
        map.pin().flush();

        let y3 = map.insert(0, &map.pin());
        let z2 = map.insert(0, &map.pin());
        let x3 = map.insert(0, &map.pin());
        assert_eq!(y3.index, y2.index);
        assert_ne!(y3.generation, y2.generation);
        assert_eq!(z2.index, z.index);
        assert_ne!(z2.generation, z.generation);
        assert_eq!(x3.index, x2.index);
        assert_ne!(x3.generation, x2.generation);

        map.remove(x3, &map.pin());
        map.remove(y3, &map.pin());
        map.remove(z2, &map.pin());
    }

    #[test]
    fn reusing_slots_invalidated1() {
        let map = SlotMap::new(10);

        let x = map.insert(0, &map.pin());
        let y = map.insert(0, &map.pin());

        map.invalidate(y, &map.pin());
        map.remove_invalidated(y);
        map.pin().flush();

        let y2 = map.insert(0, &map.pin());
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.invalidate(x, &map.pin());
        map.remove_invalidated(x);
        map.pin().flush();

        let x2 = map.insert(0, &map.pin());
        assert_eq!(x2.index, x.index);
        assert_ne!(x2.generation, x.generation);

        map.invalidate(y2, &map.pin());
        map.invalidate(x2, &map.pin());
        map.remove_invalidated(y2);
        map.remove_invalidated(x2);
    }

    #[test]
    fn reusing_slots_invalidated2() {
        let map = SlotMap::new(10);

        let x = map.insert(0, &map.pin());

        map.invalidate(x, &map.pin());
        map.remove_invalidated(x);
        map.pin().flush();

        let x2 = map.insert(0, &map.pin());
        assert_eq!(x.index, x2.index);
        assert_ne!(x.generation, x2.generation);

        let y = map.insert(0, &map.pin());
        let z = map.insert(0, &map.pin());

        map.invalidate(y, &map.pin());
        map.invalidate(x2, &map.pin());
        map.remove_invalidated(y);
        map.remove_invalidated(x2);
        map.pin().flush();

        let x3 = map.insert(0, &map.pin());
        let y2 = map.insert(0, &map.pin());
        assert_eq!(x3.index, x2.index);
        assert_ne!(x3.generation, x2.generation);
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.invalidate(x3, &map.pin());
        map.invalidate(y2, &map.pin());
        map.invalidate(z, &map.pin());
        map.remove_invalidated(x3);
        map.remove_invalidated(y2);
        map.remove_invalidated(z);
    }

    #[test]
    fn reusing_slots_invalidated3() {
        let map = SlotMap::new(10);

        let x = map.insert(0, &map.pin());
        let y = map.insert(0, &map.pin());

        map.remove(x, &map.pin());
        map.remove(y, &map.pin());
        map.pin().flush();

        let y2 = map.insert(0, &map.pin());
        let x2 = map.insert(0, &map.pin());
        let z = map.insert(0, &map.pin());
        assert_eq!(x2.index, x.index);
        assert_ne!(x2.generation, x.generation);
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.remove(x2, &map.pin());
        map.remove(z, &map.pin());
        map.remove(y2, &map.pin());
        map.pin().flush();

        let y3 = map.insert(0, &map.pin());
        let z2 = map.insert(0, &map.pin());
        let x3 = map.insert(0, &map.pin());
        assert_eq!(y3.index, y2.index);
        assert_ne!(y3.generation, y2.generation);
        assert_eq!(z2.index, z.index);
        assert_ne!(z2.generation, z.generation);
        assert_eq!(x3.index, x2.index);
        assert_ne!(x3.generation, x2.generation);

        map.remove(x3, &map.pin());
        map.remove(y3, &map.pin());
        map.remove(z2, &map.pin());
    }

    #[test]
    fn reusing_slots_mut1() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(0);
        let y = map.insert_mut(0);

        map.remove_mut(y);

        let y2 = map.insert_mut(0);
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.remove_mut(x);

        let x2 = map.insert_mut(0);
        assert_eq!(x2.index, x.index);
        assert_ne!(x2.generation, x.generation);

        map.remove_mut(y2);
        map.remove_mut(x2);
    }

    #[test]
    fn reusing_slots_mut2() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(0);

        map.remove_mut(x);

        let x2 = map.insert_mut(0);
        assert_eq!(x.index, x2.index);
        assert_ne!(x.generation, x2.generation);

        let y = map.insert_mut(0);
        let z = map.insert_mut(0);

        map.remove_mut(y);
        map.remove_mut(x2);

        let x3 = map.insert_mut(0);
        let y2 = map.insert_mut(0);
        assert_eq!(x3.index, x2.index);
        assert_ne!(x3.generation, x2.generation);
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.remove_mut(x3);
        map.remove_mut(y2);
        map.remove_mut(z);
    }

    #[test]
    fn reusing_slots_mut3() {
        let mut map = SlotMap::new(10);

        let x = map.insert_mut(0);
        let y = map.insert_mut(0);

        map.remove_mut(x);
        map.remove_mut(y);

        let y2 = map.insert_mut(0);
        let x2 = map.insert_mut(0);
        let z = map.insert_mut(0);
        assert_eq!(x2.index, x.index);
        assert_ne!(x2.generation, x.generation);
        assert_eq!(y2.index, y.index);
        assert_ne!(y2.generation, y.generation);

        map.remove_mut(x2);
        map.remove_mut(z);
        map.remove_mut(y2);

        let y3 = map.insert_mut(0);
        let z2 = map.insert_mut(0);
        let x3 = map.insert_mut(0);
        assert_eq!(y3.index, y2.index);
        assert_ne!(y3.generation, y2.generation);
        assert_eq!(z2.index, z.index);
        assert_ne!(z2.generation, z.generation);
        assert_eq!(x3.index, x2.index);
        assert_ne!(x3.generation, x2.generation);

        map.remove_mut(x3);
        map.remove_mut(y3);
        map.remove_mut(z2);
    }

    #[test]
    fn get_disjoint_mut() {
        let mut map = SlotMap::new(3);

        let x = map.insert_mut(1);
        let y = map.insert_mut(2);
        let z = map.insert_mut(3);

        assert_eq!(map.get_disjoint_mut([x, y]), Some([&mut 1, &mut 2]));
        assert_eq!(map.get_disjoint_mut([y, z]), Some([&mut 2, &mut 3]));
        assert_eq!(map.get_disjoint_mut([z, x]), Some([&mut 3, &mut 1]));

        assert_eq!(
            map.get_disjoint_mut([x, y, z]),
            Some([&mut 1, &mut 2, &mut 3]),
        );
        assert_eq!(
            map.get_disjoint_mut([z, y, x]),
            Some([&mut 3, &mut 2, &mut 1]),
        );

        assert_eq!(map.get_disjoint_mut([x, x]), None);
        assert_eq!(
            map.get_disjoint_mut([x, SlotId::new(3, OCCUPIED_TAG)]),
            None,
        );

        map.remove_mut(y);

        assert_eq!(map.get_disjoint_mut([x, z]), Some([&mut 1, &mut 3]));

        assert_eq!(map.get_disjoint_mut([y]), None);
        assert_eq!(map.get_disjoint_mut([x, y]), None);
        assert_eq!(map.get_disjoint_mut([y, z]), None);

        let y = map.insert_mut(2);

        assert_eq!(
            map.get_disjoint_mut([x, y, z]),
            Some([&mut 1, &mut 2, &mut 3]),
        );

        map.remove_mut(x);
        map.remove_mut(z);

        assert_eq!(map.get_disjoint_mut([y]), Some([&mut 2]));

        assert_eq!(map.get_disjoint_mut([x]), None);
        assert_eq!(map.get_disjoint_mut([z]), None);

        map.remove_mut(y);

        assert_eq!(map.get_disjoint_mut([]), Some([]));
    }

    #[test]
    fn tagged() {
        let map = SlotMap::new(1);
        let guard = &map.pin();

        let x = map.insert_with_tag(42, 1, guard);
        assert_eq!(x.generation() & TAG_MASK, 1);
        assert_eq!(map.get(x, guard), Some(&42));
    }

    #[test]
    fn tagged_mut() {
        let mut map = SlotMap::new(1);

        let x = map.insert_with_tag_mut(42, 1);
        assert_eq!(x.generation() & TAG_MASK, 1);
        assert_eq!(map.get_mut(x), Some(&mut 42));
    }

    #[test]
    fn remove_unchecked() {
        let map = SlotMap::new(1);

        let x = map.insert(69, &map.pin());

        // SAFETY: `x` refers to an occupied slot.
        assert_eq!(unsafe { map.remove_unchecked(x, &map.pin()) }, &69);

        assert_eq!(map.get(x, &map.pin()), None);
    }

    #[test]
    fn invalidate() {
        let map = SlotMap::new(1);

        let x = map.insert(69, &map.pin());

        assert_eq!(map.invalidate(x, &map.pin()), Some(&69));
        assert_eq!(map.invalidate(x, &map.pin()), None);
        assert_eq!(map.get(x, &map.pin()), None);
        assert_eq!(map.remove(x, &map.pin()), None);
        assert_eq!(map.remove_invalidated(x), Some(()));
        assert_eq!(map.remove_invalidated(x), None);
        assert_eq!(map.get(x, &map.pin()), None);
        assert_eq!(map.remove(x, &map.pin()), None);

        map.pin().flush();

        let guard = &map.pin();
        let y = map.insert(42, guard);

        assert_eq!(map.invalidate(y, guard), Some(&42));
        assert_eq!(map.invalidate(y, guard), None);
        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.remove(y, guard), None);
        assert_eq!(map.remove_invalidated(y), Some(()));
        assert_eq!(map.remove_invalidated(y), None);
        assert_eq!(map.get(y, guard), None);
        assert_eq!(map.remove(y, guard), None);
    }

    #[test]
    fn remove_invalidated_unchecked() {
        let map = SlotMap::new(1);

        let x = map.insert(69, &map.pin());

        assert_eq!(map.invalidate(x, &map.pin()), Some(&69));

        // SAFETY: `x` refers to an invalidated slot.
        unsafe { map.remove_invalidated_unchecked(x) };

        assert_eq!(map.get(x, &map.pin()), None);
    }

    #[test]
    fn revive_or_insert() {
        let mut map = SlotMap::new(1);

        let x = map.insert(MaybeUninit::new(Box::new(69)), &map.pin());
        map.remove(x, &map.pin());
        map.pin().flush();

        let guard = map.pin();
        let (y, value) = map.revive_or_insert_with(&guard, |_| MaybeUninit::new(Box::new(42)));

        assert_eq!(y, SlotId::new(x.index, x.generation() + ONE_GENERATION));

        assert_eq!(
            // SAFETY: The value is initialized.
            unsafe { value.assume_init_ref() },
            &Box::new(69),
        );

        drop(guard);

        // SAFETY: The value is initialized.
        unsafe { MaybeUninit::assume_init(map.remove_mut(y).unwrap()) };
    }

    #[test]
    fn header_shards() {
        let map = SlotMap::<_, i32>::new(0);

        thread::scope(|s| {
            let map = &map;
            let shard_count = SHARD_COUNT.load(Relaxed);

            for _ in 0..shard_count {
                s.spawn(move || {
                    assert_eq!(map.inner.header().shards().count(), shard_count);
                });
            }
        });
    }

    // TODO: Testing concurrent generational collections is the most massive pain in the ass. We
    // aren't testing the actual implementations but rather ones that don't take the generation into
    // account because of that.

    const ITERATIONS: u32 = if cfg!(miri) { 1_000 } else { 1_000_000 };

    #[test]
    fn multi_threaded1() {
        const THREADS: u32 = 2;

        let map = SlotMap::new(ITERATIONS);

        thread::scope(|s| {
            let inserter = || {
                for _ in 0..ITERATIONS / THREADS {
                    map.insert(0, &map.pin());
                }
            };

            for _ in 0..THREADS {
                s.spawn(inserter);
            }
        });

        thread::scope(|s| {
            let remover = || {
                for index in 0..ITERATIONS {
                    let _ = map.remove(SlotId::new(index, OCCUPIED_TAG), &map.pin());
                }
            };

            for _ in 0..THREADS {
                s.spawn(remover);
            }
        });

        assert_eq!(map.len(), 0);
    }

    #[test]
    fn multi_threaded2() {
        const CAPACITY: u32 = 8_000;

        let map = SlotMap::new(CAPACITY);

        thread::scope(|s| {
            let insert_remover = || {
                for _ in 0..ITERATIONS / 6 {
                    let x = map.insert(0, &map.pin());
                    let y = map.insert(0, &map.pin());
                    map.remove(y, &map.pin());
                    let z = map.insert(0, &map.pin());
                    map.remove(x, &map.pin());
                    map.remove(z, &map.pin());
                }
            };
            let iterator = || {
                for _ in 0..ITERATIONS / CAPACITY * 2 {
                    for index in 0..CAPACITY {
                        if let Some(value) = map.index(index, &map.pin()) {
                            let _ = *value;
                        }
                    }
                }
            };

            s.spawn(iterator);
            s.spawn(iterator);
            s.spawn(iterator);
            s.spawn(insert_remover);
        });
    }

    #[test]
    fn multi_threaded3() {
        let map = SlotMap::new(ITERATIONS / 10);

        thread::scope(|s| {
            let inserter = || {
                for i in 0..ITERATIONS {
                    if i % 10 == 0 {
                        map.insert(0, &map.pin());
                    } else {
                        thread::yield_now();
                    }
                }
            };
            let remover = || {
                for _ in 0..ITERATIONS {
                    map.remove_index(0, &map.pin());
                }
            };
            let getter = || {
                for _ in 0..ITERATIONS {
                    if let Some(value) = map.index(0, &map.pin()) {
                        let _ = *value;
                    }
                }
            };

            s.spawn(getter);
            s.spawn(getter);
            s.spawn(getter);
            s.spawn(getter);
            s.spawn(remover);
            s.spawn(remover);
            s.spawn(remover);
            s.spawn(inserter);
        });
    }
}