allocator 0.0.2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

//! An allocator inspired by `libarena`. `realloc` fails, `free` is a no-op.
//! The destructor frees everything, observe the lifetimes :P
//!
//! Given that Arena is already highly specialized, there's no default chunk size.
//! Keep it high enough not to allocate new chunks too often
//! but low enough not to waste too much memory.

pub use allocator::{Allocator};
use malloc;
use core::prelude::*;
use core::ptr;
use core::mem;
use core::kinds::marker;
use core::num::Int;
use core::cmp;
use core::intrinsics;

// Convenience.
static mut a: malloc::Malloc = malloc::Malloc;

pub struct Arena {
    chunk_size: uint,
    chunks: uint,
    first_free: uint,
    ptr: *mut Chunk,
    _nosend: marker::NoSend,
    _nosync: marker::NoSync,
}

impl Arena {
    pub fn new(chunk_size: uint) -> Arena { Arena {
        chunks: 0,
        chunk_size: chunk_size,
        first_free: 0,
        ptr: ptr::null_mut(),
        _nosend: marker::NoSend,
        _nosync: marker::NoSync
    }}

    fn add_chunk(&mut self) -> Option<&mut Chunk> { unsafe {
        let size = self.chunk_size;
        self.add_custom_chunk(size, 1)
    }}

    fn add_custom_chunk(&mut self, size: uint, align: uint) -> Option<&mut Chunk> { unsafe {
        let c = self.chunks;
        try!(a.ensure::<Chunk>(&mut self.ptr, c, c+1));
        let cp = self.ptr.offset(c as int);
        try!(Chunk::fill(cp, self.chunk_size + align - 1));
        self.chunks += 1;
        Some(&mut *cp)
    }}
}

#[unsafe_destructor]
impl Drop for Arena {
    fn drop(&mut self) { unsafe {
        for i in range(0, self.chunks as int) {
            ptr::read(self.ptr.offset(i));
        }
        a.free::<Chunk>(self.ptr, self.chunks);
    }}
}

impl Allocator for Arena {
    unsafe fn alloc<T>(&mut self, count: uint) -> Option<*mut T> {
        let bytes = as_bytes!(count);
        let align = mem::min_align_of::<T>();

        if bytes > self.chunk_size {
            let chunk = try!(self.add_custom_chunk(bytes, align));
            return Some(try!(chunk.alloc(bytes, align)) as *mut T);
        }

        // all chunks are full
        if self.first_free >= self.chunks {
            try!(self.add_chunk());
        }

        for i in range(self.first_free, self.chunks) {
            let chunk: &mut Chunk = &mut *self.ptr.offset(i as int);
            match chunk.alloc(bytes, align) {
                None => continue,
                Some(p) => {
                    if chunk.is_full() && i == self.first_free {
                        self.first_free += 1;
                    }
                    return Some(p as *mut T);
                }
            }
        }

        // still no luck, get a new one.
        let chunk: &mut Chunk = try!(self.add_chunk());
        let p: *mut u8 = try!(chunk.alloc(bytes, align));
        Some(p as *mut T)
    }

    unsafe fn realloc<T>(&mut self, _buf: &mut *mut T, current: uint, items: uint) -> Option<uint> {
        if current >= items {
            Some(current)
        } else {
            None
        }
    }

    unsafe fn ensure<T>(&mut self, _buf: &mut *mut T, current: uint, min: uint) -> Option<uint> {
        if current >= min {
            Some(current)
        } else {
            None
        }
    }

    unsafe fn free<T>(&mut self, _buf: *mut T, _count: uint) {
        // no-op
    }
}



struct Chunk {
    ptr: *mut u8,
    cap: uint,
    end: uint,
    _nosend: marker::NoSend,
    _nosync: marker::NoSync,
}
impl Copy for Chunk {}

impl Chunk {
    fn fill(c: *mut Chunk, size: uint) -> Option<()> { #![inline] unsafe {
        let area = try!(a.alloc(size));
        *c = Chunk { ptr: area, cap: size, end: 0,
                   _nosend: marker::NoSend, _nosync: marker::NoSync};
        Some(())
    }}

    // assumes align is a power of 2, which works because we only use the align intrinsics
    fn alloc(&mut self, size: uint, align: uint) -> Option<*mut u8> { #![inline] unsafe {
        let off = (self.end + (align - 1)) & !(align - 1);
        let newend = off + size;
        if newend > self.cap { return None; }
        self.end = newend;
        Some(self.ptr.offset(off as int))
    }}

    fn is_full(&self) -> bool {
        self.cap == self.end
    }
}

#[unsafe_destructor]
impl Drop for Chunk {
    fn drop(&mut self) { unsafe {
        a.free(self.ptr, self.cap);
    }}
}