1 extern crate core;
2 use super::allocated_memory;
3 use super::allocated_stack_memory::AllocatedStackMemory;
4 use super::SliceWrapper;
5 
6 pub trait Allocator<T> {
7     type AllocatedMemory : allocated_memory::AllocatedSlice<T>;
alloc_cell(&mut self, len : usize) -> Self::AllocatedMemory8     fn alloc_cell(&mut self, len : usize) -> Self::AllocatedMemory;
free_cell(&mut self, data : Self::AllocatedMemory)9     fn free_cell(&mut self, data : Self::AllocatedMemory);
10 }
11 
12 
13 pub struct StackAllocator<'a,
14                            T :'a,
15                            U : allocated_memory::AllocatedSlice<&'a mut [T]>> {
16     pub nop : &'a mut [T],
17     pub system_resources : U,
18     pub free_list_start : usize,
19     pub free_list_overflow_count : usize,
20     pub initialize : fn(&mut[T]),
21 }
22 
23 impl <'a, T : 'a, U : allocated_memory::AllocatedSlice<&'a mut[T]> >
24      StackAllocator <'a, T, U> {
clear_if_necessary(self : &Self, index : usize, data : AllocatedStackMemory<'a, T>) -> AllocatedStackMemory<'a, T>25     fn clear_if_necessary(self : &Self, index : usize, data : AllocatedStackMemory<'a, T>)
26     -> AllocatedStackMemory<'a, T> {
27         if index + 1 != self.system_resources.slice().len() {
28             let fnp = self.initialize;
29             fnp(data.mem);
30         }
31         return data;
32     }
33 }
34 impl<'a, T : 'a, U : allocated_memory::AllocatedSlice<&'a mut[T]> >
35     Allocator<T> for StackAllocator <'a, T, U> {
36     type AllocatedMemory = AllocatedStackMemory<'a, T>;
alloc_cell(self : &mut StackAllocator<'a, T, U>, len : usize) -> AllocatedStackMemory<'a, T>37     fn alloc_cell(self : &mut StackAllocator<'a, T, U>,
38                   len : usize) -> AllocatedStackMemory<'a, T> {
39         if len == 0 {
40             return AllocatedStackMemory::<'a, T>::default();
41         }
42         let mut index : usize = self.free_list_start;
43         let mut found : bool = false;
44         for free_resource in self.system_resources.slice()[self.free_list_start..].iter() {
45             if free_resource.len() >= len {
46                 found = true;
47                 break;
48             }
49             index += 1;
50         }
51         if !found {
52             panic!("OOM");
53         }
54         let available_slice = core::mem::replace(&mut self.system_resources.slice_mut()[index],
55                                                     &mut[]);
56         if available_slice.len() == len
57            || (available_slice.len() < len + 32
58                && index + 1 != self.system_resources.slice().len()) {
59             // we don't want really small wasted slices
60             // we must assign free_list_start
61             if index != self.free_list_start {
62                 assert!(index > self.free_list_start);
63                 let farthest_free_list = core::mem::replace(
64                     &mut self.system_resources.slice_mut()[self.free_list_start],
65                     &mut []);
66                 let _ = core::mem::replace(&mut self.system_resources.slice_mut()[index],
67                                    farthest_free_list);
68             }
69             self.free_list_start += 1;
70             return self.clear_if_necessary(index,
71                                            AllocatedStackMemory::<'a, T>{mem:available_slice});
72         } else { // the memory allocated was not the entire range of items. Split and move on
73             let (retval, return_to_sender) = available_slice.split_at_mut(len);
74             let _ = core::mem::replace(&mut self.system_resources.slice_mut()[index], return_to_sender);
75             return self.clear_if_necessary(index, AllocatedStackMemory::<'a, T>{mem:retval});
76         }
77     }
free_cell(self : &mut StackAllocator<'a, T, U>, val : AllocatedStackMemory<'a, T>)78     fn free_cell(self : &mut StackAllocator<'a, T, U>,
79                  val : AllocatedStackMemory<'a, T>) {
80         if val.slice().len() == 0 {
81             return;
82         }
83         if self.free_list_start > 0 {
84             self.free_list_start -=1;
85             let _ = core::mem::replace(&mut self.system_resources.slice_mut()[self.free_list_start],
86                                val.mem);
87 
88         } else {
89             for _i in 0..3 {
90                self.free_list_overflow_count += 1;
91                self.free_list_overflow_count %= self.system_resources.slice().len();
92                if self.system_resources.slice()[self.free_list_overflow_count].len() < val.mem.len() {
93                    let _ = core::mem::replace(&mut self.system_resources.slice_mut()[self.free_list_overflow_count],
94                                       val.mem);
95                    return;
96                }
97             }
98         }
99     }
100 }
101