]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! The arena, a fast but limited type of allocator. | |
12 | //! | |
13 | //! Arenas are a type of allocator that destroy the objects within, all at | |
14 | //! once, once the arena itself is destroyed. They do not support deallocation | |
15 | //! of individual objects while the arena itself is still alive. The benefit | |
16 | //! of an arena is very fast allocation; just a pointer bump. | |
17 | //! | |
18 | //! This crate has two arenas implemented: `TypedArena`, which is a simpler | |
19 | //! arena but can only hold objects of a single type, and `Arena`, which is a | |
20 | //! more complex, slower arena which can hold objects of any type. | |
21 | ||
c34b1796 AL |
22 | // Do not remove on snapshot creation. Needed for bootstrap. (Issue #22364) |
23 | #![cfg_attr(stage0, feature(custom_attribute))] | |
1a4d82fc | 24 | #![crate_name = "arena"] |
85aaf69f | 25 | #![unstable(feature = "rustc_private")] |
1a4d82fc JJ |
26 | #![staged_api] |
27 | #![crate_type = "rlib"] | |
28 | #![crate_type = "dylib"] | |
29 | #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png", | |
30 | html_favicon_url = "http://www.rust-lang.org/favicon.ico", | |
31 | html_root_url = "http://doc.rust-lang.org/nightly/")] | |
32 | ||
85aaf69f | 33 | #![feature(alloc)] |
1a4d82fc | 34 | #![feature(box_syntax)] |
85aaf69f SL |
35 | #![feature(core)] |
36 | #![feature(staged_api)] | |
37 | #![feature(unboxed_closures)] | |
38 | #![feature(unsafe_destructor)] | |
39 | #![cfg_attr(test, feature(test))] | |
1a4d82fc JJ |
40 | |
41 | extern crate alloc; | |
42 | ||
43 | use std::cell::{Cell, RefCell}; | |
44 | use std::cmp; | |
1a4d82fc | 45 | use std::intrinsics; |
85aaf69f | 46 | use std::marker; |
1a4d82fc | 47 | use std::mem; |
1a4d82fc JJ |
48 | use std::ptr; |
49 | use std::rc::Rc; | |
50 | use std::rt::heap::{allocate, deallocate}; | |
51 | ||
52 | // The way arena uses arrays is really deeply awful. The arrays are | |
53 | // allocated, and have capacities reserved, but the fill for the array | |
54 | // will always stay at 0. | |
55 | #[derive(Clone, PartialEq)] | |
56 | struct Chunk { | |
57 | data: Rc<RefCell<Vec<u8>>>, | |
85aaf69f | 58 | fill: Cell<usize>, |
1a4d82fc JJ |
59 | is_copy: Cell<bool>, |
60 | } | |
61 | ||
62 | impl Chunk { | |
85aaf69f | 63 | fn capacity(&self) -> usize { |
1a4d82fc JJ |
64 | self.data.borrow().capacity() |
65 | } | |
66 | ||
67 | unsafe fn as_ptr(&self) -> *const u8 { | |
68 | self.data.borrow().as_ptr() | |
69 | } | |
70 | } | |
71 | ||
72 | /// A slower reflection-based arena that can allocate objects of any type. | |
73 | /// | |
74 | /// This arena uses `Vec<u8>` as a backing store to allocate objects from. For | |
75 | /// each allocated object, the arena stores a pointer to the type descriptor | |
76 | /// followed by the object (potentially with alignment padding after each | |
77 | /// element). When the arena is destroyed, it iterates through all of its | |
78 | /// chunks, and uses the tydesc information to trace through the objects, | |
79 | /// calling the destructors on them. One subtle point that needs to be | |
80 | /// addressed is how to handle panics while running the user provided | |
81 | /// initializer function. It is important to not run the destructor on | |
82 | /// uninitialized objects, but how to detect them is somewhat subtle. Since | |
83 | /// `alloc()` can be invoked recursively, it is not sufficient to simply exclude | |
84 | /// the most recent object. To solve this without requiring extra space, we | |
85 | /// use the low order bit of the tydesc pointer to encode whether the object | |
86 | /// it describes has been fully initialized. | |
87 | /// | |
88 | /// As an optimization, objects with destructors are stored in different chunks | |
89 | /// than objects without destructors. This reduces overhead when initializing | |
90 | /// plain-old-data (`Copy` types) and means we don't need to waste time running | |
91 | /// their destructors. | |
85aaf69f | 92 | pub struct Arena<'longer_than_self> { |
1a4d82fc JJ |
93 | // The head is separated out from the list as a unbenchmarked |
94 | // microoptimization, to avoid needing to case on the list to access the | |
95 | // head. | |
96 | head: RefCell<Chunk>, | |
97 | copy_head: RefCell<Chunk>, | |
98 | chunks: RefCell<Vec<Chunk>>, | |
85aaf69f | 99 | _marker: marker::PhantomData<*mut &'longer_than_self()>, |
1a4d82fc JJ |
100 | } |
101 | ||
85aaf69f | 102 | impl<'a> Arena<'a> { |
1a4d82fc | 103 | /// Allocates a new Arena with 32 bytes preallocated. |
85aaf69f SL |
104 | pub fn new() -> Arena<'a> { |
105 | Arena::new_with_size(32) | |
1a4d82fc JJ |
106 | } |
107 | ||
108 | /// Allocates a new Arena with `initial_size` bytes preallocated. | |
85aaf69f | 109 | pub fn new_with_size(initial_size: usize) -> Arena<'a> { |
1a4d82fc JJ |
110 | Arena { |
111 | head: RefCell::new(chunk(initial_size, false)), | |
112 | copy_head: RefCell::new(chunk(initial_size, true)), | |
113 | chunks: RefCell::new(Vec::new()), | |
85aaf69f | 114 | _marker: marker::PhantomData, |
1a4d82fc JJ |
115 | } |
116 | } | |
117 | } | |
118 | ||
85aaf69f | 119 | fn chunk(size: usize, is_copy: bool) -> Chunk { |
1a4d82fc JJ |
120 | Chunk { |
121 | data: Rc::new(RefCell::new(Vec::with_capacity(size))), | |
85aaf69f | 122 | fill: Cell::new(0), |
1a4d82fc JJ |
123 | is_copy: Cell::new(is_copy), |
124 | } | |
125 | } | |
126 | ||
127 | #[unsafe_destructor] | |
85aaf69f | 128 | impl<'longer_than_self> Drop for Arena<'longer_than_self> { |
1a4d82fc JJ |
129 | fn drop(&mut self) { |
130 | unsafe { | |
131 | destroy_chunk(&*self.head.borrow()); | |
85aaf69f | 132 | for chunk in &*self.chunks.borrow() { |
1a4d82fc JJ |
133 | if !chunk.is_copy.get() { |
134 | destroy_chunk(chunk); | |
135 | } | |
136 | } | |
137 | } | |
138 | } | |
139 | } | |
140 | ||
141 | #[inline] | |
85aaf69f | 142 | fn round_up(base: usize, align: usize) -> usize { |
1a4d82fc JJ |
143 | (base.checked_add(align - 1)).unwrap() & !(align - 1) |
144 | } | |
145 | ||
146 | // Walk down a chunk, running the destructors for any objects stored | |
147 | // in it. | |
148 | unsafe fn destroy_chunk(chunk: &Chunk) { | |
149 | let mut idx = 0; | |
150 | let buf = chunk.as_ptr(); | |
151 | let fill = chunk.fill.get(); | |
152 | ||
153 | while idx < fill { | |
85aaf69f | 154 | let tydesc_data: *const usize = mem::transmute(buf.offset(idx as isize)); |
1a4d82fc JJ |
155 | let (tydesc, is_done) = un_bitpack_tydesc_ptr(*tydesc_data); |
156 | let (size, align) = ((*tydesc).size, (*tydesc).align); | |
157 | ||
158 | let after_tydesc = idx + mem::size_of::<*const TyDesc>(); | |
159 | ||
160 | let start = round_up(after_tydesc, align); | |
161 | ||
162 | //debug!("freeing object: idx = {}, size = {}, align = {}, done = {}", | |
163 | // start, size, align, is_done); | |
164 | if is_done { | |
85aaf69f | 165 | ((*tydesc).drop_glue)(buf.offset(start as isize) as *const i8); |
1a4d82fc JJ |
166 | } |
167 | ||
168 | // Find where the next tydesc lives | |
169 | idx = round_up(start + size, mem::align_of::<*const TyDesc>()); | |
170 | } | |
171 | } | |
172 | ||
173 | // We encode whether the object a tydesc describes has been | |
174 | // initialized in the arena in the low bit of the tydesc pointer. This | |
175 | // is necessary in order to properly do cleanup if a panic occurs | |
176 | // during an initializer. | |
177 | #[inline] | |
85aaf69f SL |
178 | fn bitpack_tydesc_ptr(p: *const TyDesc, is_done: bool) -> usize { |
179 | p as usize | (is_done as usize) | |
1a4d82fc JJ |
180 | } |
181 | #[inline] | |
85aaf69f | 182 | fn un_bitpack_tydesc_ptr(p: usize) -> (*const TyDesc, bool) { |
1a4d82fc JJ |
183 | ((p & !1) as *const TyDesc, p & 1 == 1) |
184 | } | |
185 | ||
c34b1796 AL |
186 | // HACK(eddyb) TyDesc replacement using a trait object vtable. |
187 | // This could be replaced in the future with a custom DST layout, | |
188 | // or `&'static (drop_glue, size, align)` created by a `const fn`. | |
189 | struct TyDesc { | |
190 | drop_glue: fn(*const i8), | |
191 | size: usize, | |
192 | align: usize | |
193 | } | |
194 | ||
9346a6ac AL |
195 | trait AllTypes { fn dummy(&self) { } } |
196 | impl<T:?Sized> AllTypes for T { } | |
197 | ||
c34b1796 AL |
198 | unsafe fn get_tydesc<T>() -> *const TyDesc { |
199 | use std::raw::TraitObject; | |
200 | ||
201 | let ptr = &*(1 as *const T); | |
202 | ||
203 | // Can use any trait that is implemented for all types. | |
9346a6ac | 204 | let obj = mem::transmute::<&AllTypes, TraitObject>(ptr); |
c34b1796 AL |
205 | obj.vtable as *const TyDesc |
206 | } | |
207 | ||
85aaf69f SL |
208 | impl<'longer_than_self> Arena<'longer_than_self> { |
209 | fn chunk_size(&self) -> usize { | |
1a4d82fc JJ |
210 | self.copy_head.borrow().capacity() |
211 | } | |
212 | ||
213 | // Functions for the POD part of the arena | |
85aaf69f | 214 | fn alloc_copy_grow(&self, n_bytes: usize, align: usize) -> *const u8 { |
1a4d82fc JJ |
215 | // Allocate a new chunk. |
216 | let new_min_chunk_size = cmp::max(n_bytes, self.chunk_size()); | |
217 | self.chunks.borrow_mut().push(self.copy_head.borrow().clone()); | |
218 | ||
219 | *self.copy_head.borrow_mut() = | |
85aaf69f | 220 | chunk((new_min_chunk_size + 1).next_power_of_two(), true); |
1a4d82fc JJ |
221 | |
222 | return self.alloc_copy_inner(n_bytes, align); | |
223 | } | |
224 | ||
225 | #[inline] | |
85aaf69f | 226 | fn alloc_copy_inner(&self, n_bytes: usize, align: usize) -> *const u8 { |
1a4d82fc JJ |
227 | let start = round_up(self.copy_head.borrow().fill.get(), align); |
228 | ||
229 | let end = start + n_bytes; | |
230 | if end > self.chunk_size() { | |
231 | return self.alloc_copy_grow(n_bytes, align); | |
232 | } | |
233 | ||
234 | let copy_head = self.copy_head.borrow(); | |
235 | copy_head.fill.set(end); | |
236 | ||
237 | unsafe { | |
85aaf69f | 238 | copy_head.as_ptr().offset(start as isize) |
1a4d82fc JJ |
239 | } |
240 | } | |
241 | ||
242 | #[inline] | |
243 | fn alloc_copy<T, F>(&self, op: F) -> &mut T where F: FnOnce() -> T { | |
244 | unsafe { | |
245 | let ptr = self.alloc_copy_inner(mem::size_of::<T>(), | |
246 | mem::min_align_of::<T>()); | |
247 | let ptr = ptr as *mut T; | |
248 | ptr::write(&mut (*ptr), op()); | |
249 | return &mut *ptr; | |
250 | } | |
251 | } | |
252 | ||
253 | // Functions for the non-POD part of the arena | |
85aaf69f SL |
254 | fn alloc_noncopy_grow(&self, n_bytes: usize, |
255 | align: usize) -> (*const u8, *const u8) { | |
1a4d82fc JJ |
256 | // Allocate a new chunk. |
257 | let new_min_chunk_size = cmp::max(n_bytes, self.chunk_size()); | |
258 | self.chunks.borrow_mut().push(self.head.borrow().clone()); | |
259 | ||
260 | *self.head.borrow_mut() = | |
85aaf69f | 261 | chunk((new_min_chunk_size + 1).next_power_of_two(), false); |
1a4d82fc JJ |
262 | |
263 | return self.alloc_noncopy_inner(n_bytes, align); | |
264 | } | |
265 | ||
266 | #[inline] | |
85aaf69f SL |
267 | fn alloc_noncopy_inner(&self, n_bytes: usize, |
268 | align: usize) -> (*const u8, *const u8) { | |
1a4d82fc JJ |
269 | // Be careful to not maintain any `head` borrows active, because |
270 | // `alloc_noncopy_grow` borrows it mutably. | |
271 | let (start, end, tydesc_start, head_capacity) = { | |
272 | let head = self.head.borrow(); | |
273 | let fill = head.fill.get(); | |
274 | ||
275 | let tydesc_start = fill; | |
276 | let after_tydesc = fill + mem::size_of::<*const TyDesc>(); | |
277 | let start = round_up(after_tydesc, align); | |
278 | let end = start + n_bytes; | |
279 | ||
280 | (start, end, tydesc_start, head.capacity()) | |
281 | }; | |
282 | ||
283 | if end > head_capacity { | |
284 | return self.alloc_noncopy_grow(n_bytes, align); | |
285 | } | |
286 | ||
287 | let head = self.head.borrow(); | |
288 | head.fill.set(round_up(end, mem::align_of::<*const TyDesc>())); | |
289 | ||
290 | unsafe { | |
291 | let buf = head.as_ptr(); | |
85aaf69f | 292 | return (buf.offset(tydesc_start as isize), buf.offset(start as isize)); |
1a4d82fc JJ |
293 | } |
294 | } | |
295 | ||
296 | #[inline] | |
297 | fn alloc_noncopy<T, F>(&self, op: F) -> &mut T where F: FnOnce() -> T { | |
298 | unsafe { | |
299 | let tydesc = get_tydesc::<T>(); | |
300 | let (ty_ptr, ptr) = | |
301 | self.alloc_noncopy_inner(mem::size_of::<T>(), | |
302 | mem::min_align_of::<T>()); | |
85aaf69f | 303 | let ty_ptr = ty_ptr as *mut usize; |
1a4d82fc JJ |
304 | let ptr = ptr as *mut T; |
305 | // Write in our tydesc along with a bit indicating that it | |
306 | // has *not* been initialized yet. | |
307 | *ty_ptr = mem::transmute(tydesc); | |
308 | // Actually initialize it | |
309 | ptr::write(&mut(*ptr), op()); | |
310 | // Now that we are done, update the tydesc to indicate that | |
311 | // the object is there. | |
312 | *ty_ptr = bitpack_tydesc_ptr(tydesc, true); | |
313 | ||
314 | return &mut *ptr; | |
315 | } | |
316 | } | |
317 | ||
318 | /// Allocates a new item in the arena, using `op` to initialize the value, | |
319 | /// and returns a reference to it. | |
320 | #[inline] | |
85aaf69f | 321 | pub fn alloc<T:'longer_than_self, F>(&self, op: F) -> &mut T where F: FnOnce() -> T { |
1a4d82fc JJ |
322 | unsafe { |
323 | if intrinsics::needs_drop::<T>() { | |
324 | self.alloc_noncopy(op) | |
325 | } else { | |
326 | self.alloc_copy(op) | |
327 | } | |
328 | } | |
329 | } | |
330 | } | |
331 | ||
332 | #[test] | |
333 | fn test_arena_destructors() { | |
334 | let arena = Arena::new(); | |
85aaf69f | 335 | for i in 0..10 { |
1a4d82fc JJ |
336 | // Arena allocate something with drop glue to make sure it |
337 | // doesn't leak. | |
338 | arena.alloc(|| Rc::new(i)); | |
339 | // Allocate something with funny size and alignment, to keep | |
340 | // things interesting. | |
341 | arena.alloc(|| [0u8, 1u8, 2u8]); | |
342 | } | |
343 | } | |
344 | ||
1a4d82fc | 345 | #[test] |
c34b1796 | 346 | #[should_panic] |
1a4d82fc JJ |
347 | fn test_arena_destructors_fail() { |
348 | let arena = Arena::new(); | |
349 | // Put some stuff in the arena. | |
85aaf69f | 350 | for i in 0..10 { |
1a4d82fc JJ |
351 | // Arena allocate something with drop glue to make sure it |
352 | // doesn't leak. | |
353 | arena.alloc(|| { Rc::new(i) }); | |
354 | // Allocate something with funny size and alignment, to keep | |
355 | // things interesting. | |
85aaf69f | 356 | arena.alloc(|| { [0u8, 1, 2] }); |
1a4d82fc JJ |
357 | } |
358 | // Now, panic while allocating | |
85aaf69f | 359 | arena.alloc::<Rc<i32>, _>(|| { |
1a4d82fc JJ |
360 | panic!(); |
361 | }); | |
362 | } | |
363 | ||
364 | /// A faster arena that can hold objects of only one type. | |
1a4d82fc JJ |
365 | pub struct TypedArena<T> { |
366 | /// A pointer to the next object to be allocated. | |
367 | ptr: Cell<*const T>, | |
368 | ||
369 | /// A pointer to the end of the allocated area. When this pointer is | |
370 | /// reached, a new chunk is allocated. | |
371 | end: Cell<*const T>, | |
372 | ||
373 | /// A pointer to the first arena segment. | |
374 | first: RefCell<*mut TypedArenaChunk<T>>, | |
85aaf69f SL |
375 | |
376 | /// Marker indicating that dropping the arena causes its owned | |
377 | /// instances of `T` to be dropped. | |
378 | _own: marker::PhantomData<T>, | |
1a4d82fc JJ |
379 | } |
380 | ||
381 | struct TypedArenaChunk<T> { | |
85aaf69f SL |
382 | marker: marker::PhantomData<T>, |
383 | ||
1a4d82fc JJ |
384 | /// Pointer to the next arena segment. |
385 | next: *mut TypedArenaChunk<T>, | |
386 | ||
387 | /// The number of elements that this chunk can hold. | |
85aaf69f | 388 | capacity: usize, |
1a4d82fc JJ |
389 | |
390 | // Objects follow here, suitably aligned. | |
391 | } | |
392 | ||
85aaf69f | 393 | fn calculate_size<T>(capacity: usize) -> usize { |
1a4d82fc JJ |
394 | let mut size = mem::size_of::<TypedArenaChunk<T>>(); |
395 | size = round_up(size, mem::min_align_of::<T>()); | |
396 | let elem_size = mem::size_of::<T>(); | |
397 | let elems_size = elem_size.checked_mul(capacity).unwrap(); | |
398 | size = size.checked_add(elems_size).unwrap(); | |
399 | size | |
400 | } | |
401 | ||
402 | impl<T> TypedArenaChunk<T> { | |
403 | #[inline] | |
85aaf69f | 404 | unsafe fn new(next: *mut TypedArenaChunk<T>, capacity: usize) |
1a4d82fc JJ |
405 | -> *mut TypedArenaChunk<T> { |
406 | let size = calculate_size::<T>(capacity); | |
407 | let chunk = allocate(size, mem::min_align_of::<TypedArenaChunk<T>>()) | |
408 | as *mut TypedArenaChunk<T>; | |
409 | if chunk.is_null() { alloc::oom() } | |
410 | (*chunk).next = next; | |
411 | (*chunk).capacity = capacity; | |
412 | chunk | |
413 | } | |
414 | ||
415 | /// Destroys this arena chunk. If the type descriptor is supplied, the | |
416 | /// drop glue is called; otherwise, drop glue is not called. | |
417 | #[inline] | |
85aaf69f | 418 | unsafe fn destroy(&mut self, len: usize) { |
1a4d82fc JJ |
419 | // Destroy all the allocated objects. |
420 | if intrinsics::needs_drop::<T>() { | |
421 | let mut start = self.start(); | |
85aaf69f | 422 | for _ in 0..len { |
1a4d82fc | 423 | ptr::read(start as *const T); // run the destructor on the pointer |
85aaf69f | 424 | start = start.offset(mem::size_of::<T>() as isize) |
1a4d82fc JJ |
425 | } |
426 | } | |
427 | ||
428 | // Destroy the next chunk. | |
429 | let next = self.next; | |
430 | let size = calculate_size::<T>(self.capacity); | |
c34b1796 AL |
431 | let self_ptr: *mut TypedArenaChunk<T> = self; |
432 | deallocate(self_ptr as *mut u8, size, | |
1a4d82fc JJ |
433 | mem::min_align_of::<TypedArenaChunk<T>>()); |
434 | if !next.is_null() { | |
435 | let capacity = (*next).capacity; | |
436 | (*next).destroy(capacity); | |
437 | } | |
438 | } | |
439 | ||
440 | // Returns a pointer to the first allocated object. | |
441 | #[inline] | |
442 | fn start(&self) -> *const u8 { | |
443 | let this: *const TypedArenaChunk<T> = self; | |
444 | unsafe { | |
85aaf69f | 445 | mem::transmute(round_up(this.offset(1) as usize, |
1a4d82fc JJ |
446 | mem::min_align_of::<T>())) |
447 | } | |
448 | } | |
449 | ||
450 | // Returns a pointer to the end of the allocated space. | |
451 | #[inline] | |
452 | fn end(&self) -> *const u8 { | |
453 | unsafe { | |
454 | let size = mem::size_of::<T>().checked_mul(self.capacity).unwrap(); | |
85aaf69f | 455 | self.start().offset(size as isize) |
1a4d82fc JJ |
456 | } |
457 | } | |
458 | } | |
459 | ||
460 | impl<T> TypedArena<T> { | |
461 | /// Creates a new `TypedArena` with preallocated space for eight objects. | |
462 | #[inline] | |
463 | pub fn new() -> TypedArena<T> { | |
464 | TypedArena::with_capacity(8) | |
465 | } | |
466 | ||
467 | /// Creates a new `TypedArena` with preallocated space for the given number of | |
468 | /// objects. | |
469 | #[inline] | |
85aaf69f | 470 | pub fn with_capacity(capacity: usize) -> TypedArena<T> { |
1a4d82fc JJ |
471 | unsafe { |
472 | let chunk = TypedArenaChunk::<T>::new(ptr::null_mut(), capacity); | |
473 | TypedArena { | |
474 | ptr: Cell::new((*chunk).start() as *const T), | |
475 | end: Cell::new((*chunk).end() as *const T), | |
476 | first: RefCell::new(chunk), | |
85aaf69f | 477 | _own: marker::PhantomData, |
1a4d82fc JJ |
478 | } |
479 | } | |
480 | } | |
481 | ||
482 | /// Allocates an object in the `TypedArena`, returning a reference to it. | |
483 | #[inline] | |
484 | pub fn alloc(&self, object: T) -> &mut T { | |
485 | if self.ptr == self.end { | |
486 | self.grow() | |
487 | } | |
488 | ||
489 | let ptr: &mut T = unsafe { | |
490 | let ptr: &mut T = mem::transmute(self.ptr.clone()); | |
491 | ptr::write(ptr, object); | |
492 | self.ptr.set(self.ptr.get().offset(1)); | |
493 | ptr | |
494 | }; | |
495 | ||
496 | ptr | |
497 | } | |
498 | ||
499 | /// Grows the arena. | |
500 | #[inline(never)] | |
501 | fn grow(&self) { | |
502 | unsafe { | |
503 | let chunk = *self.first.borrow_mut(); | |
504 | let new_capacity = (*chunk).capacity.checked_mul(2).unwrap(); | |
505 | let chunk = TypedArenaChunk::<T>::new(chunk, new_capacity); | |
506 | self.ptr.set((*chunk).start() as *const T); | |
507 | self.end.set((*chunk).end() as *const T); | |
508 | *self.first.borrow_mut() = chunk | |
509 | } | |
510 | } | |
511 | } | |
512 | ||
513 | #[unsafe_destructor] | |
514 | impl<T> Drop for TypedArena<T> { | |
515 | fn drop(&mut self) { | |
516 | unsafe { | |
517 | // Determine how much was filled. | |
85aaf69f SL |
518 | let start = self.first.borrow().as_ref().unwrap().start() as usize; |
519 | let end = self.ptr.get() as usize; | |
1a4d82fc JJ |
520 | let diff = (end - start) / mem::size_of::<T>(); |
521 | ||
522 | // Pass that to the `destroy` method. | |
523 | (**self.first.borrow_mut()).destroy(diff) | |
524 | } | |
525 | } | |
526 | } | |
527 | ||
528 | #[cfg(test)] | |
529 | mod tests { | |
530 | extern crate test; | |
531 | use self::test::Bencher; | |
532 | use super::{Arena, TypedArena}; | |
533 | ||
534 | #[allow(dead_code)] | |
535 | struct Point { | |
85aaf69f SL |
536 | x: i32, |
537 | y: i32, | |
538 | z: i32, | |
539 | } | |
540 | ||
541 | #[test] | |
542 | fn test_arena_alloc_nested() { | |
543 | struct Inner { value: u8 } | |
544 | struct Outer<'a> { inner: &'a Inner } | |
545 | enum EI<'e> { I(Inner), O(Outer<'e>) } | |
546 | ||
547 | struct Wrap<'a>(TypedArena<EI<'a>>); | |
548 | ||
549 | impl<'a> Wrap<'a> { | |
550 | fn alloc_inner<F:Fn() -> Inner>(&self, f: F) -> &Inner { | |
551 | let r: &EI = self.0.alloc(EI::I(f())); | |
552 | if let &EI::I(ref i) = r { | |
553 | i | |
554 | } else { | |
555 | panic!("mismatch"); | |
556 | } | |
557 | } | |
558 | fn alloc_outer<F:Fn() -> Outer<'a>>(&self, f: F) -> &Outer { | |
559 | let r: &EI = self.0.alloc(EI::O(f())); | |
560 | if let &EI::O(ref o) = r { | |
561 | o | |
562 | } else { | |
563 | panic!("mismatch"); | |
564 | } | |
565 | } | |
566 | } | |
567 | ||
568 | let arena = Wrap(TypedArena::new()); | |
569 | ||
570 | let result = arena.alloc_outer(|| Outer { | |
571 | inner: arena.alloc_inner(|| Inner { value: 10 }) }); | |
572 | ||
573 | assert_eq!(result.inner.value, 10); | |
1a4d82fc JJ |
574 | } |
575 | ||
576 | #[test] | |
577 | pub fn test_copy() { | |
578 | let arena = TypedArena::new(); | |
85aaf69f | 579 | for _ in 0..100000 { |
1a4d82fc JJ |
580 | arena.alloc(Point { |
581 | x: 1, | |
582 | y: 2, | |
583 | z: 3, | |
584 | }); | |
585 | } | |
586 | } | |
587 | ||
588 | #[bench] | |
589 | pub fn bench_copy(b: &mut Bencher) { | |
590 | let arena = TypedArena::new(); | |
591 | b.iter(|| { | |
592 | arena.alloc(Point { | |
593 | x: 1, | |
594 | y: 2, | |
595 | z: 3, | |
596 | }) | |
597 | }) | |
598 | } | |
599 | ||
600 | #[bench] | |
601 | pub fn bench_copy_nonarena(b: &mut Bencher) { | |
602 | b.iter(|| { | |
c34b1796 | 603 | let _: Box<_> = box Point { |
1a4d82fc JJ |
604 | x: 1, |
605 | y: 2, | |
606 | z: 3, | |
c34b1796 | 607 | }; |
1a4d82fc JJ |
608 | }) |
609 | } | |
610 | ||
611 | #[bench] | |
612 | pub fn bench_copy_old_arena(b: &mut Bencher) { | |
613 | let arena = Arena::new(); | |
614 | b.iter(|| { | |
615 | arena.alloc(|| { | |
616 | Point { | |
617 | x: 1, | |
618 | y: 2, | |
619 | z: 3, | |
620 | } | |
621 | }) | |
622 | }) | |
623 | } | |
624 | ||
625 | #[allow(dead_code)] | |
626 | struct Noncopy { | |
627 | string: String, | |
85aaf69f | 628 | array: Vec<i32>, |
1a4d82fc JJ |
629 | } |
630 | ||
631 | #[test] | |
632 | pub fn test_noncopy() { | |
633 | let arena = TypedArena::new(); | |
85aaf69f | 634 | for _ in 0..100000 { |
1a4d82fc JJ |
635 | arena.alloc(Noncopy { |
636 | string: "hello world".to_string(), | |
637 | array: vec!( 1, 2, 3, 4, 5 ), | |
638 | }); | |
639 | } | |
640 | } | |
641 | ||
642 | #[bench] | |
643 | pub fn bench_noncopy(b: &mut Bencher) { | |
644 | let arena = TypedArena::new(); | |
645 | b.iter(|| { | |
646 | arena.alloc(Noncopy { | |
647 | string: "hello world".to_string(), | |
648 | array: vec!( 1, 2, 3, 4, 5 ), | |
649 | }) | |
650 | }) | |
651 | } | |
652 | ||
653 | #[bench] | |
654 | pub fn bench_noncopy_nonarena(b: &mut Bencher) { | |
655 | b.iter(|| { | |
c34b1796 | 656 | let _: Box<_> = box Noncopy { |
1a4d82fc JJ |
657 | string: "hello world".to_string(), |
658 | array: vec!( 1, 2, 3, 4, 5 ), | |
c34b1796 | 659 | }; |
1a4d82fc JJ |
660 | }) |
661 | } | |
662 | ||
663 | #[bench] | |
664 | pub fn bench_noncopy_old_arena(b: &mut Bencher) { | |
665 | let arena = Arena::new(); | |
666 | b.iter(|| { | |
667 | arena.alloc(|| Noncopy { | |
668 | string: "hello world".to_string(), | |
669 | array: vec!( 1, 2, 3, 4, 5 ), | |
670 | }) | |
671 | }) | |
672 | } | |
673 | } |