moa_idalloc 0.1.4

//! 密集回收式 id 分配器(位图实现)。

use moa_bitops::bitmap::BitMap;

/// 位图初始容量(位数);用满后翻倍增长。
const INITIAL_CAP: usize = 64;

/// 密集回收式 id 分配器。
///
/// [`alloc`](IdAllocator::alloc) 总是返回**当前最小的空闲 id**,[`free`](IdAllocator::free)
/// 后立即回收复用,位图按需翻倍增长。适合需要小而密、可读、可复用号的场景(如 pid)。
///
/// 本身**不加锁**——并发使用时由调用方用锁(如 `Spinlock`)包裹。
pub struct IdAllocator {
    map: BitMap,
    /// 下次搜索的起点提示(并非已分配数量)。
    next: usize,
    /// 当前位图容量(位数);`0` 表示尚未初始化。
    cap: usize,
}

impl IdAllocator {
    /// 创建一个空分配器(惰性初始化,首次 `alloc` 时再分配位图)。
    pub const fn new() -> Self {
        Self { map: BitMap::new(), next: 0, cap: 0 }
    }

    /// 分配最小的空闲 id;位图用满时自动翻倍扩容。
    #[inline]
    pub fn alloc(&mut self) -> usize {
        if self.cap == 0 {
            self.map.init(INITIAL_CAP);
            self.cap = INITIAL_CAP;
        }
        let mut idx = self.map.find_next_zero_bit(self.next);
        if idx == self.cap {
            self.map.extend(self.cap);
            self.cap *= 2;
            idx = self.map.find_next_zero_bit(idx);
        }
        self.next = idx + 1;
        self.map.set_bit(idx);
        idx
    }

    /// 归还一个先前由 [`alloc`](IdAllocator::alloc) 分配的 id,使其可被复用。
    ///
    /// 释放从未分配过/超出当前容量的 id 是无操作(不会越界 panic)。
    #[inline]
    pub fn free(&mut self, id: usize) {
        if id >= self.cap {
            return;
        }
        self.map.clear_bit(id);
        // 把搜索提示回退到被释放的位置,保证"最小空闲优先"。
        if self.next > id {
            self.next = id;
        }
    }
}

impl Default for IdAllocator {
    fn default() -> Self {
        Self::new()
    }
}