surelock 0.1.0

//! Pre-sorted lock collection.
//!
//! A [`LockSet`] wraps an [`Acquirable`] and pre-computes the acquisition
//! order (sorted by [`LockId`]). Construct once, lock many times via
//! [`MutexKey::lock`](crate::key::MutexKey::lock).

use alloc::vec::Vec;

use crate::{acquirable::Acquirable, id::LockId};

/// A prepared set of locks, pre-sorted by [`LockId`].
///
/// For tuples of arity 3 and above and for slices, all locks must be
/// at the same level. 2-tuples may contain locks at different levels
/// (the key advances to the maximum of the two). Construct once,
/// lock many times via [`MutexKey::lock`](crate::key::MutexKey::lock).
///
/// # Examples
///
/// ```rust
/// use surelock::{mutex::Mutex, set::LockSet};
///
/// let a: Mutex<u32> = Mutex::new(1);
/// let b: Mutex<u32> = Mutex::new(2);
///
/// // Sort happens once at construction time.
/// let set = LockSet::new((&a, &b));
/// ```
pub struct LockSet<L> {
    group: L,
    /// Indices into the group, sorted by `LockId`.
    sorted_indices: Vec<usize>,
}

impl<L: core::fmt::Debug> core::fmt::Debug for LockSet<L> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("LockSet")
            .field("sorted_indices", &self.sorted_indices)
            .finish_non_exhaustive()
    }
}

/// Build a sorted index permutation from a group's [`LockId`]s.
///
/// Returns the sorted indices and whether any duplicates were found.
#[allow(clippy::indexing_slicing)] // indices are 0..ids.len(), always in bounds
pub(crate) fn build_sorted<'a, L: Acquirable<'a>>(group: &L) -> (Vec<usize>, bool) {
    let mut ids: Vec<LockId> = Vec::new();
    group.collect_ids(&mut ids);

    let mut indices: Vec<usize> = (0..ids.len()).collect();
    indices.sort_by_key(|&i| ids[i]);

    let has_duplicates = indices.windows(2).any(|w| ids[w[0]] == ids[w[1]]);

    (indices, has_duplicates)
}

impl<L> LockSet<L> {
    /// Create a new `LockSet`, pre-sorting by [`LockId`].
    ///
    /// Construction allocates a small index vector proportional to
    /// the number of locks. For hot loops acquiring the same set
    /// repeatedly, construct the `LockSet` once outside the loop
    /// and reuse it.
    ///
    /// An empty group (e.g., an empty slice) is valid. Locking an
    /// empty set is a no-op that still advances the key's level to
    /// the group's `MaxLvl`.
    ///
    /// See [`try_new`](LockSet::try_new) for a non-panicking
    /// alternative that returns `None` on duplicates.
    ///
    /// # Panics
    ///
    /// Panics if any two locks in the group share the same
    /// [`LockId`] (i.e., the same `&Mutex` appears
    /// more than once).
    #[must_use]
    pub fn new<'a>(group: L) -> Self
    where
        L: Acquirable<'a>,
    {
        let (sorted_indices, has_duplicates) = build_sorted(&group);

        assert!(!has_duplicates, "LockSet contains duplicate locks");

        Self {
            group,
            sorted_indices,
        }
    }

    /// Try to create a new `LockSet`, returning `None` if any locks
    /// are duplicated.
    ///
    /// Same as [`new`](LockSet::new) but returns `None` instead of
    /// panicking when two locks share the same
    /// [`LockId`]. An empty group always returns
    /// `Some`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use surelock::{mutex::Mutex, set::LockSet};
    ///
    /// let a: Mutex<u32> = Mutex::new(1);
    /// let b: Mutex<u32> = Mutex::new(2);
    ///
    /// // Distinct locks -- succeeds.
    /// assert!(LockSet::try_new((&a, &b)).is_some());
    ///
    /// // Same lock twice -- returns None.
    /// assert!(LockSet::try_new((&a, &a)).is_none());
    /// ```
    #[must_use]
    pub fn try_new<'a>(group: L) -> Option<Self>
    where
        L: Acquirable<'a>,
    {
        let (sorted_indices, has_duplicates) = build_sorted(&group);

        if has_duplicates {
            return None;
        }

        Some(Self {
            group,
            sorted_indices,
        })
    }

    /// Acquire all locks in sorted order, returning guards.
    pub(crate) fn lock_sorted<'a>(&'a self) -> <L as Acquirable<'a>>::Guard
    where
        L: Acquirable<'a>,
    {
        self.group.lock_sorted(&self.sorted_indices)
    }
}