cjc_data/detcoll/
index_vec.rs

1//! `IndexVec<I, V>` — dense ID → value table.
2//!
3//! Strongly-typed `Vec` indexed by a newtype ID instead of `usize`. Use
4//! for "every entity gets a sequentially-allocated ID" patterns:
5//! `SymbolId → SymbolData`, `NodeId → NodeData`, `TypeId → TypeInfo`,
6//! `BlockId → BasicBlock`. Lookup is `O(1)` array access; iteration is
7//! deterministic insertion order.
8//!
9//! No hashing, no probing, no allocator overhead beyond `Vec` growth.
10//! For dense IDs this is strictly better than `BTreeMap<u32, V>`:
11//! constant-time lookup, contiguous memory, zero indirection.
12
13use std::marker::PhantomData;
14
15/// Newtype ID trait. Implement for any newtype wrapping a small
16/// non-negative integer (`u32` is the conventional choice).
17pub trait Idx: Copy + Eq + std::fmt::Debug {
18    fn from_usize(i: usize) -> Self;
19    fn index(self) -> usize;
20}
21
22/// Convenience macro to declare a newtype ID.
23#[macro_export]
24macro_rules! det_idx {
25    ($name:ident) => {
26        #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
27        pub struct $name(pub u32);
28        impl $crate::detcoll::Idx for $name {
29            #[inline]
30            fn from_usize(i: usize) -> Self {
31                debug_assert!(i <= u32::MAX as usize);
32                Self(i as u32)
33            }
34            #[inline]
35            fn index(self) -> usize {
36                self.0 as usize
37            }
38        }
39    };
40}
41
42#[derive(Debug, Clone)]
43pub struct IndexVec<I: Idx, V> {
44    data: Vec<V>,
45    _marker: PhantomData<I>,
46}
47
48impl<I: Idx, V> Default for IndexVec<I, V> {
49    fn default() -> Self {
50        Self::new()
51    }
52}
53
54impl<I: Idx, V> IndexVec<I, V> {
55    pub fn new() -> Self {
56        Self {
57            data: Vec::new(),
58            _marker: PhantomData,
59        }
60    }
61
62    pub fn with_capacity(cap: usize) -> Self {
63        Self {
64            data: Vec::with_capacity(cap),
65            _marker: PhantomData,
66        }
67    }
68
69    pub fn len(&self) -> usize {
70        self.data.len()
71    }
72
73    pub fn is_empty(&self) -> bool {
74        self.data.is_empty()
75    }
76
77    /// Append a value, returning the assigned ID. Allocation is
78    /// monotonic — IDs are stable for the lifetime of this `IndexVec`.
79    pub fn push(&mut self, value: V) -> I {
80        let i = self.data.len();
81        self.data.push(value);
82        I::from_usize(i)
83    }
84
85    /// `O(1)` lookup. Returns `None` for out-of-range IDs.
86    pub fn get(&self, id: I) -> Option<&V> {
87        self.data.get(id.index())
88    }
89
90    /// `O(1)` mutable lookup. Returns `None` for out-of-range IDs.
91    pub fn get_mut(&mut self, id: I) -> Option<&mut V> {
92        self.data.get_mut(id.index())
93    }
94
95    /// Iterate `(id, &value)` pairs in insertion order.
96    pub fn iter(&self) -> impl Iterator<Item = (I, &V)> + '_ {
97        self.data
98            .iter()
99            .enumerate()
100            .map(|(i, v)| (I::from_usize(i), v))
101    }
102
103    /// Iterate `&value` only, in insertion order.
104    pub fn values(&self) -> impl Iterator<Item = &V> + '_ {
105        self.data.iter()
106    }
107
108    /// Borrow as a slice, for code that wants positional access.
109    pub fn as_slice(&self) -> &[V] {
110        &self.data
111    }
112}
113
114impl<I: Idx, V> std::ops::Index<I> for IndexVec<I, V> {
115    type Output = V;
116    fn index(&self, id: I) -> &V {
117        &self.data[id.index()]
118    }
119}
120
121impl<I: Idx, V> std::ops::IndexMut<I> for IndexVec<I, V> {
122    fn index_mut(&mut self, id: I) -> &mut V {
123        &mut self.data[id.index()]
124    }
125}
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130
131    crate::det_idx!(NodeId);
132
133    #[test]
134    fn push_and_lookup_roundtrip() {
135        let mut iv: IndexVec<NodeId, &'static str> = IndexVec::new();
136        let a = iv.push("alpha");
137        let b = iv.push("beta");
138        let c = iv.push("gamma");
139        assert_eq!(a, NodeId(0));
140        assert_eq!(b, NodeId(1));
141        assert_eq!(c, NodeId(2));
142        assert_eq!(iv[a], "alpha");
143        assert_eq!(iv[b], "beta");
144        assert_eq!(iv[c], "gamma");
145    }
146
147    #[test]
148    fn out_of_range_get_returns_none() {
149        let iv: IndexVec<NodeId, i32> = IndexVec::new();
150        assert!(iv.get(NodeId(0)).is_none());
151    }
152
153    #[test]
154    fn iter_yields_insertion_order() {
155        let mut iv: IndexVec<NodeId, i32> = IndexVec::new();
156        iv.push(10);
157        iv.push(20);
158        iv.push(30);
159        let collected: Vec<i32> = iv.values().copied().collect();
160        assert_eq!(collected, vec![10, 20, 30]);
161    }
162
163    #[test]
164    fn deterministic_under_repeat() {
165        let mut a: IndexVec<NodeId, i32> = IndexVec::new();
166        let mut b: IndexVec<NodeId, i32> = IndexVec::new();
167        for v in [3, 1, 4, 1, 5, 9, 2, 6] {
168            a.push(v);
169            b.push(v);
170        }
171        let av: Vec<i32> = a.values().copied().collect();
172        let bv: Vec<i32> = b.values().copied().collect();
173        assert_eq!(av, bv);
174    }
175}
cjc_data/detcoll/index_vec.rs

cjc_data/detcoll/
index_vec.rs
