pi_slotmap 0.2.1

//! Contains the dense slot map implementation.

// There is quite a lot of unsafe code in this implementation. To prevent the
// same explanation over and over again, care must be taken that indices in
// slots and keys from key-value pairs **that are stored inside the slot map**
// are valid. Keys that are received from the user are not trusted (as they
// might have come from a different slot map or malicious serde deseralization).

use std::convert::TryFrom;
#[cfg(all(nightly, any(doc, feature = "unstable")))]
use alloc::collections::TryReserveError;
use alloc::collections::VecDeque;
use alloc::vec::Vec;
use core::iter::FusedIterator;
#[allow(unused_imports)] // MaybeUninit is only used on nightly at the moment.
use core::mem::MaybeUninit;
use core::ops::{Index, IndexMut};
use std::sync::atomic::{Ordering, AtomicU32};

use crate::util::{Never, UnwrapUnchecked};
use pi_key_alloter::{DefaultKey, Key, key_data};

// A slot, which represents storage for an index and a current version.
// Can be occupied or vacant.
#[derive(Debug, Clone)]
struct Slot {
    // Even = vacant, odd = occupied.
    version: u32,

    // An index when occupied, the next free slot otherwise.
    pub(crate) idx: u32, // 表示非空索引或空索引
}

/// Dense slot map, storage with stable unique keys.
///
/// See [crate documentation](crate) for more details.
#[derive(Debug)]
pub struct DelaySlotMap<K: Key, V> {
    keys: Vec<K>,
    values: Vec<V>,
    slots: Vec<Slot>,
    free_head: u32,

	free_vec: VecDeque<u32>,
	alloc_count: AtomicU32,
}

impl<V> DelaySlotMap<DefaultKey, V> {
    /// Construct a new, empty [`DenseSlotMap`].
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm: DenseSlotMap<_, i32> = DenseSlotMap::new();
    /// ```
    pub fn new() -> Self {
        Self::with_capacity_and_key(0)
    }

    /// Creates an empty [`DenseSlotMap`] with the given capacity.
    ///
    /// The slot map will not reallocate until it holds at least `capacity`
    /// elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm: DenseSlotMap<_, i32> = DenseSlotMap::with_capacity(10);
    /// ```
    pub fn with_capacity(capacity: usize) -> DelaySlotMap<DefaultKey, V> {
        Self::with_capacity_and_key(capacity)
    }
}

impl<K: Key, V> DelaySlotMap<K, V> {
    /// Constructs a new, empty [`DenseSlotMap`] with a custom key type.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// new_key_type! {
    ///     struct PositionKey;
    /// }
    /// let mut positions: DenseSlotMap<PositionKey, i32> = DenseSlotMap::with_key();
    /// ```
    pub fn with_key() -> Self {
        Self::with_capacity_and_key(0)
    }

    /// Creates an empty [`DenseSlotMap`] with the given capacity and a custom key
    /// type.
    ///
    /// The slot map will not reallocate until it holds at least `capacity`
    /// elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// new_key_type! {
    ///     struct MessageKey;
    /// }
    /// let mut messages = DenseSlotMap::with_capacity_and_key(3);
    /// let welcome: MessageKey = messages.insert("Welcome");
    /// let good_day = messages.insert("Good day");
    /// let hello = messages.insert("Hello");
    /// ```
    pub fn with_capacity_and_key(capacity: usize) -> Self {
        // Create slots with a sentinel at index 0.
        // We don't actually use the sentinel for anything currently, but
        // HopSlotMap does, and if we want keys to remain valid through
        // conversion we have to have one as well.
        let mut slots = Vec::with_capacity(capacity + 1);
        slots.push(Slot {
            idx: 0,
            version: 0,
        });

        DelaySlotMap {
            keys: Vec::with_capacity(capacity),
            values: Vec::with_capacity(capacity),
            slots,
            free_head: 1,

			free_vec: VecDeque::with_capacity(0),
			alloc_count: AtomicU32::new(0),
        }
    }

    /// Reserve one entity ID concurrently.
    ///
    /// Equivalent to `self.reserve_entities(1).next().unwrap()`, but more efficient.
    pub fn reserve_entity(&self) -> K {
        let n = self.alloc_count.fetch_add(1, Ordering::Relaxed);
        if n < self.free_vec.len() as u32 {
            // Allocate from the freelist.
            let id = self.free_vec[n as usize];
            K::from(unsafe {key_data(id, self.slots[id as usize].version | 1)})
        } else {
            // Grab a new ID, outside the range of `meta.len()`. `flush()` must
            // eventually be called to make it valid.
            //
            // As `self.alloc_count` goes more and more negative, we return IDs farther
            // and farther beyond `meta.len()`.
			K::from(unsafe {key_data(u32::try_from(self.slots.len() + (n as usize - self.free_vec.len())).expect("too many entities"), 1)})
        }
    }

    /// Check that we do not have pending work requiring `flush()` to be called.
    fn verify_flushed(&mut self) {
        debug_assert!(
            !self.needs_flush(),
            "flush() needs to be called before this operation is legal"
        );
    }

    fn needs_flush(&mut self) -> bool {
		*self.alloc_count.get_mut() > 0
    }

