wowlab_engine_sim/queue/
wheel.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 mechanics: arena allocation, slot bitmap, insertion, and the unsafe hot-path pop.
4
5use wowlab_engine_ports::Event;
6
7use super::EventQueue;
8
9pub(super) const WHEEL_SHIFT: u32 = 5;
10pub(super) const WHEEL_SIZE: usize = 32768;
11pub(super) const WHEEL_MASK: usize = WHEEL_SIZE - 1;
12pub(super) const BITMAP_SIZE: usize = WHEEL_SIZE / 64;
13
14pub(super) const DEFAULT_ARENA_CAPACITY: usize = 16384;
15pub(super) const WORD_SHIFT: usize = 6;
16pub(super) const BIT_POSITION_MASK: usize = 63;
17
18pub(super) const WHEEL_SPAN_MS: u32 = 32_768_u32 << WHEEL_SHIFT;
19
20pub(super) type NodeIdx = u32;
21pub(super) const NULL_IDX: NodeIdx = u32::MAX;
22
23#[derive(Clone)]
24pub(super) struct EventNode {
25    pub(super) time_ms: u32,
26    pub(super) seq: u64,
27    pub(super) event: Event,
28    pub(super) next: NodeIdx,
29}
30
31#[derive(Clone)]
32pub(super) struct OverflowEntry {
33    pub(super) time_ms: u32,
34    pub(super) seq: u64,
35    pub(super) event: Event,
36}
37
38impl EventQueue {
39    pub(super) fn insert_into_wheel(&mut self, time_ms: u32, seq: u64, event: Event) {
40        #[cfg(debug_assertions)]
41        {
42            let delta = time_ms.wrapping_sub(self.wheel_base_ms);
43
44            debug_assert!(
45                delta < WHEEL_SPAN_MS,
46                "timing wheel wrap-around: delta {} from wheel_base {} exceeds span {} (WHEEL_SIZE={})",
47                delta,
48                self.wheel_base_ms,
49                WHEEL_SPAN_MS,
50                WHEEL_SIZE,
51            );
52        };
53
54        let slot_idx = time_to_slot(time_ms);
55        let new_idx = self.alloc_node(time_ms, seq, event);
56
57        let tail_idx = self.wheel_tail[slot_idx];
58
59        if tail_idx == NULL_IDX {
60            self.wheel_head[slot_idx] = new_idx;
61            self.wheel_tail[slot_idx] = new_idx;
62            self.set_slot_bit(slot_idx);
63
64            return;
65        }
66
67        let tail = &self.arena[tail_idx as usize];
68
69        if event_order_after(time_ms, event, seq, tail.time_ms, tail.event, tail.seq) {
70            self.arena[tail_idx as usize].next = new_idx;
71            self.wheel_tail[slot_idx] = new_idx;
72
73            return;
74        }
75
76        let mut prev_idx = NULL_IDX;
77        let mut curr_idx = self.wheel_head[slot_idx];
78
79        while curr_idx != NULL_IDX {
80            let curr = &self.arena[curr_idx as usize];
81
82            if event_order_after(curr.time_ms, curr.event, curr.seq, time_ms, event, seq) {
83                break;
84            }
85
86            prev_idx = curr_idx;
87            curr_idx = curr.next;
88        }
89
90        self.arena[new_idx as usize].next = curr_idx;
91
92        if prev_idx == NULL_IDX {
93            self.wheel_head[slot_idx] = new_idx;
94        } else {
95            self.arena[prev_idx as usize].next = new_idx;
96        }
97    }
98
99    pub(super) fn rotate_wheel_base(&mut self) {
100        self.wheel_base_ms = self.wheel_base_ms.wrapping_add(WHEEL_SPAN_MS);
101        self.current_slot = 0;
102
103        let span = WHEEL_SPAN_MS;
104        let base = self.wheel_base_ms;
105
106        let drained: Vec<OverflowEntry> = std::mem::take(&mut self.overflow);
107
108        for entry in drained {
109            if entry.time_ms.wrapping_sub(base) >= span {
110                self.overflow.push(entry);
111                continue;
112            }
113
114            self.insert_into_wheel(entry.time_ms, entry.seq, entry.event);
115        }
116    }
117
118    #[inline]
119    pub(super) fn pop_from_slot(&mut self, slot: usize, head_idx: NodeIdx) -> Event {
120        debug_assert!(
121            (head_idx as usize) < self.arena.len(),
122            "head_idx {head_idx} out of arena bounds {len}",
123            len = self.arena.len(),
124        );
125        // SAFETY: head_idx is alloc_node-issued, so it is in-bounds.
126        let node = unsafe { self.arena.get_unchecked(head_idx as usize) };
127        let event = node.event;
128        let next = node.next;
129
130        self.wheel_head[slot] = next;
131
132        if next == NULL_IDX {
133            self.wheel_tail[slot] = NULL_IDX;
134            self.clear_slot_bit(slot);
135        }
136
137        self.free_node(head_idx);
138        self.count -= 1;
139
140        event
141    }
142
143    #[inline]
144    pub(super) fn set_slot_bit(&mut self, slot: usize) {
145        let word = slot >> WORD_SHIFT;
146        let bit = slot & BIT_POSITION_MASK;
147
148        self.slot_bitmap[word] |= 1u64 << bit;
149    }
150
151    #[inline]
152    pub(super) fn clear_slot_bit(&mut self, slot: usize) {
153        let word = slot >> WORD_SHIFT;
154        let bit = slot & BIT_POSITION_MASK;
155
156        self.slot_bitmap[word] &= !(1u64 << bit);
157    }
158
159    #[inline]
160    pub(super) fn find_next_slot(&self) -> Option<usize> {
161        let start_word = self.current_slot >> WORD_SHIFT;
162        let start_bit = self.current_slot & BIT_POSITION_MASK;
163
164        let mask = !0u64 << start_bit;
165        let masked = self.slot_bitmap[start_word] & mask;
166
167        if masked != 0 {
168            return Some((start_word << WORD_SHIFT) | masked.trailing_zeros() as usize);
169        }
170
171        for word_idx in (start_word + 1)..BITMAP_SIZE {
172            let word = self.slot_bitmap[word_idx];
173
174            if word != 0 {
175                return Some((word_idx << WORD_SHIFT) | word.trailing_zeros() as usize);
176            }
177        }
178
179        None
180    }
181
182    #[inline]
183    pub(super) fn alloc_node(&mut self, time_ms: u32, seq: u64, event: Event) -> NodeIdx {
184        if self.free_head != NULL_IDX {
185            let idx = self.free_head;
186
187            #[cfg(debug_assertions)]
188            debug_assert_ne!(idx, NULL_IDX, "free-list head must not be sentinel");
189            self.free_head = self.arena[idx as usize].next;
190            self.arena[idx as usize] = EventNode {
191                time_ms,
192                seq,
193                event,
194                next: NULL_IDX,
195            };
196
197            idx
198        } else if (self.arena_used as usize) < self.arena.len() {
199            let idx = self.arena_used;
200
201            self.arena[idx as usize] = EventNode {
202                time_ms,
203                seq,
204                event,
205                next: NULL_IDX,
206            };
207            self.arena_used += 1;
208
209            idx
210        } else {
211            let idx = NodeIdx::try_from(self.arena.len())
212                .expect("event queue arena exceeds the u32 node-index space");
213
214            self.arena.push(EventNode {
215                time_ms,
216                seq,
217                event,
218                next: NULL_IDX,
219            });
220            self.arena_used = NodeIdx::try_from(self.arena.len())
221                .expect("event queue arena exceeds the u32 node-index space");
222
223            idx
224        }
225    }
226
227    #[inline]
228    pub(super) fn free_node(&mut self, idx: NodeIdx) {
229        #[cfg(debug_assertions)]
230        debug_assert_ne!(idx, self.free_head, "double-free of free-list head");
231
232        self.arena[idx as usize].next = self.free_head;
233        self.free_head = idx;
234    }
235}
236
237#[inline]
238const fn time_to_slot(time_ms: u32) -> usize {
239    ((time_ms >> WHEEL_SHIFT) as usize) & WHEEL_MASK
240}
241
242#[inline]
243fn event_order_after(
244    left_time: u32,
245    left_event: Event,
246    left_seq: u64,
247    right_time: u32,
248    right_event: Event,
249    right_seq: u64,
250) -> bool {
251    (left_time, left_event.priority(), left_seq) > (right_time, right_event.priority(), right_seq)
252}
wowlab_engine_sim/queue/wheel.rs

wowlab_engine_sim/queue/
wheel.rs
