vslab 2.0.0

// Copyright (C) 2020-2025 vslab authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! # VSlab
//!
//! A fast, memory-efficient slab data structure with persistent unique keys.
//!
//! This crate provides a container similar to `SlotMap` or `Slab` that offers O(1) insertion,
//! removal, and access operations. Each inserted value returns a unique key that remains valid
//! even after the value is removed, preventing access to stale data through versioning.
//!
//! ## Features
//!
//! - **O(1) Operations**: Insert, remove, and access operations all run in constant time
//! - **Versioned Keys**: Keys include version information to prevent stale data access
//! - **Memory Efficient**: Uses a free list to reuse memory of removed entries
//! - **Custom Key Types**: Support for user-defined key types via the `SlabId` trait
//! - **No Dependencies**: Core functionality uses only `std`, with optional WASM support
//! - **WASM Support**: Full support for WebAssembly targets
//!
//! ## Basic Usage
//!
//! ```rust
//! use vslab::Slab;
//!
//! // Create a slab with u64 keys and String values
//! let mut slab = Slab::<u64, String>::default();
//!
//! // Insert a value and get a unique key
//! let apple_id = slab.insert("apple".to_string());
//! let banana_id = slab.insert("banana".to_string());
//!
//! // Access values by key
//! assert_eq!(slab[apple_id], "apple");
//! assert_eq!(slab[banana_id], "banana");
//!
//! // Remove a value
//! let removed = slab.remove(apple_id).unwrap();
//! assert_eq!(removed, "apple");
//!
//! // The old key is now invalid
//! assert!(slab.get(apple_id).is_none());
//!
//! // Insert a new value (reuses the old slot)
//! let orange_id = slab.insert("orange".to_string());
//! assert_eq!(slab[orange_id], "orange");
//! ```
//!
//! ## Custom Key Types
//!
//! For better type safety, you can define custom key types:
//!
//! ```rust
//! use vslab::{Slab, new_type_id};
//!
//! // Define a custom key type
//! new_type_id!(EntityId);
//!
//! let mut entities = Slab::<EntityId, String>::default();
//! let player_id = entities.insert("Player".to_string());
//!
//! assert_eq!(entities[player_id], "Player");
//! ```
//!
//! ## Performance
//!
//! This implementation is optimized for performance:
//! - Keys are passed by value when smaller than `u64`
//! - Minimal branching in hot paths
//! - Efficient free list management
//! - Cache-friendly memory layout
//!
//! ## Comparison with Alternatives
//!
//! - **vs `Vec`**: Slab provides stable keys, Vec doesn't
//! - **vs `SlotMap`**: Similar performance, but simpler implementation
//! - **vs `Slab`**: This implementation includes versioning for better safety

use std::marker::PhantomData;

#[derive(Clone)]
enum Slot<T> {
    Occupied(Occupied<T>),
    Free(Free),
}
#[derive(Clone)]
struct Free {
    next: usize,
    version: u32,
}

#[derive(Clone)]
struct Occupied<T> {
    value: T,
    version: u32,
}

/// Trait for types that can be used as keys in a `Slab`.
///
/// This trait defines how keys are structured and provides methods to:
/// - Extract the index part of the key
/// - Extract the version part of the key
/// - Create a key from raw index and version components
///
/// The built-in `u64` implementation uses the lower 32 bits for the index
/// and the upper 32 bits for the version.
///
/// # Examples
///
/// Most users will use the built-in `u64` implementation or create custom
/// key types using the [`new_type_id`] macro.
pub trait SlabId {
    /// Extract the index part of this key.
    ///
    /// The index determines which slot in the underlying storage this key refers to.
    fn index(&self) -> usize;

    /// Extract the version part of this key.
    ///
    /// The version is used to prevent access to stale data after a slot has been
    /// reused. When a value is removed and the slot is reused, the version increments.
    fn version(&self) -> u32;

    /// Create a new key from raw index and version components.
    ///
    /// This is used internally by the slab when generating new keys.
    fn from_raw(index: usize, version: u32) -> Self;
}

