1use super::types::{
6 AnnotationTable, Arena, ArenaCheckpoint, ArenaMap, ArenaPool, ArenaStats, ArenaStatsExt,
7 ArenaString, BiMap, BumpArena, ChainedArena, DiagMeta, DoubleArena, EventCounter,
8 FrequencyTable, GrowableArena, IdDispenser, Idx, IdxRange, InterningArena, IntervalSet,
9 LinearArena, LoopClock, MemoSlot, MemoryRegion, MemoryRegionRegistry, PoolArena, ScopeStack,
10 ScopedArena, ScopedArenaExt, SimpleLruCache, SlabArena, Slot, SparseBitSet, StringInterner,
11 Timestamp, TwoGenerationArena, TypedArena, TypedId, WorkQueue, WorkStack,
12};
13
14#[cfg(test)]
15mod tests {
16 use super::*;
17 #[test]
18 fn test_arena_alloc_and_get() {
19 let mut arena = Arena::new();
20 let idx1 = arena.alloc(42);
21 let idx2 = arena.alloc(100);
22 assert_eq!(*arena.get(idx1), 42);
23 assert_eq!(*arena.get(idx2), 100);
24 }
25 #[test]
26 fn test_idx_equality() {
27 let mut arena = Arena::new();
28 let idx1 = arena.alloc("hello");
29 let idx2 = arena.alloc("world");
30 let idx1_copy = Idx::new(idx1.raw());
31 assert_eq!(idx1, idx1_copy);
32 assert_ne!(idx1, idx2);
33 }
34 #[test]
35 fn test_idx_ordering() {
36 let idx0: Idx<u32> = Idx::new(0);
37 let idx1: Idx<u32> = Idx::new(1);
38 assert!(idx0 < idx1);
39 assert!(idx1 > idx0);
40 }
41 #[test]
42 fn test_idx_range() {
43 let start: Idx<u32> = Idx::new(0);
44 let end: Idx<u32> = Idx::new(5);
45 let range = IdxRange::new(start, end);
46 assert_eq!(range.len(), 5);
47 assert!(range.contains(Idx::new(3)));
48 assert!(!range.contains(Idx::new(5)));
49 let indices: Vec<_> = range.iter().collect();
50 assert_eq!(indices.len(), 5);
51 }
52 #[test]
53 fn test_arena_alloc_many() {
54 let mut arena: Arena<u32> = Arena::new();
55 let range = arena.alloc_many([1, 2, 3, 4, 5]);
56 assert_eq!(range.len(), 5);
57 assert_eq!(arena.get_range(range), &[1, 2, 3, 4, 5]);
58 }
59 #[test]
60 fn test_arena_iter_indexed() {
61 let mut arena: Arena<u32> = Arena::new();
62 arena.alloc(10);
63 arena.alloc(20);
64 let pairs: Vec<_> = arena.iter_indexed().collect();
65 assert_eq!(pairs.len(), 2);
66 assert_eq!(*pairs[0].1, 10);
67 }
68 #[test]
69 fn test_arena_stats() {
70 let mut arena: Arena<u32> = Arena::with_capacity(16);
71 arena.alloc(1);
72 arena.alloc(2);
73 let stats = arena.stats();
74 assert_eq!(stats.len, 2);
75 assert!(stats.capacity >= 2);
76 }
77 #[test]
78 fn test_interning_arena() {
79 let mut arena: InterningArena<String> = InterningArena::new();
80 let idx1 = arena.intern("hello".to_string());
81 let idx2 = arena.intern("hello".to_string());
82 let idx3 = arena.intern("world".to_string());
83 assert_eq!(idx1, idx2);
84 assert_ne!(idx1, idx3);
85 assert_eq!(arena.len(), 2);
86 }
87 #[test]
88 fn test_slab_arena_alloc_free() {
89 let mut arena: SlabArena<u32> = SlabArena::new();
90 let idx1 = arena.alloc(10);
91 let _idx2 = arena.alloc(20);
92 assert_eq!(arena.len(), 2);
93 let val = arena.free(idx1);
94 assert_eq!(val, Some(10));
95 assert_eq!(arena.len(), 1);
96 assert_eq!(arena.free_count(), 1);
97 let idx3 = arena.alloc(30);
98 assert_eq!(idx3, idx1);
99 }
100 #[test]
101 fn test_slab_arena_get_free_returns_none() {
102 let mut arena: SlabArena<u32> = SlabArena::new();
103 let idx = arena.alloc(5);
104 arena.free(idx);
105 assert_eq!(arena.get(idx), None);
106 }
107 #[test]
108 fn test_bump_arena() {
109 let mut bump = BumpArena::with_capacity(64);
110 let off = bump.alloc_bytes(4).expect("off should be present");
111 bump.write_at(off, &[1, 2, 3, 4]);
112 assert_eq!(bump.read_at(off, 4), &[1, 2, 3, 4]);
113 assert_eq!(bump.used(), 4);
114 }
115 #[test]
116 fn test_bump_arena_overflow() {
117 let mut bump = BumpArena::with_capacity(4);
118 bump.alloc_bytes(4).expect("value should be present");
119 let r = bump.alloc_bytes(1);
120 assert!(r.is_none());
121 }
122 #[test]
123 fn test_bump_arena_reset() {
124 let mut bump = BumpArena::with_capacity(16);
125 bump.alloc_bytes(8).expect("value should be present");
126 assert_eq!(bump.used(), 8);
127 bump.reset();
128 assert_eq!(bump.used(), 0);
129 }
130 #[test]
131 fn test_arena_pool() {
132 let mut pool: ArenaPool<u32> = ArenaPool::new();
133 let mut arena = pool.acquire();
134 arena.alloc(42u32);
135 assert_eq!(arena.len(), 1);
136 pool.release(arena);
137 assert_eq!(pool.pool_size(), 1);
138 let arena2 = pool.acquire();
139 assert_eq!(arena2.len(), 0);
140 }
141 #[test]
142 fn test_idx_cast() {
143 let idx: Idx<u32> = Idx::new(5);
144 let idx2: Idx<u64> = idx.cast();
145 assert_eq!(idx2.raw(), 5);
146 }
147 #[test]
148 fn test_arena_stats_utilisation() {
149 let stats = ArenaStats {
150 len: 3,
151 capacity: 4,
152 };
153 assert!((stats.utilisation() - 0.75).abs() < 1e-9);
154 assert_eq!(stats.free(), 1);
155 }
156}
157#[cfg(test)]
158mod extra_tests {
159 use super::*;
160 #[test]
161 fn test_scoped_arena_rollback() {
162 let mut arena: ScopedArena<u32> = ScopedArena::new();
163 arena.alloc(1);
164 arena.alloc(2);
165 let cp = arena.checkpoint();
166 arena.alloc(3);
167 arena.alloc(4);
168 assert_eq!(arena.len(), 4);
169 arena.rollback(cp);
170 assert_eq!(arena.len(), 2);
171 }
172 #[test]
173 fn test_scoped_arena_multiple_checkpoints() {
174 let mut arena: ScopedArena<u32> = ScopedArena::new();
175 arena.alloc(10);
176 let cp1 = arena.checkpoint();
177 arena.alloc(20);
178 let cp2 = arena.checkpoint();
179 arena.alloc(30);
180 arena.rollback(cp2);
181 assert_eq!(arena.len(), 2);
182 arena.rollback(cp1);
183 assert_eq!(arena.len(), 1);
184 }
185 #[test]
186 fn test_double_arena() {
187 let mut da: DoubleArena<u32, &str> = DoubleArena::new();
188 let (ia, ib) = da.alloc_pair(42, "hello");
189 assert_eq!(*da.first.get(ia), 42);
190 assert_eq!(*da.second.get(ib), "hello");
191 assert_eq!(da.total_len(), 2);
192 }
193 #[test]
194 fn test_arena_map() {
195 let mut arena: Arena<u32> = Arena::new();
196 let idx1 = arena.alloc(10);
197 let idx2 = arena.alloc(20);
198 let mut map: ArenaMap<u32, String> = ArenaMap::new();
199 map.insert(idx1, "ten".to_string());
200 map.insert(idx2, "twenty".to_string());
201 assert_eq!(map.get(idx1), Some(&"ten".to_string()));
202 assert_eq!(map.get(idx2), Some(&"twenty".to_string()));
203 assert_eq!(map.count(), 2);
204 }
205 #[test]
206 fn test_arena_map_remove() {
207 let mut arena: Arena<u32> = Arena::new();
208 let idx = arena.alloc(5);
209 let mut map: ArenaMap<u32, String> = ArenaMap::new();
210 map.insert(idx, "five".to_string());
211 let removed = map.remove(idx);
212 assert_eq!(removed, Some("five".to_string()));
213 assert!(!map.contains(idx));
214 }
215 #[test]
216 fn test_arena_index_operator() {
217 let mut arena: Arena<u32> = Arena::new();
218 let idx = arena.alloc(99);
219 assert_eq!(arena[idx], 99);
220 }
221 #[test]
222 fn test_interning_arena_contains() {
223 let mut arena: InterningArena<u32> = InterningArena::new();
224 arena.intern(42);
225 assert!(arena.contains(&42));
226 assert!(!arena.contains(&99));
227 }
228 #[test]
229 fn test_slab_live_iter() {
230 let mut slab: SlabArena<u32> = SlabArena::new();
231 let i1 = slab.alloc(1);
232 let i2 = slab.alloc(2);
233 let _i3 = slab.alloc(3);
234 slab.free(i2);
235 let live: Vec<_> = slab.iter_live().collect();
236 assert_eq!(live.len(), 2);
237 assert!(live.iter().all(|(_, &v)| v != 2));
238 let _ = i1;
239 }
240}
241#[cfg(test)]
242mod tests_arena_extra {
243 use super::*;
244 #[test]
245 fn test_linear_arena() {
246 let mut arena = LinearArena::new(1024);
247 let a = arena.alloc(16, 8).expect("a should be present");
248 let b = arena.alloc(32, 8).expect("b should be present");
249 assert!(b >= a + 16);
250 assert_eq!(arena.stats().alloc_count, 2);
251 arena.reset();
252 assert_eq!(arena.used(), 0);
253 }
254 #[test]
255 fn test_linear_arena_oom() {
256 let mut arena = LinearArena::new(16);
257 assert!(arena.alloc(17, 1).is_none());
258 }
259 #[test]
260 fn test_chained_arena() {
261 let mut arena = ChainedArena::new(64);
262 for _ in 0..10 {
263 arena.alloc(10, 1);
264 }
265 assert!(arena.num_blocks() >= 2);
266 assert!(arena.total_allocated() >= 100);
267 }
268 #[test]
269 fn test_pool_arena() {
270 let mut pool = PoolArena::new(8, 4);
271 assert_eq!(pool.available(), 4);
272 let idx = pool.alloc_slot().expect("idx should be present");
273 assert_eq!(pool.available(), 3);
274 pool.free_slot(idx);
275 assert_eq!(pool.available(), 4);
276 }
277 #[test]
278 fn test_typed_arena() {
279 let mut ta: TypedArena<u64> = TypedArena::new();
280 let r = ta.alloc(42u64);
281 assert_eq!(*r, 42);
282 assert_eq!(ta.len(), 1);
283 ta.clear();
284 assert!(ta.is_empty());
285 }
286 #[test]
287 fn test_scoped_arena() {
288 let mut sa = ScopedArenaExt::new(256);
289 sa.push_scope();
290 sa.alloc(10, 1);
291 assert_eq!(sa.scope_depth(), 1);
292 sa.pop_scope();
293 assert_eq!(sa.inner.used(), 0);
294 }
295 #[test]
296 fn test_arena_checkpoint() {
297 let mut arena = LinearArena::new(256);
298 arena.alloc(16, 1);
299 let cp = ArenaCheckpoint::create(&arena);
300 arena.alloc(32, 1);
301 assert_eq!(arena.used(), 48);
302 cp.restore(&mut arena);
303 assert_eq!(arena.used(), 16);
304 }
305 #[test]
306 fn test_arena_string() {
307 let mut arena = LinearArena::new(256);
308 let s = ArenaString::store(&mut arena, "hello").expect("s should be present");
309 assert_eq!(s.len(), 5);
310 assert_eq!(arena.buf[s.offset + 5], 0);
311 }
312 #[test]
313 fn test_arena_stats_fragmentation() {
314 let mut stats = ArenaStatsExt::new();
315 stats.bytes_allocated = 80;
316 stats.wasted_bytes = 20;
317 assert!((stats.fragmentation() - 0.2).abs() < 1e-9);
318 }
319}
320#[cfg(test)]
321mod tests_arena_extra2 {
322 use super::*;
323 #[test]
324 fn test_growable_arena() {
325 let mut ga = GrowableArena::new(8);
326 ga.alloc(100, 1);
327 assert!(ga.data.len() >= 100);
328 assert_eq!(ga.count(), 1);
329 ga.reset();
330 assert_eq!(ga.used(), 0);
331 }
332 #[test]
333 fn test_two_generation_arena() {
334 let mut tga = TwoGenerationArena::new(64, 256);
335 tga.alloc_nursery(10, 1);
336 tga.alloc_nursery(10, 1);
337 tga.promote(10, 1);
338 assert_eq!(tga.num_promotions(), 1);
339 tga.minor_gc();
340 assert_eq!(tga.nursery.used(), 0);
341 assert!(tga.stable.used() > 0);
342 }
343}
344#[allow(dead_code)]
346pub trait ArenaAllocator {
347 fn alloc_raw(&mut self, bytes: usize, align: usize) -> Option<usize>;
350 fn used_bytes(&self) -> usize;
352}
353#[allow(dead_code)]
355pub fn arena_alloc_array<A: ArenaAllocator>(arena: &mut A, count: usize) -> Option<usize> {
356 let size = std::mem::size_of::<u64>() * count;
357 let align = std::mem::align_of::<u64>();
358 arena.alloc_raw(size, align)
359}
360#[cfg(test)]
361mod tests_arena_trait {
362 use super::*;
363 #[test]
364 fn test_arena_allocator_trait() {
365 let mut la = LinearArena::new(256);
366 let offset = arena_alloc_array(&mut la, 4).expect("offset should be present");
367 assert!(offset + 32 <= la.used());
368 let mut ga = GrowableArena::new(16);
369 let _offset2 = arena_alloc_array(&mut ga, 8).expect("_offset2 should be present");
370 assert!(ga.used() >= 64);
371 }
372}
373#[cfg(test)]
374mod tests_memory_region {
375 use super::*;
376 #[test]
377 fn test_memory_region() {
378 let mut r = MemoryRegion::new("heap", 0x1000, 0x4000);
379 assert!(!r.active);
380 r.activate();
381 assert!(r.active);
382 assert!(r.contains(0x2000));
383 assert!(!r.contains(0x5000));
384 assert_eq!(r.end(), 0x5000);
385 }
386 #[test]
387 fn test_memory_region_registry() {
388 let mut reg = MemoryRegionRegistry::new();
389 reg.add(MemoryRegion::new("stack", 0x0000, 0x1000));
390 reg.add(MemoryRegion::new("heap", 0x1000, 0x4000));
391 assert_eq!(reg.len(), 2);
392 assert!(reg.find(0x2000).is_some());
393 assert_eq!(
394 reg.find(0x2000).expect("value should be present").label,
395 "heap"
396 );
397 }
398}
399#[cfg(test)]
400mod tests_common_infra {
401 use super::*;
402 #[test]
403 fn test_event_counter() {
404 let mut ec = EventCounter::new();
405 ec.inc("hit");
406 ec.inc("hit");
407 ec.inc("miss");
408 assert_eq!(ec.get("hit"), 2);
409 assert_eq!(ec.get("miss"), 1);
410 assert_eq!(ec.total(), 3);
411 ec.reset();
412 assert_eq!(ec.total(), 0);
413 }
414 #[test]
415 fn test_diag_meta() {
416 let mut m = DiagMeta::new();
417 m.add("os", "linux");
418 m.add("arch", "x86_64");
419 assert_eq!(m.get("os"), Some("linux"));
420 assert_eq!(m.len(), 2);
421 let s = m.to_string();
422 assert!(s.contains("os=linux"));
423 }
424 #[test]
425 fn test_scope_stack() {
426 let mut ss = ScopeStack::new();
427 ss.push("Nat");
428 ss.push("succ");
429 assert_eq!(ss.current(), Some("succ"));
430 assert_eq!(ss.depth(), 2);
431 assert_eq!(ss.path(), "Nat.succ");
432 ss.pop();
433 assert_eq!(ss.current(), Some("Nat"));
434 }
435 #[test]
436 fn test_annotation_table() {
437 let mut tbl = AnnotationTable::new();
438 tbl.annotate("doc", "first line");
439 tbl.annotate("doc", "second line");
440 assert_eq!(tbl.get_all("doc").len(), 2);
441 assert!(tbl.has("doc"));
442 assert!(!tbl.has("other"));
443 }
444 #[test]
445 fn test_work_stack() {
446 let mut ws = WorkStack::new();
447 ws.push(1u32);
448 ws.push(2u32);
449 assert_eq!(ws.pop(), Some(2));
450 assert_eq!(ws.len(), 1);
451 }
452 #[test]
453 fn test_work_queue() {
454 let mut wq = WorkQueue::new();
455 wq.enqueue(1u32);
456 wq.enqueue(2u32);
457 assert_eq!(wq.dequeue(), Some(1));
458 assert_eq!(wq.len(), 1);
459 }
460 #[test]
461 fn test_sparse_bit_set() {
462 let mut bs = SparseBitSet::new(128);
463 bs.set(5);
464 bs.set(63);
465 bs.set(64);
466 assert!(bs.get(5));
467 assert!(bs.get(63));
468 assert!(bs.get(64));
469 assert!(!bs.get(0));
470 assert_eq!(bs.count_ones(), 3);
471 bs.clear(5);
472 assert!(!bs.get(5));
473 }
474 #[test]
475 fn test_loop_clock() {
476 let mut clk = LoopClock::start();
477 for _ in 0..10 {
478 clk.tick();
479 }
480 assert_eq!(clk.iters(), 10);
481 assert!(clk.elapsed_us() >= 0.0);
482 }
483}
484#[cfg(test)]
485mod tests_extra_data_structures {
486 use super::*;
487 #[test]
488 fn test_simple_lru_cache() {
489 let mut cache: SimpleLruCache<&str, u32> = SimpleLruCache::new(3);
490 cache.put("a", 1);
491 cache.put("b", 2);
492 cache.put("c", 3);
493 assert_eq!(cache.get(&"a"), Some(&1));
494 cache.put("d", 4);
495 assert!(cache.len() <= 3);
496 }
497 #[test]
498 fn test_string_interner() {
499 let mut si = StringInterner::new();
500 let id1 = si.intern("hello");
501 let id2 = si.intern("hello");
502 assert_eq!(id1, id2);
503 let id3 = si.intern("world");
504 assert_ne!(id1, id3);
505 assert_eq!(si.get(id1), Some("hello"));
506 assert_eq!(si.len(), 2);
507 }
508 #[test]
509 fn test_frequency_table() {
510 let mut ft = FrequencyTable::new();
511 ft.record("a");
512 ft.record("b");
513 ft.record("a");
514 ft.record("a");
515 assert_eq!(ft.freq(&"a"), 3);
516 assert_eq!(ft.freq(&"b"), 1);
517 assert_eq!(ft.most_frequent(), Some((&"a", 3)));
518 assert_eq!(ft.total(), 4);
519 assert_eq!(ft.distinct(), 2);
520 }
521 #[test]
522 fn test_bimap() {
523 let mut bm: BiMap<u32, &str> = BiMap::new();
524 bm.insert(1, "one");
525 bm.insert(2, "two");
526 assert_eq!(bm.get_b(&1), Some(&"one"));
527 assert_eq!(bm.get_a(&"two"), Some(&2));
528 assert_eq!(bm.len(), 2);
529 }
530}
531#[cfg(test)]
532mod tests_interval_set {
533 use super::*;
534 #[test]
535 fn test_interval_set() {
536 let mut s = IntervalSet::new();
537 s.add(1, 5);
538 s.add(3, 8);
539 assert_eq!(s.num_intervals(), 1);
540 assert_eq!(s.cardinality(), 8);
541 assert!(s.contains(4));
542 assert!(!s.contains(9));
543 s.add(10, 15);
544 assert_eq!(s.num_intervals(), 2);
545 }
546}
547#[allow(dead_code)]
549pub fn now_us() -> Timestamp {
550 let us = std::time::SystemTime::UNIX_EPOCH
551 .elapsed()
552 .map(|d| d.as_micros() as u64)
553 .unwrap_or(0);
554 Timestamp::from_us(us)
555}
556#[cfg(test)]
557mod tests_typed_utilities {
558 use super::*;
559 #[test]
560 fn test_timestamp() {
561 let t1 = Timestamp::from_us(1000);
562 let t2 = Timestamp::from_us(1500);
563 assert_eq!(t2.elapsed_since(t1), 500);
564 assert!(t1 < t2);
565 }
566 #[test]
567 fn test_typed_id() {
568 struct Foo;
569 let id: TypedId<Foo> = TypedId::new(42);
570 assert_eq!(id.raw(), 42);
571 assert_eq!(format!("{id}"), "#42");
572 }
573 #[test]
574 fn test_id_dispenser() {
575 struct Bar;
576 let mut disp: IdDispenser<Bar> = IdDispenser::new();
577 let a = disp.next();
578 let b = disp.next();
579 assert_eq!(a.raw(), 0);
580 assert_eq!(b.raw(), 1);
581 assert_eq!(disp.count(), 2);
582 }
583 #[test]
584 fn test_slot() {
585 let mut slot: Slot<u32> = Slot::empty();
586 assert!(!slot.is_filled());
587 slot.fill(99);
588 assert!(slot.is_filled());
589 assert_eq!(slot.get(), Some(&99));
590 let v = slot.take();
591 assert_eq!(v, Some(99));
592 assert!(!slot.is_filled());
593 }
594 #[test]
595 #[should_panic]
596 fn test_slot_double_fill() {
597 let mut slot: Slot<u32> = Slot::empty();
598 slot.fill(1);
599 slot.fill(2);
600 }
601 #[test]
602 fn test_memo_slot() {
603 let mut ms: MemoSlot<u32> = MemoSlot::new();
604 assert!(!ms.is_cached());
605 let val = ms.get_or_compute(|| 42);
606 assert_eq!(*val, 42);
607 assert!(ms.is_cached());
608 ms.invalidate();
609 assert!(!ms.is_cached());
610 }
611}