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