flaque 0.2.0

// Copyright 2026 Ivan Enderlin <ivan@mnt.io>. Licensed under the EUPL, version
// 1.2. See the `LICENSE` file.

use super::{
    cache_padded::CachePadded,
    sys::{
        hint,
        sync::atomic::{AtomicU8, Ordering},
    },
};

/// Type alias to represent the atomic value representing multiple slots.
///
/// A “row of slots” is 8 bits:
///
/// - 1 means the slot is vacant,
/// - 0 means the slot is occupied.
type AtomicSlots = AtomicU8;

/// Type alias to represent the index of a slot in an [`AtomicSlots`].
///
/// Considering [`AtomicSlots`] is a `u8`, then [`SlotIndex`] is a bit offset.
pub type SlotIndex = u32;

/// All the slots. See [`AtomicSlots`] to get a bit more information about the
/// representation.
#[repr(transparent)]
pub struct Slots(CachePadded<AtomicSlots>);

impl Slots {
    pub const SLOTS_SIZE: u32 = u8::BITS;
    const ALL_VACANT: u8 = u8::MAX;

    pub fn new() -> Self {
        Self(CachePadded::new(AtomicSlots::new(
            // 0 means occupied, 1 means vacant.
            // Start with all vacant, so only 1s.
            Self::ALL_VACANT,
        )))
    }

    /// Try to acquire a slot.
    ///
    /// If the slot is acquired, it returns `Some(slot_index)`, otherwise it
    /// returns `None` if all slots are occupied.
    pub fn try_acquire(&self) -> Option<SlotIndex> {
        let mut all_slots = self.0.load(Ordering::Relaxed);

        loop {
            let Some(vacant_slot) = all_slots.isolate_lowest_vacant() else {
                // All slots are occupied.
                return None;
            };

            let all_slots_with_vacant_turned_occupied = all_slots ^ vacant_slot;

            let Err(next_all_slots) = self.0.compare_exchange_weak(
                all_slots,
                all_slots_with_vacant_turned_occupied,
                Ordering::AcqRel,
                Ordering::Acquire,
            ) else {
                return Some(vacant_slot.index());
            };

            all_slots = next_all_slots;

            hint::spin_loop();
        }
    }

    pub fn release(&self, slot_index: SlotIndex) {
        let occupied_slot = 1 << slot_index;
        let mut all_slots = self.0.load(Ordering::Relaxed);

        loop {
            let all_slots_with_occupied_turned_vacant =
                all_slots ^ occupied_slot;

            if all_slots & occupied_slot > 0 {
                unreachable!("Releasing to a vacant slot is impossible");
            }

            let Err(next_all_slots) = self.0.compare_exchange_weak(
                all_slots,
                all_slots_with_occupied_turned_vacant,
                Ordering::AcqRel,
                Ordering::Acquire,
            ) else {
                return;
            };

            // If it failed, it's either because:
            //
            // - the slots have been modified, which is okay, let's retry until
            //   it succeeds (it must succeed because the occupied slot cannot
            //   be vacant),
            // - the occupied slot is vacant, which is a misuse of the API; a
            //   slot must not be disposed twice.

            all_slots = next_all_slots;

            hint::spin_loop();
        }
    }

    pub fn is_all_vacants(&self) -> bool {
        self.0.load(Ordering::Relaxed) == Self::ALL_VACANT
    }
}

trait Vacant {
    fn isolate_lowest_vacant(self) -> Option<Self>
    where
        Self: Sized;

    fn index(self) -> u32;
}

impl Vacant for u8 {
    /// Find the lowest vacant position in a `u8`, i.e. the lowest 1.
    ///
    /// ```rust,ignore
    /// assert_eq!(0b_0010_1000_u8.isolate_lowest_vacant(), 0b_0000_1000);
    /// ```
    #[inline(always)]
    fn isolate_lowest_vacant(self) -> Option<Self> {
        let lowest_one = self.isolate_lowest_one();

        (lowest_one > 0).then_some(lowest_one)
    }