/// A slab data structure with persistent unique keys.
///
/// A `Slab` provides O(1) insertion, removal, and access operations while maintaining
/// stable keys. When a value is inserted, a unique key is returned that can be used to
/// access the value even after other values have been removed.
///
/// The slab uses a free list to manage memory efficiently and versioning to prevent
/// access to stale data when slots are reused.
///
/// # Type Parameters
///
/// - `ID`: The key type that implements [`SlabId`]
/// - `V`: The type of values stored in the slab
///
/// # Examples
///
/// ```rust
/// use vslab::Slab;
///
/// let mut slab = Slab::<u64, String>::default();
/// let key = slab.insert("hello".to_string());
/// assert_eq!(slab[key], "hello");
/// ```
#[derive(Clone)]
pub struct Slab<ID, V> {
    raw: Vec<Slot<V>>,
    len: usize,
    free_index: usize,
    _phantom: PhantomData<ID>,
}

impl<Id, V> Default for Slab<Id, V>
where
    Id: SlabId,
{
    #[inline]
    fn default() -> Self {
        Self {
            raw: Vec::default(),
            len: 0,
            free_index: 0,
            _phantom: PhantomData,
        }
    }
}

impl<ID, V> Slab<ID, V>
where
    ID: SlabId + Copy + Clone,
{
    /// Creates a new slab with the given capacity.
    ///
    /// The slab will be able to hold at least `capacity` elements without
    /// reallocating. This is useful when you know approximately how many
    /// elements you will store.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use vslab::Slab;
    ///
    /// let slab = Slab::<u64, i32>::with_capacity(10);
    /// assert!(slab.capacity() >= 10);
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            raw: Vec::with_capacity(capacity),
            len: 0,
            free_index: 0,
            _phantom: PhantomData,
        }
    }

    /// Inserts a value into the slab, returning a unique key.
    ///
    /// The key can be used to later access, modify, or remove the value.
    /// Keys remain valid even after other values are removed.
    ///
    /// # Performance
    ///
    /// This operation runs in O(1) time.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use vslab::Slab;
    ///
    /// let mut slab = Slab::<u64, &str>::default();
    /// let key = slab.insert("hello");
    /// assert_eq!(slab[key], "hello");
    /// ```
    #[inline]
    pub fn insert(&mut self, value: V) -> ID {
        let (index, version) = if self.free_index >= self.raw.len() {
            debug_assert_eq!(self.free_index, self.raw.len());
            let index = self.free_index;
            let version = 1;
            self.raw.push(Slot::Occupied(Occupied { value, version }));
            self.free_index = self.raw.len();
            (index, version)
        } else {
            let index = self.free_index;
            let slot = &mut self.raw[self.free_index];
            let version = match slot {
                Slot::Occupied(_) => unreachable!(),
                Slot::Free(free) => {
                    self.free_index = free.next;
                    free.version
                }
            };
            *slot = Slot::Occupied(Occupied { value, version });
            (index, version)
        };
        self.len += 1;
        ID::from_raw(index, version)
    }

    /// Removes and returns the value associated with the given key.
    ///
    /// If the key is valid (i.e., it refers to an occupied slot with the correct version),
    /// the value is removed and returned. The slot is then added to the free list for reuse.
    ///
    /// If the key is invalid (stale, never used, or from a different version), `None` is returned.
    ///
    /// # Performance
    ///
    /// This operation runs in O(1) time.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use vslab::Slab;
    ///
    /// let mut slab = Slab::<u64, &str>::default();
    /// let key = slab.insert("hello");
    ///
    /// assert_eq!(slab.remove(key), Some("hello"));
    /// assert_eq!(slab.remove(key), None); // Key is now invalid
    /// ```
    #[allow(clippy::needless_pass_by_value)] // ID is smaller than u64, it is faster to pass by value
    #[inline]
    pub fn remove(&mut self, id: ID) -> Option<V> {
        let index = id.index();
        let slot = self.raw.get_mut(index)?;
        let version = match slot {
            Slot::Occupied(slot) => {
                if slot.version != id.version() {
                    return None;
                }
                slot.version
            }
            Slot::Free(_) => return None,
        };
        let slot = std::mem::replace(
            slot,
            Slot::Free(Free {
                next: self.free_index,
                version: version + 1,
            }),
        );
        self.free_index = index;
        self.len -= 1;
        match slot {
            Slot::Occupied(occupied) => Some(occupied.value),
            Slot::Free(_) => unreachable!(),
        }
    }

    /// Returns a reference to the value associated with the given key.
    ///
    /// If the key is valid (i.e., it refers to an occupied slot with the correct version),
    /// a reference to the value is returned. Otherwise, `None` is returned.
    ///
    /// # Performance
    ///
    /// This operation runs in O(1) time.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use vslab::Slab;
    ///
    /// let mut slab = Slab::<u64, &str>::default();
    /// let key = slab.insert("hello");
    ///
    /// assert_eq!(slab.get(key), Some(&"hello"));
    /// slab.remove(key);
    /// assert_eq!(slab.get(key), None); // Key is now invalid
    /// ```
    #[allow(clippy::needless_pass_by_value)] // ID is smaller than u64, it is faster to pass by value
    #[inline]
    pub fn get(&self, id: ID) -> Option<&V> {
        let index = id.index();
        let slot = self.raw.get(index)?;
        match slot {
            Slot::Occupied(slot) => {
                if slot.version == id.version() {
                    Some(&slot.value)
                } else {
                    None
                }
            }
            Slot::Free(_) => None,
        }
    }

    /// Returns a mutable reference to the value associated with the given key.
    ///
    /// If the key is valid (i.e., it refers to an occupied slot with the correct version),
    /// a mutable reference to the value is returned. Otherwise, `None` is returned.
    ///
    /// # Performance
    ///
    /// This operation runs in O(1) time.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use vslab::Slab;
    ///
    /// let mut slab = Slab::<u64, String>::default();
    /// let key = slab.insert("hello".to_string());
    ///
    /// if let Some(value) = slab.get_mut(key) {
    ///     value.push_str(" world");
    /// }
    /// assert_eq!(slab[key], "hello world");
    /// ```
    #[allow(clippy::needless_pass_by_value)] // ID is smaller than u64, it is faster to pass by value
    #[inline]
    pub fn get_mut(&mut self, id: ID) -> Option<&mut V> {
        let index = id.index();
        let slot = self.raw.get_mut(index)?;
        match slot {
            Slot::Occupied(slot) => {
                if slot.version == id.version() {
                    Some(&mut slot.value)
                } else {
                    None
                }
            }
            Slot::Free(_) => None,
        }
    }

    /// check if the slab contains the key
    #[inline]
    pub fn contains_key(&self, id: ID) -> bool {
        let index = id.index();
        let slot = self.raw.get(index);
        match slot {
            Some(Slot::Occupied(slot)) => slot.version == id.version(),
            _ => false,
        }
    }

    /// Returns the number of elements in the slab.
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the slab contains no elements.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns an iterator over the slab's key-value pairs.
    #[inline]
    pub fn iter(&self) -> Iter<'_, ID, V> {
        Iter {
            index: 0,
            inner: self.raw.iter(),
            _phantom: PhantomData,
        }
    }

    /// Returns a mutable iterator over the slab's key-value pairs.
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<'_, ID, V> {
        IterMut {
            index: 0,
            inner: self.raw.iter_mut(),
            _phantom: PhantomData,
        }
    }

    /// Returns the number of elements the slab can hold without reallocating.
    #[inline]
    pub fn capacity(&self) -> usize {
        self.raw.capacity()
    }

    /// Clears the slab, removing all values.
    #[inline]
    pub fn clear(&mut self) {
        self.free_index = 0;
        self.len = 0;
        for (i, slot) in &mut self.raw.iter_mut().enumerate() {
            match slot {
                Slot::Occupied(v) => {
                    let version = v.version;
                    *slot = Slot::Free(Free {
                        next: i + 1,
                        version: version + 1,
                    });
                }
                Slot::Free(free_v) => {
                    free_v.next = i + 1;
                }
            }
        }
    }
}

