xsd_schema/document/
element_index.rs

1//! Element index by local-name hash for the document buffer.
2//!
3//! [`ElementIndex`] maps [`QNameAtom::local_name_hash`](super::qname::QNameAtom::local_name_hash)
4//! values to lists of node references, giving O(1) lookup by element name.
5//! Callers **must** filter results by full QName because hash collisions are expected.
6
7use std::collections::HashMap;
8
9/// Index from `local_name_hash` → list of node references.
10///
11/// Used by the navigator to quickly locate elements by name without a
12/// full document scan.  Because different QNames may share the same
13/// `local_name_hash`, callers must perform a secondary equality check
14/// against the full [`QNameAtom`](super::qname::QNameAtom).
15#[derive(Debug, Default)]
16pub struct ElementIndex {
17    map: HashMap<u32, Vec<u32>>,
18}
19
20impl ElementIndex {
21    /// Creates a new empty index.
22    pub fn new() -> Self {
23        Self::default()
24    }
25
26    /// Records `node_ref` under the given `local_name_hash`.
27    pub fn add(&mut self, local_name_hash: u32, node_ref: u32) {
28        self.map.entry(local_name_hash).or_default().push(node_ref);
29    }
30
31    /// Returns all node refs that share `local_name_hash`, or an empty slice.
32    pub fn find(&self, local_name_hash: u32) -> &[u32] {
33        self.map.get(&local_name_hash).map_or(&[], |v| v.as_slice())
34    }
35
36    /// Returns the total number of hash buckets that have at least one entry.
37    pub fn len(&self) -> usize {
38        self.map.len()
39    }
40
41    /// Returns `true` if the index contains no entries.
42    pub fn is_empty(&self) -> bool {
43        self.map.is_empty()
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn new_index_is_empty() {
53        let idx = ElementIndex::new();
54        assert!(idx.is_empty());
55        assert_eq!(idx.len(), 0);
56    }
57
58    #[test]
59    fn add_and_find_single() {
60        let mut idx = ElementIndex::new();
61        idx.add(42, 7);
62        assert_eq!(idx.find(42), &[7]);
63    }
64
65    #[test]
66    fn unknown_hash_returns_empty() {
67        let idx = ElementIndex::new();
68        assert!(idx.find(999).is_empty());
69    }
70
71    #[test]
72    fn multiple_elements_same_hash() {
73        let mut idx = ElementIndex::new();
74        idx.add(42, 1);
75        idx.add(42, 5);
76        idx.add(42, 9);
77        assert_eq!(idx.find(42), &[1, 5, 9]);
78    }
79
80    #[test]
81    fn different_hashes_independent() {
82        let mut idx = ElementIndex::new();
83        idx.add(10, 1);
84        idx.add(20, 2);
85        assert_eq!(idx.find(10), &[1]);
86        assert_eq!(idx.find(20), &[2]);
87    }
88
89    #[test]
90    fn len_counts_buckets() {
91        let mut idx = ElementIndex::new();
92        idx.add(10, 1);
93        idx.add(20, 2);
94        idx.add(10, 3); // same bucket as 10
95        assert_eq!(idx.len(), 2); // two distinct hash keys
96    }
97}
xsd_schema/document/element_index.rs

xsd_schema/document/
element_index.rs