    /// Find the offset of a 1 in this `u8`.
    ///
    /// ```rust,ignore
    /// assert_eq!(0b_0010_0000_u8.index(), 5);
    /// ```
    #[inline(always)]
    fn index(self) -> u32 {
        self.trailing_zeros()
    }
}

#[cfg(test)]
mod tests {
    use super::{super::tests_helper::run, Slots, Vacant};

    #[test]
    fn test_try_acquire() {
        run(|| {
            let slots = Slots::new();

            assert_eq!(slots.try_acquire(), Some(0));
            assert_eq!(slots.try_acquire(), Some(1));
            assert_eq!(slots.try_acquire(), Some(2));
            assert_eq!(slots.try_acquire(), Some(3));
            assert_eq!(slots.try_acquire(), Some(4));
            assert_eq!(slots.try_acquire(), Some(5));
            assert_eq!(slots.try_acquire(), Some(6));
            assert_eq!(slots.try_acquire(), Some(7));
            // 8 slots maximum: they are all occupied.
            assert!(slots.try_acquire().is_none());
        })
    }

    #[test]
    fn test_release() {
        run(|| {
            let slots = Slots::new();

            // Acquire a new slot: the first available is slot 0.
            let slot_0 = slots.try_acquire().unwrap();
            assert_eq!(slot_0, 0);

            // Release slot 0.
            slots.release(slot_0);

            // Acquire new slots: the firsts available are slots 0, 1, 2 and 3.
            let slot_0 = slots.try_acquire().unwrap();
            assert_eq!(slot_0, 0);

            let slot_1 = slots.try_acquire().unwrap();
            assert_eq!(slot_1, 1);

            let slot_2 = slots.try_acquire().unwrap();
            assert_eq!(slot_2, 2);

            let slot_3 = slots.try_acquire().unwrap();
            assert_eq!(slot_3, 3);

            // Release slot 1.
            slots.release(slot_1);

            // Acquire a new slot: the first available is slot 1.
            let slot_1 = slots.try_acquire().unwrap();
            assert_eq!(slot_1, 1);

            // Acquire new slots: the firsts available are slots 4, 5, 6 and 7.
            let slot_4 = slots.try_acquire().unwrap();
            assert_eq!(slot_4, 4);

            let slot_5 = slots.try_acquire().unwrap();
            assert_eq!(slot_5, 5);

            let slot_6 = slots.try_acquire().unwrap();
            assert_eq!(slot_6, 6);

            let slot_7 = slots.try_acquire().unwrap();
            assert_eq!(slot_7, 7);

            // No slots available.
            assert!(slots.try_acquire().is_none());

            // Release slot 1.
            slots.release(slot_1);

            // Acquire a new slot: the first available is slot 1.
            let slot_1 = slots.try_acquire().unwrap();
            assert_eq!(slot_1, 1);

            // Release slot 5.
            slots.release(slot_4);

            // Acquire a new slot: the first available is slot 5.
            let slot_4 = slots.try_acquire().unwrap();
            assert_eq!(slot_4, 4);
        })
    }

    #[test]
    #[should_panic]
    fn test_release_twice() {
        run(|| {
            let slots = Slots::new();

            // Acquire a new slot.
            let slot_0 = slots.try_acquire().unwrap();
            assert_eq!(slot_0, 0);

            // Release slot 0 twice. It's impossible.
            slots.release(slot_0);
            slots.release(slot_0);
        })
    }

    #[test]
    fn test_vacant_trait() {
        run(|| {
            assert_eq!(
                0b0010_1000_u8.isolate_lowest_vacant(),
                Some(0b0000_1000)
            );
            assert_eq!(
                0b0010_1000_u8.isolate_lowest_vacant().unwrap().index(),
                3
            );
            assert!(0b0000_0000_u8.isolate_lowest_vacant().is_none());
        })
    }
}