4 template<typename Block> struct free_list_allocator {
9 mark_bits<Block> state;
11 explicit free_list_allocator(cell size, cell start);
12 void initial_free_list(cell occupied);
13 bool contains_p(Block *block);
16 Block *next_block_after(Block *block);
17 Block *next_allocated_block_after(Block *block);
18 bool can_allot_p(cell size);
19 Block *allot(cell size);
20 void free(Block *block);
21 cell occupied_space();
23 cell largest_free_block();
24 cell free_block_count();
26 template<typename Iterator, typename Sizer> void compact(Iterator &iter, Sizer &sizer);
27 template<typename Iterator, typename Sizer> void iterate(Iterator &iter, Sizer &sizer);
28 template<typename Iterator> void iterate(Iterator &iter);
31 template<typename Block>
32 free_list_allocator<Block>::free_list_allocator(cell size_, cell start_) :
36 state(mark_bits<Block>(size_,start_))
41 template<typename Block> void free_list_allocator<Block>::initial_free_list(cell occupied)
43 free_blocks.initial_free_list(start,end,occupied);
46 template<typename Block> bool free_list_allocator<Block>::contains_p(Block *block)
48 return ((cell)block - start) < size;
51 template<typename Block> Block *free_list_allocator<Block>::first_block()
53 return (Block *)start;
56 template<typename Block> Block *free_list_allocator<Block>::last_block()
61 template<typename Block> Block *free_list_allocator<Block>::next_block_after(Block *block)
63 return (Block *)((cell)block + block->size());
66 template<typename Block> Block *free_list_allocator<Block>::next_allocated_block_after(Block *block)
68 while(block != this->last_block() && block->free_p())
70 free_heap_block *free_block = (free_heap_block *)block;
71 block = (object *)((cell)free_block + free_block->size());
74 if(block == this->last_block())
80 template<typename Block> bool free_list_allocator<Block>::can_allot_p(cell size)
82 return free_blocks.can_allot_p(size);
85 template<typename Block> Block *free_list_allocator<Block>::allot(cell size)
87 size = align(size,data_alignment);
89 free_heap_block *block = free_blocks.find_free_block(size);
92 block = free_blocks.split_free_block(block,size);
93 return (Block *)block;
99 template<typename Block> void free_list_allocator<Block>::free(Block *block)
101 free_heap_block *free_block = (free_heap_block *)block;
102 free_block->make_free(block->size());
103 free_blocks.add_to_free_list(free_block);
106 template<typename Block> cell free_list_allocator<Block>::free_space()
108 return free_blocks.free_space;
111 template<typename Block> cell free_list_allocator<Block>::occupied_space()
113 return size - free_blocks.free_space;
116 template<typename Block> cell free_list_allocator<Block>::largest_free_block()
118 return free_blocks.largest_free_block();
121 template<typename Block> cell free_list_allocator<Block>::free_block_count()
123 return free_blocks.free_block_count;
126 template<typename Block>
127 void free_list_allocator<Block>::sweep()
129 free_blocks.clear_free_list();
131 Block *start = this->first_block();
132 Block *end = this->last_block();
136 /* find next unmarked block */
137 start = state.next_unmarked_block_after(start);
142 cell size = state.unmarked_block_size(start);
145 free_heap_block *free_block = (free_heap_block *)start;
146 free_block->make_free(size);
147 free_blocks.add_to_free_list(free_block);
149 start = (Block *)((char *)start + size);
154 template<typename Block, typename Iterator> struct heap_compactor {
155 mark_bits<Block> *state;
159 explicit heap_compactor(mark_bits<Block> *state_, Block *address_, Iterator &iter_) :
160 state(state_), address((char *)address_), iter(iter_) {}
162 void operator()(Block *block, cell size)
164 if(this->state->marked_p(block))
166 iter(block,(Block *)address,size);
172 /* The forwarding map must be computed first by calling
173 state.compute_forwarding(). */
174 template<typename Block>
175 template<typename Iterator, typename Sizer>
176 void free_list_allocator<Block>::compact(Iterator &iter, Sizer &sizer)
178 heap_compactor<Block,Iterator> compactor(&state,first_block(),iter);
179 iterate(compactor,sizer);
181 /* Now update the free list; there will be a single free block at
183 free_blocks.initial_free_list(start,end,(cell)compactor.address - start);
186 /* During compaction we have to be careful and measure object sizes differently */
187 template<typename Block>
188 template<typename Iterator, typename Sizer>
189 void free_list_allocator<Block>::iterate(Iterator &iter, Sizer &sizer)
191 Block *scan = first_block();
192 Block *end = last_block();
196 cell size = sizer(scan);
197 Block *next = (Block *)((cell)scan + size);
198 if(!scan->free_p()) iter(scan,size);
203 template<typename Block> struct standard_sizer {
204 cell operator()(Block *block)
206 return block->size();
210 template<typename Block>
211 template<typename Iterator>
212 void free_list_allocator<Block>::iterate(Iterator &iter)
214 standard_sizer<Block> sizer;