Struct FairClassRq 

pub struct FairClassRq { /* private fields */ }

Per-CPU run queue for the Completely Fair Scheduler.

Uses two BTreeMaps for O(log n) operations without allocation on the fast paths (pick_next, remove):

• entities: primary map keyed by (vruntime, task_id) : the minimum entry is always the next task to schedule.
• by_id: reverse index mapping task_id → primary key : enables O(log n) removal by task ID in remove() without scanning entities.

This replaces the previous BinaryHeap-based design which used lazy deletion (O(n) remove() scan, phantom entries, generation counters). The BTreeMap approach gives:

Operation	Complexity	Allocates?
enqueue	O(log n)	yes : 2 BTreeMap nodes (wakeup path)
pick_next	O(log n)	no : removes 2 nodes
remove	O(log n)	no : removes 2 nodes

No phantom entries means no generation counter, no prune_stale_head(), and no per-entry liveness checks. The BTreeMap pair is the authoritative record of which tasks are currently on the run queue.

Implementations

impl FairClassRq

pub fn new() -> Self

Creates a new instance.

Trait Implementations

impl SchedClassRq for FairClassRq

fn enqueue(&mut self, task: Arc<Task>)

Enqueues a task onto the run queue.

Clamps vruntime to min_vruntime so waking tasks do not receive an unfair head start over tasks that have been waiting. O(log n); allocates two BTreeMap nodes.

fn len(&self) -> usize

Returns the number of tasks currently on the run queue.

fn pick_next(&mut self) -> Option<Arc<Task>>

Picks the next task to run: the one with the smallest vruntime.

O(log n), allocation-free.

fn update_current( &mut self, rt: &CurrentRuntime, task: &Task, is_yield: bool, ) -> bool

Updates the vruntime of the currently-running task and decides whether it should be preempted.

Returns true if the task has exhausted its time slice or its vruntime has overtaken the leftmost task’s vruntime by more than vtime_slice.

fn remove(&mut self, task_id: TaskId) -> bool

Removes the task identified by task_id from the run queue.

Uses the by_id reverse index for O(log n) lookup, then removes both entries. Allocation-free. Returns true if the task was present.

fn is_empty(&self) -> bool

Returns whether empty.