    /// Allocates space for entities previously reserved with `reserve_entity` or
    /// `reserve_entities`, then initializes each one using the supplied function.
    ///
    /// # Safety
    /// Flush _must_ set the entity location to the correct [`ArchetypeId`] for the given [`Entity`]
    /// each time init is called. This _can_ be [`ArchetypeId::INVALID`], provided the [`Entity`]
    /// has not been assigned to an [`Archetype`][crate::archetype::Archetype].
    pub unsafe fn flush(&mut self, mut init: impl FnMut(&mut Self, K)) {
        let alloc_count = self.alloc_count.get_mut();
        let current_alloc_count = *alloc_count as usize;

		let count1; // 当前释放的空位的数量
		let count2; // 除空位以外，还需额外的分配数量
		if current_alloc_count > self.free_vec.len() {
			count1 = self.free_vec.len();
			count2 = current_alloc_count - count1;
		} else {
			count1 = current_alloc_count;
			count2 = 0;
		}

		for _i in 0..count1 {
			let index = self.free_vec[0];
			init(self, K::from(unsafe {key_data(index, self.slots[index as usize].version | 1)}));
		}

		let len = self.slots.len();
		for i in 0..count2 {
			let index = len + i;
			init(self, K::from(unsafe {key_data(index as u32, 1)}));
		}
		// let new_len = self.free_vec.len() - count1;
        // self.free_vec.set_len(new_len);
		self.alloc_count.swap(0, Ordering::Relaxed);
    }


    /// Returns the number of elements in the slot map.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::with_capacity(10);
    /// sm.insert("len() counts actual elements, not capacity");
    /// let key = sm.insert("removed elements don't count either");
    /// sm.remove(key);
    /// assert_eq!(sm.len(), 1);
    /// ```
    pub fn len(&self) -> usize {
        self.keys.len()
    }

    /// Returns if the slot map is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert("dummy");
    /// assert_eq!(sm.is_empty(), false);
    /// sm.remove(key);
    /// assert_eq!(sm.is_empty(), true);
    /// ```
    pub fn is_empty(&self) -> bool {
        self.keys.is_empty()
    }

