1 use super::*;
2 use std::cell::Cell;
3 use std::mem;
4 use std::ptr;
5 
6 struct DropTracker<'a>(&'a Cell<u32>);
7 impl<'a> Drop for DropTracker<'a> {
drop(&mut self)8     fn drop(&mut self) {
9         self.0.set(self.0.get() + 1);
10     }
11 }
12 
13 struct Node<'a, 'b: 'a>(Option<&'a Node<'a, 'b>>, u32, DropTracker<'b>);
14 
15 #[test]
arena_as_intended()16 fn arena_as_intended() {
17     let drop_counter = Cell::new(0);
18     {
19         let arena = Arena::with_capacity(2);
20 
21         let mut node: &Node = arena.alloc(Node(None, 1, DropTracker(&drop_counter)));
22         assert_eq!(arena.chunks.borrow().rest.len(), 0);
23 
24         node = arena.alloc(Node(Some(node), 2, DropTracker(&drop_counter)));
25         assert_eq!(arena.chunks.borrow().rest.len(), 0);
26 
27         node = arena.alloc(Node(Some(node), 3, DropTracker(&drop_counter)));
28         assert_eq!(arena.chunks.borrow().rest.len(), 1);
29 
30         node = arena.alloc(Node(Some(node), 4, DropTracker(&drop_counter)));
31         assert_eq!(arena.chunks.borrow().rest.len(), 1);
32 
33         assert_eq!(node.1, 4);
34         assert_eq!(node.0.unwrap().1, 3);
35         assert_eq!(node.0.unwrap().0.unwrap().1, 2);
36         assert_eq!(node.0.unwrap().0.unwrap().0.unwrap().1, 1);
37         assert!(node.0.unwrap().0.unwrap().0.unwrap().0.is_none());
38 
39         assert_eq!(arena.len(), 4);
40 
41         mem::drop(node);
42         assert_eq!(drop_counter.get(), 0);
43 
44         let mut node: &Node = arena.alloc(Node(None, 5, DropTracker(&drop_counter)));
45         assert_eq!(arena.chunks.borrow().rest.len(), 1);
46 
47         node = arena.alloc(Node(Some(node), 6, DropTracker(&drop_counter)));
48         assert_eq!(arena.chunks.borrow().rest.len(), 1);
49 
50         node = arena.alloc(Node(Some(node), 7, DropTracker(&drop_counter)));
51         assert_eq!(arena.chunks.borrow().rest.len(), 2);
52 
53         assert_eq!(drop_counter.get(), 0);
54 
55         assert_eq!(node.1, 7);
56         assert_eq!(node.0.unwrap().1, 6);
57         assert_eq!(node.0.unwrap().0.unwrap().1, 5);
58         assert!(node.0.unwrap().0.unwrap().0.is_none());
59 
60         assert_eq!(drop_counter.get(), 0);
61     }
62     assert_eq!(drop_counter.get(), 7);
63 }
64 
65 #[test]
ensure_into_vec_maintains_order_of_allocation()66 fn ensure_into_vec_maintains_order_of_allocation() {
67     let arena = Arena::with_capacity(1); // force multiple inner vecs
68     for &s in &["t", "e", "s", "t"] {
69         arena.alloc(String::from(s));
70     }
71     let vec = arena.into_vec();
72     assert_eq!(vec, vec!["t", "e", "s", "t"]);
73 }
74 
75 #[test]
test_zero_cap()76 fn test_zero_cap() {
77     let arena = Arena::with_capacity(0);
78     let a = arena.alloc(1);
79     let b = arena.alloc(2);
80     assert_eq!(*a, 1);
81     assert_eq!(*b, 2);
82     assert_eq!(arena.len(), 2);
83 }
84 
85 #[test]
test_alloc_extend()86 fn test_alloc_extend() {
87     let arena = Arena::with_capacity(2);
88     for i in 0..15 {
89         let slice = arena.alloc_extend(0..i);
90         for (j, &elem) in slice.iter().enumerate() {
91             assert_eq!(j, elem);
92         }
93     }
94 }
95 
96 #[test]
test_alloc_uninitialized()97 fn test_alloc_uninitialized() {
98     const LIMIT: usize = 15;
99     let drop_counter = Cell::new(0);
100     unsafe {
101         let arena: Arena<Node> = Arena::with_capacity(4);
102         for i in 0..LIMIT {
103             let slice = arena.alloc_uninitialized(i);
104             for (j, elem) in (&mut *slice).iter_mut().enumerate() {
105                 ptr::write(elem, Node(None, j as u32, DropTracker(&drop_counter)));
106             }
107             assert_eq!(drop_counter.get(), 0);
108         }
109     }
110     assert_eq!(drop_counter.get(), (0..LIMIT).fold(0, |a, e| a + e) as u32);
111 }
112 
113 #[test]
test_alloc_extend_with_drop_counter()114 fn test_alloc_extend_with_drop_counter() {
115     let drop_counter = Cell::new(0);
116     {
117         let arena = Arena::with_capacity(2);
118         let iter = (0..100).map(|j| Node(None, j as u32, DropTracker(&drop_counter)));
119         let older_ref = Some(&arena.alloc_extend(iter)[0]);
120         assert_eq!(drop_counter.get(), 0);
121         let iter = (0..100).map(|j| Node(older_ref, j as u32, DropTracker(&drop_counter)));
122         arena.alloc_extend(iter);
123         assert_eq!(drop_counter.get(), 0);
124     }
125     assert_eq!(drop_counter.get(), 200);
126 }
127 
128 #[test]
test_uninitialized_array()129 fn test_uninitialized_array() {
130     let arena = Arena::with_capacity(2);
131     let uninit = arena.uninitialized_array();
132     arena.alloc_extend(0..2);
133     unsafe {
134         for (&a, b) in (&*uninit).iter().zip(0..2) {
135             assert_eq!(a, b);
136         }
137         assert!((&*arena.uninitialized_array()).as_ptr() != (&*uninit).as_ptr());
138         arena.alloc(0);
139         let uninit = arena.uninitialized_array();
140         assert_eq!((&*uninit).len(), 3);
141     }
142 }
143 
144 #[test]
dont_trust_the_iterator_size()145 fn dont_trust_the_iterator_size() {
146     use std::iter::repeat;
147 
148     struct WrongSizeIter<I>(I);
149     impl<I> Iterator for WrongSizeIter<I>
150     where
151         I: Iterator,
152     {
153         type Item = I::Item;
154 
155         fn next(&mut self) -> Option<Self::Item> {
156             self.0.next()
157         }
158 
159         fn size_hint(&self) -> (usize, Option<usize>) {
160             (0, Some(0))
161         }
162     }
163 
164     impl<I> ExactSizeIterator for WrongSizeIter<I> where I: Iterator {}
165 
166     let arena = Arena::with_capacity(2);
167     arena.alloc(0);
168     let slice = arena.alloc_extend(WrongSizeIter(repeat(1).take(1_000)));
169     // Allocation of 1000 elements should have created a new chunk
170     assert_eq!(arena.chunks.borrow().rest.len(), 1);
171     assert_eq!(slice.len(), 1000);
172 }
173 
174 #[test]
arena_is_send()175 fn arena_is_send() {
176     fn assert_is_send<T: Send>(_: T) {}
177 
178     // If `T` is `Send`, ...
179     assert_is_send(42_u32);
180 
181     // Then `Arena<T>` is also `Send`.
182     let arena: Arena<u32> = Arena::new();
183     assert_is_send(arena);
184 }
185 
186 #[test]
iter_mut_low_capacity()187 fn iter_mut_low_capacity() {
188     #[derive(Debug, PartialEq, Eq)]
189     struct NonCopy(usize);
190 
191     const MAX: usize = 1_000;
192     const CAP: usize = 16;
193 
194     let mut arena = Arena::with_capacity(CAP);
195     for i in 1..MAX {
196         arena.alloc(NonCopy(i));
197     }
198 
199     assert!(
200         arena.chunks.borrow().rest.len() > 1,
201         "expected multiple chunks"
202     );
203 
204     let mut iter = arena.iter_mut();
205     for i in 1..MAX {
206         assert_eq!(Some(&mut NonCopy(i)), iter.next());
207     }
208 
209     assert_eq!(None, iter.next());
210 }
211 
212 #[test]
iter_mut_high_capacity()213 fn iter_mut_high_capacity() {
214     #[derive(Debug, PartialEq, Eq)]
215     struct NonCopy(usize);
216 
217     const MAX: usize = 1_000;
218     const CAP: usize = 8192;
219 
220     let mut arena = Arena::with_capacity(CAP);
221     for i in 1..MAX {
222         arena.alloc(NonCopy(i));
223     }
224 
225     assert!(
226         arena.chunks.borrow().rest.is_empty(),
227         "expected single chunk"
228     );
229 
230     let mut iter = arena.iter_mut();
231     for i in 1..MAX {
232         assert_eq!(Some(&mut NonCopy(i)), iter.next());
233     }
234 
235     assert_eq!(None, iter.next());
236 }
237 
assert_size_hint<T>(arena_len: usize, iter: IterMut<'_, T>)238 fn assert_size_hint<T>(arena_len: usize, iter: IterMut<'_, T>) {
239     let (min, max) = iter.size_hint();
240 
241     assert!(max.is_some());
242     let max = max.unwrap();
243 
244     // Check that the actual arena length lies between the estimated min and max
245     assert!(min <= arena_len);
246     assert!(max >= arena_len);
247 
248     // Check that the min and max estimates are within a factor of 3
249     assert!(min >= arena_len / 3);
250     assert!(max <= arena_len * 3);
251 }
252 
253 #[test]
size_hint()254 fn size_hint() {
255     #[derive(Debug, PartialEq, Eq)]
256     struct NonCopy(usize);
257 
258     const MAX: usize = 32;
259     const CAP: usize = 0;
260 
261     for cap in CAP..(CAP + 16/* check some non-power-of-two capacities */) {
262         let mut arena = Arena::with_capacity(cap);
263         for i in 1..MAX {
264             arena.alloc(NonCopy(i));
265             let iter = arena.iter_mut();
266             assert_size_hint(i, iter);
267         }
268     }
269 }
270 
271 #[test]
272 #[cfg(not(miri))]
size_hint_low_initial_capacities()273 fn size_hint_low_initial_capacities() {
274     #[derive(Debug, PartialEq, Eq)]
275     struct NonCopy(usize);
276 
277     const MAX: usize = 25_000;
278     const CAP: usize = 0;
279 
280     for cap in CAP..(CAP + 128/* check some non-power-of-two capacities */) {
281         let mut arena = Arena::with_capacity(cap);
282         for i in 1..MAX {
283             arena.alloc(NonCopy(i));
284             let iter = arena.iter_mut();
285             assert_size_hint(i, iter);
286         }
287     }
288 }
289 
290 #[test]
291 #[cfg(not(miri))]
size_hint_high_initial_capacities()292 fn size_hint_high_initial_capacities() {
293     #[derive(Debug, PartialEq, Eq)]
294     struct NonCopy(usize);
295 
296     const MAX: usize = 25_000;
297     const CAP: usize = 8164;
298 
299     for cap in CAP..(CAP + 128/* check some non-power-of-two capacities */) {
300         let mut arena = Arena::with_capacity(cap);
301         for i in 1..MAX {
302             arena.alloc(NonCopy(i));
303             let iter = arena.iter_mut();
304             assert_size_hint(i, iter);
305         }
306     }
307 }
308 
309 #[test]
310 #[cfg(not(miri))]
size_hint_many_items()311 fn size_hint_many_items() {
312     #[derive(Debug, PartialEq, Eq)]
313     struct NonCopy(usize);
314 
315     const MAX: usize = 5_000_000;
316     const CAP: usize = 16;
317 
318     let mut arena = Arena::with_capacity(CAP);
319     for i in 1..MAX {
320         arena.alloc(NonCopy(i));
321         let iter = arena.iter_mut();
322         assert_size_hint(i, iter);
323     }
324 }
325