wowlab_engine_sim/queue/
mod.rs

1// #t(file: rust_unchecked_indexing) timing wheel with bounded-index arithmetic; all indices masked by WHEEL_MASK or from arena alloc
2
3//! Timing wheel event queue: 32768 slots x 32ms, far-future events held in an overflow bucket reinserted on rotation.
4
5#[cfg(test)]
6mod tests;
7
8mod wheel;
9
10use wheel::{
11    BITMAP_SIZE, DEFAULT_ARENA_CAPACITY, EventNode, NULL_IDX, NodeIdx, OverflowEntry, WHEEL_SIZE,
12    WHEEL_SPAN_MS, WORD_SHIFT,
13};
14use wowlab_engine_ports::Event;
15
16/// Priority event queue using a timing wheel with arena-allocated linked lists.
17pub struct EventQueue {
18    arena: Vec<EventNode>,
19    arena_used: u32,
20    free_head: NodeIdx,
21
22    wheel_head: Vec<NodeIdx>,
23    wheel_tail: Vec<NodeIdx>,
24
25    slot_bitmap: [u64; BITMAP_SIZE],
26    current_slot: usize,
27
28    current_time_ms: u32,
29
30    wheel_base_ms: u32,
31
32    overflow: Vec<OverflowEntry>,
33
34    next_seq: u64,
35    count: usize,
36}
37
38impl EventQueue {
39    /// Construct an empty queue with the default arena capacity.
40    #[must_use]
41    pub fn new() -> Self {
42        Self::with_capacity(DEFAULT_ARENA_CAPACITY)
43    }
44
45    /// Construct an empty queue, pre-sizing the arena to at least `capacity` nodes.
46    #[must_use]
47    pub fn with_capacity(capacity: usize) -> Self {
48        let arena_size = capacity.max(DEFAULT_ARENA_CAPACITY);
49
50        Self {
51            arena: Vec::with_capacity(arena_size),
52            arena_used: 0,
53            free_head: NULL_IDX,
54            wheel_head: vec![NULL_IDX; WHEEL_SIZE],
55            wheel_tail: vec![NULL_IDX; WHEEL_SIZE],
56            slot_bitmap: [0; BITMAP_SIZE],
57            current_slot: 0,
58            current_time_ms: 0,
59            wheel_base_ms: 0,
60            overflow: Vec::new(),
61            next_seq: 0,
62            count: 0,
63        }
64    }
65
66    /// Push an event onto the queue.
67    ///
68    /// # Panics
69    ///
70    /// Panics if the event precedes the last event popped from this queue.
71    pub fn push(&mut self, event: Event) {
72        let time_ms = event.timestamp().as_millis();
73
74        assert!(
75            time_ms >= self.current_time_ms,
76            "event time {time_ms} precedes current queue time {current}",
77            current = self.current_time_ms,
78        );
79        let seq = self.next_seq;
80
81        self.next_seq += 1;
82        self.count += 1;
83
84        if time_ms.wrapping_sub(self.wheel_base_ms) >= WHEEL_SPAN_MS {
85            self.overflow.push(OverflowEntry {
86                time_ms,
87                seq,
88                event,
89            });
90
91            return;
92        }
93
94        self.insert_into_wheel(time_ms, seq, event);
95    }
96
97    /// Pop the highest-priority event (smallest timestamp, priority, then sequence).
98    #[inline]
99    pub fn pop(&mut self) -> Option<Event> {
100        loop {
101            let head_idx = self.wheel_head[self.current_slot];
102
103            if head_idx != NULL_IDX {
104                let event = self.pop_from_slot(self.current_slot, head_idx);
105
106                self.current_time_ms = event.timestamp().as_millis();
107
108                return Some(event);
109            }
110
111            if let Some(next_slot) = self.find_next_slot() {
112                self.current_slot = next_slot;
113            } else {
114                if self.overflow.is_empty() {
115                    return None;
116                }
117
118                self.rotate_wheel_base();
119            }
120        }
121    }
122
123    /// Reset to empty without deallocating; keeps arena/wheel capacity.
124    #[inline]
125    pub fn clear(&mut self) {
126        if self.count == 0 && self.overflow.is_empty() {
127            self.current_slot = 0;
128            self.current_time_ms = 0;
129            self.wheel_base_ms = 0;
130            self.next_seq = 0;
131
132            return;
133        }
134
135        for word_idx in 0..BITMAP_SIZE {
136            let word = self.slot_bitmap[word_idx];
137
138            if word == 0 {
139                continue;
140            }
141
142            let mut bits = word;
143
144            while bits != 0 {
145                let bit_pos = bits.trailing_zeros() as usize;
146                let slot_idx = (word_idx << WORD_SHIFT) | bit_pos;
147
148                self.wheel_head[slot_idx] = NULL_IDX;
149                self.wheel_tail[slot_idx] = NULL_IDX;
150                bits &= bits - 1;
151            }
152
153            self.slot_bitmap[word_idx] = 0;
154        }
155
156        self.overflow.clear();
157        self.arena_used = 0;
158        self.free_head = NULL_IDX;
159        self.current_slot = 0;
160        self.current_time_ms = 0;
161        self.wheel_base_ms = 0;
162        self.next_seq = 0;
163        self.count = 0;
164    }
165
166    /// `true` iff no events are pending in either the wheel or the overflow bucket.
167    #[must_use]
168    pub fn is_empty(&self) -> bool {
169        self.count == 0
170    }
171
172    /// Number of events currently queued, including those in the overflow bucket.
173    #[must_use]
174    pub fn len(&self) -> usize {
175        self.count
176    }
177
178    /// Current sim-time tracked by the queue, advancing monotonically with each `pop`.
179    #[inline]
180    #[cfg(test)]
181    #[must_use]
182    pub(crate) fn current_time_ms(&self) -> u32 {
183        self.current_time_ms
184    }
185}
186
187impl std::fmt::Debug for EventQueue {
188    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
189        f.debug_struct("EventQueue")
190            .field("count", &self.count)
191            .field("arena_used", &self.arena_used)
192            .field("current_slot", &self.current_slot)
193            .field("current_time_ms", &self.current_time_ms)
194            .field("wheel_base_ms", &self.wheel_base_ms)
195            .field("overflow_len", &self.overflow.len())
196            .finish_non_exhaustive()
197    }
198}
199
200impl Default for EventQueue {
201    fn default() -> Self {
202        Self::new()
203    }
204}
wowlab_engine_sim/queue/mod.rs

wowlab_engine_sim/queue/
mod.rs