    /// Returns the number of elements the [`DenseSlotMap`] can hold without
    /// reallocating.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let sm: DenseSlotMap<_, f64> = DenseSlotMap::with_capacity(10);
    /// assert_eq!(sm.capacity(), 10);
    /// ```
    pub fn capacity(&self) -> usize {
        self.keys.capacity()
    }

    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the [`DenseSlotMap`]. The collection may reserve more space to
    /// avoid frequent reallocations.
    ///
    /// # Panics
    ///
    /// Panics if the new allocation size overflows [`usize`].
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// sm.insert("foo");
    /// sm.reserve(32);
    /// assert!(sm.capacity() >= 33);
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        self.keys.reserve(additional);
        self.values.reserve(additional);
        // One slot is reserved for the sentinel.
        let needed = (self.len() + additional).saturating_sub(self.slots.len() - 1);
        self.slots.reserve(needed);
    }

    /// Tries to reserve capacity for at least `additional` more elements to be
    /// inserted in the [`DenseSlotMap`]. The collection may reserve more space to
    /// avoid frequent reallocations.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// sm.insert("foo");
    /// sm.try_reserve(32).unwrap();
    /// assert!(sm.capacity() >= 33);
    /// ```
    #[cfg(all(nightly, any(doc, feature = "unstable")))]
    #[cfg_attr(all(nightly, doc), doc(cfg(feature = "unstable")))]
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
        self.keys.try_reserve(additional)?;
        self.values.try_reserve(additional)?;
        // One slot is reserved for the sentinel.
        let needed = (self.len() + additional).saturating_sub(self.slots.len() - 1);
        self.slots.try_reserve(needed)
    }

    /// Returns [`true`] if the slot map contains `key`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert(42);
    /// assert_eq!(sm.contains_key(key), true);
    /// sm.remove(key);
    /// assert_eq!(sm.contains_key(key), false);
    /// ```
    pub fn contains_key(&self, key: K) -> bool {
        let kd = key.data();
        self.slots
            .get(kd.index() as usize)
            .map_or(false, |slot| slot.version == kd.version())
    }

    /// Inserts a value into the slot map. Returns a unique key that can be used
    /// to access this value.
    ///
    /// # Panics
    ///
    /// Panics if the number of elements in the slot map equals
    /// 2<sup>32</sup> - 2.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert(42);
    /// assert_eq!(sm[key], 42);
    /// ```
    // #[inline(always)]
    pub fn insert(&mut self, value: V) -> K {
		self.verify_flushed();
        unsafe { self.try_insert_with_key::<_, Never>(move |_| Ok(value)).unwrap_unchecked_() }
    }

    /// Inserts a value given by `f` into the slot map. The key where the
    /// value will be stored is passed into `f`. This is useful to store values
    /// that contain their own key.
    ///
    /// # Panics
    ///
    /// Panics if the number of elements in the slot map equals
    /// 2<sup>32</sup> - 2.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert_with_key(|k| (k, 20));
    /// assert_eq!(sm[key], (key, 20));
    /// ```
    // #[inline(always)]
    pub fn insert_with_key<F>(&mut self, f: F) -> K
    where
        F: FnOnce(K) -> V,
    {
        unsafe { self.try_insert_with_key::<_, Never>(move |k| Ok(f(k))).unwrap_unchecked_() }
    }

    /// Inserts a value given by `f` into the slot map. The key where the
    /// value will be stored is passed into `f`. This is useful to store values
    /// that contain their own key.
    ///
    /// If `f` returns `Err`, this method returns the error. The slotmap is untouched.
    ///
    /// # Panics
    ///
    /// Panics if the number of elements in the slot map equals
    /// 2<sup>32</sup> - 2.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.try_insert_with_key::<_, ()>(|k| Ok((k, 20))).unwrap();
    /// assert_eq!(sm[key], (key, 20));
    ///
    /// sm.try_insert_with_key::<_, ()>(|k| Err(())).unwrap_err();
    /// ```
    pub fn try_insert_with_key<F, E>(&mut self, f: F) -> Result<K, E>
    where
        F: FnOnce(K) -> Result<V, E>,
    {
        if self.len() >= (core::u32::MAX - 1) as usize {
            panic!("DenseSlotMap number of elements overflow");
        }

		
		let idx = self.free_vec.pop_front();
//         let idx = self.free_head;
// idx
		if let Some(idx) = idx {
			let slot = unsafe{self.slots.get_unchecked_mut(idx as usize)};
			let occupied_version = slot.version | 1;
            let key = unsafe {key_data(idx, occupied_version)}.into();

            // Push value before adjusting slots/freelist in case f panics or returns an error.
            self.values.push(f(key)?);
            self.keys.push(key);
            // self.free_head = slot.index()_or_free;
            // slot.index()_or_free = self.keys.len() as u32 - 1;
            slot.version = occupied_version;

			slot.idx = (self.keys.len() - 1) as u32;
            return Ok(key);
		}

        // Push value before adjusting slots/freelist in case f panics or returns an error.
        let key = unsafe {key_data(self.slots.len() as u32, 1)}.into();
        self.values.push(f(key)?);
        self.keys.push(key);
        self.slots.push(Slot {
            version: 1,
            idx: self.keys.len() as u32 - 1,
        });
        Ok(key)
    }

    // Helper function to add a slot to the freelist. Returns the index that
    // was stored in the slot.
    // #[inline(always)]
    fn free_slot(&mut self, slot_idx: usize) -> u32 {
        let slot = &mut self.slots[slot_idx];
        let value_idx = slot.idx;
        slot.version = slot.version.wrapping_add(1);
		slot.idx = self.free_vec.len() as u32;
		self.free_vec.push_back(slot_idx as u32);
        
        self.free_head = slot_idx as u32;
        value_idx
    }

    // Helper function to remove a value from a slot and make the slot free.
    // Returns the value removed.
    // #[inline(always)]
    fn remove_from_slot(&mut self, slot_idx: usize) -> V {
        let value_idx = self.free_slot(slot_idx);

        // Remove values/slot_indices by swapping to end.
        let _ = self.keys.swap_remove(value_idx as usize);
        let value = self.values.swap_remove(value_idx as usize);

        // Did something take our place? Update its slot to new position.
        if let Some(k) = self.keys.get(value_idx as usize) {
            self.slots[k.data().index() as usize].idx = value_idx;
        }

        value
    }

    /// Removes a key from the slot map, returning the value at the key if the
    /// key was not previously removed.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert(42);
    /// assert_eq!(sm.remove(key), Some(42));
    /// assert_eq!(sm.remove(key), None);
    /// ```
    pub fn remove(&mut self, key: K) -> Option<V> {
		self.verify_flushed();
        let kd = key.data();
        if self.contains_key(kd.into()) {
            Some(self.remove_from_slot(kd.index() as usize))
        } else {
            None
        }
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all key-value pairs `(k, v)` such that
    /// `f(k, &mut v)` returns false. This method invalidates any removed keys.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    ///
    /// let k3 = sm.insert(2);
    /// let k1 = sm.insert(0);
    /// let k2 = sm.insert(1);
    ///
    /// sm.retain(|key, val| key == k1 || *val == 1);
    ///
    /// assert!(sm.contains_key(k1));
    /// assert!(sm.contains_key(k2));
    /// assert!(!sm.contains_key(k3));
    ///
    /// assert_eq!(2, sm.len());
    /// ```
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(K, &mut V) -> bool,
    {
        let mut i = 0;
        while i < self.keys.len() {
            let (should_keep, slot_idx) = {
                let (kd, mut value) = (self.keys[i].data(), &mut self.values[i]);
                (f(kd.into(), &mut value), kd.index() as usize)
            };

            if should_keep {
                i += 1;
            } else {
                // We do not increment i here intentionally. This index has just
                // been replaced with a new value.
                self.remove_from_slot(slot_idx);
            }
        }
    }

    /// Clears the slot map. Keeps the allocated memory for reuse.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// for i in 0..10 {
    ///     sm.insert(i);
    /// }
    /// assert_eq!(sm.len(), 10);
    /// sm.clear();
    /// assert_eq!(sm.len(), 0);
    /// ```
    pub fn clear(&mut self) {
        self.drain();
    }

    /// Clears the slot map, returning all key-value pairs in arbitrary order
    /// as an iterator. Keeps the allocated memory for reuse.
    ///
    /// When the iterator is dropped all elements in the slot map are removed,
    /// even if the iterator was not fully consumed. If the iterator is not
    /// dropped (using e.g. [`std::mem::forget`]), only the elements that were
    /// iterated over are removed.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let k = sm.insert(0);
    /// let v: Vec<_> = sm.drain().collect();
    /// assert_eq!(sm.len(), 0);
    /// assert_eq!(v, vec![(k, 0)]);
    /// ```
    pub fn drain(&mut self) -> Drain<K, V> {
        Drain { sm: self }
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert("bar");
    /// assert_eq!(sm.get(key), Some(&"bar"));
    /// sm.remove(key);
    /// assert_eq!(sm.get(key), None);
    /// ```
    pub fn get(&self, key: K) -> Option<&V> {
        let kd = key.data();
        self.slots
            .get(kd.index() as usize)
            .filter(|slot| slot.version == kd.version())
            .map(|slot| unsafe {
                // This is safe because we only store valid indices.
                let idx = slot.idx as usize;
                self.values.get_unchecked(idx)
            })
    }

    /// Returns a reference to the value corresponding to the key without
    /// version or bounds checking.
    ///
    /// # Safety
    ///
    /// This should only be used if `contains_key(key)` is true. Otherwise it is
    /// potentially unsafe.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert("bar");
    /// assert_eq!(unsafe { sm.get_unchecked(key) }, &"bar");
    /// sm.remove(key);
    /// // sm.get_unchecked(key) is now dangerous!
    /// ```
    pub unsafe fn get_unchecked(&self, key: K) -> &V {
        debug_assert!(self.contains_key(key));
        let idx = self.slots.get_unchecked(key.data().index() as usize).idx;
        &self.values.get_unchecked(idx as usize)
    }

    /// Returns a mutable reference to the value corresponding to the key.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert(3.5);
    /// if let Some(x) = sm.get_mut(key) {
    ///     *x += 3.0;
    /// }
    /// assert_eq!(sm[key], 6.5);
    /// ```
    pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
        let kd = key.data();
        self.slots
            .get(kd.index() as usize)
            .filter(|slot| slot.version == kd.version())
            .map(|slot| slot.idx as usize)
            .map(move |idx| unsafe {
                // This is safe because we only store valid indices.
                self.values.get_unchecked_mut(idx)
            })
    }

    /// Returns a mutable reference to the value corresponding to the key
    /// without version or bounds checking.
    ///
    /// # Safety
    ///
    /// This should only be used if `contains_key(key)` is true. Otherwise it is
    /// potentially unsafe.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let key = sm.insert("foo");
    /// unsafe { *sm.get_unchecked_mut(key) = "bar" };
    /// assert_eq!(sm[key], "bar");
    /// sm.remove(key);
    /// // sm.get_unchecked_mut(key) is now dangerous!
    /// ```
    pub unsafe fn get_unchecked_mut(&mut self, key: K) -> &mut V {
        debug_assert!(self.contains_key(key));
        let idx = self.slots.get_unchecked(key.data().index() as usize).idx;
        self.values.get_unchecked_mut(idx as usize)
    }

    /// Returns mutable references to the values corresponding to the given
    /// keys. All keys must be valid and disjoint, otherwise [`None`] is
    /// returned.
    ///
    /// Requires at least stable Rust version 1.51.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let ka = sm.insert("butter");
    /// let kb = sm.insert("apples");
    /// let kc = sm.insert("charlie");
    /// sm.remove(kc); // Make key c invalid.
    /// assert_eq!(sm.get_disjoint_mut([ka, kb, kc]), None); // Has invalid key.
    /// assert_eq!(sm.get_disjoint_mut([ka, ka]), None); // Not disjoint.
    /// let [a, b] = sm.get_disjoint_mut([ka, kb]).unwrap();
    /// std::mem::swap(a, b);
    /// assert_eq!(sm[ka], "apples");
    /// assert_eq!(sm[kb], "butter");
    /// ```
    #[cfg(has_min_const_generics)]
    pub fn get_disjoint_mut<const N: usize>(&mut self, keys: [K; N]) -> Option<[&mut V; N]> {
        // Create an uninitialized array of `MaybeUninit`. The `assume_init` is
        // safe because the type we are claiming to have initialized here is a
        // bunch of `MaybeUninit`s, which do not require initialization.
        let mut ptrs: [MaybeUninit<*mut V>; N] = unsafe { MaybeUninit::uninit().assume_init() };

        let mut i = 0;
        while i < N {
            // We can avoid this clone after min_const_generics and array_map.
            let kd = keys[i].data();
            if !self.contains_key(kd.into()) {
                break;
            }

            // This key is valid, and thus the slot is occupied. Temporarily
            // mark it as unoccupied so duplicate keys would show up as invalid.
            // This gives us a linear time disjointness check.
            unsafe {
                let slot = self.slots.get_unchecked_mut(kd.index() as usize);
                slot.version ^= 1;
                let ptr = self.values.get_unchecked_mut(slot.idx as usize);
                ptrs[i] = MaybeUninit::new(ptr);
            }
            i += 1;
        }

        // Undo temporary unoccupied markings.
        for k in &keys[..i] {
            let idx = k.data().index() as usize;
            unsafe {
                self.slots.get_unchecked_mut(idx).version ^= 1;
            }
        }

        if i == N {
            // All were valid and disjoint.
            Some(unsafe { core::mem::transmute_copy::<_, [&mut V; N]>(&ptrs) })
        } else {
            None
        }
    }

    /// Returns mutable references to the values corresponding to the given
    /// keys. All keys must be valid and disjoint.
    ///
    /// Requires at least stable Rust version 1.51.
    ///
    /// # Safety
    ///
    /// This should only be used if `contains_key(key)` is true for every given
    /// key and no two keys are equal. Otherwise it is potentially unsafe.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let ka = sm.insert("butter");
    /// let kb = sm.insert("apples");
    /// let [a, b] = unsafe { sm.get_disjoint_unchecked_mut([ka, kb]) };
    /// std::mem::swap(a, b);
    /// assert_eq!(sm[ka], "apples");
    /// assert_eq!(sm[kb], "butter");
    /// ```
    #[cfg(has_min_const_generics)]
    pub unsafe fn get_disjoint_unchecked_mut<const N: usize>(
        &mut self,
        keys: [K; N],
    ) -> [&mut V; N] {
        // Safe, see get_disjoint_mut.
        let mut ptrs: [MaybeUninit<*mut V>; N] = MaybeUninit::uninit().assume_init();
        for i in 0..N {
            ptrs[i] = MaybeUninit::new(self.get_unchecked_mut(keys[i]));
        }
        core::mem::transmute_copy::<_, [&mut V; N]>(&ptrs)
    }

    /// An iterator visiting all key-value pairs in arbitrary order. The
    /// iterator element type is `(K, &'a V)`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let k0 = sm.insert(0);
    /// let k1 = sm.insert(1);
    /// let k2 = sm.insert(2);
    ///
    /// let mut it = sm.iter();
    /// for (k, v) in sm.iter() {
    ///     println!("key: {:?}, val: {}", k, v);
    /// }
    /// ```
    pub fn iter(&self) -> Iter<K, V> {
        Iter {
            inner_keys: self.keys.iter(),
            inner_values: self.values.iter(),
        }
    }

    /// An iterator visiting all key-value pairs in arbitrary order, with
    /// mutable references to the values. The iterator element type is
    /// `(K, &'a mut V)`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// let mut sm = DenseSlotMap::new();
    /// let k0 = sm.insert(10);
    /// let k1 = sm.insert(20);
    /// let k2 = sm.insert(30);
    ///
    /// for (k, v) in sm.iter_mut() {
    ///     if k != k1 {
    ///         *v *= -1;
    ///     }
    /// }
    ///
    /// assert_eq!(sm[k0], -10);
    /// assert_eq!(sm[k1], 20);
    /// assert_eq!(sm[k2], -30);
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<K, V> {
        IterMut {
            inner_keys: self.keys.iter(),
            inner_values: self.values.iter_mut(),
        }
    }

    /// An iterator visiting all keys in arbitrary order. The iterator element
    /// type is K.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// # use std::collections::HashSet;
    /// let mut sm = DenseSlotMap::new();
    /// let k0 = sm.insert(10);
    /// let k1 = sm.insert(20);
    /// let k2 = sm.insert(30);
    /// let keys: HashSet<_> = sm.keys().collect();
    /// let check: HashSet<_> = vec![k0, k1, k2].into_iter().collect();
    /// assert_eq!(keys, check);
    /// ```
    pub fn keys(&self) -> Keys<K, V> {
        Keys { inner: self.iter() }
    }

    /// An iterator visiting all values in arbitrary order. The iterator element
    /// type is `&'a V`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// # use std::collections::HashSet;
    /// let mut sm = DenseSlotMap::new();
    /// let k0 = sm.insert(10);
    /// let k1 = sm.insert(20);
    /// let k2 = sm.insert(30);
    /// let values: HashSet<_> = sm.values().collect();
    /// let check: HashSet<_> = vec![&10, &20, &30].into_iter().collect();
    /// assert_eq!(values, check);
    /// ```
    pub fn values(&self) -> Values<K, V> {
        Values { inner: self.iter() }
    }

    /// An iterator visiting all values mutably in arbitrary order. The iterator
    /// element type is `&'a mut V`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use slotmap::*;
    /// # use std::collections::HashSet;
    /// let mut sm = DenseSlotMap::new();
    /// sm.insert(1);
    /// sm.insert(2);
    /// sm.insert(3);
    /// sm.values_mut().for_each(|n| { *n *= 3 });
    /// let values: HashSet<_> = sm.into_iter().map(|(_k, v)| v).collect();
    /// let check: HashSet<_> = vec![3, 6, 9].into_iter().collect();
    /// assert_eq!(values, check);
    /// ```
    pub fn values_mut(&mut self) -> ValuesMut<K, V> {
        ValuesMut {
            inner: self.iter_mut(),
        }
    }
}

