ifc_lite_core/
dense_index.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at https://mozilla.org/MPL/2.0/.
4
5//! Direct span lookup for dense express ids, without hash-table bucket padding.
6
7use std::sync::Arc;
8use crate::{columnar_index::EntityIndexStore, EntityDecoder};
9
10/// Immutable direct-address index for sources whose offsets fit `u32`.
11/// Construction refuses sparse ids when its arrays would exceed the three
12/// compact input columns. Presence is separate from the span, so id zero and
13/// an empty span at offset zero remain valid entries.
14pub struct DenseEntityIndex {
15    starts: Vec<u32>,
16    lengths: Vec<u32>,
17    present: Vec<u64>,
18}
19
20impl DenseEntityIndex {
21    /// Build from strictly ascending, unique ids and parallel span columns.
22    /// Returns `None` for mismatched/unsorted columns, empty input, or a sparse
23    /// id range. The allocation bound is checked before allocating any array;
24    /// a lone `u32::MAX` id cannot request a multi-gigabyte allocation.
25    pub fn try_from_columns(ids: &[u32], starts: &[u32], lengths: &[u32]) -> Option<Self> {
26        if ids.is_empty() || starts.len() != ids.len() || lengths.len() != ids.len()
27            || !ids.windows(2).all(|pair| pair[0] < pair[1]) {
28            return None;
29        }
30        let slots = u64::from(*ids.last()?) + 1;
31        let words = slots.div_ceil(64);
32        if slots * 8 + words * 8 > ids.len() as u64 * 12 { return None; }
33        let slots = usize::try_from(slots).ok()?;
34        let mut index = Self {
35            starts: vec![0; slots], lengths: vec![0; slots],
36            present: vec![0; usize::try_from(words).ok()?],
37        };
38        for (i, &id) in ids.iter().enumerate() {
39            let slot = id as usize;
40            index.starts[slot] = starts[i];
41            index.lengths[slot] = lengths[i];
42            index.present[slot / 64] |= 1u64 << (slot % 64);
43        }
44        Some(index)
45    }
46
47    /// Return the authored `(start, end)` span, or `None` for an absent id.
48    #[inline]
49    pub fn lookup(&self, id: u32) -> Option<(usize, usize)> {
50        let slot = id as usize;
51        let start = *self.starts.get(slot)? as usize;
52        if self.present[slot / 64] & (1u64 << (slot % 64)) == 0 { return None; }
53        Some((start, start + self.lengths[slot] as usize))
54    }
55}
56
57impl EntityDecoder<'_> {
58    /// Install an immutable direct-address index for this decoder's source.
59    /// Like `set_columnar_index`, source bytes and indexed spans must agree.
60    pub fn set_dense_index(&mut self, index: Arc<DenseEntityIndex>) {
61        self.entity_index = Some(EntityIndexStore::Dense(index));
62    }
63}
64
65#[cfg(test)]
66#[path = "dense_index_tests.rs"]
67mod tests;
ifc_lite_core/dense_index.rs

ifc_lite_core/
dense_index.rs
