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    grid_axis_index: Arc<crate::decoder::GridAxisIndex>,
19}
20
21impl DenseEntityIndex {
22    /// Build from strictly ascending, unique ids and parallel span columns.
23    /// Returns `None` for mismatched/unsorted columns, empty input, or a sparse
24    /// id range. The allocation bound is checked before allocating any array;
25    /// a lone `u32::MAX` id cannot request a multi-gigabyte allocation.
26    pub fn try_from_columns(ids: &[u32], starts: &[u32], lengths: &[u32]) -> Option<Self> {
27        if ids.is_empty() || starts.len() != ids.len() || lengths.len() != ids.len()
28            || !ids.windows(2).all(|pair| pair[0] < pair[1]) {
29            return None;
30        }
31        let slots = u64::from(*ids.last()?) + 1;
32        let words = slots.div_ceil(64);
33        if slots * 8 + words * 8 > ids.len() as u64 * 12 { return None; }
34        let slots = usize::try_from(slots).ok()?;
35        let mut index = Self {
36            starts: vec![0; slots], lengths: vec![0; slots],
37            present: vec![0; usize::try_from(words).ok()?],
38            grid_axis_index: Arc::default(),
39        };
40        for (i, &id) in ids.iter().enumerate() {
41            let slot = id as usize;
42            index.starts[slot] = starts[i];
43            index.lengths[slot] = lengths[i];
44            index.present[slot / 64] |= 1u64 << (slot % 64);
45        }
46        Some(index)
47    }
48
49    /// Return the authored `(start, end)` span, or `None` for an absent id.
50    #[inline]
51    pub fn lookup(&self, id: u32) -> Option<(usize, usize)> {
52        let slot = id as usize;
53        let start = *self.starts.get(slot)? as usize;
54        if self.present[slot / 64] & (1u64 << (slot % 64)) == 0 { return None; }
55        Some((start, start.saturating_add(self.lengths[slot] as usize)))
56    }
57}
58
59impl EntityDecoder<'_> {
60    /// Install an immutable direct-address index for this decoder's source.
61    /// Like `set_columnar_index`, source bytes and indexed spans must agree.
62    pub fn set_dense_index(&mut self, index: Arc<DenseEntityIndex>) {
63        self.set_grid_axis_index(index.grid_axis_index.clone());
64        self.entity_index = Some(EntityIndexStore::Dense(index));
65    }
66}
67
68#[cfg(test)]
69#[path = "dense_index_tests.rs"]
70mod tests;
ifc_lite_core/dense_index.rs

ifc_lite_core/
dense_index.rs