impl<K: Key, V> Clone for DelaySlotMap<K, V>
where
    V: Clone,
{
    fn clone(&self) -> Self {
        Self {
            keys: self.keys.clone(),
            values: self.values.clone(),
            slots: self.slots.clone(),
			free_vec: self.free_vec.clone(),
			alloc_count: AtomicU32::new(self.alloc_count.load(Ordering::Relaxed)),
            ..*self
        }
    }

    fn clone_from(&mut self, source: &Self) {
        self.keys.clone_from(&source.keys);
        self.values.clone_from(&source.values);
        self.slots.clone_from(&source.slots);
        self.free_head = source.free_head;
    }
}

impl<K: Key, V> Default for DelaySlotMap<K, V> {
    fn default() -> Self {
        Self::with_key()
    }
}

impl<K: Key, V> Index<K> for DelaySlotMap<K, V> {
    type Output = V;

    fn index(&self, key: K) -> &V {
        match self.get(key) {
            Some(r) => r,
            None => panic!("invalid DenseSlotMap key used"),
        }
    }
}

impl<K: Key, V> IndexMut<K> for DelaySlotMap<K, V> {
    fn index_mut(&mut self, key: K) -> &mut V {
        match self.get_mut(key) {
            Some(r) => r,
            None => panic!("invalid DenseSlotMap key used"),
        }
    }
}