/// An iterator over the key-value pairs in a `Slab`.
pub struct Iter<'a, ID, V> {
    index: usize,
    inner: std::slice::Iter<'a, Slot<V>>,
    _phantom: PhantomData<ID>,
}

impl<'a, ID, V> Iterator for Iter<'a, ID, V>
where
    ID: SlabId,
{
    type Item = (ID, &'a V);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.inner.next()? {
                Slot::Occupied(slot) => {
                    let id = ID::from_raw(self.index, slot.version);
                    self.index += 1;
                    return Some((id, &slot.value));
                }
                Slot::Free(_) => {
                    self.index += 1;
                    continue;
                }
            }
        }
    }
}

/// A mutable iterator over the key-value pairs in a `Slab`.
pub struct IterMut<'a, ID, V> {
    index: usize,
    inner: std::slice::IterMut<'a, Slot<V>>,
    _phantom: PhantomData<ID>,
}

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

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.inner.next() {
                Some(Slot::Occupied(slot)) => {
                    let id = ID::from_raw(self.index, slot.version);
                    self.index += 1;
                    return Some((id, &mut slot.value));
                }
                Some(Slot::Free(_)) => {
                    self.index += 1;
                    continue;
                }
                None => return None,
            }
        }
    }
}

impl<ID, V> std::ops::Index<ID> for Slab<ID, V>
where
    ID: SlabId + Copy + Clone,
{
    type Output = V;

    /// # Panics
    ///
    /// Panics if index not found
    #[inline]
    fn index(&self, index: ID) -> &Self::Output {
        self.get(index).expect("index not found")
    }
}

