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

extern crate core;
use super::allocated_memory;
use super::allocated_stack_memory::AllocatedStackMemory;
use super::SliceWrapper;

pub trait Allocator<T> {
    type AllocatedMemory : allocated_memory::AllocatedSlice<T>;
    fn alloc_cell(&mut self, len : usize) -> Self::AllocatedMemory;
    fn free_cell(&mut self, data : Self::AllocatedMemory);
}


pub struct StackAllocator<'a,
                           T :'a,
                           U : allocated_memory::AllocatedSlice<&'a mut [T]>> {
    pub nop : &'a mut [T],
    pub system_resources : U,
    pub free_list_start : usize,
    pub free_list_overflow_count : usize,
    pub initialize : fn(&mut[T]),
}

impl <'a, T : 'a, U : allocated_memory::AllocatedSlice<&'a mut[T]> >
     StackAllocator <'a, T, U> {
    fn clear_if_necessary(self : &Self, index : usize, data : AllocatedStackMemory<'a, T>)
    -> AllocatedStackMemory<'a, T> {
        if index + 1 != self.system_resources.slice().len() {
            let fnp = self.initialize;
            fnp(data.mem);
        }
        return data;
    }
}
impl<'a, T : 'a, U : allocated_memory::AllocatedSlice<&'a mut[T]> >
    Allocator<T> for StackAllocator <'a, T, U> {
    type AllocatedMemory = AllocatedStackMemory<'a, T>;
    fn alloc_cell(self : &mut StackAllocator<'a, T, U>,
                  len : usize) -> AllocatedStackMemory<'a, T> {
        if len == 0 {
            return AllocatedStackMemory::<'a, T>::default();
        }
        let mut index : usize = self.free_list_start;
        let mut found : bool = false;
        for free_resource in self.system_resources.slice()[self.free_list_start..].iter() {
            if free_resource.len() >= len {
                found = true;
                break;
            }
            index += 1;
        }
        if !found {
            panic!("OOM");
        }
        let available_slice = core::mem::replace(&mut self.system_resources.slice_mut()[index],
                                                    &mut[]);
        if available_slice.len() == len
           || (available_slice.len() < len + 32
               && index + 1 != self.system_resources.slice().len()) {
            // we don't want really small wasted slices
            // we must assign free_list_start
            if index != self.free_list_start {
                assert!(index > self.free_list_start);
                let farthest_free_list = core::mem::replace(
                    &mut self.system_resources.slice_mut()[self.free_list_start],
                    &mut []);
                let _ = core::mem::replace(&mut self.system_resources.slice_mut()[index],
                                   farthest_free_list);
            }
            self.free_list_start += 1;
            return self.clear_if_necessary(index,
                                           AllocatedStackMemory::<'a, T>{mem:available_slice});
        } else { // the memory allocated was not the entire range of items. Split and move on
            let (retval, return_to_sender) = available_slice.split_at_mut(len);
            let _ = core::mem::replace(&mut self.system_resources.slice_mut()[index], return_to_sender);
            return self.clear_if_necessary(index, AllocatedStackMemory::<'a, T>{mem:retval});
        }
    }
    fn free_cell(self : &mut StackAllocator<'a, T, U>,
                 val : AllocatedStackMemory<'a, T>) {
        if val.slice().len() == 0 {
            return;
        }
        if self.free_list_start > 0 {
            self.free_list_start -=1;
            let _ = core::mem::replace(&mut self.system_resources.slice_mut()[self.free_list_start],
                               val.mem);

        } else {
            for _i in 0..3 {
               self.free_list_overflow_count += 1;
               self.free_list_overflow_count %= self.system_resources.slice().len();
               if self.system_resources.slice()[self.free_list_overflow_count].len() < val.mem.len() {
                   let _ = core::mem::replace(&mut self.system_resources.slice_mut()[self.free_list_overflow_count],
                                      val.mem);
                   return;
               }
            }
        }
    }
}