// Iterators.
/// A draining iterator for [`DenseSlotMap`].
///
/// This iterator is created by [`DenseSlotMap::drain`].
#[derive(Debug)]
pub struct Drain<'a, K: 'a + Key, V: 'a> {
    sm: &'a mut DelaySlotMap<K, V>,
}

/// An iterator that moves key-value pairs out of a [`DenseSlotMap`].
///
/// This iterator is created by calling the `into_iter` method on [`DenseSlotMap`],
/// provided by the [`IntoIterator`] trait.
#[derive(Debug, Clone)]
pub struct IntoIter<K, V> {
    inner_keys: alloc::vec::IntoIter<K>,
    inner_values: alloc::vec::IntoIter<V>,
}

/// An iterator over the key-value pairs in a [`DenseSlotMap`].
///
/// This iterator is created by [`DenseSlotMap::iter`].
#[derive(Debug)]
pub struct Iter<'a, K: 'a + Key, V: 'a> {
    inner_keys: core::slice::Iter<'a, K>,
    inner_values: core::slice::Iter<'a, V>,
}

impl<'a, K: 'a + Key, V: 'a> Clone for Iter<'a, K, V> {
    fn clone(&self) -> Self {
        Iter {
            inner_keys: self.inner_keys.clone(),
            inner_values: self.inner_values.clone(),
        }
    }
}