impl<ID, V> std::ops::IndexMut<ID> for Slab<ID, V>
where
    ID: SlabId + Copy + Clone,
{
    /// # Panics
    /// may panic if index not found
    #[inline]
    fn index_mut(&mut self, index: ID) -> &mut V {
        self.get_mut(index).expect("index not found")
    }
}

impl SlabId for u64 {
    #[inline]
    fn index(&self) -> usize {
        *self as u32 as usize
    }

    #[inline]
    fn version(&self) -> u32 {
        (*self >> 32) as u32
    }

    #[inline]
    fn from_raw(index: usize, version: u32) -> Self {
        let index = u64::from(u32::try_from(index).expect("index out of range"));
        let version = u64::from(version);
        version << 32 | index
    }
}

/// Creates a new type-safe key type for use with `Slab`.
///
/// This macro generates a new struct that implements the `SlabId` trait,
/// providing better type safety than using raw `u64` keys directly.
///
/// The generated type includes:
/// - `Debug`, `Clone`, `Copy`, `Hash`, `PartialEq`, `Eq`, `PartialOrd`, `Ord` implementations
/// - `Display` implementation for formatting
/// - `Default` implementation that creates an invalid key
/// - Helper methods like `invalid()`, `is_valid()`, `is_null()`
/// - Conversion methods to/from `u64`
///
/// # Examples
///
/// ```rust
/// use vslab::{Slab, new_type_id};
///
/// // Define a custom key type
/// new_type_id!(EntityId);
///
/// let mut entities = Slab::<EntityId, String>::default();
/// let player_id = entities.insert("Player".to_string());
/// let enemy_id = entities.insert("Enemy".to_string());
///
/// // Type safety: EntityId and u64 keys cannot be mixed
/// // let invalid: Slab<u64, String> = Slab::default();
/// // invalid.insert(player_id); // Compile error!
///
/// assert_eq!(entities[player_id], "Player");
/// assert_eq!(entities[enemy_id], "Enemy");
/// assert!(player_id.is_valid());
/// assert!(!EntityId::invalid().is_valid());
/// ```
#[macro_export]
macro_rules! new_type_id {

    (
        $(#[$outer:meta])*
        $name:ident
    ) => {

        #[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
        #[repr(C)]
        $(#[$outer])*
        pub struct $name(u64);

        impl $crate::SlabId for $name {
            /// Index part of the id
            #[inline]
            fn index(&self) -> usize {
                self.0.index()
            }

            /// Version part of the id
            #[inline]
            fn version(&self) -> u32 {
                self.0.version()
            }

            /// Create a new id from raw index and version
            #[inline]
            fn from_raw(index: usize, version: u32) -> Self {
                Self(u64::from_raw(index, version))
            }
        }

        impl std::fmt::Display for $name {
            #[inline]
            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                self.0.fmt(f)
            }
        }

        impl Default for $name {
            /// The default id is invalid
            #[inline]
            fn default() -> Self {
                $crate::SlabId::from_raw(Self::EMPTY_INDEX, 1)
            }
        }

        impl $name {
            const EMPTY_INDEX: usize = u32::MAX as usize;

            /// Create an invalid id
            #[allow(unused)]
            #[inline]
            pub fn invalid() -> Self {
                Self::default()
            }

            /// Encode the id into a u64
            #[allow(unused)]
            #[inline]
            pub fn into_u64(self) -> u64 {
                self.0
            }

            //// Decode the id from a u64
            #[allow(unused)]
            #[inline]
            pub fn from_u64(id: u64) -> Self {
                Self(id)
            }

            //// Check if the id is valid
            #[allow(unused)]
            #[inline]
            pub fn is_valid(self) -> bool {
                self != Self::default()
            }

            /// Check if the id is null
            #[allow(unused)]
            #[inline]
            pub fn is_null(self) -> bool {
                $crate::SlabId::index(&self) == Self::EMPTY_INDEX
            }
        }
    };
}

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

    use super::*;

    wasm_bindgen_test_configure!(run_in_browser);

    #[test]
    #[wasm_bindgen_test]
    fn test_slab() {
        let mut slab = Slab::<u64, i32>::default();

        let id0 = slab.insert(5);
        assert_eq!(slab.len(), 1);
        assert_eq!(id0.index(), 0);
        assert_eq!(slab.get(id0).unwrap(), &5);

        let id1 = slab.insert(6);
        assert_eq!(slab.len(), 2);
        assert_eq!(id1.index(), 1);
        assert_eq!(slab.get_mut(id0).unwrap(), &5);

        assert_eq!(slab.remove(id0).unwrap(), 5);
        assert_eq!(slab.len(), 1);

        //id0 is removed, so get/remove should return None.
        assert!(slab.remove(id0).is_none());
        assert!(slab.get(id0).is_none());
        assert!(slab.get_mut(id0).is_none());

        let id2 = slab.insert(7);

        assert_eq!(id2.index(), 0);
        assert_eq!(id2.version(), 2);

        // id0 is expired, get/remove should return None
        assert!(slab.get(id0).is_none());
        assert!(slab.get_mut(id0).is_none());
        assert!(slab.remove(id0).is_none());

        assert_eq!(slab.remove(id2).unwrap(), 7);
        assert_eq!(slab.remove(id1).unwrap(), 6);

        assert!(slab.is_empty());

        let invalid_id = u64::from_raw(100, 1);
        assert!(slab.get(invalid_id).is_none());
        assert!(slab.get_mut(invalid_id).is_none());
    }

    #[test]
    #[wasm_bindgen_test]
    fn test_slab_iter() {
        let mut slab = Slab::<u64, i32>::default();

        let mut id = slab.insert(8);
        slab.remove(id).unwrap();
        id = slab.insert(9);
        slab.insert(10);
        slab.insert(11);
        slab.remove(id).unwrap();
        slab.insert(12);

        let mut iter = slab.iter();
        {
            let (id, value) = iter.next().unwrap();
            assert_eq!(id.index(), 0);
            assert_eq!(id.version(), 3);
            assert_eq!(id, u64::from_raw(0, 3));
            assert_eq!(value, &12);
            let value = slab.get(id).unwrap();
            assert_eq!(value, &12);

            let value = slab[id];
            assert_eq!(value, 12);
        }
        {
            let (id, value) = iter.next().unwrap();
            assert_eq!(id.index(), 1);
            assert_eq!(id.version(), 1);
            assert_eq!(id, u64::from_raw(1, 1));
            assert_eq!(value, &10);
            let value = slab.get(id).unwrap();
            assert_eq!(value, &10);

            let value = slab[id];
            assert_eq!(value, 10);
        }
        {
            let (id, value) = iter.next().unwrap();
            assert_eq!(id.index(), 2);
            assert_eq!(id.version(), 1);
            assert_eq!(id, u64::from_raw(2, 1));
            assert_eq!(value, &11);
            let value = slab.get(id).unwrap();
            assert_eq!(value, &11);

            let value = slab[id];
            assert_eq!(value, 11);
        }
        assert!(iter.next().is_none());

        let mut iter = slab.iter_mut();
        {
            let (id, value) = iter.next().unwrap();
            assert_eq!(id.index(), 0);
            assert_eq!(id.version(), 3);
            assert_eq!(id, u64::from_raw(0, 3));
            assert_eq!(value, &mut 12);
        }
        {
            let (id, value) = iter.next().unwrap();
            assert_eq!(id.index(), 1);
            assert_eq!(id.version(), 1);
            assert_eq!(id, u64::from_raw(1, 1));
            assert_eq!(value, &mut 10);
        }
        {
            let (id, value) = iter.next().unwrap();
            assert_eq!(id.index(), 2);
            assert_eq!(id.version(), 1);
            assert_eq!(id, u64::from_raw(2, 1));
            assert_eq!(value, &mut 11);
        }
        assert!(iter.next().is_none());
        assert_eq!(slab.get(u64::from_raw(0, 3)), Some(&12));
        assert_eq!(slab.get(u64::from_raw(1, 1)), Some(&10));

        assert!(slab.contains_key(u64::from_raw(0, 3)));
        assert!(slab.contains_key(u64::from_raw(1, 1)));
        assert!(!slab.contains_key(u64::from_raw(0, 1)));
        assert!(!slab.contains_key(u64::from_raw(1, 3)));
        assert!(slab.contains_key(u64::from_raw(2, 1)));
        assert!(!slab.contains_key(u64::from_raw(3, 1)));

        {
            let slab = &mut slab;

            let value = slab[u64::from_raw(0, 3)];
            assert_eq!(value, 12);
        }

        slab.remove(u64::from_raw(3, 1));
    }

    #[test]
    #[wasm_bindgen_test]
    #[allow(clippy::cast_sign_loss)]
    fn test_slab_capacity() {
        let mut slab = Slab::<u64, i32>::with_capacity(10);
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 0);

        for i in 0..10 {
            slab.insert(i);
            assert_eq!(slab.capacity(), 10);
            assert_eq!(slab.len(), (i + 1) as usize);
        }

        slab.insert(10);
        assert_eq!(slab.capacity(), 20);
        assert_eq!(slab.len(), 11);
    }

    #[test]
    #[wasm_bindgen_test]
    fn test_slab_remove() {
        let mut slab = Slab::<u64, i32>::with_capacity(10);
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 0);

        let id = slab.insert(1);
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 1);

        slab.remove(id);
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 0);

        slab.remove(id);
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 0);
    }

    new_type_id!(TestId);

    #[test]
    #[wasm_bindgen_test]
    fn test_type_id() {
        let id = TestId::default();
        assert_eq!(id.index(), u32::MAX as usize);
        assert_eq!(id.version(), 1);
        assert_eq!(id, TestId::default());
        assert_eq!(id.to_string(), "8589934591");

        let id = TestId::from_raw(1, 2);
        assert_eq!(id.index(), 1);
        assert_eq!(id.version(), 2);
        assert_eq!(id, TestId::from_raw(1, 2));
        assert_eq!(id.to_string(), "8589934593");

        let id = TestId::from_raw(1, 2);
        assert_eq!(id.into_u64(), 8589934593_u64);
        assert_eq!(TestId::from_u64(8589934593_u64), TestId::from_raw(1, 2));
        assert!(id.is_valid());
        assert!(!TestId::default().is_valid());
        assert!(TestId::default().is_null());
    }

    #[test]
    #[wasm_bindgen_test]
    fn test_slab_clear() {
        let mut slab = Slab::<u64, i32>::with_capacity(10);
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 0);

        for i in 0..10 {
            slab.insert(i);
        }
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 10);
        slab.clear();
        assert_eq!(slab.capacity(), 10);
        assert_eq!(slab.len(), 0);
        for (i, v) in slab.raw.iter().enumerate() {
            match v {
                Slot::Occupied(_) => panic!("Occupied slot found"),
                Slot::Free(free_v) => {
                    assert_eq!(free_v.next, i + 1)
                }
            }
        }
        for i in 0..5 {
            slab.insert(i);
        }
        slab.clear();
        for (i, v) in slab.raw.iter().enumerate() {
            match v {
                Slot::Occupied(_) => panic!("Occupied slot found"),
                Slot::Free(free_v) => {
                    assert_eq!(free_v.next, i + 1)
                }
            }
        }
    }
}