linkrs_storage/edge/pure_csr/
iter.rs

1use linkrs_core::types::{EdgeId, VertexId};
2
3use super::super::Nbr;
4use super::overflow::PureOverflowChunk;
5use super::{PureTopologyCsr, INVALID_EDGE_ID};
6
7/// Borrowed walk over one pure-topology row.
8///
9/// Holds slices of the primary window plus the overflow chain reference, so
10/// iteration needs no allocation. Sentinel holes are skipped inline.
11#[derive(Debug, Clone, Copy)]
12pub struct PureRowIter<'a> {
13    pub(crate) csr: &'a PureTopologyCsr,
14    pub(crate) primary_endpoints: &'a [u32],
15    pub(crate) primary_ids: &'a [u64],
16    pub(crate) primary_idx: usize,
17    pub(crate) overflow: Option<&'a Vec<PureOverflowChunk>>,
18    pub(crate) chunk_idx: usize,
19    pub(crate) slot_idx: usize,
20}
21
22impl<'a> Iterator for PureRowIter<'a> {
23    type Item = Nbr;
24
25    fn next(&mut self) -> Option<Self::Item> {
26        while self.primary_idx < self.primary_endpoints.len() {
27            let endpoint = self.primary_endpoints[self.primary_idx];
28            let edge_id = EdgeId(self.primary_ids[self.primary_idx]);
29            self.primary_idx += 1;
30            if edge_id != INVALID_EDGE_ID {
31                return Some(self.csr.make_nbr(endpoint, edge_id));
32            }
33        }
34        let chunks = self.overflow?;
35        while self.chunk_idx < chunks.len() {
36            let chunk = &chunks[self.chunk_idx];
37            while self.slot_idx < chunk.len() {
38                let endpoint = chunk.endpoints[self.slot_idx];
39                let edge_id = EdgeId(chunk.edge_ids[self.slot_idx]);
40                self.slot_idx += 1;
41                if edge_id != INVALID_EDGE_ID {
42                    return Some(self.csr.make_nbr(endpoint, edge_id));
43                }
44            }
45            self.chunk_idx += 1;
46            self.slot_idx = 0;
47        }
48        None
49    }
50}
51
52/// Borrowed walk over every live entry of the table without allocating.
53///
54/// Advances one borrowed row walk at a time, so full-table rebuilds and
55/// scans iterate with no intermediate vector regardless of primary versus
56/// overflow layout. Sentinel holes are skipped inline by the row walk.
57#[derive(Debug, Clone, Copy)]
58pub struct PureAllIter<'a> {
59    pub(crate) csr: &'a PureTopologyCsr,
60    pub(crate) cap: u32,
61    pub(crate) vid: u32,
62    pub(crate) row: PureRowIter<'a>,
63}
64
65impl<'a> Iterator for PureAllIter<'a> {
66    type Item = (VertexId, Nbr);
67
68    fn next(&mut self) -> Option<Self::Item> {
69        loop {
70            if self.vid >= self.cap {
71                return None;
72            }
73            if let Some(nbr) = self.row.next() {
74                return Some((VertexId::from_u32(self.vid), nbr));
75            }
76            self.vid += 1;
77            if self.vid < self.cap {
78                self.row = self.csr.iter_row(self.vid);
79            }
80        }
81    }
82}
linkrs_storage/edge/pure_csr/iter.rs

linkrs_storage/edge/pure_csr/
iter.rs