/// A mutable iterator over the key-value pairs in a [`DenseSlotMap`].
///
/// This iterator is created by [`DenseSlotMap::iter_mut`].
#[derive(Debug)]
pub struct IterMut<'a, K: 'a + Key, V: 'a> {
    inner_keys: core::slice::Iter<'a, K>,
    inner_values: core::slice::IterMut<'a, V>,
}

/// An iterator over the keys in a [`DenseSlotMap`].
///
/// This iterator is created by [`DenseSlotMap::keys`].
#[derive(Debug)]
pub struct Keys<'a, K: 'a + Key, V> {
    inner: Iter<'a, K, V>,
}

impl<'a, K: 'a + Key, V: 'a> Clone for Keys<'a, K, V> {
    fn clone(&self) -> Self {
        Keys {
            inner: self.inner.clone(),
        }
    }
}

/// An iterator over the values in a [`DenseSlotMap`].
///
/// This iterator is created by [`DenseSlotMap::values`].
#[derive(Debug)]
pub struct Values<'a, K: 'a + Key, V> {
    inner: Iter<'a, K, V>,
}

impl<'a, K: 'a + Key, V: 'a> Clone for Values<'a, K, V> {
    fn clone(&self) -> Self {
        Values {
            inner: self.inner.clone(),
        }
    }
}

/// A mutable iterator over the values in a [`DenseSlotMap`].
///
/// This iterator is created by [`DenseSlotMap::values_mut`].
#[derive(Debug)]
pub struct ValuesMut<'a, K: 'a + Key, V: 'a> {
    inner: IterMut<'a, K, V>,
}

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

    fn next(&mut self) -> Option<(K, V)> {
        // We make no iteration order guarantees, so we just repeatedly pop.
        let key = self.sm.keys.pop();
        let value = self.sm.values.pop();

        if let (Some(k), Some(v)) = (key, value) {
            self.sm.free_slot(k.data().index() as usize);
            Some((k, v))
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.sm.keys.len();
        (len, Some(len))
    }
}

impl<'a, K: Key, V> Drop for Drain<'a, K, V> {
    fn drop(&mut self) {
        self.for_each(|_drop| {});
    }
}

impl<K: Key, V> Iterator for IntoIter<K, V> {
    type Item = (K, V);

    fn next(&mut self) -> Option<(K, V)> {
        let key = self.inner_keys.next();
        let value = self.inner_values.next();

        if let (Some(k), Some(v)) = (key, value) {
            Some((k, v))
        } else {
            None
        }
    }

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

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

    fn next(&mut self) -> Option<(K, &'a V)> {
        let key = self.inner_keys.next();
        let value = self.inner_values.next();

        if let (Some(k), Some(v)) = (key, value) {
            Some((*k, v))
        } else {
            None
        }
    }

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

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

    fn next(&mut self) -> Option<(K, &'a mut V)> {
        let key = self.inner_keys.next();
        let value = self.inner_values.next();

        if let (Some(k), Some(v)) = (key, value) {
            Some((*k, v))
        } else {
            None
        }
    }

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

impl<'a, K: 'a + Key, V> Iterator for Keys<'a, K, V> {
    type Item = K;

    fn next(&mut self) -> Option<K> {
        self.inner.next().map(|(key, _)| key)
    }

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

impl<'a, K: 'a + Key, V> Iterator for Values<'a, K, V> {
    type Item = &'a V;

    fn next(&mut self) -> Option<&'a V> {
        self.inner.next().map(|(_, value)| value)
    }

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

impl<'a, K: 'a + Key, V> Iterator for ValuesMut<'a, K, V> {
    type Item = &'a mut V;

    fn next(&mut self) -> Option<&'a mut V> {
        self.inner.next().map(|(_, value)| value)
    }

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

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

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

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

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

impl<K: Key, V> IntoIterator for DelaySlotMap<K, V> {
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            inner_keys: self.keys.into_iter(),
            inner_values: self.values.into_iter(),
        }
    }
}

