lewis.moe
Nothing to see here, move along
1use lancer_core::bitmap::BitmapAllocator;
2use proptest::prelude::*;
3
4#[test]
5fn allocate_all_then_free_all() {
6 let mut bm: BitmapAllocator<[u64; 2]> = BitmapAllocator::new();
7 bm.init(100);
8 bm.mark_range_free(0..100);
9 assert_eq!(bm.free_items(), 100);
10
11 let indices: Vec<usize> = (0..100)
12 .map(|_| bm.allocate().expect("should allocate"))
13 .collect();
14 assert_eq!(bm.free_items(), 0);
15 assert!(bm.allocate().is_none());
16
17 indices.iter().for_each(|&idx| {
18 bm.deallocate(idx).expect("should deallocate");
19 });
20 assert_eq!(bm.free_items(), 100);
21}
22
23#[test]
24fn double_free_returns_error() {
25 let mut bm: BitmapAllocator<[u64; 1]> = BitmapAllocator::new();
26 bm.init(64);
27 bm.mark_range_free(0..64);
28
29 let idx = bm.allocate().unwrap();
30 bm.deallocate(idx).unwrap();
31 assert!(bm.deallocate(idx).is_err());
32}
33
34#[test]
35fn invariant_holds_after_mixed_ops() {
36 let mut bm: BitmapAllocator<[u64; 2]> = BitmapAllocator::new();
37 bm.init(50);
38 bm.mark_range_free(0..50);
39
40 (0..25).for_each(|_| {
41 bm.allocate().unwrap();
42 });
43 assert_eq!(bm.used_items() + bm.free_items(), bm.total_items());
44}
45
46#[test]
47fn allocated_index_in_range() {
48 let mut bm: BitmapAllocator<[u64; 2]> = BitmapAllocator::new();
49 bm.init(80);
50 bm.mark_range_free(0..80);
51
52 (0..80).for_each(|_| {
53 let idx = bm.allocate().unwrap();
54 assert!(idx < 80, "index {} out of range", idx);
55 });
56}
57
58proptest! {
59 #[test]
60 fn alloc_n_free_permuted(seed in 0u64..10000) {
61 let total = 64usize;
62 let mut bm: BitmapAllocator<[u64; 1]> = BitmapAllocator::new();
63 bm.init(total);
64 bm.mark_range_free(0..total);
65
66 let mut indices: Vec<usize> = (0..total)
67 .map(|_| bm.allocate().expect("should allocate"))
68 .collect();
69
70 let mut rng_state = seed;
71 let len = indices.len();
72 (0..len).rev().for_each(|i| {
73 rng_state = rng_state.wrapping_mul(6364136223846793005).wrapping_add(1);
74 let j = (rng_state as usize) % (i + 1);
75 indices.swap(i, j);
76 });
77
78 indices.iter().for_each(|&idx| {
79 bm.deallocate(idx).expect("should deallocate");
80 });
81 prop_assert_eq!(bm.used_items(), 0);
82 prop_assert_eq!(bm.free_items(), total);
83 }
84
85 #[test]
86 fn alloc_until_none_matches_free_count(free_count in 1usize..65) {
87 let mut bm: BitmapAllocator<[u64; 1]> = BitmapAllocator::new();
88 bm.init(64);
89 bm.mark_range_free(0..free_count);
90
91 let initial_free = bm.free_items();
92 let mut allocated = 0usize;
93 while bm.allocate().is_some() {
94 allocated += 1;
95 }
96 prop_assert_eq!(allocated, initial_free);
97 }
98
99 #[test]
100 fn invariant_always_holds(ops in proptest::collection::vec(0u8..3, 1..200)) {
101 let mut bm: BitmapAllocator<[u64; 1]> = BitmapAllocator::new();
102 bm.init(64);
103 bm.mark_range_free(0..64);
104 let mut live: Vec<usize> = Vec::new();
105
106 ops.iter().for_each(|&op| {
107 match op {
108 0 => {
109 bm.allocate().into_iter().for_each(|idx| live.push(idx));
110 }
111 1 => {
112 live.pop().into_iter().for_each(|idx| {
113 bm.deallocate(idx).unwrap();
114 });
115 }
116 _ => {}
117 }
118 assert_eq!(bm.used_items() + bm.free_items(), bm.total_items());
119 });
120 }
121}