cch_rs/cch/
query.rs

1//! High-performance shortest path queries.
2//!
3//! This module implements the bidirectional Dijkstra search used to find the shortest path
4//! within the customized hierarchy.
5//!
6//! To achieve maximum throughput, the query state ([`Query`]) is stored in a thread-local
7//! variable (`QUERY_BUFFER`). It uses an `epoch` counter to implicitly clear the visited
8//! state between queries. This completely eliminates the need for dynamic memory allocation
9//! and `Vec` clearing during individual routing requests.
10
11use crate::cch::Cch;
12use crate::cch::customize::Weights;
13
14#[repr(C)]
15#[derive(Clone, Copy)]
16pub struct QuerySlot {
17    pub dist: f32,
18    pub epoch: u32,
19    pub parent_node: u32,
20    pub parent_edge: u32,
21}
22
23pub struct Query {
24    pub fw: Vec<QuerySlot>,
25    pub bw: Vec<QuerySlot>,
26    pub epoch: u32,
27}
28
29impl Query {
30    pub fn new(n: usize) -> Self {
31        let s = QuerySlot {
32            dist: f32::INFINITY,
33            epoch: 0,
34            parent_node: u32::MAX,
35            parent_edge: u32::MAX,
36        };
37        Self {
38            fw: vec![s; n],
39            bw: vec![s; n],
40            epoch: 0,
41        }
42    }
43
44    pub fn next(&mut self) {
45        self.epoch = self.epoch.wrapping_add(1);
46        if self.epoch == 0 {
47            self.fw.iter_mut().chain(&mut self.bw).for_each(|s| s.epoch = 0);
48            self.epoch = 1;
49        }
50    }
51}
52
53pub struct QueryResult {
54    pub distance: f32,
55    pub from_rank: u32,
56    pub to_rank: u32,
57    pub meeting: u32,
58}
59
60impl Cch {
61    #[inline(always)]
62    unsafe fn relax(&self, u: u32, weights: &[f32], slots: *mut QuerySlot, epoch: u32) -> Option<u32> {
63        let u_idx = u as usize;
64        unsafe {
65            let u_slot = &*slots.add(u_idx);
66            if u_slot.epoch == epoch {
67                let d_u = u_slot.dist;
68                let start = *self.topology.first_out.get_unchecked(u_idx) as usize;
69                let end = *self.topology.first_out.get_unchecked(u_idx + 1) as usize;
70
71                for i in start..end {
72                    let (v_idx, w) = (*self.topology.head.get_unchecked(i) as usize, *weights.get_unchecked(i));
73                    let v_s = &mut *slots.add(v_idx);
74                    let dist = d_u + w;
75
76                    if v_s.epoch != epoch || dist < v_s.dist {
77                        *v_s = QuerySlot {
78                            dist,
79                            epoch,
80                            parent_node: u,
81                            parent_edge: i as u32,
82                        };
83                    }
84                }
85            }
86            *self.topology.etree.get_unchecked(u_idx)
87        }
88    }
89
90    pub fn query(&self, q: &mut Query, w: &Weights, from: u32, to: u32) -> Option<QueryResult> {
91        let (f_r, t_r) = (self.ranks[from as usize], self.ranks[to as usize]);
92        q.next();
93        let (e, fw_p, bw_p) = (q.epoch, q.fw.as_mut_ptr(), q.bw.as_mut_ptr());
94
95        unsafe {
96            let init = |p: *mut QuerySlot| {
97                *p = QuerySlot {
98                    dist: 0.0,
99                    epoch: e,
100                    parent_node: u32::MAX,
101                    parent_edge: u32::MAX,
102                }
103            };
104            init(fw_p.add(f_r as usize));
105            init(bw_p.add(t_r as usize));
106
107            let mut curr = Some(f_r);
108            while let Some(c) = curr {
109                curr = self.relax(c, &w.up, fw_p, e);
110            }
111
112            let (mut best_d, mut meeting, mut curr) = (f32::INFINITY, u32::MAX, Some(t_r));
113            while let Some(c) = curr {
114                let (fs, bs) = (&*fw_p.add(c as usize), &*bw_p.add(c as usize));
115                if fs.epoch == e && bs.epoch == e && fs.dist + bs.dist < best_d {
116                    best_d = fs.dist + bs.dist;
117                    meeting = c;
118                }
119                curr = self.relax(c, &w.down, bw_p, e);
120            }
121
122            (best_d < f32::INFINITY).then_some(QueryResult {
123                distance: best_d,
124                from_rank: f_r,
125                to_rank: t_r,
126                meeting,
127            })
128        }
129    }
130}
cch_rs/cch/query.rs

cch_rs/cch/
query.rs