impl<'a, K: 'a + Key, V> FusedIterator for Iter<'a, K, V> {}
impl<'a, K: 'a + Key, V> FusedIterator for IterMut<'a, K, V> {}
impl<'a, K: 'a + Key, V> FusedIterator for Keys<'a, K, V> {}
impl<'a, K: 'a + Key, V> FusedIterator for Values<'a, K, V> {}
impl<'a, K: 'a + Key, V> FusedIterator for ValuesMut<'a, K, V> {}
impl<'a, K: 'a + Key, V> FusedIterator for Drain<'a, K, V> {}
impl<K: Key, V> FusedIterator for IntoIter<K, V> {}

impl<'a, K: 'a + Key, V> ExactSizeIterator for Iter<'a, K, V> {}
impl<'a, K: 'a + Key, V> ExactSizeIterator for IterMut<'a, K, V> {}
impl<'a, K: 'a + Key, V> ExactSizeIterator for Keys<'a, K, V> {}
impl<'a, K: 'a + Key, V> ExactSizeIterator for Values<'a, K, V> {}
impl<'a, K: 'a + Key, V> ExactSizeIterator for ValuesMut<'a, K, V> {}
impl<'a, K: 'a + Key, V> ExactSizeIterator for Drain<'a, K, V> {}
impl<K: Key, V> ExactSizeIterator for IntoIter<K, V> {}

// Serialization with serde.
#[cfg(feature = "serde")]
mod serialize {
    use serde::{de, Deserialize, Deserializer, Serialize, Serializer};

    use super::*;

    #[derive(Serialize, Deserialize)]
    struct SerdeSlot<T> {
        value: Option<T>,
        version: u32,
    }

    impl<K: Key, V: Serialize> Serialize for DelaySlotMap<K, V> {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: Serializer,
        {
            let serde_slots: Vec<_> = self
                .slots
                .iter()
                .map(|slot| SerdeSlot {
                    value: if slot.version % 2 == 1 {
                        self.values.get(slot.idx as usize)
                    } else {
                        None
                    },
                    version: slot.version,
                })
                .collect();
            serde_slots.serialize(serializer)
        }
    }

    impl<'de, K: Key, V: Deserialize<'de>> Deserialize<'de> for DelaySlotMap<K, V> {
        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
        where
            D: Deserializer<'de>,
        {
            let serde_slots: Vec<SerdeSlot<V>> = Deserialize::deserialize(deserializer)?;
            if serde_slots.len() >= u32::max_value() as usize {
                return Err(de::Error::custom(&"too many slots"));
            }

            // Ensure the first slot exists and is empty for the sentinel.
            if serde_slots.get(0).map_or(true, |slot| slot.version % 2 == 1) {
                return Err(de::Error::custom(&"first slot not empty"));
            }

            // Rebuild slots, key and values.
            let mut keys = Vec::new();
            let mut values = Vec::new();
            let mut slots = Vec::new();
            slots.push(Slot {
                idx: 0,
                version: 0,
            });

            let mut next_free = serde_slots.len();
            for (i, serde_slot) in serde_slots.into_iter().enumerate().skip(1) {
                let occupied = serde_slot.version % 2 == 1;
                if occupied ^ serde_slot.value.is_some() {
                    return Err(de::Error::custom(&"inconsistent occupation in Slot"));
                }

                if let Some(value) = serde_slot.value {
                    let kd = unsafe {key_data(i as u32, serde_slot.version)};
                    keys.push(kd.into());
                    values.push(value);
                    slots.push(Slot {
                        version: serde_slot.version,
                        idx: keys.len() as u32 - 1,
                    });
                } else {
                    slots.push(Slot {
                        version: serde_slot.version,
                        idx: next_free as u32,
                    });
                    next_free = i;
                }
            }
			
            Ok(DelaySlotMap {
                keys,
                values,
                slots,
                free_head: next_free as u32,

				// TODO
				free_vec: VecDeque::new(),
				alloc_count:AtomicU32::new(0), 
            })
        }
    }
}

// #[cfg(test)]
// mod tests {
//     use std::collections::{HashMap, HashSet};

//     use quickcheck::quickcheck;

//     use super::*;

//     #[derive(Clone)]
//     struct CountDrop<'a>(&'a core::cell::RefCell<usize>);

//     impl<'a> Drop for CountDrop<'a> {
//         fn drop(&mut self) {
//             *self.0.borrow_mut() += 1;
//         }
//     }

//     #[test]
//     fn check_drops() {
//         let drops = core::cell::RefCell::new(0usize);

//         {
//             let mut clone = {
//                 // Insert 1000 items.
//                 let mut sm = DenseSlotMap::new();
//                 let mut sm_keys = Vec::new();
//                 for _ in 0..1000 {
//                     sm_keys.push(sm.insert(CountDrop(&drops)));
//                 }

//                 // Remove even keys.
//                 for i in (0..1000).filter(|i| i % 2 == 0) {
//                     sm.remove(sm_keys[i]);
//                 }

//                 // Should only have dropped 500 so far.
//                 assert_eq!(*drops.borrow(), 500);

//                 // Let's clone ourselves and then die.
//                 sm.clone()
//             };

//             // Now all original items should have been dropped exactly once.
//             assert_eq!(*drops.borrow(), 1000);

//             // Re-use some empty slots.
//             for _ in 0..250 {
//                 clone.insert(CountDrop(&drops));
//             }
//         }

//         // 1000 + 750 drops in total should have happened.
//         assert_eq!(*drops.borrow(), 1750);
//     }

