olean_export/env/
table.rs1use super::term::{Expr, ExprId, Id, Level, Name};
2use hashbrown::{hash_table::Entry, HashTable};
3use parking_lot::{Mutex, MutexGuard};
4use rustc_hash::FxBuildHasher;
5use std::{
6 hash::{BuildHasher, Hash},
7 ops::Index,
8 sync::{
9 atomic::{AtomicUsize, Ordering::Relaxed},
10 OnceLock,
11 },
12};
13
14const SHARDS: usize = 256;
15
16const CHUNK: usize = 1 << 14;
17
18#[derive(Debug)]
19pub(super) struct Shard<T> {
20 nodes: Vec<T>,
21 index: HashTable<u32>,
22}
23
24fn hash<T: Hash>(t: &T) -> u64 {
25 FxBuildHasher.hash_one(t)
26}
27
28const fn shard_of(h: u64) -> usize {
30 (h.wrapping_mul(0x9e37_79b9_7f4a_7c15) >> 56) as usize % SHARDS
31}
32
33fn id(n: usize) -> u32 {
34 u32::try_from(n).expect("table overflow")
35}
36
37#[derive(Debug)]
40pub(super) struct Shared<T>(Vec<Mutex<Shard<T>>>);
41
42impl<T: Hash + Eq> Shared<T> {
43 pub(super) fn new(zero: T, n: usize) -> Self {
45 let mut shards: Vec<_> = (0..SHARDS)
46 .map(|_| Shard {
47 nodes: Vec::with_capacity(n / SHARDS),
48 index: HashTable::with_capacity(n / SHARDS),
49 })
50 .collect();
51 shards[0].index.insert_unique(hash(&zero), 0, |_| 0);
52 shards[0].nodes.push(zero);
53 Self(shards.into_iter().map(Mutex::new).collect())
54 }
55
56 pub(super) fn intern(&self, t: T) -> Id<T> {
57 let h = hash(&t);
58 let k = shard_of(h);
59 let mut g = self.0[k].lock();
60 let s = &mut *g;
61 let nodes = &mut s.nodes;
62 let i = match s.index.entry(
63 h,
64 |&i| nodes[i as usize] == t,
65 |&i| hash(&nodes[i as usize]),
66 ) {
67 Entry::Occupied(e) => *e.get() as usize,
68 Entry::Vacant(e) => {
69 e.insert(id(nodes.len()));
70 nodes.push(t);
71 nodes.len() - 1
72 }
73 };
74 drop(g);
75 Id::new(id(i * SHARDS + k))
76 }
77
78 pub(super) fn freeze(self) -> Table<T> {
79 Table(self.0.into_iter().map(Mutex::into_inner).collect())
80 }
81}
82
83impl<T> Table<T> {
84 pub(super) fn thaw(self) -> Shared<T> {
85 Shared(self.0.into_iter().map(Mutex::new).collect())
86 }
87}
88
89#[derive(Debug)]
92pub struct Table<T>(pub(super) Vec<Shard<T>>);
93
94impl<T: Hash + Eq> Table<T> {
95 pub fn get(&self, t: &T) -> Option<Id<T>> {
96 let h = hash(t);
97 let k = shard_of(h);
98 let s = &self.0[k];
99 let i = s.index.find(h, |&i| s.nodes[i as usize] == *t)?;
100 Some(Id::new(id(*i as usize * SHARDS + k)))
101 }
102
103 #[must_use]
105 pub fn len(&self) -> usize {
106 self.0.iter().map(|s| s.nodes.len()).sum()
107 }
108
109 #[must_use]
110 pub fn is_empty(&self) -> bool {
111 self.len() == 0
112 }
113
114 #[must_use]
116 pub fn bound(&self) -> usize {
117 self.0.iter().map(|s| s.nodes.len()).max().unwrap_or(0) * SHARDS
118 }
119}
120
121impl<T> Index<Id<T>> for Table<T> {
122 type Output = T;
123 fn index(&self, i: Id<T>) -> &T {
124 let i = i.index();
125 &self.0[i % SHARDS].nodes[i / SHARDS]
126 }
127}
128
129#[derive(Debug)]
130pub(super) struct Chunk {
131 nodes: Vec<Expr>,
132 ranks: Vec<u32>,
133}
134
135pub(super) struct SharedExprs {
141 index: Vec<Mutex<HashTable<u32>>>,
142 chunks: Slots,
143 next: AtomicUsize,
144}
145
146const PAGE: usize = 512;
147
148type Slot = OnceLock<Box<Mutex<Chunk>>>;
149
150struct Slots(Box<[OnceLock<Box<[Slot]>>]>);
152
153impl Slots {
154 fn new() -> Self {
155 Self(
156 (0..=u32::MAX as usize / CHUNK / PAGE)
157 .map(|_| OnceLock::new())
158 .collect(),
159 )
160 }
161
162 fn get(&self, k: usize) -> &Slot {
163 let page = self.0.get(k / PAGE).expect("table overflow");
164 &page.get_or_init(|| (0..PAGE).map(|_| OnceLock::new()).collect())[k % PAGE]
165 }
166
167 fn into_chunks(self) -> impl Iterator<Item = Chunk> {
169 self.0
170 .into_vec()
171 .into_iter()
172 .filter_map(OnceLock::into_inner)
173 .flat_map(<[_]>::into_vec)
174 .map_while(OnceLock::into_inner)
175 .map(|c| c.into_inner())
176 }
177}
178
179impl SharedExprs {
180 pub(super) fn new(n: usize) -> Self {
181 Self {
182 index: (0..SHARDS)
183 .map(|_| Mutex::new(HashTable::with_capacity(n / SHARDS)))
184 .collect(),
185 chunks: Slots::new(),
186 next: AtomicUsize::new(0),
187 }
188 }
189
190 fn chunk(&self, k: usize) -> MutexGuard<'_, Chunk> {
191 self.chunks
192 .get(k)
193 .get()
194 .expect("chunk is published before its ids")
195 .lock()
196 }
197
198 fn with<R>(&self, i: u32, f: impl FnOnce(&mut Expr, &mut u32) -> R) -> R {
200 let i = i as usize;
201 let mut g = self.chunk(i / CHUNK);
202 let c = &mut *g;
203 let r = f(&mut c.nodes[i % CHUNK], &mut c.ranks[i % CHUNK]);
204 drop(g);
205 r
206 }
207
208 #[allow(clippy::significant_drop_tightening)]
210 pub(super) fn intern(&self, e: Expr, rank: u32, cursor: &mut Option<usize>) -> ExprId {
211 let h = hash(&e);
212 let mut index = self.index[shard_of(h)].lock();
213 let entry = index.entry(
214 h,
215 |&i| self.with(i, |n, _| *n == e),
216 |&i| self.with(i, |n, _| hash(n)),
217 );
218 let i = match entry {
219 Entry::Occupied(o) => {
220 let i = *o.get();
221 self.with(i, |n, r| {
222 if rank < *r {
223 *n = e;
224 *r = rank;
225 }
226 });
227 i
228 }
229 Entry::Vacant(v) => {
230 let (k, mut c) = match cursor.map(|k| (k, self.chunk(k))) {
231 Some((k, c)) if c.nodes.len() < CHUNK => (k, c),
232 _ => {
233 let k = self.next.fetch_add(1, Relaxed);
234 self.chunks.get(k).get_or_init(|| {
235 Box::new(Mutex::new(Chunk {
236 nodes: Vec::with_capacity(CHUNK),
237 ranks: Vec::with_capacity(CHUNK),
238 }))
239 });
240 *cursor = Some(k);
241 (k, self.chunk(k))
242 }
243 };
244 let i = id(k * CHUNK + c.nodes.len());
245 c.nodes.push(e);
246 c.ranks.push(rank);
247 v.insert(i);
248 i
249 }
250 };
251 Id::new(i)
252 }
253
254 pub(super) fn freeze(self) -> (Exprs, Vec<HashTable<u32>>, Vec<Vec<u32>>) {
256 let (nodes, ranks) = self
257 .chunks
258 .into_chunks()
259 .map(|c| (c.nodes, c.ranks))
260 .unzip();
261 let index = self.index.into_iter().map(Mutex::into_inner).collect();
262 (Exprs(nodes), index, ranks)
263 }
264
265 pub(super) fn thaw(exprs: Exprs, index: Vec<HashTable<u32>>, ranks: Vec<Vec<u32>>) -> Self {
266 let n = exprs.0.len();
267 let chunks = Slots::new();
268 for (k, (nodes, ranks)) in exprs.0.into_iter().zip(ranks).enumerate() {
269 chunks
270 .get(k)
271 .set(Box::new(Mutex::new(Chunk { nodes, ranks })))
272 .expect("chunk is set once");
273 }
274 Self {
275 index: index.into_iter().map(Mutex::new).collect(),
276 chunks,
277 next: AtomicUsize::new(n),
278 }
279 }
280}
281
282#[derive(Debug, Default)]
284pub struct Exprs(pub(super) Vec<Vec<Expr>>);
285
286impl Exprs {
287 #[must_use]
289 pub fn len(&self) -> usize {
290 self.0.iter().map(Vec::len).sum()
291 }
292
293 #[must_use]
294 pub fn is_empty(&self) -> bool {
295 self.len() == 0
296 }
297
298 #[must_use]
300 pub const fn bound(&self) -> usize {
301 self.0.len() * CHUNK
302 }
303}
304
305impl Index<ExprId> for Exprs {
306 type Output = Expr;
307 fn index(&self, i: ExprId) -> &Expr {
308 let i = i.index();
309 &self.0[i / CHUNK][i % CHUNK]
310 }
311}
312
313pub(super) struct Tables {
315 pub(super) names: Shared<Name>,
316 pub(super) levels: Shared<Level>,
317 pub(super) exprs: SharedExprs,
318}