oyster.cafe
Nothing to see here, move along meow
1use crate::intrusive_list::{IntrusiveList, ListLinks};
2
3pub struct RunQueueTag;
4
5pub struct RunQueue {
6 bitmap: [u64; 4],
7 lists: [IntrusiveList; 256],
8}
9
10impl RunQueue {
11 pub const fn new() -> Self {
12 Self {
13 bitmap: [0; 4],
14 lists: [IntrusiveList::empty(); 256],
15 }
16 }
17
18 pub fn enqueue(&mut self, id: u32, priority: u8, store: &mut impl ListLinks<RunQueueTag>) {
19 let p = priority as usize;
20 self.lists[p].append(id, store);
21 self.bitmap[p / 64] |= 1u64 << (p % 64);
22 }
23
24 pub fn dequeue_highest(
25 &mut self,
26 store: &mut impl ListLinks<RunQueueTag>,
27 ) -> Option<(u32, u8)> {
28 let (word_idx, bit) = (0..4).rev().find_map(|w| match self.bitmap[w] {
29 0 => None,
30 bits => Some((w, 63 - bits.leading_zeros() as usize)),
31 })?;
32
33 let priority = word_idx * 64 + bit;
34 let head = self.lists[priority].pop_head(store)?;
35
36 if self.lists[priority].is_empty() {
37 self.bitmap[word_idx] &= !(1u64 << bit);
38 }
39
40 Some((head, priority as u8))
41 }
42
43 pub fn remove(&mut self, id: u32, priority: u8, store: &mut impl ListLinks<RunQueueTag>) {
44 let p = priority as usize;
45 if self.lists[p].unlink(id, store) && self.lists[p].is_empty() {
46 self.bitmap[p / 64] &= !(1u64 << (p % 64));
47 }
48 }
49
50 pub fn is_empty(&self) -> bool {
51 self.bitmap[0] == 0 && self.bitmap[1] == 0 && self.bitmap[2] == 0 && self.bitmap[3] == 0
52 }
53}