linkrs_storage/edge/pure_csr/
trait_impl.rs

1use linkrs_core::types::{EdgeId, Timestamp, VertexId};
2use linkrs_core::StorageResult;
3
4use super::super::csr_trait::MutableCsrTrait;
5use super::super::{EdgePosition, Nbr};
6use super::overflow::PureOverflowChunk;
7use super::{PureTopologyCsr, INVALID_EDGE_ID};
8
9impl MutableCsrTrait for PureTopologyCsr {
10    fn insert_edge(
11        &mut self,
12        src_vid: u32,
13        dst: VertexId,
14        edge_id: EdgeId,
15        _ts: Timestamp,
16    ) -> StorageResult<()> {
17        self.insert_edge_returning_position(src_vid, dst, edge_id)
18            .map(|_| ())
19    }
20
21    fn delete_edge(
22        &mut self,
23        src_vid: u32,
24        edge_id: EdgeId,
25        _ts: Timestamp,
26    ) -> StorageResult<bool> {
27        if super::super::csr_shared::is_gap_edge(edge_id) {
28            return Ok(false);
29        }
30
31        let src_idx = src_vid as usize;
32        if src_idx >= self.vertex_capacity() {
33            return Ok(false);
34        }
35
36        let found = {
37            let (start, end) = self.primary_window(src_idx);
38            self.edge_ids[start..end]
39                .iter()
40                .enumerate()
41                .find_map(|(i, &eid)| {
42                    if EdgeId(eid) == edge_id {
43                        Some((start + i, self.endpoints[start + i]))
44                    } else {
45                        None
46                    }
47                })
48        };
49        if let Some((idx, endpoint)) = found {
50            self.edge_ids[idx] = INVALID_EDGE_ID.0;
51            self.edge_count -= 1;
52            self.track_live_remove(src_vid, endpoint);
53            return Ok(true);
54        }
55
56        if let Some((chunk_idx, edge_idx)) = self.scan_overflow_for_edge_id(src_vid, edge_id) {
57            let endpoint =
58                self.overflow_chunks.get(src_vid).unwrap()[chunk_idx].endpoints[edge_idx];
59            if let Some(chunks) = self.overflow_chunks.get_mut(src_vid) {
60                chunks[chunk_idx].edge_ids[edge_idx] = INVALID_EDGE_ID.0;
61                self.edge_count -= 1;
62                self.track_live_remove(src_vid, endpoint);
63                return Ok(true);
64            }
65        }
66
67        Ok(false)
68    }
69
70    fn delete_edge_by_dst(&mut self, src_vid: u32, dst: VertexId, ts: Timestamp) -> usize {
71        let mut noop = |_: EdgeId| {};
72        self.delete_edge_by_dst_reporting(src_vid, dst, ts, &mut noop)
73    }
74
75    fn delete_edge_by_dst_reporting(
76        &mut self,
77        src_vid: u32,
78        dst: VertexId,
79        _ts: Timestamp,
80        on_deleted: &mut dyn FnMut(EdgeId),
81    ) -> usize {
82        let Some((decoded_endpoint, _decoded_rank)) = dst.try_decode_edge_endpoint() else {
83            return 0;
84        };
85        let Some(target_endpoint) = decoded_endpoint.as_internal_u32() else {
86            return 0;
87        };
88        let src_idx = src_vid as usize;
89        if src_idx >= self.vertex_capacity() {
90            return 0;
91        }
92
93        let mut deleted = 0usize;
94
95        let (start, end) = self.primary_window(src_idx);
96        for i in start..end {
97            if self.endpoints[i] == target_endpoint && self.edge_ids[i] != INVALID_EDGE_ID.0 {
98                let eid = EdgeId(self.edge_ids[i]);
99                self.edge_ids[i] = INVALID_EDGE_ID.0;
100                self.edge_count -= 1;
101                on_deleted(eid);
102                deleted += 1;
103            }
104        }
105
106        if let Some(chunks) = self.overflow_chunks.get_mut(src_vid) {
107            for chunk in chunks.iter_mut() {
108                let to_delete: Vec<(usize, u64)> = chunk
109                    .edge_ids
110                    .iter()
111                    .enumerate()
112                    .filter(|(i, &eid)| {
113                        chunk.endpoints[*i] == target_endpoint && EdgeId(eid) != INVALID_EDGE_ID
114                    })
115                    .map(|(i, &eid)| (i, eid))
116                    .collect();
117                for (i, eid) in to_delete {
118                    chunk.edge_ids[i] = INVALID_EDGE_ID.0;
119                    self.edge_count -= 1;
120                    on_deleted(EdgeId(eid));
121                    deleted += 1;
122                }
123            }
124        }
125
126        if deleted > 0 {
127            self.track_live_remove(src_vid, target_endpoint);
128        }
129
130        deleted
131    }
132
133    fn delete_edge_by_dst_reporting_positioned(
134        &mut self,
135        src_vid: u32,
136        dst: VertexId,
137        _ts: Timestamp,
138        on_deleted: &mut dyn FnMut(EdgeId, Option<EdgePosition>),
139    ) -> usize {
140        let Some((decoded_endpoint, _decoded_rank)) = dst.try_decode_edge_endpoint() else {
141            return 0;
142        };
143        let Some(target_endpoint) = decoded_endpoint.as_internal_u32() else {
144            return 0;
145        };
146        let src_idx = src_vid as usize;
147        if src_idx >= self.vertex_capacity() {
148            return 0;
149        }
150
151        let mut deleted = 0usize;
152
153        let (start, end) = self.primary_window(src_idx);
154        for (i, idx) in (start..end).enumerate() {
155            if self.endpoints[idx] == target_endpoint && self.edge_ids[idx] != INVALID_EDGE_ID.0 {
156                let eid = EdgeId(self.edge_ids[idx]);
157                self.edge_ids[idx] = INVALID_EDGE_ID.0;
158                self.edge_count -= 1;
159                on_deleted(eid, Some(EdgePosition::Primary { slot: i as u32 }));
160                deleted += 1;
161            }
162        }
163
164        if let Some(chunks) = self.overflow_chunks.get_mut(src_vid) {
165            for (chunk_idx, chunk) in chunks.iter_mut().enumerate() {
166                let to_delete: Vec<(usize, u64)> = chunk
167                    .edge_ids
168                    .iter()
169                    .enumerate()
170                    .filter(|(i, &eid)| {
171                        chunk.endpoints[*i] == target_endpoint && EdgeId(eid) != INVALID_EDGE_ID
172                    })
173                    .map(|(i, &eid)| (i, eid))
174                    .collect();
175                for (slot_idx, eid) in to_delete {
176                    chunk.edge_ids[slot_idx] = INVALID_EDGE_ID.0;
177                    self.edge_count -= 1;
178                    on_deleted(
179                        EdgeId(eid),
180                        Some(EdgePosition::Overflow {
181                            chunk: chunk_idx as u32,
182                            slot: slot_idx as u32,
183                        }),
184                    );
185                    deleted += 1;
186                }
187            }
188        }
189
190        if deleted > 0 {
191            self.track_live_remove(src_vid, target_endpoint);
192        }
193
194        deleted
195    }
196
197    fn locate_edge(&self, src_vid: u32, edge_id: EdgeId) -> Option<(EdgePosition, Nbr)> {
198        let mut found = None;
199        self.visit_physical_with_position(src_vid, |position, nbr| {
200            if nbr.edge_id == edge_id {
201                found = Some((position, nbr));
202                false
203            } else {
204                true
205            }
206        });
207        found
208    }
209
210    fn delete_edge_at_position(
211        &mut self,
212        src_vid: u32,
213        position: EdgePosition,
214        expected: EdgeId,
215        _ts: Timestamp,
216    ) -> StorageResult<bool> {
217        match position {
218            EdgePosition::Primary { slot } => {
219                let src_idx = src_vid as usize;
220                if src_idx >= self.vertex_capacity() {
221                    return Ok(false);
222                }
223                if slot as usize >= self.rows.degrees[src_idx] as usize {
224                    return Ok(false);
225                }
226                let idx = self.rows.adj_offsets[src_idx] as usize + slot as usize;
227                if idx >= self.edge_ids.len() || EdgeId(self.edge_ids[idx]) != expected {
228                    return Ok(false);
229                }
230                if self.edge_ids[idx] == INVALID_EDGE_ID.0 {
231                    return Ok(false);
232                }
233                let endpoint = self.endpoints[idx];
234                self.edge_ids[idx] = INVALID_EDGE_ID.0;
235                self.edge_count -= 1;
236                self.track_live_remove(src_vid, endpoint);
237                Ok(true)
238            }
239            EdgePosition::Overflow { chunk, slot } => {
240                let Some(chunks) = self.overflow_chunks.get_mut(src_vid) else {
241                    return Ok(false);
242                };
243                let Some(c) = chunks.get_mut(chunk as usize) else {
244                    return Ok(false);
245                };
246                if slot as usize >= c.len() {
247                    return Ok(false);
248                }
249                if c.edge_id_at(slot as usize) != Some(expected) {
250                    return Ok(false);
251                }
252                if c.edge_ids[slot as usize] == INVALID_EDGE_ID.0 {
253                    return Ok(false);
254                }
255                let endpoint = c.endpoints[slot as usize];
256                c.edge_ids[slot as usize] = INVALID_EDGE_ID.0;
257                self.edge_count -= 1;
258                self.track_live_remove(src_vid, endpoint);
259                Ok(true)
260            }
261        }
262    }
263
264    fn revert_delete_at_position(
265        &mut self,
266        src_vid: u32,
267        position: EdgePosition,
268        expected: EdgeId,
269        _ts: Timestamp,
270    ) -> bool {
271        match position {
272            EdgePosition::Primary { slot } => {
273                let src_idx = src_vid as usize;
274                if src_idx >= self.vertex_capacity() {
275                    return false;
276                }
277                if slot as usize >= self.rows.degrees[src_idx] as usize {
278                    return false;
279                }
280                let idx = self.rows.adj_offsets[src_idx] as usize + slot as usize;
281                if idx >= self.edge_ids.len() {
282                    return false;
283                }
284                if self.edge_ids[idx] != INVALID_EDGE_ID.0 {
285                    return false;
286                }
287                self.edge_ids[idx] = expected.0;
288                self.edge_count += 1;
289                let endpoint = self.endpoints[idx];
290                self.track_live_insert(src_vid, endpoint, EdgePosition::Primary { slot });
291                true
292            }
293            EdgePosition::Overflow { chunk, slot } => {
294                let Some(chunks) = self.overflow_chunks.get_mut(src_vid) else {
295                    return false;
296                };
297                let Some(c) = chunks.get_mut(chunk as usize) else {
298                    return false;
299                };
300                if slot as usize >= c.len() {
301                    return false;
302                }
303                if c.edge_ids[slot as usize] != INVALID_EDGE_ID.0 {
304                    return false;
305                }
306                let endpoint = c.endpoints[slot as usize];
307                c.edge_ids[slot as usize] = expected.0;
308                self.edge_count += 1;
309                self.track_live_insert(src_vid, endpoint, EdgePosition::Overflow { chunk, slot });
310                true
311            }
312        }
313    }
314
315    fn delete_edge_by_offset(
316        &mut self,
317        src_vid: u32,
318        offset: i32,
319        _ts: Timestamp,
320    ) -> StorageResult<bool> {
321        if offset < 0 {
322            return Ok(false);
323        }
324        let src_idx = src_vid as usize;
325        if src_idx >= self.vertex_capacity() {
326            return Ok(false);
327        }
328        if offset as usize >= self.rows.degrees[src_idx] as usize {
329            return Ok(false);
330        }
331        let idx = self.rows.adj_offsets[src_idx] as usize + offset as usize;
332        if idx >= self.edge_ids.len() {
333            return Ok(false);
334        }
335        if self.edge_ids[idx] == INVALID_EDGE_ID.0 {
336            return Ok(false);
337        }
338        let endpoint = self.endpoints[idx];
339        self.edge_ids[idx] = INVALID_EDGE_ID.0;
340        self.edge_count -= 1;
341        self.track_live_remove(src_vid, endpoint);
342        Ok(true)
343    }
344
345    fn revert_delete_by_offset(&mut self, _src_vid: u32, _offset: i32, _ts: Timestamp) -> bool {
346        // Deletion overwrites the edge id with the unassignable sentinel, so
347        // an offset-only revert cannot recover the erased identity. Callers
348        // needing restore must keep the edge id and use the positioned path.
349        false
350    }
351
352    fn nbr_at_offset(&self, src_vid: u32, offset: i32) -> Option<Nbr> {
353        if offset < 0 {
354            return None;
355        }
356        let src_idx = src_vid as usize;
357        if src_idx >= self.vertex_capacity() || self.rows.primary_capacities[src_idx] == 0 {
358            return None;
359        }
360        if offset as usize >= self.rows.degrees[src_idx] as usize {
361            return None;
362        }
363        let idx = self.rows.adj_offsets[src_idx] as usize + offset as usize;
364        let endpoint = *self.endpoints.get(idx)?;
365        let edge_id = EdgeId(*self.edge_ids.get(idx)?);
366        Some(self.make_nbr(endpoint, edge_id))
367    }
368
369    /// Locate the first live edge by endpoint without consulting snapshots.
370    ///
371    /// Wide rows answer from the endpoint location index: a present key
372    /// addresses its slot directly, an absent key returns without scanning.
373    /// Narrow rows without an index fall through to the linear walk.
374    fn get_edge_physical(&self, src_vid: u32, dst: VertexId) -> Option<Nbr> {
375        let (decoded_endpoint, _decoded_rank) = dst.try_decode_edge_endpoint()?;
376        let target_endpoint = decoded_endpoint.as_internal_u32()?;
377
378        let src_idx = src_vid as usize;
379        if src_idx >= self.vertex_capacity() {
380            return None;
381        }
382
383        if let Some(set) = self.live_sets.get(src_vid) {
384            let position = set.position(&target_endpoint)?;
385            let nbr = match position {
386                EdgePosition::Primary { slot } => {
387                    let base = self.rows.adj_offsets[src_idx] as usize;
388                    let idx = base + slot as usize;
389                    let endpoint = *self.endpoints.get(idx)?;
390                    let edge_id = EdgeId(*self.edge_ids.get(idx)?);
391                    self.make_nbr(endpoint, edge_id)
392                }
393                EdgePosition::Overflow { chunk, slot } => {
394                    let chunks = self.overflow_chunks.get(src_vid)?;
395                    let c = chunks.get(chunk as usize)?;
396                    let endpoint = c.endpoint_at(slot as usize)?;
397                    let edge_id = c.edge_id_at(slot as usize)?;
398                    self.make_nbr(endpoint, edge_id)
399                }
400            };
401            // Position mismatch means the row moved without a rebuild, which
402            // must not happen; fall back to the scan instead of answering
403            // from the wrong slot.
404            if nbr.endpoint == target_endpoint
405                && nbr.edge_id != INVALID_EDGE_ID
406                && nbr.delete_ts == Timestamp::MAX
407            {
408                return Some(nbr);
409            }
410        }
411
412        let (start, end) = self.primary_window(src_idx);
413        for i in start..end {
414            if self.endpoints[i] == target_endpoint && self.edge_ids[i] != INVALID_EDGE_ID.0 {
415                return Some(self.make_nbr(self.endpoints[i], EdgeId(self.edge_ids[i])));
416            }
417        }
418
419        if let Some(single) = self.overflow_chunks.single_chunk(src_vid) {
420            for i in 0..single.len() {
421                if single.endpoints[i] == target_endpoint && single.edge_ids[i] != INVALID_EDGE_ID.0
422                {
423                    return Some(self.make_nbr(single.endpoints[i], EdgeId(single.edge_ids[i])));
424                }
425            }
426            return None;
427        }
428
429        if let Some(chunks) = self.overflow_chunks.get(src_vid) {
430            for chunk in chunks {
431                for i in 0..chunk.len() {
432                    if chunk.endpoints[i] == target_endpoint
433                        && chunk.edge_ids[i] != INVALID_EDGE_ID.0
434                    {
435                        return Some(self.make_nbr(chunk.endpoints[i], EdgeId(chunk.edge_ids[i])));
436                    }
437                }
438            }
439        }
440
441        None
442    }
443
444    fn physical_edges_of(&self, src_vid: u32) -> Vec<Nbr> {
445        let mut out = Vec::new();
446        self.fill_physical_into(src_vid, &mut out);
447        out
448    }
449
450    fn fill_physical_into(&self, src_vid: u32, out: &mut Vec<Nbr>) {
451        out.clear();
452        let src_idx = src_vid as usize;
453        if src_idx >= self.vertex_capacity() {
454            return;
455        }
456        let (start, end) = self.primary_window(src_idx);
457        out.reserve(end - start);
458        for i in start..end {
459            let edge_id = EdgeId(self.edge_ids[i]);
460            if edge_id == INVALID_EDGE_ID {
461                continue;
462            }
463            out.push(self.make_nbr(self.endpoints[i], edge_id));
464        }
465        if let Some(single) = self.overflow_chunks.single_chunk(src_vid) {
466            out.reserve(single.len());
467            for i in 0..single.len() {
468                let edge_id = EdgeId(single.edge_ids[i]);
469                if edge_id == INVALID_EDGE_ID {
470                    continue;
471                }
472                out.push(self.make_nbr(single.endpoints[i], edge_id));
473            }
474            return;
475        }
476        if let Some(chunks) = self.overflow_chunks.get(src_vid) {
477            for chunk in chunks {
478                out.reserve(chunk.len());
479                for i in 0..chunk.len() {
480                    let edge_id = EdgeId(chunk.edge_ids[i]);
481                    if edge_id == INVALID_EDGE_ID {
482                        continue;
483                    }
484                    out.push(self.make_nbr(chunk.endpoints[i], edge_id));
485                }
486            }
487        }
488    }
489
490    fn has_physical_entries(&self, vid: u32) -> bool {
491        let idx = vid as usize;
492        if idx >= self.vertex_capacity() {
493            return false;
494        }
495        if self.rows.degrees[idx] > 0 {
496            return true;
497        }
498        self.overflow_chunks
499            .get(vid)
500            .is_some_and(|chunks| chunks.iter().any(|c| !c.is_empty()))
501    }
502
503    fn primary_contains(&self, src_vid: u32, edge_id: EdgeId) -> bool {
504        let src_idx = src_vid as usize;
505        if src_idx >= self.vertex_capacity() {
506            return false;
507        }
508        let (start, end) = self.primary_window(src_idx);
509        self.edge_ids[start..end]
510            .iter()
511            .any(|&eid| EdgeId(eid) == edge_id)
512    }
513
514    fn rollback_insert(&mut self, src_vid: u32, edge_id: EdgeId) -> bool {
515        let src_idx = src_vid as usize;
516        if src_idx >= self.vertex_capacity() {
517            return false;
518        }
519
520        let found = {
521            let (start, end) = self.primary_window(src_idx);
522            self.edge_ids[start..end]
523                .iter()
524                .enumerate()
525                .find_map(|(i, &eid)| {
526                    if EdgeId(eid) == edge_id {
527                        Some((start + i, self.endpoints[start + i]))
528                    } else {
529                        None
530                    }
531                })
532        };
533        if let Some((idx, _endpoint)) = found {
534            let degree = self.rows.degrees[src_idx] as usize;
535            let base = self.rows.adj_offsets[src_idx] as usize;
536            self.endpoints
537                .copy_within(base + idx - base + 1..base + degree, base + idx - base);
538            self.edge_ids
539                .copy_within(base + idx - base + 1..base + degree, base + idx - base);
540            self.rows.degrees[src_idx] -= 1;
541            // The left-shift duplicates the old tail slot outside the
542            // shrunk window; loads count every non-invalid slot, so the
543            // tail must die here.
544            let tail = base + self.rows.degrees[src_idx] as usize;
545            self.edge_ids[tail] = INVALID_EDGE_ID.0;
546            self.sub_capacity(1);
547            self.edge_count -= 1;
548            self.rebuild_live_set_for_vertex(src_vid);
549            return true;
550        }
551
552        if let Some((chunk_idx, edge_idx)) = self.scan_overflow_for_edge_id(src_vid, edge_id) {
553            let detached = if let Some(chunks) = self.overflow_chunks.get_mut(src_vid) {
554                chunks[chunk_idx].remove(edge_idx);
555                if chunks[chunk_idx].is_empty() {
556                    let removed = chunks.remove(chunk_idx);
557                    Some((removed.capacity(), chunks.is_empty()))
558                } else {
559                    None
560                }
561            } else {
562                return false;
563            };
564            self.edge_count -= 1;
565            if let Some((freed, emptied)) = detached {
566                self.sub_capacity(freed);
567                if emptied {
568                    self.overflow_chunks.remove(src_vid);
569                }
570            }
571            self.rebuild_live_set_for_vertex(src_vid);
572            return true;
573        }
574
575        false
576    }
577
578    fn revert_delete_by_edge_id(
579        &mut self,
580        _src_vid: u32,
581        _edge_id: EdgeId,
582        _ts: Timestamp,
583    ) -> bool {
584        // Deleted slots hold the sentinel instead of the edge id, so an
585        // id-keyed scan cannot locate them. Restoration uses the positioned
586        // path with the expected id supplied by the caller.
587        false
588    }
589
590    /// Timestamp-filtered point lookup.
591    ///
592    /// Pure rows store no timestamps: [`Self::make_nbr`] stamps every live
593    /// entry identically, so the timestamp carries no information here and
594    /// this entry shares the physical indexed path exactly instead of
595    /// duplicating its scan. Wide rows therefore get the same absent-key
596    /// short-circuit as [`Self::get_edge_physical`].
597    fn get_edge(&self, src_vid: u32, dst: VertexId, _ts: Timestamp) -> Option<Nbr> {
598        self.get_edge_physical(src_vid, dst)
599    }
600
601    fn edges_of(&self, src_vid: u32, _ts: Timestamp) -> Vec<Nbr> {
602        let src_idx = src_vid as usize;
603        if src_idx >= self.vertex_capacity() {
604            return Vec::new();
605        }
606
607        let (start, end) = self.primary_window(src_idx);
608        let overflow_len = self
609            .overflow_chunks
610            .get(src_vid)
611            .map(|chunks| chunks.iter().map(|chunk| chunk.len()).sum::<usize>())
612            .unwrap_or(0);
613        let mut result = Vec::with_capacity((end - start) + overflow_len);
614
615        for i in start..end {
616            if self.edge_ids[i] != INVALID_EDGE_ID.0 {
617                result.push(self.make_nbr(self.endpoints[i], EdgeId(self.edge_ids[i])));
618            }
619        }
620
621        if let Some(chunks) = self.overflow_chunks.get(src_vid) {
622            for chunk in chunks {
623                for i in 0..chunk.len() {
624                    if chunk.edge_ids[i] != INVALID_EDGE_ID.0 {
625                        result.push(self.make_nbr(chunk.endpoints[i], EdgeId(chunk.edge_ids[i])));
626                    }
627                }
628            }
629        }
630
631        result
632    }
633
634    fn compact_vertex_with_reporting(
635        &mut self,
636        vid: u32,
637        _cutoff: Timestamp,
638        _on_edge_removed: &mut dyn FnMut(EdgeId, Timestamp),
639    ) -> usize {
640        let idx = vid as usize;
641        if idx >= self.vertex_capacity() {
642            return 0;
643        }
644
645        let mut removed = 0usize;
646
647        let base = self.rows.adj_offsets[idx] as usize;
648        let degree = self.rows.degrees[idx] as usize;
649        let mut keep = 0usize;
650        for i in 0..degree {
651            let idx_i = base + i;
652            if self.edge_ids[idx_i] == INVALID_EDGE_ID.0 {
653                // Holes carry no edge identity: drop them silently instead
654                // of reporting the sentinel to the authority above.
655                removed += 1;
656            } else {
657                if keep != i {
658                    self.endpoints[base + keep] = self.endpoints[idx_i];
659                    self.edge_ids[base + keep] = self.edge_ids[idx_i];
660                }
661                keep += 1;
662            }
663        }
664        self.rows.degrees[idx] = keep as u32;
665        self.rows.primary_capacities[idx] = keep as u32;
666
667        if self.overflow_chunks.get(vid).is_some() {
668            let chunks = self.overflow_chunks.remove(vid).unwrap_or_default();
669            let freed: usize = chunks.iter().map(|chunk| chunk.capacity()).sum();
670            self.sub_capacity(freed);
671            let mut kept_ep: Vec<u32> = Vec::new();
672            let mut kept_eid: Vec<u64> = Vec::new();
673            for chunk in &chunks {
674                for i in 0..chunk.len() {
675                    let eid = chunk.edge_ids[i];
676                    if eid == INVALID_EDGE_ID.0 {
677                        removed += 1;
678                    } else {
679                        kept_ep.push(chunk.endpoints[i]);
680                        kept_eid.push(eid);
681                    }
682                }
683            }
684            if !kept_ep.is_empty() {
685                let single = PureOverflowChunk::consolidated(&kept_ep, &kept_eid);
686                let added = single.capacity();
687                self.add_capacity(added);
688                self.overflow_chunks.insert(vid, vec![single]);
689            }
690            self.rebuild_live_set_for_vertex(vid);
691        } else if removed > 0 {
692            self.rebuild_live_set_for_vertex(vid);
693        }
694
695        removed
696    }
697
698    fn reclaimable_count(&self, vid: u32, _cutoff: Timestamp) -> usize {
699        let idx = vid as usize;
700        if idx >= self.vertex_capacity() {
701            return 0;
702        }
703        self.vertex_census(vid).1
704    }
705
706    fn vertex_census(&self, vid: u32) -> (usize, usize, usize) {
707        let idx = vid as usize;
708        if idx >= self.vertex_capacity() {
709            return (0, 0, 0);
710        }
711        let mut alive = 0usize;
712        let mut dead = 0usize;
713        let (start, end) = self.primary_window(idx);
714        for i in start..end {
715            if self.edge_ids[i] != INVALID_EDGE_ID.0 {
716                alive += 1;
717            } else {
718                dead += 1;
719            }
720        }
721        let mut capacity = self.rows.primary_capacities[idx] as usize;
722        if let Some(chunks) = self.overflow_chunks.get(vid) {
723            capacity += chunks.iter().map(|chunk| chunk.capacity()).sum::<usize>();
724            for chunk in chunks {
725                for &eid in &chunk.edge_ids {
726                    if eid != INVALID_EDGE_ID.0 {
727                        alive += 1;
728                    } else {
729                        dead += 1;
730                    }
731                }
732            }
733        }
734        (alive, dead, capacity)
735    }
736
737    fn row_gap(&self, vid: u32) -> usize {
738        let idx = vid as usize;
739        if idx >= self.vertex_capacity() {
740            return 0;
741        }
742        self.rows.primary_capacities[idx].saturating_sub(self.rows.degrees[idx]) as usize
743    }
744
745    fn row_density(&self, vid: u32) -> f32 {
746        let idx = vid as usize;
747        if idx >= self.vertex_capacity() {
748            return 1.0;
749        }
750        let cap = self.rows.primary_capacities[idx] as f32;
751        if cap == 0.0 {
752            return 1.0;
753        }
754        self.rows.degrees[idx] as f32 / cap
755    }
756
757    fn used_memory_size(&self) -> usize {
758        std::mem::size_of::<Self>()
759            + self.endpoints.len() * 4
760            + self.edge_ids.len() * 8
761            + self.rows.adj_offsets.len() * 4 * 3
762            + self.primary_sorted.capacity() * std::mem::size_of::<bool>()
763            + self.overflow_chunks.index_bytes()
764            + self.overflow_chunks.total_entry_count() * (4 + 8)
765            + self.live_sets.index_bytes()
766            + self.live_sets.heap_bytes_total()
767    }
768}
linkrs_storage/edge/pure_csr/trait_impl.rs

linkrs_storage/edge/pure_csr/
trait_impl.rs