//     #[cfg(all(nightly, feature = "unstable"))]
//     #[test]
//     fn disjoint() {
//         // Intended to be run with miri to find any potential UB.
//         let mut sm = DenseSlotMap::new();

//         // Some churn.
//         for i in 0..20usize {
//             sm.insert(i);
//         }
//         sm.retain(|_, i| *i % 2 == 0);

//         let keys: Vec<_> = sm.keys().collect();
//         for i in 0..keys.len() {
//             for j in 0..keys.len() {
//                 if let Some([r0, r1]) = sm.get_disjoint_mut([keys[i], keys[j]]) {
//                     *r0 ^= *r1;
//                     *r1 = r1.wrapping_add(*r0);
//                 } else {
//                     assert!(i == j);
//                 }
//             }
//         }

//         for i in 0..keys.len() {
//             for j in 0..keys.len() {
//                 for k in 0..keys.len() {
//                     if let Some([r0, r1, r2]) = sm.get_disjoint_mut([keys[i], keys[j], keys[k]]) {
//                         *r0 ^= *r1;
//                         *r0 = r0.wrapping_add(*r2);
//                         *r1 ^= *r0;
//                         *r1 = r1.wrapping_add(*r2);
//                         *r2 ^= *r0;
//                         *r2 = r2.wrapping_add(*r1);
//                     } else {
//                         assert!(i == j || j == k || i == k);
//                     }
//                 }
//             }
//         }
//     }

//     quickcheck! {
//         fn qc_slotmap_equiv_hashmap(operations: Vec<(u8, u32)>) -> bool {
//             let mut hm = HashMap::new();
//             let mut hm_keys = Vec::new();
//             let mut unique_key = 0u32;
//             let mut sm = DenseSlotMap::new();
//             let mut sm_keys = Vec::new();

//             #[cfg(not(feature = "serde"))]
//             let num_ops = 3;
//             #[cfg(feature = "serde")]
//             let num_ops = 4;

//             for (op, val) in operations {
//                 match op % num_ops {
//                     // Insert.
//                     0 => {
//                         hm.insert(unique_key, val);
//                         hm_keys.push(unique_key);
//                         unique_key += 1;

//                         sm_keys.push(sm.insert(val));
//                     }

//                     // Delete.
//                     1 => {
//                         // 10% of the time test clear.
//                         if val % 10 == 0 {
//                             let hmvals: HashSet<_> = hm.drain().map(|(_, v)| v).collect();
//                             let smvals: HashSet<_> = sm.drain().map(|(_, v)| v).collect();
//                             if hmvals != smvals {
//                                 return false;
//                             }
//                         }
//                         if hm_keys.is_empty() { continue; }

//                         let idx = val as usize % hm_keys.len();
//                         if hm.remove(&hm_keys[idx]) != sm.remove(sm_keys[idx]) {
//                             return false;
//                         }
//                     }

//                     // Access.
//                     2 => {
//                         if hm_keys.is_empty() { continue; }
//                         let idx = val as usize % hm_keys.len();
//                         let (hm_key, sm_key) = (&hm_keys[idx], sm_keys[idx]);

//                         if hm.contains_key(hm_key) != sm.contains_key(sm_key) ||
//                            hm.get(hm_key) != sm.get(sm_key) {
//                             return false;
//                         }
//                     }

//                     // Serde round-trip.
//                     #[cfg(feature = "serde")]
//                     3 => {
//                         let ser = serde_json::to_string(&sm).unwrap();
//                         sm = serde_json::from_str(&ser).unwrap();
//                     }

//                     _ => unreachable!(),
//                 }
//             }

//             let mut smv: Vec<_> = sm.values().collect();
//             let mut hmv: Vec<_> = hm.values().collect();
//             smv.sort();
//             hmv.sort();
//             smv == hmv
//         }
//     }

//     #[cfg(feature = "serde")]
//     #[test]
//     fn slotmap_serde() {
//         let mut sm = DenseSlotMap::new();
//         // Self-referential structure.
//         let first = sm.insert_with_key(|k| (k, 23i32));
//         let second = sm.insert((first, 42));

//         // Make some empty slots.
//         let empties = vec![sm.insert((first, 0)), sm.insert((first, 0))];
//         empties.iter().for_each(|k| {
//             sm.remove(*k);
//         });

//         let third = sm.insert((second, 0));
//         sm[first].0 = third;

//         let ser = serde_json::to_string(&sm).unwrap();
//         let de: DenseSlotMap<DefaultKey, (DefaultKey, i32)> = serde_json::from_str(&ser).unwrap();
//         assert_eq!(de.len(), sm.len());

//         let mut smkv: Vec<_> = sm.iter().collect();
//         let mut dekv: Vec<_> = de.iter().collect();
//         smkv.sort();
//         dekv.sort();
//         assert_eq!(smkv, dekv);
//     }

//     #[cfg(feature = "serde")]
//     #[test]
//     fn slotmap_serde_freelist() {
//         let mut sm = DenseSlotMap::new();
//         let k0 = sm.insert(5i32);
//         let k1 = sm.insert(5i32);
//         sm.remove(k0);
//         sm.remove(k1);

//         let ser = serde_json::to_string(&sm).unwrap();
//         let mut de: DenseSlotMap<DefaultKey, i32> = serde_json::from_str(&ser).unwrap();

//         de.insert(0);
//         de.insert(1);
//         de.insert(2);
//         assert_eq!(de.len(), 3);
//     }
// }