5 void free_list::clear_free_list() {
6 for (cell i = 0; i < free_list_count; i++)
7 small_blocks[i].clear();
13 void free_list::initial_free_list(cell start, cell end, cell occupied) {
15 if (occupied != end - start) {
16 free_heap_block* last_block = (free_heap_block*)(start + occupied);
17 last_block->make_free(end - (cell)last_block);
18 add_to_free_list(last_block);
22 void free_list::add_to_free_list(free_heap_block* block) {
23 cell size = block->size();
28 if (size < free_list_count * data_alignment)
29 small_blocks[size / data_alignment].push_back(block);
31 large_blocks.insert(block);
34 free_heap_block* free_list::find_free_block(cell size) {
35 // Check small free lists
36 cell bucket = size / data_alignment;
37 if (bucket < free_list_count) {
38 std::vector<free_heap_block*>& blocks = small_blocks[bucket];
39 if (blocks.size() == 0) {
40 // Round up to a multiple of 'size'
41 cell large_block_size = ((allocation_page_size + size - 1) / size) * size;
43 // Allocate a block this big
44 free_heap_block* large_block = find_free_block(large_block_size);
48 large_block = split_free_block(large_block, large_block_size);
50 // Split it up into pieces and add each piece back to the free list
51 for (cell offset = 0; offset < large_block_size; offset += size) {
52 free_heap_block* small_block = large_block;
53 large_block = (free_heap_block*)((cell)large_block + size);
54 small_block->make_free(size);
55 add_to_free_list(small_block);
59 free_heap_block* block = blocks.back();
63 free_space -= block->size();
67 // Check large free list
70 large_block_set::iterator iter = large_blocks.lower_bound(&key);
71 large_block_set::iterator end = large_blocks.end();
74 free_heap_block* block = *iter;
75 large_blocks.erase(iter);
78 free_space -= block->size();
87 free_heap_block* free_list::split_free_block(free_heap_block* block,
89 if (block->size() != size) {
90 // split the block in two
91 free_heap_block* split = (free_heap_block*)((cell)block + size);
92 split->make_free(block->size() - size);
93 block->make_free(size);
94 add_to_free_list(split);
100 bool free_list::can_allot_p(cell size) {
101 return largest_free_block() >= std::max(size, allocation_page_size);
104 cell free_list::largest_free_block() {
105 if (large_blocks.size()) {
106 large_block_set::reverse_iterator last = large_blocks.rbegin();
107 return (*last)->size();
109 for (int i = free_list_count - 1; i >= 0; i--) {
110 if (small_blocks[i].size())
111 return small_blocks[i].back()->size();