logicaffeine_kernel/dag/sem/
table.rs

1//! The value engine's hash tables: open addressing with linear probing over small `Copy` keys
2//! and `u32` values, one slot per cache line access, Fibonacci-hashed.
3//!
4//! Every value the engine builds is interned and every cache is keyed on ids, so these tables
5//! are on the hottest paths — an environment extension, a neutral application, an evaluation
6//! lookup each probe one. A general hash map spends several times the instructions of a probe
7//! here on hashing, metadata and growth policy.
8
9/// A key a table can hold: its hash must be well mixed in the TOP bits.
10pub trait Key: Copy + Eq {
11    /// Every bit set: what a vacant slot holds, so that emptying a table is one byte fill.
12    const VACANT: Self;
13    fn hash(&self) -> u64;
14}
15
16const K: u64 = 0x9E37_79B9_7F4A_7C15;
17
18#[inline]
19fn mix2(a: u32, b: u32) -> u64 {
20    (((a as u64) << 32) | b as u64).wrapping_mul(K)
21}
22
23impl Key for (u32, u32) {
24    const VACANT: Self = (u32::MAX, u32::MAX);
25
26    #[inline]
27    fn hash(&self) -> u64 {
28        mix2(self.0, self.1)
29    }
30}
31
32impl Key for (u32, u32, u32) {
33    const VACANT: Self = (u32::MAX, u32::MAX, u32::MAX);
34
35    #[inline]
36    fn hash(&self) -> u64 {
37        (mix2(self.0, self.1) ^ (self.2 as u64)).wrapping_mul(K)
38    }
39}
40
41impl Key for (u32, u32, u32, u32) {
42    const VACANT: Self = (u32::MAX, u32::MAX, u32::MAX, u32::MAX);
43
44    #[inline]
45    fn hash(&self) -> u64 {
46        (mix2(self.0, self.1) ^ (((self.2 as u64) << 32) | self.3 as u64)).wrapping_mul(K)
47    }
48}
49
50impl Key for (u32, u64) {
51    const VACANT: Self = (u32::MAX, u64::MAX);
52
53    #[inline]
54    fn hash(&self) -> u64 {
55        ((self.0 as u64).wrapping_mul(K) ^ self.1).wrapping_mul(K)
56    }
57}
58
59const EMPTY: u32 = u32::MAX;
60
61#[derive(Copy, Clone)]
62struct Slot<Q> {
63    key: Q,
64    /// [`EMPTY`] marks a vacant slot.
65    val: u32,
66}
67
68/// A table that lives for a session: emptied rarely, by filling its slots with the vacant
69/// pattern (all bits set — a `memset`).
70#[derive(Clone)]
71pub struct Table<Q: Key> {
72    slots: Vec<Slot<Q>>,
73    shift: u32,
74    len: usize,
75}
76
77impl<Q: Key> Default for Table<Q> {
78    fn default() -> Self {
79        Self::new()
80    }
81}
82
83impl<Q: Key> Table<Q> {
84    const VACANT: Slot<Q> = Slot {
85        key: Q::VACANT,
86        val: EMPTY,
87    };
88
89    pub fn new() -> Table<Q> {
90        let cap = 1 << 10;
91        Table {
92            slots: vec![Self::VACANT; cap],
93            shift: 64 - 10,
94            len: 0,
95        }
96    }
97
98    #[inline]
99    pub fn get(&self, k: &Q) -> Option<u32> {
100        let mask = self.slots.len() - 1;
101        let mut i = (k.hash() >> self.shift) as usize;
102        loop {
103            let s = &self.slots[i];
104            if s.val == EMPTY {
105                return None;
106            }
107            if s.key == *k {
108                return Some(s.val);
109            }
110            i = (i + 1) & mask;
111        }
112    }
113
114    /// Inserts a key that is not present (`v` is never `EMPTY`: ids stay below it).
115    #[inline]
116    pub fn insert(&mut self, k: Q, v: u32) {
117        debug_assert!(v != EMPTY);
118        if (self.len + 1) * 2 > self.slots.len() {
119            self.grow();
120        }
121        self.place(k, v);
122        self.len += 1;
123    }
124
125    #[inline]
126    fn place(&mut self, k: Q, v: u32) {
127        let mask = self.slots.len() - 1;
128        let mut i = (k.hash() >> self.shift) as usize;
129        while self.slots[i].val != EMPTY {
130            i = (i + 1) & mask;
131        }
132        self.slots[i] = Slot { key: k, val: v };
133    }
134
135    fn grow(&mut self) {
136        let cap = self.slots.len() * 2;
137        let old = std::mem::replace(&mut self.slots, vec![Self::VACANT; cap]);
138        self.shift = 64 - cap.trailing_zeros();
139        for s in old {
140            if s.val != EMPTY {
141                self.place(s.key, s.val);
142            }
143        }
144    }
145
146    pub fn contains(&self, k: &Q) -> bool {
147        self.get(k).is_some()
148    }
149
150    /// Empties the table, keeping its storage.
151    pub fn clear(&mut self) {
152        if self.len > 0 {
153            self.slots.fill(Self::VACANT);
154            self.len = 0;
155        }
156    }
157
158    pub fn len(&self) -> usize {
159        self.len
160    }
161
162    pub fn is_empty(&self) -> bool {
163        self.len == 0
164    }
165
166    pub fn bytes(&self) -> usize {
167        self.slots.capacity() * std::mem::size_of::<Slot<Q>>()
168    }
169}
170
171#[derive(Copy, Clone)]
172struct StampedSlot<Q> {
173    key: Q,
174    val: u32,
175    /// The table generation that wrote this slot; older generations read as vacant.
176    generation: u32,
177}
178
179/// A table emptied often (at every declaration): emptying it is one increment.
180#[derive(Clone)]
181pub struct StampedTable<Q: Key> {
182    slots: Vec<StampedSlot<Q>>,
183    shift: u32,
184    len: usize,
185    generation: u32,
186}
187
188impl<Q: Key> Default for StampedTable<Q> {
189    fn default() -> Self {
190        Self::new()
191    }
192}
193
194impl<Q: Key> StampedTable<Q> {
195    const VACANT: StampedSlot<Q> = StampedSlot {
196        key: Q::VACANT,
197        val: 0,
198        generation: 0,
199    };
200
201    pub fn new() -> StampedTable<Q> {
202        let cap = 1 << 10;
203        StampedTable {
204            slots: vec![Self::VACANT; cap],
205            shift: 64 - 10,
206            len: 0,
207            generation: 1,
208        }
209    }
210
211    #[inline]
212    pub fn get(&self, k: &Q) -> Option<u32> {
213        let mask = self.slots.len() - 1;
214        let mut i = (k.hash() >> self.shift) as usize;
215        loop {
216            let s = &self.slots[i];
217            if s.generation != self.generation {
218                return None;
219            }
220            if s.key == *k {
221                return Some(s.val);
222            }
223            i = (i + 1) & mask;
224        }
225    }
226
227    /// Inserts a key that is not present.
228    #[inline]
229    pub fn insert(&mut self, k: Q, v: u32) {
230        if (self.len + 1) * 2 > self.slots.len() {
231            self.grow();
232        }
233        self.place(k, v);
234        self.len += 1;
235    }
236
237    #[inline]
238    fn place(&mut self, k: Q, v: u32) {
239        let mask = self.slots.len() - 1;
240        let mut i = (k.hash() >> self.shift) as usize;
241        while self.slots[i].generation == self.generation {
242            i = (i + 1) & mask;
243        }
244        self.slots[i] = StampedSlot {
245            key: k,
246            val: v,
247            generation: self.generation,
248        };
249    }
250
251    fn grow(&mut self) {
252        let cap = self.slots.len() * 2;
253        let old = std::mem::replace(&mut self.slots, vec![Self::VACANT; cap]);
254        self.shift = 64 - cap.trailing_zeros();
255        let g = self.generation;
256        self.generation = 1;
257        for s in old {
258            if s.generation == g {
259                self.place(s.key, s.val);
260            }
261        }
262    }
263
264    /// Empties the table in O(1), keeping its storage.
265    pub fn clear(&mut self) {
266        self.len = 0;
267        self.generation = self.generation.wrapping_add(1);
268        if self.generation == 0 {
269            for s in self.slots.iter_mut() {
270                s.generation = 0;
271            }
272            self.generation = 1;
273        }
274    }
275
276    pub fn bytes(&self) -> usize {
277        self.slots.capacity() * std::mem::size_of::<StampedSlot<Q>>()
278    }
279}
logicaffeine_kernel/dag/sem/table.rs

logicaffeine_kernel/dag/sem/
table.rs
